(+)분류 : 가져온 문서/오메가
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. 성질 ✎ ⊖
생성함수끼리 또는 다른 스칼라값과 더하거나 곱해도 생성함수이다. 고로, \\{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
\\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}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)
