2.2 분할과 조합적 정수론

정수 분할은 대상을 나누는 '방법'의 개수를 세는 학문입니다. 오일러는 무한급수와 무한곱을 연결하는 생성함수를 도입하여, 복잡한 조합론적 문제를 대수적인 전개식으로 변환했습니다.

1. 정수 분할 (Partition of Integers)

정수 $n$의 분할이란 $n$을 양의 정수들의 합으로 나타내는 방법이며, 합의 순서는 고려하지 않습니다. 이를 $p(n)$으로 표기합니다.

예시: $p(4) = 5$

수열 $\{p(n)\}$의 성질을 분석하기 위해, 이 수열을 계수로 갖는 멱급수를 정의합니다. 오일러는 다음과 같은 아름다운 무한곱 형태를 발견했습니다.

$$\sum_{n=0}^{\infty} p(n)x^n = \prod_{k=1}^{\infty} \frac{1}{1-x^k}$$

이 식의 우변을 전개하면 $x^n$의 계수가 정확히 $n$을 분할하는 방법의 수와 일치하게 됩니다.

분할을 점의 배열로 시각화한 것을 페러스 도표라고 합니다. 도표를 행과 열을 바꾸어(전치) 얻는 분할을 공액 분할(Conjugate Partition)이라 부릅니다.

Theorem

"$n$을 최대 $k$개의 항으로 분할하는 방법의 수"는 "$n$을 $k$ 이하의 항들로만 분할하는 방법의 수"와 같습니다. (도표의 대칭성을 통해 자명하게 증명됨)

분할 함수 $p(n)$을 효율적으로 계산하기 위한 재귀식의 기초가 됩니다.

$$\prod_{k=1}^{\infty} (1-x^k) = \sum_{n=-\infty}^{\infty} (-1)^n x^{n(3n-1)/2} = 1 - x - x^2 + x^5 + x^7 - \dots$$