Generating Function
수열
a_n=\{a_0, a_1, \cdots, a_k, \cdots\}=\{a_k\}에 대해 다음
G(x)를 말한다.
\displaystyle G(x)=\sum_{k=0}^{\infty}a_kx^k = a_0+a_1x+a_2x^2+\cdots이를
a_n의 보통 생성함수(Ordinary Generating Function)
(1)라고도 한다.
생성함수라는 용어는 라플라스의 확률이론분석(The2 orie Analytique des Probabilities, Paris, 1812)에서 처음 사용되었다.
목차
1. 성질
2. 지수 생성함수
3. 영상
생성함수끼리 또는 다른 스칼라값과 더하거나 곱해도 생성함수이다. 고로, \{a_k\}의 생성함수 A(x)와 \{b_k\}의 생성함수 B(x)에 대하여
\displaystyle A(x)+B(x) = \sum_{k=0}^{\infty}a_kx^k+\sum_{k=0}^{\infty}b_kx^k=\sum_{k=0}^{\infty}(a_k+b_k)x^k
\displaystyle A(x)B(x) = (a_0+a_1x+a_2x^2+\cdots)(b_0+b_1x+b_2x^2+\cdots) = \sum_{k=0}^{\infty}d_kx^k \ (d_k = \sum_{i=0}^k a_ib_{k-i})
\displaystyle A(x)+n=(a_0+n)+a_1x+a_2x^2+\cdots = \sum_{k=0}^{\infty}e_kx^k \ (e_0 = a_0+n, \text{ otherwise } e_i = a_i)
\displaystyle nA(x)=n\sum_{k=0}^{\infty}a_kx^k=\sum_{k=0}^{\infty}na_kx^k
2. 지수 생성함수 ✎
수열
a_n=\{a_k\}에 대하여,
a_n의 지수 생성함수(Exponential Generating Function)
EG(x)는 다음의 급수로 정의된다.
\displaystyle EG(x)=\sum_{k=0}^{\infty}a_k \frac{x^k}{k!} = a_0 + a_1\frac{x}{1!} + a_2\frac{x}{2!}+\cdots이 급수의 이름이 지수 생성함수인 이유는 가장 대표적인 수열 중 하나인
\forall n\text{ }a_n=1의 지수 생성함수가
e^x이기 때문이다.
\displaystyle EG(x)=\sum_{k=0}^{\infty}\frac{x^k}{k!}=e^x(2)
