논술 생성함수

＊생성함수

수열 $\displaystyle a_0,a_1,a_2,\ldots$에 대하여$\displaystyle A(x)=a_0+a_1x+a_2x^2+\cdots=\sum_{n=0}^{\infty}a_nx^n$을 이 수열의 생성함수라 한다.수열의 각 항을 $\displaystyle x$의 차수에 따라 계수로 나란히 적은 식이다.

여기서는 $\displaystyle x$에 값을 대입하여 합을 구하기보다,각 차수의 계수를 계산하는 데 생성함수를 사용한다.이처럼 계수에 주목하여 다루는 형식적인 급수에서는 수렴을 전제로 하지 않는다.

＊생성함수의 곱과 수열의 합성곱

두 수열의 생성함수를 각각$\displaystyle A(x)=\sum_{n=0}^{\infty}a_nx^n,\qquad B(x)=\sum_{n=0}^{\infty}b_nx^n$이라 하자. 두 식을 곱할 때 $\displaystyle x^n$의 계수는차수의 합이 $\displaystyle n$인 항들을 곱하여 더한 값이다.$\displaystyle c_n=a_0b_n+a_1b_{n-1}+\cdots+a_nb_0=\sum_{k=0}^{n}a_kb_{n-k}$따라서$\displaystyle A(x)B(x)=\sum_{n=0}^{\infty}c_nx^n$이다. 특정 차수의 계수를 구하는 데에는 유한개의 항만 필요하다.

이렇게 얻은 수열 $\displaystyle \{c_n\}$을 두 수열 $\displaystyle \{a_n\}$, $\displaystyle \{b_n\}$의 합성곱이라 한다.곱하는 두 항의 첨자 합은 항상 $\displaystyle n$이다.즉, 수열의 합성곱은 생성함수의 곱에 대응한다.

수열을 각각 $\displaystyle a,b,c$, 합성곱을 $\displaystyle *$로 나타내면,합성곱은 교환법칙과 결합법칙, 덧셈에 대한 분배법칙을 만족한다.$\displaystyle a*b=b*a,\qquad (a*b)*c=a*(b*c)$$\displaystyle a*(b+c)=a*b+a*c$

수열 $\displaystyle (1,0,0,\ldots)$의 생성함수는 $\displaystyle 1$이다.이 수열과 합성곱을 하면 원래 수열이 그대로 나오므로,이 수열은 합성곱의 항등원이다.

＊경우의 수와 생성함수

선택할 수 있는 개수를 $\displaystyle x$의 지수로 나타내자.어떤 물건을 고르지 않거나 한 개 고를 수 있다면 $\displaystyle 1+x$,두 개까지 고를 수 있다면 $\displaystyle 1+x+x^2$로 나타낸다.같은 종류의 물건은 서로 구별하지 않는다고 하자.

한 종류는 두 개까지, 다른 종류는 세 개까지 고를 수 있을 때,전체 선택을 다음 곱으로 나타낼 수 있다.$\displaystyle (1+x+x^2)(1+x+x^2+x^3)$각 인수에서 항을 하나씩 고르면, 지수의 합은 고른 물건의 총개수가 된다.같은 차수의 항들을 모은 계수는 그 개수를 고르는 방법의 수이다.

예를 들어 $\displaystyle x^3$은 $\displaystyle 1\cdot x^3$, $\displaystyle x\cdot x^2$, $\displaystyle x^2\cdot x$에서 나온다.따라서 $\displaystyle x^3$의 계수는 $\displaystyle 3$이고, 총 세 개를 고르는 방법도 세 가지이다.

서로 다른 $\displaystyle n$개의 물건을 각각 고르거나 고르지 않는 경우는$\displaystyle (1+x)^n=\sum_{r=0}^{n}{}_n\mathrm C_r x^r$으로 나타낼 수 있다. $\displaystyle x^r$의 계수는 정확히 $\displaystyle r$개를 고르는 방법의 수이다.

＊점화식과 생성함수

생성함수에 $\displaystyle x$를 곱하면 각 항의 차수가 하나씩 올라간다.이 성질을 이용하면 점화식을 생성함수에 관한 식으로 바꿀 수 있다.

피보나치 수열$\displaystyle a_0=0,\qquad a_1=1,\qquad a_n=a_{n-1}+a_{n-2}\quad(n\ge2)$의 생성함수를 $\displaystyle A(x)$라 하자. 점화식의 양변에 $\displaystyle x^n$을 곱하여$\displaystyle n=2$부터 더하면$\displaystyle A(x)-x=xA(x)+x^2A(x)$이므로$\displaystyle A(x)=\frac{x}{1-x-x^2}$이다. 점화식과 처음 몇 항에 관한 조건이 하나의 식에 함께 담긴다.

처음에 뺀 $\displaystyle a_0,a_1x$와 같은 항들을 챙겨야 한다.점화식이 어느 항부터 성립하는지에 따라, 생성함수의 식에서 따로 남는 항이 달라진다.