생성함수 (수학)

일반적인 역학에서의 모함수 수학에서 어떤 수열 *a**'n* (n은 자연수)에 대하여, :f(x)= a_0+a_1x+a_2x^2+\cdots+a_nx^n+\cdots = \sum_{k=0}^\infty a_k x^k 와 같이 미지수의 계수가 수열의 각 항으로 되어 있는 멱급수 형태의 함수 즉, 그 수열을 계수로 하는 멱급수를 **생성함수*'(生成函數, generating function)라고 한다. 아브라암 드무아브르가 1730년에 일반 선형 점화식 문제를 풀기 위해 도입하였다.Donald E. Knuth, *The Art of Computer Programming, Volume 1 Fundamental Algorithms (Third Edition)'' Addison-Wesley. . Section 1.2.9: "Generating Functions". 생성함수는 여러 경우에 이용되는데 예를 들어 어떤 수열에 대한 점화식을 이용해 일반항을 알아낼 때에도 쓰인다.
# 정의

## 일반 생성함수
수열 *a**'n*의 **일반 생성함수**(ordinary generating function)는 다음과 같이 정의한다. :G(a_n;x)=\sum_{n=0}^\infty a_nx^n. 별도의 말이 없는 경우, 보통 생성함수는 일반생성함수를 말한다. 만약 *a**'n*이 이산 확률 변수의 확률 질량 함수라면 그 생성함수는 **확률 생성 함수**라고 부른다. 일반생성함수는 인덱스가 여러 개인 배열로 일반화시킬 수 있다. 예를 들어, 2차원 배열 *a**m,n* (*n*, *m*은 자연수)의 일반생성함수는 다음과 같이 정의한다. :G(a_{m,n};x,y)=\sum_{m,n=0}^\infty a_{m,n}x^my^n.
## 간단한 수열의 예
다항식(Polynomials)은 일반 생성함수(ordinary generating functions)의 특수한 경우로, 이는 유한 수열(finite sequences)에 해당하며, 동일하게 일정 시점 이후로 사라지는 수열에 해당한다. 이러한 다항식은 많은 유한 수열이 생성함수로 해석될 수 있기 때문에 중요하다. 예를 들어, 푸앵카레 다항식(Poincare polynomial)과 기타 다른 수열들이 이에 해당한다. 가장 기본적인 생성함수 중 하나는 상수 수열 1, 1, 1, 1, 1, 1, 1, 1, 1, ….. 의 생성함수로, 이 수열의 일반 생성함수는 기하급수(geometric series)이다. \sum_{n=0}^\infty x^n= \frac{1}{1-x} 왼쪽 항은 오른쪽 항의 맥클로린 급수(Maclaurin series) 전개이다. 또는, 이 등식은 왼쪽의 거듭제곱 급수를 1-x 로 곱한 결과가 상수 거듭제곱 급수(멱급수) 1이 됨을 확인함으로써도 확인해 볼 수 있다(다시 말해, x^0의 계수를 제외한 모든 계수가 0임을 확인하는 것이다.). 더욱이, 이러한 성질을 가지는 다른 거듭제곱 급수(멱급수)는 존재하지 않는다. 따라서 왼쪽 항은 거듭제곱 급수(멱급수)의 환(ring)에서 1 - x의 곱셈적 역원(multiplicative inverse)을 나타낸다. 다른 수열에 대한 일반 생성함수의 표현식은 이 결과로부터 쉽게 유도할 수 있다. 예를 들어, 변수 x를 ax로 치환하면 임의의 상수 a에 대해 기하수열 1, a, a2, a3, ….. 의 생성함수를 얻을 수 있다. \sum_{n=0}^\infty(ax)^n= \frac{1}{1-ax} 특히, 𝑎 = −1일 때는 다음과 같은 형태를 갖는다. \sum_{n=0}^\infty(-1)^nx^n= \frac{1}{1+x} 𝑥를 더 큰 거듭제곱으로 대체하면 수열에 간격을 만들 수 있다. 예를 들어, 수열 1, 0, 1, 0, 1, 0, ... (홀수 차수는 생략됨)에 대한 생성 함수는 다음과 같다. \sum_{n=0}^\infty x^{2n} = \frac{1}{1-x^2} 초기 생성 함수를 제곱하거나 양변을 x에 대해 미분하고 변수를 n → n + 1로 바꾸면 계수가 1, 2, 3, 4, 5, ...로 이루어진 수열을 얻을 수 있다. 이는 다음과 같은 식으로 표현된다. \sum_{n=0}^\infty(n+1)x^n= \frac{1}{(1-x)^2} 세제곱의 경우는 삼각수(1, 3, 6, 10, 15, 21, ...)로 이루어지며, 그 n번째 항은 이항 계수(n+2/2)로 표현된다. 이는 다음과 같은 생성 함수로 나타낼 수 있다. \sum_{n=0}^\infty\binom{n+2}2 x^n= \frac{1}{(1-x)^3} 일반적으로, 임의의 음이 아닌 정수 k와 0이 아닌 실수 𝑎에 대해 다음과 같은 생성 함수가 성립한다. \sum_{n=0}^\infty a^n\binom{n+k}k x^n= \frac{1}{(1-ax)^{k+1\, 또한, 2\binom{n+2}2 - 3\binom{n+1}1 + \binom{n}0 = 2\frac{(n+1)(n+2)}2 -3(n+1) + 1 = n^2 이항 계수를 이용하여 제곱수 수열(0, 1, 4, 9, 16, ...)에 대한 생성 함수를 구할 수 있다. 이 수열에 대한 생성 함수는 다음과 같은 선형 결합으로 표현된다. G(n^2;x) = \sum_{n=0}^\infty n^2x^n = \frac{2}{(1-x)^3} - \frac{3}{(1-x)^2} + \frac{1}{1-x} = \frac{x(x+1)}{(1-x)^3} 이 수열은 기하급수의 도함수 합을 이용하여 다른 방식으로도 생성할 수 있다. \begin{align} G(n^2;x) & = \sum_{n=0}^\infty n^2x^n \\\\[] & = \sum_{n=0}^\infty n(n-1) x^n + \sum_{n=0}^\infty n x^n \\\\[] & = x^2 D^2\left[\frac{1}{1-x}\right] + x D\left[\frac{1}{1-x}\right] \\\\[] & = \frac{2 x^2}{(1-x)^3} + \frac{x}{(1-x)^2} =\frac{x(x+1)}{(1-x)^3} \end{align} 귀납법을 사용하면, 임의의 양의 정수 m>1에 대해 다음과 같이 일반화할 수 있다. n^m = \sum_{j=0}^m \begin{Bmatrix} m \\\ j \end{Bmatrix} \frac{n!}{(n-j)!} 여기서 {n,k}는 제2종 스털링 수(Stirling numbers of the second kind)를 나타낸다. 이 수에 대한 생성 함수는 다음과 같다. \sum_{n = 0}^\infty \frac{n!}{ (n-j)!} \, z^n = \frac{j! \cdot z^j}{(1-z)^{j+1 마지막으로, 이 결과를 일반화하여 k차 항에 대한 생성 함수도 구할 수 있다. 이 부분은 제곱 함수의 결과를 일반화하여 정수 m차 항에 대한 유사한 생성 함수를 도출하는 방법을 설명하고 있다. 특히, 다음과 같은 형태로 표현할 수 있다. \frac{z^k}{(1-z)^{k+1 = \sum_{i=0}^k \binom{k}{i} \frac{(-1)^{k-i{(1-z)^{i+1 이 식을 통해 z^k/(1-z)^k+1 를 항으로 분해할 수 있다. 이는 잘 알려진 유한 합 항등식(finite sum identity)과 스털링 수(Stirling numbers)를 적용하여 다음과 같은 생성 함수를 구할 수 있게 한다. \sum_{n = 0}^\infty n^m z^n = \sum_{j=0}^m \begin{Bmatrix} m+1 \\\ j+1 \end{Bmatrix} \frac{(-1)^{m-j} j!}{(1-z)^{j+1 여기서 {m+1, j+1}는 제 2종 스털링 수(Stirling numbers of the second kind)를 나타낸다. 이 결과는 제곱 수 케이스를 확장하여 n^m 형태의 정수 m차 항에 대한 생성 함수를 구할 수 있게 한다.
## 지수 생성함수
수열 *a**'n*의 **지수 생성함수'''(exponential generating function)는 다음과 같이 정의한다. :\operatorname{EG}(a_n;x)=\sum _{n=0}^{\infty} a_n \frac{x^n}{n!}.
## 푸아송 생성 함수
수열 *a**'n*의 **푸아송 생성함수'''(poisson generating function)는 다음과 같이 정의한다. :\operatorname{PG}(a_n;x)=\sum _{n=0}^{\infty} a_n e^{-x} \frac{x^n}{n!} = e^{-x}\, \operatorname{EG}(a_n;x).
## 람베르트 급수
수열 *a**'n*의 **람베르트 급수'''(lambert series)는 다음과 같이 정의한다. :\operatorname{LG}(a_n;x)=\sum _{n=1}^{\infty} a_n \frac{x^n}{1-x^n}.
## 벨 급수
수열 *a**'n*의 **벨 급수*'(bell series)는 미지수 *x*와 소수 *p'' 두 가지로 표현된 급수로,Apostol IANT pp.42–43 다음과 같이 정의한다. :\operatorname{BG}_p(a_n;x)=\sum_{n=0}^\infty a_{p^n}x^n. :