자연계열 1번

(가) 주어진 수열 $\displaystyle a_n,\ n=0,1,2,\cdots$을 계수로 가지는 무한 급수 $\displaystyle A(x)=a_0+a_1x+a_2x^2+a_3x^3+\cdots$를 수열 $\displaystyle \{a_n\}$의 생성함수라고 한다. 수열 $\displaystyle 1,-1,0,0,0,0,\cdots$의 생성함수는 $\displaystyle 1-1x+0x^2+0x^3+\cdots=1-x$이며 수열 $\displaystyle 1,1,1,1,1,1,\cdots$의 생성함수는 $\displaystyle 1+1x+1x^2+1x^3+\cdots=1+x+x^2+x^3+\cdots$이다. $\displaystyle B(x)=b_0+b_1x+b_2x^2+b_3x^3+\cdots$가 수열 $\displaystyle \{b_n\}$의 생성함수이고 두 생성함수의 합을 $\displaystyle A(x)+B(x):=(a_0+b_0)+(a_1+b_1)x+(a_2+b_2)x^2+(a_3+b_3)x^3+\cdots$로 정의하면 $\displaystyle A(x)+B(x)$는 수열 $\displaystyle \{a_n+b_n\}$의 생성함수가 됨을 알 수 있다. 두 생성함수 $\displaystyle A(x)$와 $\displaystyle B(x)$의 곱을 다음과 같이 정의하는 것은 매우 자연스럽다:$\displaystyle \begin{aligned}A(x)B(x)&=a_0b_0+(a_0b_1+a_1b_0)x+(a_0b_2+a_1b_1+a_2b_0)x^2+(a_0b_3+a_1b_2+a_2b_1+a_3b_0)x^3+\cdots\end{aligned}$이제 $\displaystyle A(x)B(x)$는 수열 $\displaystyle \{a_n\}$과 수열 $\displaystyle \{b_n\}$에 의해서 만들어지는 새로운 수열 $\displaystyle \{c_n\},\ c_n=\sum_{i=0}^n a_i b_{n-i}$, 의 생성함수임을 알 수 있다.$\displaystyle (1-x)(1+x+x^2+x^3+\cdots)=1+(1-1)x+(1-1)x^2+(1-1)x^3+\cdots=1$ 이므로 $\displaystyle 1+x+x^2+x^3+\cdots=\frac1{1-x}$라고 표현할 수 있다.

(나) 수열 $\displaystyle a_n,\ n=0,1,2,\cdots$는 초깃값 $\displaystyle a_0$과 함수 $\displaystyle f_n,\ n\ge1$, 들에 의해 정해지는 점화식 $\displaystyle a_n=f_n(a_0,a_1,\cdots,a_{n-1}),\ n\ge1$, 이 주어지면 유일한 방법으로 결정된다. 예를 들어 $\displaystyle d_0=d_1=1$, $\displaystyle d_n=d_{n-1}+d_{n-2},\ n\ge2$에 의하여 수열 $\displaystyle \{d_n\}$은 완벽히 결정 된다: $\displaystyle d_0=d_1=1$, $\displaystyle d_2=d_1+d_0=2$, $\displaystyle d_3=d_2+d_1=2+1=3$, ...따라서 초깃값과 점화식이 같은 두 수열은 같은 수열이며 같은 생성함수를 가지게 됨을 알 수 있다.

예제 1. 자연수 $\displaystyle n$을 1과 2의 합으로 나타내는 방법의 수를 $\displaystyle d_n$이라고 하자. 이 때 더하는 순서가 다르면 다른 방법으로 생각한다. 예를 들어 $\displaystyle n=4$이면 다음 다섯 가지 서로 다른 방법이 존재 한다: $\displaystyle 1+1+1+1$, $\displaystyle 1+1+2$, $\displaystyle 1+2+1$, $\displaystyle 2+1+1$, $\displaystyle 2+2$. 따라서 $\displaystyle d_4=5$이다. 수열 $\displaystyle \{d_n\}$의 점화식을 구해보자. $\displaystyle n$을 1과 2의 합으로 나타내는 방법은 그 첫 번째 수가 1인 경우와 2인 경우로 나누어 생각해볼 수 있으며 첫 수가 1이면 나머지 수들은 그 합이 $\displaystyle n-1$ 그리고 첫 수가 2이면 나머지 수들은 그 합이 $\displaystyle n-2$가 되어야 함을 알 수 있다. 따라서 $\displaystyle d_n=d_{n-1}+d_{n-2},\ n\ge3$, 이 성립하며 편의상 $\displaystyle d_0=1$이라 약속하면 $\displaystyle d_2=d_1+d_0$도 성립한다.(1) 이제 수열 $\displaystyle \{d_n\}$의 생성함수를 $\displaystyle D(x)$라고 하면 $\displaystyle \{d_n\}$이 만족하는 점화식을 적절히 사용하여 다음과 같은 계산을 할 수 있다.$\displaystyle \begin{aligned}D(x)&=d_0+d_1x+d_2x^2+d_3x^3+\cdots\\&=1+x+(d_1+d_0)x^2+(d_2+d_1)x^3+\cdots\\&=1+x+(d_1x^2+d_2x^3+d_3x^4+\cdots)+(d_0x^2+d_1x^3+d_2x^4+\cdots)\\&=1+x+(xD(x)-d_0x)+x^2D(x)\end{aligned}$따라서 $\displaystyle D(x)(1-x-x^2)=1$이며, $\displaystyle \alpha=\frac{1+\sqrt5}2,\ \beta=\frac{1-\sqrt5}2$일 때,$\displaystyle \begin{aligned}D(x)&=\frac1{(1-x-x^2)}=\frac1{(1-\alpha x)(1-\beta x)}\\&=\frac1{\sqrt5x}\left(\frac1{1-\alpha x}-\frac1{1-\beta x}\right)\\&=\frac1{\sqrt5x}((1+\alpha x+\alpha^2x^2+\cdots)-(1+\beta x+\beta^2x^2+\cdots))\end{aligned}$이 된다. 그리고 $\displaystyle D(x)$에서 $\displaystyle x^n$의 계수를 읽으면 $\displaystyle d_n=\frac1{\sqrt5}(\alpha^{n+1}-\beta^{n+1})$이 된다.

(2) 점화식 $\displaystyle d_n=d_{n-1}+d_{n-2},\ n\ge2$, 을 다른 방법으로 생각해보자.$\displaystyle d_n=d_{n-1}+d_{n-2}=0d_n+1d_{n-1}+1d_{n-2}+0d_{n-3}+\cdots+0d_0$이므로 $\displaystyle a_0=0,a_1=1,a_2=1,a_3=a_4=a_5=\cdots=0$이라하면 $\displaystyle d_n=\sum_{i=0}^n a_i d_{n-i},\ n\ge2$, 가 만족된다. 따라서 수열 $\displaystyle \{a_n\}$의 생성함수는 $\displaystyle A(x)=x+x^2$이며 생성함수의 곱의 규칙에 의하여$\displaystyle \begin{aligned}D(x)&=d_0+d_1x+(a_0d_2+a_1d_1+a_2d_0)x^2+(a_0d_3+a_1d_2+a_2d_1+a_3d_0)x^3+\cdots\\&=d_0+d_1x-(a_0d_0)-(a_0d_1+a_1d_0)x\\&\quad+(a_0d_0)+(a_0d_1+a_1d_0)x+(a_0d_2+a_1d_1+a_2d_0)x^2+(a_0d_3+a_1d_2+a_2d_1+a_3d_0)x^3+\cdots\\&=1+x-x+A(x)D(x)=1+(x+x^2)D(x)\end{aligned}$이며 (1)에서와 같이 $\displaystyle D(x)=\frac1{1-x-x^2}$이 된다.

예제 2. 다섯 개의 수 $\displaystyle x_1,x_2,x_3,x_4,x_5$를 더하는 순서를 정하는 방법의 수를 구해보자. $\displaystyle x_1+x_2+x_3+x_4+x_5$를 계산하는 순서는 괄호를 이용하면 자연스럽게 정해진다. 예를 들어 $\displaystyle (x_1+x_2)+(x_3+(x_4+x_5))$는 $\displaystyle (x_1+x_2)$와 $\displaystyle (x_3+(x_4+x_5))$를 더하는 일을 마지막에 해야 함을 뜻한다. 덧셈기호 양쪽의 값을 계산하는 순서는 덧셈기호의 왼쪽을 먼저 계산하는 것으로 정하면 $\displaystyle (x_1+x_2)$을 먼저 계산하고 $\displaystyle (x_3+(x_4+x_5))$를 계산한 후에 두 수의 합을 계산하면 된다.$\displaystyle n$개의 수 $\displaystyle x_1,x_2,\cdots,x_n$를 더하는 순서를 정하는 방법의 수를 $\displaystyle e_n$이라고 한다면 우리가 구하고자 하는 수 는 $\displaystyle e_5$이며, $\displaystyle e_1=1$로 약속하면 마지막으로 실행하는 덧셈의 위치에 따라 $\displaystyle e_5=e_1e_4+e_2e_3+e_3e_2+e_4e_1$로 쓸 수 있음을 알 수 있다. 이 때 $\displaystyle e_0=0$이라 하면 $\displaystyle n\ge2$일 때 $\displaystyle e_n=\sum_{i=0}^n e_i e_{n-i}$이 성립한다. 따라서 $\displaystyle E(x)$를 수열 $\displaystyle \{e_n\}$의 생성함수라 하면 $\displaystyle E(x)$가 만족하는 식을 얻을 수 있다.