생성함수 (수학)

수학에서 어떤 수열 a_n (n은 자연수)에 대하여,

f(x)=a_{0}+a_{1}x+a_{2}x^{2}+\cdots +a_{n}x^{n}+\cdots =\sum _{k=0}^{\infty }a_{k}x^{k}

와 같이 미지수의 계수가 수열의 각 항으로 되어 있는 멱급수 형태의 함수 즉, 그 수열을 계수로 하는 멱급수를 생성함수(生成函數, generating function)라고 한다.

아브라암 드무아브르가 1730년에 일반 선형 점화식 문제를 풀기 위해 도입하였다.^[1] 생성함수는 여러 경우에 이용되는데 예를 들어 어떤 수열에 대한 점화식을 이용해 일반항을 알아낼 때에도 쓰인다.

정의

일반 생성함수

수열 a_n의 일반 생성함수(ordinary generating function)는 다음과 같이 정의한다.

G(a_{n};x)=\sum _{n=0}^{\infty }a_{n}x^{n}.

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

만약 a_n이 이산 확률 변수의 확률 질량 함수라면 그 생성함수는 확률 생성 함수라고 부른다.

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

G(a_{m,n};x,y)=\sum _{m,n=0}^{\infty }a_{m,n}x^{m}y^{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)^{n}x^{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^{2}x^{n}={\frac {2}{(1-x)^{3}}}-{\frac {3}{(1-x)^{2}}}+{\frac {1}{1-x}}={\frac {x(x+1)}{(1-x)^{3}}}$

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

${\begin{aligned}G(n^{2};x)&=\sum _{n=0}^{\infty }n^{2}x^{n}\\[4px]&=\sum _{n=0}^{\infty }n(n-1)x^{n}+\sum _{n=0}^{\infty }nx^{n}\\[4px]&=x^{2}D^{2}\left[{\frac {1}{1-x}}\right]+xD\left[{\frac {1}{1-x}}\right]\\[4px]&={\frac {2x^{2}}{(1-x)^{3}}}+{\frac {x}{(1-x)^{2}}}={\frac {x(x+1)}{(1-x)^{3}}}\end{aligned}}$

귀납법을 사용하면, 임의의 양의 정수 $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 두 가지로 표현된 급수로,^[2] 다음과 같이 정의한다.

\operatorname {BG} _{p}(a_{n};x)=\sum _{n=0}^{\infty }a_{p^{n}}x^{n}.

같이 보기

각주

↑ 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".
↑ 틀:Apostol IANT pp.42–43

[1] 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".

[2] 틀:Apostol IANT pp.42–43

[1]

[2]