분할수(Partition number)

4를 자연수의 합으로 쓰는 방법은 4, 3+1, 2+2, 2+1+1, 1+1+1+1의 다섯 가지입니다. 더하는 순서는 따지지 않으므로 3+1과 1+3은 같은 것으로 칩니다. 이런 방법의 수를 n의 분할수 $p(n)$이라고 합니다. n = 1, 2, 3, …에 대해 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, …로 커집니다.

분할 하나를 칸의 줄로 그리면 편리합니다. 가장 큰 부분을 맨 위 줄에, 그다음 부분을 그 아래 줄에 왼쪽을 맞춰 쌓은 그림이 영 도형입니다. 영국의 수학자 앨프리드 영의 이름이 붙었고, 같은 영국의 노먼 페러스의 이름을 따 페러스 도형이라고도 합니다. n = 의 분할 () 이전 다음 무작위 대각선으로 뒤집기

영 도형을 대각선에 대해 뒤집으면 가로줄과 세로줄이 바뀌어 또 하나의 분할, 켤레 분할 나옵니다. 뒤집기는 분할들 사이의 일대일대응이고 줄의 개수와 가장 긴 줄의 길이를 맞바꾸므로, '부분이 k개 이하인 분할'과 '가장 큰 부분이 k 이하인 분할'은 개수가 같습니다. 그림 한 장이 증명입니다.

오일러의 생성함수. 분할은 1을 몇 개, 2를 몇 개, 3을 몇 개 쓸지 정하는 일입니다. 그래서 생성함수는 등비급수⁠(geometric series)⁠ $\frac1{1-x^k} = 1 + x^k + x^{2k} + \cdots$들의 곱입니다(위의 식). 이 식으로 오일러는 뜻밖의 사실을 보였습니다. 서로 다른 부분으로만 된 분할의 수와 홀수 부분으로만 된 분할의 수는 언제나 같습니다. 예를 들어 n = 5이면 5, 4+1, 3+2와 5, 3+1+1, 1+1+1+1+1로 세 가지씩입니다. 부분마다 한 번 쓰거나 안 쓰는 분할의 생성함수는 $(1+x)(1+x^2)(1+x^3)\cdots$입니다. 그 각 인수를 $\frac{1-x^{2k}}{1-x^k}$로 바꾸면 분자에 모인 $(1-x^2)(1-x^4)(1-x^6)\cdots$가 분모의 짝수 지수 인수와 모두 약분됩니다. 분모에는 $(1-x)(1-x^3)(1-x^5)\cdots$만 남고, 이것이 바로 홀수 부분만 쓰는 분할의 생성함수입니다. 지금 n에서는 서로 다른 부분으로 된 분할이 가지, 홀수 부분으로 된 분할이 가지입니다.

분할수는 $p(n)$ = (지금 n)처럼 처음에는 느리게 자라지만 어떤 다항식⁠(polynomial)⁠보다도 빨리 커집니다. p(100) = 190,569,292입니다. 1918년 영국의 수학자 하디와 인도 출신의 라마누잔은 $p(n) \sim \frac{1}{4n\sqrt3}\,e^{\pi\sqrt{2n/3}}$임을 보였습니다. ∼는 n이 커질수록 두 변의 비가 1로 다가간다는 뜻입니다. n = 100에서 오른쪽은 약 1억 9928만으로, 실제 값보다 약 4.6% 큽니다. 지수가 n이 아니라 $\sqrt n$에 비례하니, 1보다 큰 수 c의 거듭제곱 $c^n$보다는 결국 느리게 자랍니다. 라마누잔은 $p(5k+4)$가 언제나 5의 배수⁠(multiple)⁠, 곧 5로 나눈 나머지⁠(remainder)⁠가 0이라는 것도 발견했습니다(p(4) = 5, p(9) = 30, p(14) = 135, …). 이런 나머지의 규칙은 모듈러 연산⁠(modular arithmetic)⁠의 언어로 씁니다.

이어지는 곳. 순서를 따지면 분할이 아니라 합성이 되고, 그 수는 별과 막대⁠(stars and bars)⁠로 간단히 셉니다. n을 k개의 자연수의 순서 있는 합으로 쓰는 방법은 $\binom{n-1}{k-1}$가지입니다. 원소⁠(element)⁠ n개의 순열⁠(permutation)⁠을 순환들로 쪼개면 순환의 길이들이 n의 분할을 이룹니다. 수 대신 집합⁠(set)⁠을 겹치지 않는 조각들로 나누는 일은 동치관계⁠(equivalence relation)⁠를 정하는 일과 같고(같은 조각에 든 것끼리를 '같다'고 보면 됩니다), 그 수를 미국의 수학자 에릭 템플 벨의 이름을 따 벨 수⁠(Bell number)⁠라고 부릅니다. 예를 들어 {1, 2, 3}을 나누는 방법은 {1, 2, 3}, {1, 2}{3}, {1, 3}{2}, {2, 3}{1}, {1}{2}{3}의 다섯 가지입니다. 2×n 모양의 영 도형에 1부터 2n까지를 줄마다 오른쪽으로, 칸마다 아래로 커지게 채우는 방법의 수는 카탈랑 수⁠(Catalan number)⁠입니다.