분할

자연수의 분할

자연수 n을 r개의 자연수의 합으로 표현하기
$p(n,r)$ 로 표기한다.

p(n,\; 2) = \left\lfloor \frac{n}{2} \right\rfloor \\[10pt] p(n,\; 3) = round\;(\frac{n^2}{12})

분할수

자연수 n을 분할하는 방법의 수
$P_{n}$ 또는 $p(n)$ 으로 표기한다.

공식으로 표현하면 다음과 같다.

P_{n} = \sum_{k=1}^{n} p(n,k)

동적 프로그래밍을 통한 분할

$p(n, r)$ 에는 닫힌 공식이 없어서 점화식으로 구한다. $n$ 을 정확히 $r$ 개의 자연수로 나누는 방법을 1을 쓰느냐 안 쓰느냐로 가른다.

가장 작은 조각이 1이면, 그 1을 떼고 남은 $n-1$ 을 $r-1$ 개로 나눈다 → $p(n-1,\ r-1)$
모든 조각이 2 이상이면, 각 조각에서 1씩 빼도 여전히 자연수다 → $p(n-r,\ r)$

두 경우가 겹치지 않고 빠짐없으므로

p(n,\ r) = p(n-1,\ r-1) + p(n-r,\ r)

이다. 시작값은 $p(n,\ 1) = 1$ , $p(n,\ n) = 1$ 이고, $r > n$ 이면 $0$ 이다.

python

def partitions(n, r):
    # dp[i][j] = i를 정확히 j개의 자연수로 나누는 방법의 수
    dp = [[0] * (r + 1) for _ in range(n + 1)]
    dp[0][0] = 1
    for i in range(1, n + 1):
        for j in range(1, min(i, r) + 1):
            dp[i][j] = dp[i - 1][j - 1] + dp[i - j][j]
    return dp[n][r]

표를 한 번 채우므로 시간복잡도는 $O(nr)$ 이다. 분할수 $P_n$ 은 이 표의 한 행을 더하면 나온다.

집합의 분할

앞의 분할은 수를 쪼갠 것이고, 여기서는 원소를 구별하는 집합을 쪼갠다. 같은 크기로 나누더라도 어떤 원소가 어디에 들어갔느냐가 다르면 다른 분할이다.

$n$ 개의 원소를 비어 있지 않은 $k$ 개의 묶음으로 나누는 방법의 수를 제2종 스털링 수라 하고 $S(n,\ k)$ 또는 $\left\{ {n \atop k} \right\}$ 로 적는다. 점화식은 수의 분할과 같은 방식으로 나온다 — $n$ 번째 원소를 혼자 두느냐 아니냐로 가른다.

혼자 두면 남은 $n-1$ 개를 $k-1$ 묶음으로 → $S(n-1,\ k-1)$
아니면 남은 $n-1$ 개를 이미 $k$ 묶음으로 나눈 뒤 그중 하나에 넣는다 → $k \cdot S(n-1,\ k)$

S(n,\ k) = S(n-1,\ k-1) + k \cdot S(n-1,\ k)

시작값은 $S(0,\ 0) = 1$ 이고 $S(n,\ 0) = 0\ (n \ge 1)$ 이다.

묶음 수를 정하지 않고 전부 더한 것이 벨 수다.

B_n = \sum_{k=0}^{n} S(n,\ k)

$B_0$ 부터 차례로 $1,\ 1,\ 2,\ 5,\ 15,\ 52,\ 203$ 이다. 예를 들어 $\{a, b, c\}$ 의 분할은 $\{abc\}$ , $\{ab\}\{c\}$ , $\{ac\}\{b\}$ , $\{bc\}\{a\}$ , $\{a\}\{b\}\{c\}$ 의 다섯 가지로 $B_3 = 5$ 와 맞는다.