[조합론] 6. 점화식(3: 생성함수)

[조합론] 6. 점화식(3: 생성함수)

수열 $a_{0},\,a_{1},\,a_{2},\,\cdots$에 대하여 멱급수 $$f(x)=\sum_{i=0}^{\infty}{a_{i}x^{i}}=a_{0}+a_{1}x+a_{2}x^{2}+\cdots$$ 를 이 수열의 생성함수(generating function)라고 한다. 생성함수는 함수를 관찰해서 수열의 성질을 파악할 수 있는 중요한 역할을 하고, 생성함수를 이용하여 수열의 일반항 및 점화식을 구할 수 있다.

참고: 여기서 가장 중요한 것은 수열 $a_{n}$이고, $x^{n}$은 계수들을 구분하는 기호에 불과하다. $$1+x+x^{2}+x^{3}+\cdots=\frac{1}{1-x}$$ 는 생성함수에서 가장 많이 사용되는 등식이고, 이 생성함수로부터 상수수열 $a_{n}=1$을 구할 수 있다. 또한 위의 급수를 제곱한 급수 $$(1+x+x^{2}+x^{3}+\cdots)^{n}=\frac{1}{(1-x)^{n}}$$ 에서 $x^{r}$의 계수는 $_{n}H_{r}$이다. 그 이유는 다음과 같다. $$\begin{align*}(1+x)^{n}&=1+\binom{n}{1}x+\binom{n}{2}x^{2}+\cdots+\binom{n}{r}x^{r}+\cdots+\binom{n}{n}x^{n}\\(1-x^{m})^{n}&=1-\binom{n}{1}x^{m}+\binom{m}{2}x^{2m}+\cdots+(-1)^{r}\binom{n}{r}x^{rm}+\cdots+(-1)^{n}\binom{n}{n}x^{nm}\\ \frac{1}{(1-x)^{n}}&=1+\binom{1+n-1}{1}x+\binom{2+n-1}{2}x^{2}+\cdots+\binom{r+n-1}{r}x^{r}+\cdots\\&=1+\,_{n}H_{1}x+\,_{n}H_{2}x^{2}+\cdots+\,_{n}H_{r}x^{r}+\cdots\end{align*}$$

아보카도 1개, 레몬 2개, 오렌지 3개가 있다. 아보카도를 $A$, 레몬을 $L$, 오렌지를 $O$로 표시하면, $ALO$는 아보카도, 레몬, 오렌지를 각각 1개씩 선택한 것을 의미하고, $ALLOO=AL^{2}O^{2}$는 아보카도 1개, 레몬 2개, 오렌지 2개를 선택한 것을 의미한다. 순서를 고려할 필요가 없으므로 교환법칙이 성립한다. 두 사람의 선택이 각각 $ALO$, $AL^{2}O^{2}$이면, $ALO+AL^{2}O^{2}$로 나타낼 수 있다. 아래의 식 $$(1+A)(1+O+O^{2})(1+P+P^{2}+P^{3})$$ 을 다항식이라고 생각하고 전개하면 각각의 계수들은 과일을 고르는 방법의 수로 나타내어지고 전개식에서 지수의 합이 $n$인 항들은 과일 $n$개를 고르는 방법의 수이다.

예를들어 과일을 3개 고른다고 하면 $AL^{2},\,ALO,\,AO^{2},\,L^{2}O,\,LO^{2},\,O^{3}$으로 6가지이고 아래의 다항식에서 $x^{3}$의 계수는 6이다. $$(1+x)(1+x+x^{2})(1+x+x^{2}+x^{3})=1+3x+5x^{2}+6x^{3}+5x^{4}+3x^{5}+x^{6}$$ 이 다항식의 첫번째 인수에서 $x$는 아보카도를, 두번째 인수에서 $x$는 레몬을, 세번째 인수에서 $x$는 오렌지를 의미한다. 따라서 위의 다항식은 과일 $n\,(0\leq n\leq6)$개를 선택하는 방법에 대한 생성함수이다.

예: 7개의 통에 각각 같은 종류의 장난감이 있다. 통에서 중복을 허용해서 뽑되, 각 통에서 2개 이상 6개 이하가 뽑히도록 25개를 선택하는 경우의 수는?

풀이: 장난감 선택에 대한 생성함수는 $(x^{2}+x^{3}+x^{4}+x^{5}+x^{6})$이므로 이 문제에 대한 생성함수는 $$(x^{2}+x^{3}+x^{4}+x^{5}+x^{6})^{7}$$ 이고, $x^{25}$의 계수가 이 문제의 답이다. $$\begin{align*}(x^{2}+x^{3}+x^{4}+x^{5}+x^{6})^{7}&=x^{14}(1+x+x^{2}+x^{3}+x^{4})^{7}\end{align*}$$ 이므로 문제의 답은 $(1+x+x^{2}+x^{3}+x^{4})^{7}$에서 $x^{11}$의 계수가 된다. 이때 $$(1+x+x^{2}+x^{3}+x^{4})^{7}=\left(\frac{1-x^{5}}{1-x}\right)^{7}=\frac{(1-x^{5})^{7}}{(1-x)^{7}}$$ 이고 $$\begin{align*}(1-x^{5})&=1-\binom{7}{1}x^{5}+\binom{7}{2}x^{10}-\binom{7}{3}x^{15}+\cdots\\ \frac{1}{(1-x)^{7}}&=(1+x+x^{2}+x^{3}+\cdots)^{7}=1+\,_{7}H_{1}x+\,_{7}H_{2}x^{2}+\,_{7}H_{3}x^{3}+\cdots\end{align*}$$ 이므로 이 다항식에서의 $x^{11}$의 계수는 $$1\cdot\,_{7}H_{11}+(-1)\binom{7}{1}\,_{7}H_{6}+\binom{7}{2}\,_{7}H_{1}=\binom{17}{6}+(-1)\binom{7}{1}\binom{12}{6}+\binom{7}{2}\binom{7}{6}=6055$$ 이고 이것이 문제의 답이다.

예: 25개의 사탕을 7명의 어린이에게 분배하는데 첫번째 어린이는 최대 10개만 받을 수 있고, 나머지 어린이에게는 제한이 없다고 하면 나누어 주는 경우의 수는?

풀이: 이 문제에 대한 생성함수는 $$(1+x+x^{2}+\cdots+x^{10})(1+x+x^{2}+\cdots)^{6}=\frac{1-x^{11}}{1-x}\frac{1}{(1-x)^{6}}=\frac{1-x^{11}}{(1-x)^{7}}$$ 이고 이 생성함수의 $x^{25}$의 계수가 이 문제의 답이다. $$\begin{align*}\frac{1}{(1-x)^{7}}&=(1+x+x^{2}+\cdots)^{7}\\&=1+\,_{7}H_{1}x+\,_{7}H_{2}+\cdots+\,_{7}H_{r}+\cdots\end{align*}$$ 이므로 $$_{7}H_{25}\cdot1+\,_{7}H_{14}(-1)=\binom{31}{25}-\binom{20}{14}=697521$$ 이 이 문제의 답이다.

 

정리: 수열 $a_{n},\,b_{n}$의 생성함수를 각각 $f(x),\,g(x)$라고 하면 다음 성질들이 성립한다.

(1) 수열 $c_{n}=a_{n}\pm b_{n}$의 생성함수는 $f(x)\pm g(x)$이다.

(2) 수열 $c_{n}=a_{n-k}$의 생성함수는 $x^{k}f(x)$이다.

(3) 수열 $\displaystyle c_{n}=\sum_{k=0}^{n}{a_{k}b_{n-k}}$의 생성함수는 $f(x)g(x)$이다.

(4) 수열 $\displaystyle c_{n}=\sum_{k=0}^{n}{a_{k}}$의 생성함수는 $\displaystyle\frac{f(x)}{1-x}$이다.

(5) 수열 $c_{n}=na_{n}$의 생성함수는 $xf'(x)$이다.

증명: $f(x),\,g(x)$는 각각 수열 $a_{n},\,b_{n}$의 생성함수이므로 $$\begin{align*}f(x)&=\sum_{n=0}^{\infty}{a_{n}x^{n}}=a_{0}+a_{1}x+a_{2}x^{2}+\cdots\\g(x)&=\sum_{n=0}^{\infty}{b_{n}x^{n}}=b_{0}+b_{1}x+b_{2}x^{2}+\cdots\end{align*}$$ 이다.

(1): $$\sum_{n=0}^{\infty}{c_{n}x^{n}}=\sum_{n=0}^{\infty}{(a_{n}\pm b_{n})x^{n}}=f(x)\pm g(x)$$ 이므로 수열 $c_{n}=a_{n}\pm b_{n}$의 생성함수는 $f(x)\pm g(x)$이다.

(2): $$\sum_{n=0}^{\infty}{c_{n}x^{n}}=\sum_{n=0}^{\infty}{a_{n}x^{n+k}}=x^{k}f(x)$$ 이므로 수열 $c_{n}=a_{n-k}$의 생성함수는 $x^{k}f(x)$이다.

(3): $$\begin{align*}f(x)g(x)&=(a_{0}+a_{1}x+a_{2}x^{2}+\cdots)(b_{0}+b_{1}x+b_{2}x^{2}+\cdots)\\&=a_{0}b_{0}+(a_{0}b_{1}+a_{1}b_{0})x+(a_{0}b_{2}+a_{1}b_{1}+a_{2}b_{0})x^{2}+\cdots\\&=\sum_{n=0}^{\infty}{c_{n}x^{n}}\end{align*}$$ 이므로 수열 $\displaystyle c_{n}=\sum_{k=0}^{n}{a_{k}b_{n-k}}$의 생성함수는 $f(x)g(x)$이다.

(4): $$\begin{align*}\frac{f(x)}{1-x}&=(a_{0}+a_{1}x+a_{2}x^{2}+\cdots)(1+x+x^{2}+\cdots)\\&=a_{0}+(a_{0}+a_{1})x+(a_{0}+a_{1}+a_{2})x^{2}+\cdots\\&=\sum_{n=0}^{\infty}{c_{n}x^{n}}\end{align*}$$ 이므로 수열 $\displaystyle c_{n}=\sum_{k=0}^{n}{a_{k}}$의 생성함수는 $\displaystyle\frac{f(x)}{1-x}$이다.

(5): $$\begin{align*}xf'(x)&=x(a_{1}+2a_{2}x+3a_{3}x^{3}+\cdots)\\&=a_{1}x+2a_{2}x^{2}+3a_{3}x^{3}+\cdots\\&=\sum_{n=0}^{\infty}{na_{n}x^{n}}\end{align*}$$ 이므로 수열 $c_{n}=na_{n}$의 생성함수는 $xf'(x)$이다. 

생성함수를 이용하여 점화식을 구할 수 있다.

예: 점화식 $a_{n}=5a_{n-1}-6a_{n-2},\,a_{0}=1,\,a_{1}=-2$의 일반항은?

풀이: 수열 $a_{n}$의 생성함수를 $\displaystyle f(x)=\sum_{n=0}^{\infty}{a_{n}x^{n}}$이라 하자. 그러면 $$\begin{align*}f(x)&=a_{0}+a_{1}x+a_{2}x^{2}+a_{3}x^{3}+\cdots\\&=a_{0}+a_{1}x+(5a_{1}-6a_{0})x^{2}+(5a_{2}-6a_{1})x^{3}+\cdots\\&=a_{0}+a_{1}x+5x(a_{1}x+a_{2}x^{2}+\cdots)-6x^{2}(a_{0}+a_{1}x+a_{2}x^{2}+\cdots)\\&=a_{0}+(a_{1}-5a_{0})x+5xf(x)-6x^{2}f(x)\\&=1-7x+(5x-6x^{2})f(x)\end{align*}$$ 이므로 $(6x^{2}-5x+1)f(x)=1-7x$이고 $$\begin{align*}f(x)&=\frac{1-7x}{6x^{2}-5x+1}=\frac{5}{1-2x}-\frac{4}{1-3x}\\&=5\sum_{n=0}^{\infty}{2^{n}x^{n}}-4\sum_{n=0}^{\infty}{3^{n}x^{n}}\\&=\sum_{n=0}^{\infty}{(5\cdot2^{n}-4\cdot3^{n})x^{n}}\end{align*}$$ 이므로 따라서 $a_{n}=5\cdot2^{n}-4\cdot3^{n}\,(n\geq0)$이다.

예: 점화식 $a_{n}=8a_{n-1}+10^{n-1},\,a_{0}=1$의 일반항은?

풀이: 수열 $a_{n}$의 생성함수를 $\displaystyle f(x)=\sum_{n=0}^{\infty}{a_{n}x^{n}}$이라 하자. 그러면 $$\begin{align*}f(x)&=a_{0}+a_{1}x+a_{2}x^{2}+a_{3}x^{3}+\cdots\\&=a_{0}+\sum_{n=1}^{\infty}{a_{n}}x^{n}=a_{0}+\sum_{n=1}^{\infty}{(8a_{n-1}+10^{n-1})}\\&=1+8xf(x)+\frac{x}{1-10x}\end{align*}$$ 이고 $$\begin{align*}g(x)&=\frac{1-9x}{(1-8x)(1-10x)}=\frac{1}{2(1-8x)}+\frac{1}{2(1-10x)}\\&=\frac{1}{2}\sum_{n=0}^{\infty}{8^{n}x^{n}}+\frac{1}{2}\sum_{n=0}^{\infty}{10^{n}x^{n}}\\&=\frac{1}{2}\sum_{n=0}^{\infty}{(8^{n}+10^{n})x^{n}}\end{align*}$$ 이므로 따라서 $\displaystyle a_{n}=\frac{8^{n}+10^{n}}{2}$이다.

예: 부정방정식 $x_{1}+2x_{2}+3x_{3}=n$의 음이 아닌 정수해의 개수 $a_{n}$은?

풀이: 각 변수의 선택을 나타내는 생성함수는 $$\begin{align*}1+x+x^{2}+\cdots&=\frac{1}{1-x}\,(x_{1})\\1+x^{2}+x^{4}+\cdots&=\frac{1}{1-x^{2}}\,(2x_{2})\\1+x^{3}+x^{6}+\cdots&=\frac{1}{1-x^{3}}\,(3x_{3})\end{align*}$$ 이므로 $a_{n}$의 생성함수를 $\displaystyle f(x)=\sum_{n=0}^{\infty}{a_{n}x^{n}}$라고 하면 $$\begin{align*}f(x)&=(1+x+x^{2}+\cdots)(1+x^{2}+x^{4}+\cdots)(1+x^{3}+x^{6}+\cdots)\\&=\frac{1}{1-x}\frac{1}{1-x^{2}}\frac{1}{1-x^{3}}=\frac{1}{(1-x)^{3}}\frac{1}{1+x}\frac{1}{1+x+x^{2}}\\&=\frac{1}{(1-x)^{3}}\frac{1}{1+x}\frac{1}{1-\omega x}\frac{1}{1-\omega^{2}x}\\&=\frac{A}{1-x}+\frac{B}{(1-x)^{2}}+\frac{C}{(1-x)^{3}}+\frac{D}{1+x}+\frac{E}{1-\omega x}+\frac{F}{1-\omega^{2}x}\end{align*}$$ 이고 여기서 $\displaystyle\omega=e^{\frac{2\pi}{3}i}$이다. 위 식을 만족하는 $A,\,B,\,C,\,D,\,E,\,F$를 구하면 $$A=\frac{17}{72},\,B=\frac{1}{4},\,C=\frac{1}{6},\,D=\frac{1}{8},\,E=\frac{1}{9},\,F=\frac{1}{9}$$ 이므로 $$\begin{align*}f(x)&=\sum_{n=0}^{\infty}{\left(\frac{17}{72}+\frac{1}{4}_{2}H_{n}+\frac{1}{6}_{3}H_{n}+\frac{1}{8}(-1)^{n}+\frac{1}{9}\omega^{n}+\frac{1}{9}\omega^{2n}\right)x^{n}}\\&=\sum_{n=0}^{\infty}{\left(\frac{17}{72}+\frac{n+1}{4}+\frac{(n+1)(n+2)}{6}+\frac{1}{8}(-1)^{n}+\frac{1}{9}\delta_{n}\right)}\end{align*}$$ 이고 $$\delta_{n}=\omega^{n}+\omega^{2n}=\begin{cases}2,\,&(n\equiv0\,(\text{mod}\,3))\\-1,\,&(n\not\equiv0\,(\text{mod}\,3))\end{cases}$$ 이므로 따라서 $$a_{n}=\frac{17}{72}+\frac{n+1}{4}+\frac{(n+1)(n+2)}{6}+\frac{1}{8}(-1)^{n}+\frac{1}{9}\delta_{n}$$ 이다.(이 문제는 자연수 $n$을 3 이하의 자연수의 합으로 나타내는 방법의 수를 구하는 문제와 같다.)

예: 자연수 $n$을 분할하는 경우의 수를 $p(n)$이라고 할 때, $p(n)$의 생성함수는?

풀이: 자연수의 분할은 1이 몇개 있는가, 2가 몇개 있는가, ... 등으로 구별되므로 그 생성함수는 $$\begin{align*}P_{n}(x)&=(1+x+x^{2}+\cdots)(1+x^{2}+x^{4}+\cdots)(1+x^{3}+x^{6}+\cdots)\cdots(1+x^{n}+x^{2n}+\cdots)\cdots\\&=\frac{1}{1-x}\frac{1}{1-x^{2}}\frac{1}{1-x^{3}}\cdots\frac{1}{1-x^{n}}\cdots\\&=\prod_{n=1}^{\infty}{\frac{1}{1-x^{i}}}\end{align*}$$ 이다.

($p(n)$은 위 생성함수에서 $x^{n}$의 계수이다.)

예: 자연수 $n$을 서로 다른 자연수들의 합으로 나타내는 경우의 수를 $a_{n}$이라고 할 때, $a_{n}$의 생성함수는?

풀이: 한번 사용한 자연수는 다시 사용할 수 없으므로 모든 자연수는 사용되거나 사용되지 않거나 이 두가지 경우만이 가능하다. 그러므로 생성함수는 $$\begin{align*}f(x)&=(1+x)(1+x^{2})(1+x^{3})\cdots(1+x^{n})\cdots\\&=\prod_{n=1}^{\infty}{(1+x^{n})}\end{align*}$$ 이다.

참고자료:

조합 및 그래프이론, 김정진, 교우사