생성함수

수열 $a_0,a_1,a_2,\dots$을 거듭제곱급수의 계수로 담은 $G(x)=\sum a_nx^n$을 생성함수라 한다. 수열에 대한 복잡한 계산이 다항식의 곱셈과 나눗셈으로 바뀐다. 드 무아브르와 오일러가 발전시킨 방법이다.

핵심 개념

  • $\frac{1}{1-x}=1+x+x^2+\cdots$ (모든 계수가 $1$)
  • $\frac{1}{(1-x)^k}=\sum_n{}_kH_n\,x^n$
  • 곱의 의미: $A(x)B(x)$의 $x^n$의 계수는 $\sum_ka_kb_{n-k}$. ‘두 가지를 합쳐 $n$이 되는 방법의 수’이다.

핵심 정리

  • 피보나치 수열의 생성함수는 $\frac{x}{1-x-x^2}$이다.
  • 자연수 $n$을 서로 다른 자연수의 합으로 나타내는 방법의 수와 홀수들의 합으로 나타내는 방법의 수는 같다 (오일러).
증명 보기

피보나치. $G(x)=\sum_{n\ge1}F_nx^n$이라 하자. $G-xG-x^2G$를 계산하면 $x^n$ ($n\ge3$)의 계수는 $F_n-F_{n-1}-F_{n-2}=0$이고, 남는 것은 $F_1x+(F_2-F_1)x^2=x$이다. 따라서 $G(1-x-x^2)=x$, $G=\frac{x}{1-x-x^2}$이다.

오일러의 분할 정리. 서로 다른 자연수의 합으로 나타내는 방법의 생성함수는 각 수 $k$를 ‘쓰거나 안 쓰거나’이므로 $\prod_{k\ge1}(1+x^k)$이다. 홀수들의 합(중복 허용)은 각 홀수 $k$를 몇 번 쓸지 고르므로 $\prod_{k\text{ 홀수}}\frac{1}{1-x^k}$이다. 그런데

$$1+x^k=\frac{1-x^{2k}}{1-x^k}$$

이므로 $\prod_k(1+x^k)=\prod_k\frac{1-x^{2k}}{1-x^k}$이고, 분자의 $1-x^{2k}$ (짝수 지수)가 분모의 짝수 지수 인수와 모두 약분되어 분모에 홀수 지수만 남는다. 두 생성함수가 같으므로 계수도 같다. $\blacksquare$

예제

  • $5$를 서로 다른 자연수의 합으로: $5$, $4+1$, $3+2$ (3가지). 홀수의 합으로: $5$, $3+1+1$, $1+1+1+1+1$ (3가지)
  • $10$원, $50$원 동전으로 $100$원을 만드는 방법: $\frac{1}{(1-x^{10})(1-x^{50})}$에서 $x^{100}$의 계수. $50$원을 $0,1,2$개 쓰는 경우이므로 $3$가지

확인 문제

주사위 두 개를 던져 눈의 합이 $7$이 되는 경우의 수를 생성함수로 구하시오.

풀이 보기

주사위 하나의 생성함수는 $x+x^2+\cdots+x^6$이다. 두 개이면 $(x+\cdots+x^6)^2$이고 $x^7$의 계수는 $(1,6),(2,5),\dots,(6,1)$의 $6$이다.

정리

  • 수열을 급수의 계수로 담으면 합성곱이 곱셈이 된다.
  • 점화식은 생성함수의 방정식으로 바뀐다.
알림: 보호된 콘텐츠입니다.