생성함수 (수학) 문서 원본 보기

{{위키데이터 속성 추적}}
{{다른 뜻|모함수 (물리학)|수학의 생성함수(모함수)|일반적인 역학에서의 모함수}}

[[수학]]에서 어떤 [[수열]] ''a''<sub>''n''</sub> (n은 [[자연수]])에 대하여,
:<math>f(x)= a_0+a_1x+a_2x^2+\cdots+a_nx^n+\cdots = \sum_{k=0}^\infty a_k x^k</math>
와 같이 미지수의 계수가 수열의 각 항으로 되어 있는 [[형식적 멱급수|멱급수]] 형태의 [[함수]] 즉, 그 수열을 계수로 하는 [[멱급수]]를 '''생성함수'''(生成函數, generating function)라고 한다.

[[아브라암 드무아브르]]가 1730년에 일반 선형 점화식 문제를 풀기 위해 도입하였다.<ref>Donald E. Knuth, ''The Art of Computer Programming, Volume 1 Fundamental Algorithms (Third Edition)'' Addison-Wesley. {{ISBN|0-201-89683-4}}. Section 1.2.9: "Generating Functions".</ref> 생성함수는 여러 경우에 이용되는데 예를 들어 어떤 수열에 대한 [[점화식]]을 이용해 [[일반항]]을 알아낼 때에도 쓰인다.

==정의==
===일반 생성함수===
수열 ''a''<sub>''n''</sub>의 '''일반 생성함수'''(ordinary generating function)는 다음과 같이 정의한다.

:<math>G(a_n;x)=\sum_{n=0}^\infty a_nx^n.</math>

별도의 말이 없는 경우, 보통 생성함수는 일반생성함수를 말한다.

만약 ''a''<sub>''n''</sub>이 [[이산 확률 변수]]의 [[확률 질량 함수]]라면 그 생성함수는 '''확률 생성 함수'''라고 부른다.

일반생성함수는 인덱스가 여러 개인 배열로 일반화시킬 수 있다. 예를 들어, 2차원 배열 ''a''<sub>''m,n''</sub> (''n'', ''m''은 자연수)의 일반생성함수는 다음과 같이 정의한다.

:<math>G(a_{m,n};x,y)=\sum_{m,n=0}^\infty a_{m,n}x^my^n.</math>

=== 간단한 수열의 예 ===
다항식(Polynomials)은 일반 생성함수(ordinary generating functions)의 특수한 경우로, 이는 유한 수열(finite sequences)에 해당하며, 동일하게 일정 시점 이후로 사라지는 수열에 해당한다.

이러한 다항식은 많은 유한 수열이 생성함수로 해석될 수 있기 때문에 중요하다. 예를 들어, 푸앵카레 다항식(Poincare polynomial)과 기타 다른 수열들이 이에 해당한다.

가장 기본적인 생성함수 중 하나는 상수 수열 1, 1, 1, 1, 1, 1, 1, 1, 1, ….. 의 생성함수로, 이 수열의 일반 생성함수는 기하급수(geometric series)이다.

<math>\sum_{n=0}^\infty x^n= \frac{1}{1-x}</math>

왼쪽 항은 오른쪽 항의 맥클로린 급수(Maclaurin series) 전개이다. 또는, 이 등식은 왼쪽의 거듭제곱 급수를 <math>1-x
</math>로 곱한 결과가 상수 거듭제곱 급수(멱급수) 1이 됨을 확인함으로써도 확인해 볼 수 있다(다시 말해, x^0의 계수를 제외한 모든 계수가 0임을 확인하는 것이다.). 

더욱이, 이러한 성질을 가지는 다른 거듭제곱 급수(멱급수)는 존재하지 않는다. 따라서 왼쪽 항은 거듭제곱 급수(멱급수)의 환(ring)에서 1 - x의 곱셈적 역원(multiplicative inverse)을 나타낸다.

다른 수열에 대한 일반 생성함수의 표현식은 이 결과로부터 쉽게 유도할 수 있다. 예를 들어, 변수 x를 ax로 치환하면 임의의 상수 a에 대해 기하수열 1, a, a2, a3, ….. 의 생성함수를 얻을 수 있다.

<math>\sum_{n=0}^\infty(ax)^n= \frac{1}{1-ax}</math>

특히, 𝑎 = −1일 때는 다음과 같은 형태를 갖는다.

<math>\sum_{n=0}^\infty(-1)^nx^n= \frac{1}{1+x}</math>

𝑥를 더 큰 거듭제곱으로 대체하면 수열에 간격을 만들 수 있다. 예를 들어, 수열 1, 0, 1, 0, 1, 0, ... (홀수 차수는 생략됨)에 대한 생성 함수는 다음과 같다.

<math>\sum_{n=0}^\infty x^{2n} = \frac{1}{1-x^2}</math>

초기 생성 함수를 제곱하거나 양변을 x에 대해 미분하고 변수를 n → n + 1로 바꾸면 계수가 1, 2, 3, 4, 5, ...로 이루어진 수열을 얻을 수 있다. 이는 다음과 같은 식으로 표현된다.

<math>\sum_{n=0}^\infty(n+1)x^n= \frac{1}{(1-x)^2}</math>

세제곱의 경우는 삼각수(1, 3, 6, 10, 15, 21, ...)로 이루어지며, 그 n번째 항은 이항 계수(n+2/2)로 표현된다. 이는 다음과 같은 생성 함수로 나타낼 수 있다.

<math>\sum_{n=0}^\infty\binom{n+2}2 x^n= \frac{1}{(1-x)^3}</math>

일반적으로, 임의의 음이 아닌 정수 k와 0이 아닌 실수 𝑎에 대해 다음과 같은 생성 함수가 성립한다.

<math>\sum_{n=0}^\infty a^n\binom{n+k}k x^n= \frac{1}{(1-ax)^{k+1}}\,</math>

또한,  

<math>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</math>

이항 계수를 이용하여 제곱수 수열(0, 1, 4, 9, 16, ...)에 대한 생성 함수를 구할 수 있다. 이 수열에 대한 생성 함수는 다음과 같은 선형 결합으로 표현된다.

<math>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}</math>

이 수열은 기하급수의 도함수 합을 이용하여 다른 방식으로도 생성할 수 있다.

<math>\begin{align}
G(n^2;x)
 & = \sum_{n=0}^\infty n^2x^n \\[4px]
 & = \sum_{n=0}^\infty n(n-1) x^n + \sum_{n=0}^\infty n x^n \\[4px]
 & = x^2 D^2\left[\frac{1}{1-x}\right] + x D\left[\frac{1}{1-x}\right] \\[4px]
 & = \frac{2 x^2}{(1-x)^3} + \frac{x}{(1-x)^2} =\frac{x(x+1)}{(1-x)^3}
\end{align}</math>

귀납법을 사용하면, 임의의 양의 정수 <math>m>1</math>에 대해 다음과 같이 일반화할 수 있다.

<math>n^m = \sum_{j=0}^m \begin{Bmatrix} m \\ j \end{Bmatrix} \frac{n!}{(n-j)!}</math>

여기서 {n,k}는 제2종 스털링 수(Stirling numbers of the second kind)를 나타낸다. 이 수에 대한 생성 함수는 다음과 같다.

<math>\sum_{n = 0}^\infty \frac{n!}{ (n-j)!} \, z^n = \frac{j! \cdot z^j}{(1-z)^{j+1}}</math>

마지막으로, 이 결과를 일반화하여 k차 항에 대한 생성 함수도 구할 수 있다. 이 부분은 제곱 함수의 결과를 일반화하여 정수 m차 항에 대한 유사한 생성 함수를 도출하는 방법을 설명하고 있다. 특히, 다음과 같은 형태로 표현할 수 있다.

<math>\frac{z^k}{(1-z)^{k+1}} = \sum_{i=0}^k \binom{k}{i} \frac{(-1)^{k-i}}{(1-z)^{i+1}}</math>

이 식을 통해 z^k/(1-z)^k+1 를 항으로 분해할 수 있다. 이는 잘 알려진 유한 합 항등식(finite sum identity)과 스털링 수(Stirling numbers)를 적용하여 다음과 같은 생성 함수를 구할 수 있게 한다.

<math>\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}}</math>

여기서 {m+1, j+1}는 제 2종 스털링 수(Stirling numbers of the second kind)를 나타낸다. 이 결과는 제곱 수 케이스를 확장하여 n^m 형태의 정수 m차 항에 대한 생성 함수를 구할 수 있게 한다.

===지수 생성함수===
수열 ''a''<sub>''n''</sub>의 '''지수 생성함수'''(exponential generating function)는 다음과 같이 정의한다.

:<math>\operatorname{EG}(a_n;x)=\sum _{n=0}^{\infty} a_n \frac{x^n}{n!}.</math>

===푸아송 생성 함수===
수열 ''a''<sub>''n''</sub>의 '''푸아송 생성함수'''(poisson generating function)는 다음과 같이 정의한다.

:<math>\operatorname{PG}(a_n;x)=\sum _{n=0}^{\infty} a_n e^{-x} \frac{x^n}{n!} = e^{-x}\, \operatorname{EG}(a_n;x).</math>

===람베르트 급수===
수열 ''a''<sub>''n''</sub>의 '''람베르트 급수'''(lambert series)는 다음과 같이 정의한다.

:<math>\operatorname{LG}(a_n;x)=\sum _{n=1}^{\infty} a_n \frac{x^n}{1-x^n}.</math>

===벨 급수===

수열 ''a''<sub>''n''</sub>의 '''벨 급수'''(bell series)는 미지수 ''x''와 소수 ''p'' 두 가지로 표현된 급수로,<ref>{{Apostol IANT}} pp.42–43</ref> 다음과 같이 정의한다.

:<math>\operatorname{BG}_p(a_n;x)=\sum_{n=0}^\infty a_{p^n}x^n.</math>
:

== 같이 보기 ==
* [[모멘트 생성 함수]]
* [[자연수 분할]]
* [[Z변환]]
* [[음계산법]]

== 각주 ==
{{각주}}

{{전거 통제}}

[[분류:조합론]]