[[분류:가져온 문서/오메가]]
Generating Function
수열 [math(a_n=\{a_0, a_1, \cdots, a_k, \cdots\}=\{a_k\})]에 대해 다음 [math(G(x))]를 말한다.
<math>\displaystyle G(x)=\sum_{k=0}^{\infty}a_kx^k = a_0+a_1x+a_2x^2+\cdots</math>
이를 [math(a_n)]의 보통 생성함수(Ordinary Generating Function)[* 지수 생성함수와 견주어 부르는 말이다.]라고도 한다.
생성함수라는 용어는 라플라스의 확률이론분석(The2 orie Analytique des Probabilities, Paris, 1812)에서 처음 사용되었다.
== 성질 ==
생성함수끼리 또는 다른 스칼라값과 더하거나 곱해도 생성함수이다. 고로, [math(\{a_k\})]의 생성함수 [math(A(x))]와 [math(\{b_k\})]의 생성함수 [math(B(x))]에 대하여
[math(\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)]
[math(\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}))]
[math(\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))]
[math(\displaystyle nA(x)=n\sum_{k=0}^{\infty}a_kx^k=\sum_{k=0}^{\infty}na_kx^k)]
== 지수 생성함수 ==
수열 [math(a_n=\{a_k\})]에 대하여, [math(a_n)]의 지수 생성함수(Exponential Generating Function) [math(EG(x))]는 다음의 급수로 정의된다.
[math(\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 )]
이 급수의 이름이 지수 생성함수인 이유는 가장 대표적인 수열 중 하나인 [math(\forall n\text{ }a_n=1)]의 지수 생성함수가 [math(e^x)]이기 때문이다.
* [math(\displaystyle EG(x)=\sum_{k=0}^{\infty}\frac{x^k}{k!}=e^x)][* [math(e^x)]의 거듭제곱 급수이다.]
== 영상 ==
[youtube(Bq4NK7gObwo)]
[Include(틀:가져옴2,O=오메가, C=[[https://creativecommons.org/licenses/by-nc-sa/3.0/deed.ko|CC BY-NC-SA 3.0]])]
