[조합론] 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*}$$이다.

참고자료:

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