정수의 분할

정의

정수의 분할은 양의 정수를 (중복을 허용하여) 양의 정수들의 내림차순(오름차순) 합으로 나타내는 것이다. 즉, 임의의 양의 정수 N에 대해

[math]\displaystyle{ N=n_1+n_2+\cdots+n_k }[/math]

로 나타내는 것이다. 단, [math]\displaystyle{ n_1,n_2,\cdots,n_k }[/math]는 양의 정수면서 [math]\displaystyle{ n_1\ge n_2\ge\cdots \ge n_k }[/math]이다.

예

• 1
• 2 = 1+1
• 3 = 2+1 = 1+1+1
• 4 = 3+1 = 2+2 = 2+1+1 = 1+1+1+1
• 5 = 4+1 = 3+2 = 3+1+1 = 2+2+1 = 2+1+1+1 = 1+1+1+1+1

분할 수(partition numbers)

양의 정수 n을 분할하는 경우의 수를 p(n)으로 쓰자. 그러면

[math]\displaystyle{ p(1)=1,\; p(2)=2,\; p(3)=3,\;p(4)=5,\; p(5)=7,\cdots }[/math]

이다. 그리고 [math]\displaystyle{ p(0)=1,\; p(-n)=0 \left(n \in \mathbb{N} \right) }[/math]으로 정의한다(OEIS의 수열 A000041). 이를 분할 함수(partition function)라고도 한다.

p(n)의 생성함수는 다음과 같다.

[math]\displaystyle{ \sum_{n=0}^{\infty}p(n)x^n=\prod_{k=1}^{\infty} \frac{1}{1-x^k} }[/math]

특수한 조건의 분할

홀수로의 분할과 서로 다른 수로의 분할

1748년 레온하르트 오일러는 임의의 양의 정수를 서로 다른 양의 정수의 합으로 나타내는 경우의 수가 홀수의 합으로 나타내는 경우의 수와 같다는 것을 발견했다(OEIS의 수열 A000009).

예를 한 번 들어 보자. 27=16+8+3 이다. 이제 (16,8,3)에서, 짝수는 꺼내서 반으로 나누고 다시 넣는다. 그러니까 16을 꺼내고 2개의 8을 넣는다. 그러면, (8,8,8,3)이 된다. 이것을 짝수가 없을 때까지 하면 된다. 결과적으로, (1: 24개, 3: 1개)가 된다. 뭔가 함정같지만 이제 홀수의 합으로 나타낸 거다. 야호!. 반대로 할 때에는 예상이 되지만 중복되는 수가 있으면 꺼내서 그 두개를 합한 수를 넣는다. 이걸 계속 하면 된다. 그러면, 24개의 1은 12개의 2가 되고, 12개의 2는 6개의 4가 되고, 6개의 4는 3개의 8이 된다. 여기서 주의할 건, 2개의 8을 꺼내 16을 넣으면 16이 1개, 8이 1개가 돼서 중복되는 게 사라진다. 그리고 이건 처음 (16,8,3)과 같아진다.

증명은 아래와 같다. 위의 예시 과정을 수학적으로 멋있게 적어놓은 거다.

임의의 양의 정수를 서로 다른 양의 정수의 합으로 나타내는 경우의 수에 대한 생성함수를 [math]\displaystyle{ f(x) }[/math]라 하자. 이때 문제의 경우의 수는 [math]\displaystyle{ 1,2,3,\cdots }[/math] 중 중복되지 않게 임의 개를 뽑아 그 합이 n이 되도록 하는 경우의 수와 동일하다. 따라서

[math]\displaystyle{ f(x)=(1+x)(1+x^2)(1+x^3)\cdots(1+x^n)\cdots=\prod_{k=1}^{\infty}(1+x^k) }[/math]

이때

[math]\displaystyle{ 1+x^k=\frac{1-x^{2k}}{1-x^k} }[/math]

이므로

[math]\displaystyle{ \prod_{k=1}^{\infty}(1+x^k)=\prod_{k=1}^{\infty}\frac{1-x^{2k}}{1-x^k} }[/math]

이다. 그러면

[math]\displaystyle{ \prod_{k=1}^{\infty}\frac{1-x^{2k}}{1-x^k}=\frac{1-x^2}{1-x}\frac{1-x^4}{1-x^2}\frac{1-x^6}{1-x^3}\cdots\frac{1-x^{2n}}{1-x^n}\cdots }[/math]

이므로

[math]\displaystyle{ f(x)=\prod_{k=1}^{\infty}\frac{1}{1-x^{2k-1}} }[/math]

이다. 이것은 임의의 양의 정수를 홀수의 합으로 나타내는 경우의 수에 대한 생성함수와 동일하다.

일반화

예시에서 보면 짝수(2의 배수)는 계속 반 나눠서 홀수(2의 배수가 아닌 수)를 만들고, 반대로 같은 수가 두 개 있으면 합쳐주고하는 식이다. 그런데, 꼭 2의 배수에 대해서만 할 필요가 없다. 일반화를 하면서 알아서 피곤해 지는 방법. 2 대신에 m+1을 넣자. m+1의 배수는 계속 m+1등분 해서 m+1의 배수가 아닌 수를 만들고, 반대로 같은 수가 m+1개가 있으면 합쳐준다. 그리고 예전에 이와같은 아이디어로 확장을 한 것이 있다.

1883년 J.W.L 글레이셔는 오일러의 발견을 확장하여, 임의의 양의 정수를, 같은 수를 m번까지 사용할 수 있는 분할의 경우의 수가 m+1로 나누어지지 않는 양의 정수들의 합으로 나타내는 경우의 수와 같음을 증명했다. m이 1일때, 위의 경우가 된다. 증명은 아래와 같다.

임의의 양의 정수를 m번까지 중복된 양의 정수의 합으로 나타내는 경우의 수에 대한 생성함수를 [math]\displaystyle{ f(x) }[/math]라고 하자. 각 수에 대해 m번까지 중복할 수 있다. 따라서,

[math]\displaystyle{ f(x) = (1 + x + \cdots + x^m)(1 + x^2 + \cdots + x^{2m}) \cdots (1+x^k+\cdots+x^{km}) \cdots = \prod_{k=1}^{\infty} \sum_{i=0}^{m} x^i }[/math]

이고,

[math]\displaystyle{ f(x) = \prod_{k=1}^{\infty} \sum_{i=0}^{m} x^i = \prod_{k=1}^{\infty} \frac{1-x^{km+k}}{1-x^k} }[/math]

인데, 약분해 버리고 남는 부분은 [math]\displaystyle{ k }[/math]가 [math]\displaystyle{ m+1 }[/math]의 배수가 아닐 때이다. 즉,

[math]\displaystyle{ f(x) = \prod_{k=1, m+1 \not\mid k}^{\infty} \frac{1}{1-x^k} }[/math]

이것은 임의의 양의 정수를 m+1로 나누어지지 않는 양의 정수들의 합으로 나타내는 경우의 수에 대한 생성함수다.