분할수
分割數 / partition number, number of partitions
1. 개요
자연수 n을 분할하는 방법의 수, 즉 순서를 고려하지 않고 1개 이상의 자연수의 합으로 표시하는 방법의 수를 분할수라고 한다. $$P_n$$ 또는 $$p(n)$$ 으로 표기한다.
2. 예시
예를 들어 n = 4 인 경우는
5가지 방법으로 분할이 가능하다. 그러므로 $$P_4 = 5$$ 이다.
n = 5 인 경우는
7가지 방법으로 분할할 수 있다. 즉, $$P_5 = 7$$ 이다
n 을 k 개의 수로 분할하는 방법을 p(n,k)로 표기하므로, 아래 식으로 쓸 수 있다.
$$\displaystyle {P}_{n} = \sum_{k=1}^{n}p\left(n ,k \right) $$
p(1) = 1, p(2) = 2, p(3) = 3, p(4) = 5, p(5) = 7 이며, 여기서 분할수의 목록을 확인할 수 있다.
참고로 편의상 p(0) = 1 로 둔다.
한편 n의 분할 중 원소가 중복되지 않는 수, 즉 덧셈식에서 각 수가 한 번만 나오는 경우의 수를 나타내는 수열도 있다. 이를 위키백과에서는 q(n)이라고 하며, 여기서 그 수열을 확인할 수 있다. q(n) 표현을 빌리자면 q(1)=q(2)=1, q(3)=q(4)=2, q(5)=3이며, q(0) 역시 편의상 1로 표기한다.
예를 들어 q(4)를 구하자면, 앞에서 구한 4의 분할들 중 덧셈식에서 각 수가 한 번만 나오는 경우는 4, 3+1의 2가지이므로 q(4)=2이다. 마찬가지로 q(5)를 구하면 경우의 수는 5, 4+1, 3+2의 3이므로 q(5)=3이다.
q(n)은 n을 홀수만 사용해서 분할하는 방법의 수와 같다는 사실이 알려져 있다.
3. 구하는 방법
수가 작으면 하나하나 손으로 분할을 나열해도 되겠지만 좀만 커져도 힘들다. 보통은 분할수의 생성함수를 이용해 다음처럼 계산한다. 약간의 조합론 지식이 있으면, 생성함수가 다음처럼 나타난다는 것을 바로 알 수 있다.
$$ \displaystyle P(x) = \sum_{n=0}^{\infty} p(n) x^n = \prod_{i=1}^{\infty} \frac{1}{1- x^i} $$
이 생성함수에 대해서 다음의 오일러의 오각수[1] 공식 (pentagonal number formula)을 증명할 수 있다.$$ \displaystyle P(x)^{-1} = 1 + \sum_{k=1}^{\infty} (-1)^k \left( x^{k(3k+1)/2} + x^{k(3k-1)/2} \right) $$
이름의 유래는 $$k(3k \pm 1)/2$$들이 오각수라서이다. 근데 이게 그냥 나온 게 아니라, 이 공식을 증명할 때 실제로 오각수 모양의 분할 배열(페러스 다이어그램)이 중요하게 사용된다. 꽤나 신기하고 아름다운 조합적 증명이니 관심있으면 조합론 기본교재에서 찾아 읽어보자. 하여튼간 이걸 이용하면 다음의 점화식을 얻을 수 있다. ($$k<0$$이면 $$p(k)=0$$으로 간주)$$ \displaystyle p(n) = \sum_{k = 1}^{\infty} (-1)^{k+1} \left( p(n - \frac{k(3k+1)}{2}) + p (n - \frac{k(3k-1)}{2}) \right) $$
이게 컴퓨터로 계산할 때 복잡도 $$O(n^2)$$으로 해결할 수 있는 그나마 간단한 식이다.분할수의 정확한 공식으로는 하디-라마누잔-라데마커 공식이 있는데, 하디와 라마누잔이 맨 처음 얻어낸 근사식
$$\displaystyle p(n) \sim \frac{1}{4n \sqrt{3}} \exp \left( \pi \sqrt {\frac{2n}3} \right) $$
을 라데마커와 보완하여 만든 다음의 공식이다. $$ \displaystyle p(n) = {\frac {1}{\pi {\sqrt {2}}}}\sum _{k=1}^{\infty}A_{k}(n){\sqrt {k}}\cdot {\frac {d}{dn}}\left({{\frac {1}{\sqrt {n-{\frac {1}{24}}}}}\exp \left[{{\frac {\pi }{k}}{\sqrt {{\frac {2}{3}}\left(n-{\frac {1}{24}}\right)}}}\,\,\,\right]}\right) $$ [2]
물론 실전에서 이걸 써서 분할수를 계산하지는 않는다. 다만 수렴속도가 빨라 근사식으로 쓰기에는 좋다. 당장에 첫 번째 항만 보아도 주항 $$ \exp ( \pi \sqrt {2n/3} )/(4n \sqrt{3}) $$을 준다.영화 무한대를 본 남자에 이 공식에 대한 에피소드가 등장한다. 라마누잔의 증명과정 없는 정리 때문에, 라마누잔의 업적이 수학계에 인정받지 못한다. 하디는 그런 라마누잔을 돕기 위해서, 분할수의 대가인 라데마커를 끌어 들여 라마누잔의 분할수 공식이 상당히 정확하다는 점을 인정받게 한다.
중복되는 원소가 없는 분할수 q(n) 역시 근삿값에 대한 다음 공식이 있다.
$$\displaystyle q(n) \sim { { e^{\pi \sqrt {\frac{n}3} }} \over {4\sqrt[4]{3n^3}} }$$
비슷하게 오일러의 오각수 공식을 이용해서 점화식을 끌어낼 수도 있다.