2.2 정수 분할 & 생성함수 실전 예제 10선
오일러의 생성함수 $1/\prod(1-x^k)$와 페러스 도표의 대칭성을 활용하여 분할의 다양한 항등식을 증명해 봅니다.
Ex 1. 생성함수의 계수 이해
문제: $n=5$를 분할하는 방법의 수 $p(5)$를 생성함수의 전개를 통해 확인하시오.
$(1+x+x^2+\dots)(1+x^2+x^4+\dots)(1+x^3+x^6+\dots)\dots$
$x^5$가 나오는 조합:
1) $x^5$ (5)
2) $x^4 \cdot x^1$ (4+1)
3) $x^3 \cdot x^2$ (3+2)
4) $x^3 \cdot x^1 \cdot x^1$ (3+1+1)
5) $x^2 \cdot x^2 \cdot x^1$ (2+2+1)
6) $x^2 \cdot x^1 \cdot x^1 \cdot x^1$ (2+1+1+1)
7) $x^1 \cdot x^1 \cdot x^1 \cdot x^1 \cdot x^1$ (1+1+1+1+1)
$\therefore p(5) = 7$.
Ex 2. 오일러의 정리 (서로 다른 항 vs 홀수 항)
문제: $n$을 '서로 다른 항'으로 분할하는 수와 '홀수 항'으로만 분할하는 수가 같음을 생성함수로 증명하시오.
서로 다른 항 분할의 생성함수: $D(x) = \prod_{k=1}^{\infty} (1+x^k)$
홀수 항 분할의 생성함수: $O(x) = \prod_{k=1}^{\infty} \frac{1}{1-x^{2k-1}}$
$D(x) = \prod \frac{1-x^{2k}}{1-x^k} = \frac{(1-x^2)(1-x^4)(1-x^6)\dots}{(1-x^1)(1-x^2)(1-x^3)(1-x^4)\dots}$
분자의 짝수 거듭제곱 항들이 분모의 짝수 항들과 약분되어 사라진다.
남는 것은 분모의 홀수 항뿐: $\prod \frac{1}{1-x^{2k-1}} = O(x)$.
$\therefore$ 두 분할의 수는 항상 같다.
Ex 3. 최대 항의 크기 vs 항의 개수
문제: $n$을 '최대 항의 크기가 $m$ 이하'인 분할의 수와 '항의 개수가 $m$개 이하'인 분할의 수가 같음을 보이시오.
분할 $\lambda$의 페러스 도표를 $y=x$ 대칭시킨 공액 분할 $\lambda'$를 생각한다.
$\lambda$에서 최대 항의 크기가 $m$이라는 것은 도표의 첫 번째 행에 점이 $m$개 있다는 뜻이다.
이를 대칭시키면 $\lambda'$의 첫 번째 열에 점이 $m$개 있게 되므로, 이는 항의 개수가 $m$개임을 의미한다.
따라서 일대일 대응이 성립하여 두 가짓수는 같다.
Ex 4. 자가 공액 vs 서로 다른 홀수 항
문제: $n$의 '자가 공액 분할'의 개수와 $n$의 '서로 다른 홀수 항들로의 분할'의 개수가 같음을 보이시오.
자가 공액 도표에서 'ㄱ'자 모양으로 점들을 떼어내어 나열한다.
도표가 대칭이므로 각 'ㄱ'자(L-shape)의 가로와 세로 점의 개수는 같고, 합하면 항상 홀수가 된다.
또한 안쪽으로 갈수록 'ㄱ'자의 크기는 엄격하게 작아진다.
따라서 자가 공액 분할은 항상 서로 다른 홀수 항들의 합으로 변환될 수 있다.
Ex 5. 특수한 항의 분할
문제: 각 항의 크기가 2 또는 3으로만 이루어진 $n$의 분할의 생성함수를 구하시오.
각 항 $k$에 대해 사용 횟수를 결정하는 식은 $1/(1-x^k)$이다.
$\therefore f(x) = \frac{1}{(1-x^2)(1-x^3)} = (1+x^2+x^4+\dots)(1+x^3+x^6+\dots)$
이 식의 $x^n$의 계수가 구하고자 하는 분할의 수이다.
Ex 6. 분할 함수의 재귀 관계
문제: 오각수 정리를 이용하여 $p(n)$을 계산하는 재귀식을 서술하시오.
오일러의 공식: $\prod (1-x^k) = 1 - x^1 - x^2 + x^5 + x^7 - \dots = \sum a_k x^k$
이 식과 $\sum p(n)x^n$의 곱이 1임을 이용하면:
$p(n) = p(n-1) + p(n-2) - p(n-5) - p(n-7) + \dots$
여기서 지수 $1, 2, 5, 7 \dots$는 오각수 $k(3k-1)/2$들이다.
Ex 7. 라마누잔 합동식 (Mod 5)
문제: 모든 자연수 $n$에 대해 $p(5n+4) \equiv 0 \pmod 5$ 임을 확인하시오.
이 문제는 조합적 증명보다 생성함수의 모듈러 성질을 통해 증명된다.
$p(4)=5 \equiv 0$, $p(9)=30 \equiv 0$ 등 실제로 5의 배수가 나타난다.
라마누잔은 이 외에도 법 7, 11에 대한 유사한 합동식을 발견했다.
Ex 8. 분할의 기하적 구조
문제: $n$의 페러스 도표 내부에 들어갈 수 있는 가장 큰 $k \times k$ 정사각형을 '뒤르페 사각형'이라 한다. 이를 이용한 생성함수의 분해를 보이시오.
$p(n)$의 생성함수는 다음과 같이 뒤르페 사각형의 크기 $k$를 기준으로 합산할 수 있다.
$\sum p(n)x^n = \sum_{k=0}^{\infty} \frac{x^{k^2}}{(1-x)(1-x^2)\dots(1-x^k) \cdot (1-x)(1-x^2)\dots(1-x^k)}$
중간의 $x^{k^2}$은 정사각형을, 양옆의 분모는 정사각형 오른쪽과 아래쪽의 남은 분할을 의미한다.
Ex 9. 평균 항의 개수
문제: $n$을 서로 다른 $k$개의 항으로 분할하는 수 $q(n, k)$의 생성함수를 구하시오.
변수 $z$를 도입하여 항의 개수를 추적한다.
$G(x, z) = \prod_{n=1}^{\infty} (1 + zx^n)$
이 식을 전개했을 때 $z^k x^n$의 계수가 $q(n, k)$이다.
Ex 10. 고난도 분할 항등식
문제: "인접한 항의 차가 최소 2인 분할"과 "항이 $5k \pm 1$ 꼴인 분할"의 수가 같음을 서술하시오.
이것이 유명한 로저스-라마누잔 제1 항등식이다.
생성함수 형태: $\sum_{n=0}^{\infty} \frac{x^{n^2}}{(1-x)(1-x^2)\dots(1-x^n)} = \prod_{k=0}^{\infty} \frac{1}{(1-x^{5k+1})(1-x^{5k+4})}$
조합론적으로 매우 깊은 의미를 지니며 통계역학의 모델링에도 사용된다.