분할(partition)에 대한 오일러의 정리(Euler's theorem)

분할(partition)이란 주어진 양의 정수를 양의 정수들의 합으로 표현하는 방법을 연구하는 정수론 또는 조합론의 한 하위 분야이다. 양의 정수 $n$이 주어졌다고 하자. 그러면 $n$에 대한 분할수(partition number) $p(n)$은 $n$을 양의 정수들의 합으로 나타내는 서로 다른 방법의 개수를 말한다. 예를 들어 $n = 7$인 경우, 

\[ \begin{align*} &7, && 3+2+2, \\ &6+1, && 3+2+1+1, \\ &5+2, && 3+1+1+1+1, \\ &5+1+1, && 2+2+2+1, \\ &4+3, && 2+2+1+1+1, \\ &4+2+1, && 2+1+1+1+1+1, \\ &4+1+1+1, && 1+1+1+1+1+1+1+1 \\ &3+3+1, && \end{align*} \]

의 $15$가지 서로 다른 분할이 존재하고, 따라서 $p(7) = 15$임을 알 수 있다. 만약 $p(0) = 1$로 정의하면 $p(n)$은 다음과 같이 이루어진 수열이다. (OEIS: A00041) \[ 1,\, 1,\, 2,\, 3,\, 5,\, 7,\, 11,\, 15,\, 22,\, 30,\, 42,\, \ldots \]

이제 분할에 다양한 제약조건을 추가해 보자. 예를 들어 $7$을 "홀수들로 분할"하는 경우의 수를 생각해 보면, \[ \begin{align*} & 7, && 3+1+1+1+1, \\ & 5+1+1, && 1+1+1+1+1+1+1, \\ & 3+3+1, && \end{align*} \] 의 $5$가지 경우가 존재한다. 또한 $7$을 "서로 다른 양의 정수들로 분할"하는 경우의 수를 생각해 보면, \[ \begin{align*} & 7, && 6+1, && 5+2, && 4+3, && 4+2+1, \end{align*} \] 가 되어 역시 $5$가지 경우가 존재한다. 따라서 $n=7$의 경우 "홀수들로 분할"하는 경우의 수와 "서로 다른 양의 정수들로 분할"하는 경우의 수가 서로 같음을 확인할 수 있다. 이는 우연의 일치일까?

이번엔 좀 더 큰 수로 확인해 보자. 예를 들어 $n = 12$인 경우, 직접 경우를 나누어 계산해 보면 "홀수들로 분할"하는 경우의 수와 "서로 다른 양의 정수들로 분할"하는 경우의 수 모두 $15$가 나옴을 알 수 있을 것이다. 이는 단지 $n = 7,\,12$가 특별하다거나 단순한 우연의 일치가 아님을 다음의 정리를 통해서 확인하라 수 있다.

정리 1. 오일러의 정리(Euler's theorem)

양의 정수 $n$에 대하여, $n$을 "홀수들로 분할"하는 경우의 수를 $p_{o}(n)$으로, "서로 다른 양의 정수들로 분할"하는 경우의 수를 $p_{d}(n)$으로 각각 나타내기로 하자. 그러면 $p_{o}(n) = p_{d}(n)$이 언제나 성립한다.

증명 1. 임의의 양의 정수 $m$은 $2$의 거듭제곱과 홀수의 곱으로 유일하게 표현이 가능하다. 즉, 적당한 양의 정수 $k$와 홀수 $p$가 존재하여 $m = 2^k p$와 같이 유일하게 표현할 수 있다. 이 사실을 바탕으로 $p_{o}(n)$와 $p_{d}(n)$에 다음과 같이 일대일 대응을 정의하자.

우선 주어진 양의 정수 $n$의 한 "홀수들의 분할"을 다음과 같이 나타내자. \[ n = \sum_{i = 1}^{k} a_{i} (2i-1) \] 이 때, $a_i$는 $n$의 분할에서 홀수 $(2i-1)$이 나타나는 횟수를 나타낸다. 이제 각각의 $a_i$들을 이진전개하여 \[ a_i = \sum_{j=1}^{i_j} 2^{b_{ij}} \] 와 같이 표현하자. 그러면 \[ n = \sum_{i = 1}^{k} a_{i} (2i-1) = \sum_{i = 1}^{k} \left( \sum_{j=1}^{k_i} 2^{b_{ij}} \right) (2i-1) = \sum_{i = 1}^{k} \sum_{j=1}^{k_i} [2^{b_{ij}} (2i-1)] \] 각각의 $i,\, j$에 대하여 $2^{b_{ij}} (2i-1)$는 모두 서로 다른 양의 정수이므로, 위 식의 우변은 $n$의 "서로 다른 양수들의 분할"이 된다. 이 과정을 다시 역순으로 시행하면 원래의 "홀수들의 분할"을 얻으므로, 결국 $n$의 어떤 "홀수들의 분할"과 "서로 다른 양수들의 분할"은 일대일 대응 관계를 이룸을 알 수 있다. 예를 들어, $14$의 한 "홀수들의 분할" $14 = 5 + 3 + 3 + 1 + 1 + 1$의 경우 \[ \begin{align*} 14 &= 5 + 3 + 3 + 1 + 1 + 1 \\[5pt] &= 5 + 2 \cdot 3 + 3 \cdot 1 \\[5px] &= 5 + 2 \cdot 3 + (2+1) \cdot 1 \\[5px] &= 5 + 2 \cdot 3 + 2 \cdot 1 + 1 \\[5px] &= 5 + 6 + 2 + 1 \end{align*} \] 의 과정을 통해 "서로 다른 양수들의 분할" $14 = 6 + 5 + 2 + 1$을 얻을 수 있고, 이 과정을 역순으로 시행하면 다시 원래의 "홀수들의 분할"을 얻을 수 있다..

증명 2. $p_{o}(n)$과 $p_{d}(n)$의 생성함수(generating function)를 이용하면, 다음과 같이 두 생성함수가 서로 같음을 보일 수 있다. (아래 각 등식에서, 무한곱과 무한합에 대한 연산의 엄밀성을 보이는 것은 생략하기로 하자.) \[ \begin{align*} \sum_{n = 0}^{\infty} p_{d}(n) x^n &= (1+x)(1+x^2)(1+x^3)(1+x^4) \cdots \\ &= \frac{\cancel{1-x^2}}{1-x^{\phantom{1}}} \cdot \frac{\cancel{1-x^4}}{\cancel{1-x^2}} \cdot \frac{\cancel{1-x^6}}{1-x^3} \cdot \frac{\cancel{1-x^8}}{\cancel{1-x^4}} \cdots \\ &= \frac{1}{1-x} \cdot \frac{1}{1-x^3} \cdot \frac{1}{1-x^5} \cdots \\[5pt] &= (1+x+x^2 + \cdots) (1+x^3+x^6 + \cdots) (1+x^5+x^{10} + \cdots) \cdots \\[5pt] &= \sum_{n = 0}^{\infty} p_{o}(n) x^n \end{align*} \] 따라서 $p_{o}(n) = p_{d}(n)$를 얻는다..

제약조건이 추가된 분할수에 대한 더 많은 정리들

분할수에 대한 몇 가지 흥미로운 정리들을 몇 가지 더 소개해 본다.

정리 2.

양의 정수 $n$과 $k$에 대하여, $n$을 "$k$보다 작거나 같은 수들로 분할"하는 경우의 수는, $n$을 "$k$개 이하의 수들로 분할"하는 경우의 수와 같다.

정리 3. 글레이셔의 정리(Glaisher's theorem)

양의 정수 $n$과 $k$에 대하여, $n$을 "$k$로 나누어 떨어지지 않는 수들로 분할"하는 경우의 수는, $n$을 "같은 수가 $k$번 이상 반복되지 않도록 분할"하는 경우의 수와 같다.

참고. 정리 1은 정리 2에서 $k=2$인 특수한 경우임을 알 수 있다.

정리 4. 로저스-라마누잔의 정리(Rogers-Ramanujan's theorem)

양의 정수 $n$에 대하여, $n$을 "각각의 수들의 차이가 적어도 $2$ 이상 나는 수들로 분할"하는 경우의 수는, $n$을 "$5$로 나누었을 때 나머지가 $1$ 또는 $4$인 수들로 분할"하는 경우의 수와 같다.