생성함수 (수학)

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

생성함수는 수열을 표현하고 조작하는 데 사용되는 수학적 도구로, 조지 폴리아는 이를 여러 물건을 가방에 넣어 관리하는 것에 비유했고, 허버트 윌프는 숫자들을 전시하는 옷걸이에 비유했다. 일반 생성함수는 수열 $a_n$ 을 $G(a_n;x)=\sum_{n=0}^\infty a_nx^n$ 로 정의하며, 지수 생성함수, 푸아송 생성 함수, 람베르트 급수, 벨 급수, 디리클레 급수 생성 함수 등 다양한 종류가 있다. 생성함수는 점화 관계를 풀고, 수열 간의 관계를 찾으며, 점근적 거동을 탐구하는 등 다양한 수학적 문제 해결에 활용된다. 또한, 조합론에서 열거 문제를 풀고, 무한 급수를 계산하는 데에도 사용된다.

2. 정의

생성함수는 주어진 수열의 정보를 표현하고 분석하는 데 사용되는 도구이다. 일반적인 급수와 달리, 형식적 멱급수는 수렴할 필요가 없으며, 변수는 미정 변수로 남는다. 이는 생성함수가 실제 함수로 간주되지 않음을 의미한다.^[2]

라플라스는 생성함수라는 이름을 붙였지만, 오일러는 이미 이 기법을 조합론 및 정수론의 여러 문제에 적용했다.^[2] 폴리아는 생성함수를 "여러 개의 작은 물건을 담는 가방"에 비유했고,^[2] 윌프는 "일련의 숫자들을 전시하기 위해 걸어두는 옷걸이"라고 표현했다.^[2]

몇 가지 일반적인 생성함수의 형태는 다음과 같다.

일반 생성함수 (OGF):

$G(a_n;x)=\sum_{n=0}^\infty a_n x^n.$
지수 생성함수 (EGF):

$\operatorname{EG}(a_n;x)=\sum_{n=0}^\infty a_n \frac{x^n}{n!}.$
푸아송 생성함수 (PGF):

$\operatorname{PG}(a_n;x)=\sum _{n=0}^\infty a_n e^{-x} \frac{x^n}{n!} = e^{-x}\, \operatorname{EG}(a_n;x).$
람베르트 급수:

$\operatorname{LG}(a_n;x)=\sum _{n=1}^\infty a_n \frac{x^n}{1-x^n}.$
벨 급수:

$\operatorname{BG}_p(a_n;x) = \sum_{n=0}^\infty a_{p^n}x^n.$
디리클레 급수 생성함수 (DGF):

$\operatorname{DG}(a_n;s)=\sum _{n=1}^\infty \frac{a_n}{n^s}.$

2. 1. 일반 생성함수

수열 ''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.

2. 2. 지수 생성함수

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

:

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

지수 생성함수는 라벨이 지정된 객체를 포함하는 조합적 열거 문제에 대해 일반 생성함수보다 일반적으로 더 편리하다.^[3]

지수 생성함수의 또 다른 장점은 선형 점화 관계를 미분 방정식 영역으로 변환하는 데 유용하다는 것이다. 예를 들어, 선형 점화 관계

f_{n+2} = f_{n+1} + f_n

을 만족하는 피보나치 수열

\{f_n\}

을 생각해 보자. 해당 지수 생성함수는 다음과 같은 형식을 갖는다.

:

\operatorname{EF}(x) = \sum_{n=0}^\infty \frac{f_n}{n!} x^n

그리고 그 도함수는 위의 점화 관계와 직접적인 유사성을 갖는 미분 방정식

\operatorname{EF}''(x) = \operatorname{EF}'(x) + \operatorname{EF}(x)

를 만족하는 것으로 쉽게 나타낼 수 있다.

2. 3. 푸아송 생성 함수

수열 ''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).

2. 4. 람베르트 급수

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

:

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

람베르트 급수에서 지표 n은 0이 아닌 1부터 시작한다. 그렇지 않으면 첫 번째 항이 정의되지 않는다.

정수 n에 대한 거듭제곱 급수 전개에서 람베르트 급수 계수

b_n := [x^n] \operatorname{LG}(a_n;x)

는 약수 합에 의해 관련된다.

b_n = \sum_{d|n} a_d.

, < 1에 대해 다음을 보일 수 있다. ^[4]

\sum_{n = 1}^\infty \frac{q^n x^n}{1-x^n} = \sum_{n = 1}^\infty \frac{q^n x^{n^2}}{1-q x^n} + \sum_{n = 1}^\infty \frac{q^n x^{n(n+1)}}{1-x^n},

여기서 약수 함수 의 생성 함수에 대한 특수한 경우 항등식이 주어진다.

\sum_{n = 1}^\infty \frac{x^n}{1-x^n} = \sum_{n = 1}^\infty \frac{x^{n^2} \left(1+x^n\right)}{1-x^n}.

2. 5. 벨 급수

수열 ''a''_''n''의 '''벨 급수'''는 미지수 ''x''와 소수 ''p'' 두 가지로 표현된 급수로,^[34] 다음과 같이 정의한다.

:

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

수론적 함수 ''f''(''n'')과 소수 ''p''에 대한 벨 급수는 다음과 같이 주어진다.

:

f_p(x)=\sum_{n=0}^\infty f(p^n)x^n

2. 6. 디리클레 급수 생성 함수

수열 ''a''_''n''의 '''디리클레 급수 생성 함수'''(Dirichlet series generating function)는 다음과 같다.^[6]

:

\operatorname{DG}(a_n;s)=\sum _{n=1}^\infty \frac{a_n}{n^s}.

디리클레 급수 생성 함수는 ''a''_''n''이 곱셈 함수일 때 특히 유용하며, 이 경우 함수의 벨 급수를 사용하여 오일러 곱 표현^[7]을 갖는다.

:

\operatorname{DG}(a_n;s)=\prod_{p} \operatorname{BG}_p(a_n;p^{-s})\,.

만약 ''a''_''n''이 디리클레 문자라면, 해당 디리클레 급수 생성 함수는 디리클레 L-함수라고 불린다.

3. 성질

생성함수는 함수로 간주되지 않으며, "변수"는 미정 변수로 남는다. 생성함수는 수렴할 필요가 없으며, 산술 연산, 미분, 다른 생성함수와의 합성(대입)이 가능하다. 그러나 모든 표현식이 형식적 급수를 나타내는 표현식으로 의미가 있는 것은 아니다.^[2]

3. 1. 연산

일반 생성 함수의 곱은 수열의 이산 합성곱 (코시 곱)을 생성한다.^[16] 예를 들어, 일반 생성 함수

G(a_n; x)

를 갖는 수열의 누적 합 수열 (약간 더 일반적인 오일러-매클로린 공식과 비교)

(a_0, a_0 + a_1, a_0 + a_1 + a_2, \ldots)

은 생성 함수

G(a_n; x) \cdot \frac{1}{1-x}

를 갖는다. 왜냐하면

\frac{1}{1-x}

는 수열 (1, 1, ...)의 일반 생성 함수이기 때문이다.

정수

m \ge 1

에 대해, 변형된 생성 함수에 대한 다음 두 가지 유사한 항등식이 있으며, 이는 각각

\langle g_{n-m} \rangle

및

\langle g_{n+m} \rangle

의 이동 수열 변형을 열거한다.

\begin{align}& z^m G(z) = \sum_{n = m}^\infty g_{n-m} z^n \\[4px]& \frac{G(z) - g_0 - g_1 z - \cdots - g_{m-1} z^{m-1}}{z^m} = \sum_{n = 0}^\infty g_{n+m} z^n.\end{align}

다음은 생성 함수의 미분과 적분에 대한 거듭제곱 급수 전개식이다.

\begin{align}G'(z) & = \sum_{n = 0}^\infty (n+1) g_{n+1} z^n \\[4px]z \cdot G'(z) & = \sum_{n = 0}^\infty n g_{n} z^n \\[4px]\int_0^z G(t) \, dt & = \sum_{n = 1}^\infty \frac{g_{n-1}}{n} z^n.\end{align}

두 번째 식의 미분-곱셈 연산을

k

번 반복하여 수열에

n^k

를 곱할 수 있지만, 이 경우 미분과 곱셈을 번갈아 가며 수행해야 한다. 대신

k

번의 연속적인 미분을 수행하면,

k

번째 폴링 팩토리얼:

z^k G^{(k)}(z) = \sum_{n = 0}^\infty n^\underline{k} g_n z^n = \sum_{n = 0}^\infty n (n-1) \dotsb (n-k+1) g_n z^n \quad\text{for all } k \in \mathbb{N}.

제2종 스털링 수를 사용하면, 이를 다음과 같이

n^k

를 곱하는 또 다른 공식으로 변환할 수 있다 ( 생성 함수 변환의 주요 내용을 참조):

\sum_{j=0}^k \begin{Bmatrix} k \\ j \end{Bmatrix} z^j F^{(j)}(z) = \sum_{n = 0}^\infty n^k f_n z^n \quad\text{for all } k \in \mathbb{N}.

이 절에서는 일반 생성 함수

F(z)

가 주어졌을 때 수열

\{f_{an+b}\}

를 열거하는 생성 함수에 대한 공식을 제공하며, 여기서

a \ge 2

,

0 \le b < a

이며,

a

와

b

는 정수이다 (변환에 관한 주요 문서 참조).

a = 2

의 경우, 이것은 단순히 함수를 짝수 및 홀수 부분 (즉, 짝수 및 홀수 거듭제곱)으로 분해하는 익숙한 방법이다.

\begin{align}\sum_{n = 0}^\infty f_{2n} z^{2n} &= \frac{F(z) + F(-z)}{2} \\[4px]\sum_{n = 0}^\infty f_{2n+1} z^{2n+1} &= \frac{F(z) - F(-z)}{2}.\end{align}

더 일반적으로,

a \ge 3

이고

\omega_a = \exp \frac{2\pi i}{a}

가

a

번째 원시 단위근을 나타낸다고 가정하자. 그러면 이산 푸리에 변환의 응용으로 다음 공식을 얻는다.^[15]

\sum_{n = 0}^\infty f_{an+b} z^{an+b} = \frac{1}{a} \sum_{m=0}^{a-1} \omega_a^{-mb} F\left(\omega_a^m z\right).

정수

m \ge 1

에 대해, 다소 "역전된" 바닥 함수를 제공하는 또 다른 유용한 공식은 - 효과적으로 각 계수를

m

번 반복 - 다음 항등식에 의해 생성된다.^[16]

\sum_{n = 0}^\infty f_{\left\lfloor \frac{n}{m} \right\rfloor} z^n = \frac{1-z^m}{1-z} F(z^m) = \left(1 + z + \cdots + z^{m-2} + z^{m-1}\right) F(z^m).

3. 2. P-재귀 수열과 홀로노믹 생성함수

형식적 멱급수(또는 함수)가 다음 형식의 선형 미분 방정식을 만족하면 '''홀로노믹'''하다고 한다.^[17]

:

c_0(z) F^{(r)}(z) + c_1(z) F^{(r-1)}(z) + \cdots + c_r(z) F(z) = 0

여기서 계수는 유리 함수체

\mathbb{C}(z)

에 속한다.

이전 방정식에서 분모를 제거하면, 함수 가

z

에 대한 다항식이라고 가정할 수 있다. 따라서 생성 함수가 홀로노믹하다는 것은 생성 함수의 계수가 다음 형식의 '''P-재귀'''를 만족하는 경우와 동등하다.

:

\widehat{c}_s(n) f_{n+s} + \widehat{c}_{s-1}(n) f_{n+s-1} + \cdots + \widehat{c}_0(n) f_n = 0

충분히 큰 모든

n

에 대해, 여기서

\widehat{c}_{i}(n)

는

n

에 대한 고정된 유한 차수 다항식이다. 즉, 수열이 ''P-재귀적''이고 홀로노믹 생성 함수를 갖는다는 속성은 동등하다. 홀로노믹 함수는 생성 함수에 대한 Hadamard 곱 연산에 대해 닫혀 있다.

홀로노믹 생성 함수를 갖는 P-재귀 수열의 예로는

f_n \coloneqq \frac{1}{n+1} \binom{2n}{n}

및

f_n \coloneqq \frac{2^n}{n^2 + 1}

이 있으며,

\sqrt{n}

및

\log n

과 같은 수열은 해당 생성 함수의 특이성으로 인해 P-재귀적이지 ''않다''. 마찬가지로

\tan z

,

\sec z

, Γ(z)와 같이 무한히 많은 특이점을 갖는 함수는 홀로노믹 함수가 ''아니다''.^[18]

3. 3. 이산 시간 푸리에 변환과의 관계

절대 수렴하는 급수의 경우,

:

G \left ( a_n; e^{-i \omega} \right) = \sum_{n=0}^\infty a_n e^{-i \omega n}

는 수열

a_0, a_1, \dots

의 이산 시간 푸리에 변환이다.

3. 4. 수열의 점근적 성장

미적분학에서 거듭제곱 급수의 계수의 성장률을 사용하여 수렴반경을 추론할 수 있다. 반대로, 생성 함수의 수렴 반경을 사용하여 기본 수열의 점근적 성장을 추론할 수도 있다.

예를 들어, 유한한 수렴 반경 $r$을 갖는 일반 생성 함수 $G(a_n; x)$가 다음과 같이 표현될 수 있다면,

G(a_n; x) = \frac{A(x) + B(x) \left (1- \frac{x}{r} \right )^{-\beta}}{x^\alpha}

여기서 $A(x)$와 $B(x)$는 각각 $r$보다 큰 수렴 반경을 갖는 해석적 함수(또는 전체 함수)이고, $B(r) \neq 0$이면,

a_n \sim \frac{B(r)}{r^\alpha \Gamma(\beta)} \, n^{\beta-1}\left(\frac{1}{r}\right)^n \sim \frac{B(r)}{r^{\alpha}} \binom{n+\beta-1}{n}\left(\frac{1}{r}\right)^n = \frac{B(r)}{r^\alpha} \left(\!\!\binom{\beta}{n}\!\!\right)\left(\frac{1}{r}\right)^n\,,

감마 함수, 이항 계수, 또는 멀티셋 계수를 사용한다.

이 접근 방식을 반복하여 $a_n$에 대한 점근 급수의 여러 항을 생성할 수 있다.

지수 생성 함수에 대해서도 유사한 점근적 분석이 가능하다. 일반적으로, 한 수열의 생성 함수에서 다른 수열의 생성 함수를 뺀 생성 함수의 수렴 반경이 개별 생성 함수의 수렴 반경보다 크면 두 수열은 동일한 점근적 성장을 갖는다.

제곱 수열의 일반 생성 함수는 다음과 같다.

G(n^2; x) = \frac{x(x+1)}{(1-x)^3}.

$r = 1$, $\alpha = -1$, $\beta = 3$, $A(x) = 0$, 그리고 $B(x) = x + 1$을 사용하여 제곱이 예상대로 제곱처럼 증가하는 것을 확인할 수 있다.

a_n \sim \frac{B(r)}{r^\alpha \Gamma(\beta)} \, n^{\beta-1} \left (\frac{1}{r} \right)^n = \frac{1+1}{1^{-1}\,\Gamma(3)}\,n^{3-1} \left(\frac1 1\right)^n = n^2.

카탈랑 수의 일반 생성 함수는 다음과 같다.

G(C_n; x) = \frac{1-\sqrt{1-4x}}{2x}.

$r = \frac{1}{4}$, $\alpha = 1$, $\beta = -\frac{1}{2}$, $A(x) = \frac{1}{2}$, 그리고 $B(x) = -\frac{1}{2}$를 사용하면 카탈랑 수에 대해 다음과 같이 결론을 내릴 수 있다.

C_n \sim \frac{B(r)}{r^\alpha \Gamma(\beta)} \, n^{\beta-1} \left(\frac{1}{r} \right)^n = \frac{-\frac12}{\left(\frac14\right)^1 \Gamma\left(-\frac12\right)} \, n^{-\frac12-1} \left(\frac{1}{\,\frac14\,}\right)^n = \frac{4^n}{n^\frac32 \sqrt\pi}.

4. 종류

생성 함수는 수열의 정보를 담고 있는 형식적인 멱급수이다. 일반적인 급수와는 달리, 생성 함수는 수렴할 필요가 없으며, 변수는 미정 변수로 취급된다. 즉, 생성 함수는 함수로 간주되지 않는다.

일반적으로 '생성 함수'라고 하면, 이는 대개 일반 생성 함수를 의미한다. 수열 $a_n$ 의 일반 생성 함수는 다음과 같다.

: $G(a_n;x)=\sum_{n=0}^\infty a_n x^n.$

만약 $a_n$ 이 이산 확률 변수의 확률 질량 함수라면, 이의 일반 생성 함수는 확률 생성 함수라고 불린다.

수열 $a_n$ 의 지수 생성 함수는 다음과 같다.

: $\operatorname{EG}(a_n;x)=\sum_{n=0}^\infty a_n \frac{x^n}{n!}.$

지수 생성 함수는 라벨이 지정된 객체를 포함하는 조합적 열거 문제에 대해 일반 생성 함수보다 일반적으로 더 편리하다.^[3] 또한 선형 점화 관계를 미분 방정식으로 변환하는 데 유용하다. 예를 들어 피보나치 수열의 지수 생성 함수는 미분 방정식 $\operatorname{EF}''(x) = \operatorname{EF}'(x) + \operatorname{EF}(x)$ 를 만족한다.

수열 $a_n$ 의 푸아송 생성 함수는 다음과 같다.

: $\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$ 의 람베르트 급수는 다음과 같다.

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

람베르트 급수의 계수 $b_n$ 은 약수 합을 통해 $a_n$ 과 관련된다. 즉, $b_n = \sum_{d|n} a_d$ 이다.

수열 $a_n$ 의 벨 급수는 다음과 같이 표현된다.^[5]

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

형식적 디리클레 급수는 엄밀한 형식적 멱급수는 아니지만 종종 생성 함수로 분류된다. 수열 $a_n$ 의 디리클레 급수 생성 함수는 다음과 같다.^[6]

: $\operatorname{DG}(a_n;s)=\sum _{n=1}^\infty \frac{a_n}{n^s}.$

디리클레 급수 생성 함수는 $a_n$ 이 곱셈 함수일 때 특히 유용하며, 이 경우 오일러 곱 표현^[7]을 갖는다. 만약 $a_n$ 이 디리클레 문자라면, 해당 디리클레 급수 생성 함수는 디리클레 L-함수라고 불린다.

이 외에도, 이중 지수 생성 함수, 생성 함수의 Hadamard 곱과 대각 생성 함수 등이 존재한다.^[3]

4. 1. 유리 함수

수열의 일반 생성 함수는 해당 수열이 상수 계수를 갖는 선형 점화식인 경우에만 유리 함수(두 유한 차수 다항식의 비율)로 표현될 수 있다.^[13] 이는 위에 나온 예시들을 일반화한 것이다. 반대로, 다항식의 분수로 생성된 모든 수열은 상수 계수를 갖는 선형 점화식을 만족한다. 이때 계수들은 분수 분모 다항식의 계수와 동일하다. 이러한 점을 통해 상수 계수를 갖는 선형 유한 차분 방정식으로 정의된 수열의 생성 함수를 쉽게 구할 수 있으며, 이 생성 함수의 계수에 대한 명시적 폐쇄형 공식을 쉽게 구할 수 있다. 대표적인 예로 생성 함수 기법을 통해 피보나치 수에 대한 비네 공식을 유도하는 것이 있다.

또한 유리 생성 함수는 다음과 같은 형태의 준다항식(quasi-polynomial) 수열을 열거하는 생성 함수에 해당한다.^[13]

:

f_n = p_1(n) \rho_1^n + \cdots + p_\ell(n) \rho_\ell^n,

여기서 역수 근

\rho_i \isin \mathbb{C}

는 고정된 스칼라이고,

p_i(n)

은 모든

1 \le i \le \ell

에 대한 다항식이다.

일반적으로 Hadamard 곱은 유리 함수에서 유리 생성 함수를 만든다. 마찬가지로,

:

F(s, t) := \sum_{m,n \geq 0} f(m, n) w^m z^n

가 이변수 유리 생성 함수이면, 해당 대각 생성 함수는 다음과 같다.

:

\operatorname{diag}(F) := \sum_{n = 0}^\infty f(n, n) z^n,

이것은 대수적이다. 예를 들어,^[14]

:

F(s, t) := \sum_{i,j \geq 0} \binom{i+j}{i} s^i t^j = \frac{1}{1-s-t},

이 생성 함수의 대각 계수 생성 함수는 잘 알려진 OGF 공식에 의해 다음과 같이 주어진다.

:

\operatorname{diag}(F) = \sum_{n = 0}^\infty \binom{2n}{n} z^n = \frac{1}{\sqrt{1-4z}}.

이 결과는 코시 적분 공식 또는 윤곽선 적분을 사용하여 복소 잔류를 취하거나 두 변수의 형식적 멱급수를 직접 조작하는 등 여러 가지 방법으로 계산된다.

수열의 일반형 생성함수가 유리식 (두 다항식의 비)으로 표현되기 위한 필요충분 조건은, 해당 수열이 선형 점화식을 갖는 것이다.

4. 2. 다항식 수열 생성함수

생성 함수의 개념은 다른 객체의 수열로 확장될 수 있다. 예를 들어, 이항 형식의 다항식 수열은 다음 식으로 생성된다.^[3]

:

e^{xf(t)}=\sum_{n=0}^\infty \frac{p_n(x)}{n!} t^n

여기서 는 다항식 수열이고 는 특정 형태의 함수이다. 셰퍼 수열도 비슷한 방식으로 생성된다.

더 복잡한 생성 함수로 생성되는 다항식 수열의 예는 다음과 같다.

아펠 다항식
체비쇼프 다항식
차분 다항식
일반화된 아펠 다항식
Q-차분 다항식

4. 3. 기타 생성함수

이중 지수 생성 함수, 생성 함수의 Hadamard 곱과 대각 생성 함수 등이 존재한다.^[3] 컨볼루션 다항식 수열은 특수한 생성함수를 통해 정의된다.^[9]

크누스의 논문 "''Convolution Polynomials''(생성함수)"^[9]는 다음과 같은 형태의 특수한 생성 함수를 통해 일반화된 부류의 ''convolution polynomial(컨볼루션 다항식)'' 수열을 정의한다.

:

F(z)^x = \exp\bigl(x \log F(z)\bigr) = \sum_{n = 0}^\infty f_n(x) z^n,

여기서 는 을 만족하는 멱급수 전개를 갖는 어떤 해석 함수이다.

수열 가 이고 모든 , 에 대해 다음 컨볼루션 조건을 만족하면 이 수열을 ''컨볼루션 족''이라고 한다. 그리고 모든 :

:

f_n(x+y) = f_n(x) f_0(y) + f_{n-1}(x) f_1(y) + \cdots + f_1(x) f_{n-1}(y) + f_0(x) f_n(y).

영이 아닌 컨볼루션 족에 대해, 이 정의는 수열이 위에 주어진 첫 번째 형태의 일반 생성 함수를 갖는 것과 동일하다는 것을 알 수 있다.

위에 표기된 컨볼루션 다항식 수열은 다음과 같은 특징을 갖는다.

수열 는 이항 형식이다.
수열의 특수한 값에는 및 이 포함되며,
임의의 (고정된) $x, y, t \isin \mathbb{C}$ 에 대해, 이러한 다항식은 다음과 같은 형태의 컨볼루션 공식을 만족한다.

:

\begin{align}f_n(x+y) & = \sum_{k=0}^n f_k(x) f_{n-k}(y) \\f_n(2x) & = \sum_{k=0}^n f_k(x) f_{n-k}(x) \\xn f_n(x+y) & = (x+y) \sum_{k=0}^n k f_k(x) f_{n-k}(y) \\\frac{(x+y) f_n(x+y+tn)}{x+y+tn} & = \sum_{k=0}^n \frac{x f_k(x+tk)}{x+tk} \frac{y f_{n-k}(y+t(n-k))}{y+t(n-k)}.\end{align}

고정된 영이 아닌 매개변수

t \isin \mathbb{C}

에 대해, 이러한 컨볼루션 다항식 수열에 대한 수정된 생성 함수는 다음과 같다.

:

\frac{z F_n(x+tn)}{(x+tn)} = \left[z^n\right] \mathcal{F}_t(z)^x,

여기서 는 형태의 함수 방정식에 의해 암묵적으로 정의된다. 또한, 참조에 나와 있는 것처럼 행렬 방식을 사용하여 두 개의 컨볼루션 다항식 수열 와 와 각 수열에 해당하는 생성 함수 와 가 주어지면, 임의의 에 대해 다음 항등식이 성립함을 증명할 수 있다.

:

\left[z^n\right] \left(G(z) F\left(z G(z)^t\right)\right)^x = \sum_{k=0}^n F_k(x) G_{n-k}(x+tk).

컨볼루션 다항식 수열의 예로는 ''이항 멱급수'', , 소위 ''트리 다항식'', 벨 수, , 라게르 다항식, 및 스털링 컨볼루션 다항식이 있다.

더 복잡한 생성 함수로 생성되는 다항식 열로 다음과 같은 것들이 있다.

Appell polynomials|아펠 다항식^영어
체비쇼프 다항식
게겐바우어 다항식
차분 다항식
일반화 아펠 다항식
Q-difference polynomial|q-차분 다항식^영어

5. 표현

형식적 멱급수는 수렴할 필요가 없다는 점에서 일반적인 급수와 다르다. 생성 함수는 실제로 함수로 간주되지 않으며, "변수"는 미정 변수로 남는다. 따라서 생성 함수는 정의역에서 공역으로의 사상이라는 형식적 의미의 함수가 아니다.

x에 관한 식은 산술 연산, x에 대한 미분, 다른 생성 함수와의 합성(대입)을 포함할 수 있으며, 그 결과는 x의 함수처럼 보인다. 실제로, 닫힌 형식의 식은 (충분히 작은) 구체적인 x 값을 평가할 수 있으며, 형식적 급수를 급수 전개로 갖는 함수로 해석될 수 있다. 그러나 형식적 급수는 x에 0이 아닌 숫자 값을 대입할 때 수렴하는 급수를 제공할 필요가 없으므로 이러한 해석이 가능할 필요는 없다.

함수로서 의미가 있는 모든 표현식이 형식적 급수를 나타내는 표현식으로 의미가 있는 것은 아니다. 예를 들어, x의 음수 및 분수 거듭제곱은 해당 형식적 멱급수가 없는 함수의 예이다.

일반적으로 '생성 함수'라는 용어를 특별한 수식어 없이 사용할 경우, 이는 대개 일반 생성 함수를 의미한다. 수열 $a_n$ 의 ''일반 생성 함수''는 다음과 같다.

$G(a_n;x)=\sum_{n=0}^\infty a_n x^n.$

만약 $a_n$ 이 이산 확률 변수의 확률 질량 함수라면, 이의 일반 생성 함수는 확률 생성 함수라고 불린다.

수열 $a_n$ 의 ''지수 생성 함수''는 다음과 같다.

$\operatorname{EG}(a_n;x)=\sum_{n=0}^\infty a_n \frac{x^n}{n!}.$

지수 생성 함수는 라벨이 지정된 객체를 포함하는 조합적 열거 문제에 대해 일반 생성 함수보다 일반적으로 더 편리하다.^[3] 지수 생성 함수의 또 다른 장점은 선형 점화 관계를 미분 방정식 영역으로 변환하는 데 유용하다는 것이다.

수열 $a_n$ 의 ''푸아송 생성 함수''는 다음과 같다.

$\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$ 의 ''람베르트 급수''는 다음과 같다.

$\operatorname{LG}(a_n;x)=\sum _{n=1}^\infty a_n \frac{x^n}{1-x^n}.$

람베르트 급수에서 지표 n은 0이 아닌 1부터 시작한다. 정수 $n \ge 1$ 에 대한 거듭제곱 급수 전개에서 람베르트 급수 계수

$b_n := [x^n] \operatorname{LG}(a_n;x)$ 는 약수 합에 의해 관련된다.

$b_n = \sum_{d|n} a_d.$

주요 문서는 정수론에서 특수한 산술 함수와 관련된 몇 가지 예를 제공한다.

수열 $a_n$ 의 벨 급수는 미지수 x와 소수 p 모두를 사용하여 다음과 같이 표현된다:^[5]

$\operatorname{BG}_p(a_n;x) = \sum_{n=0}^\infty a_{p^n}x^n.$

형식적 디리클레 급수는 엄밀한 형식적 멱급수는 아니지만 종종 생성 함수로 분류된다. 수열 $a_n$ 의 ''디리클레 급수 생성 함수''는 다음과 같다:^[6]

$\operatorname{DG}(a_n;s)=\sum _{n=1}^\infty \frac{a_n}{n^s}.$

디리클레 급수 생성 함수는 $a_n$ 이 곱셈 함수일 때 특히 유용하며, 이 경우 함수의 벨 급수를 사용하여 오일러 곱 표현^[7]을 갖는다.

$\operatorname{DG}(a_n;s)=\prod_{p} \operatorname{BG}_p(a_n;p^{-s})\,.$

만약 $a_n$ 이 디리클레 문자라면, 해당 디리클레 급수 생성 함수는 디리클레 L-함수라고 불린다. 또한 람베르트 급수 전개의 계수 쌍과 DGF 사이의 관계도 있다. 즉, 다음을 증명할 수 있다.

$[x^n] \operatorname{LG}(a_n; x) = b_n$ 은 다음일 때만 참이다.

$\operatorname{DG}(a_n;s) \zeta(s) = \operatorname{DG}(b_n;s),$

여기서 $\zeta(s)$ 는 리만 제타 함수이다.^[8]

생성 함수의 아이디어는 다른 객체의 수열로 확장될 수 있다. 일반화된 아펠 다항식 문서에서 더 자세한 내용을 확인할 수 있다.

더 복잡한 생성 함수로 생성된 다항식 수열의 예는 다음과 같다.

아펠 다항식
체비쇼프 다항식
차분 다항식
일반화된 아펠 다항식
q-차분 다항식

다른 더 복잡한 생성 함수로 생성된 다른 수열에는 다음이 포함된다.

이중 지수 생성 함수
생성 함수의 Hadamard 곱과 대각 생성 함수, 그리고 해당 적분 변환

크누스의 논문 "''Convolution Polynomials''(생성함수)"^[9]는 다음과 같은 형태의 특수한 생성 함수를 통해 일반화된 부류의 ''convolution polynomial(컨볼루션 다항식)'' 수열을 정의한다.

F(z)^x = \exp\bigl(x \log F(z)\bigr) = \sum_{n = 0}^\infty f_n(x) z^n,

여기서 F는

F(0)=1

을 만족하는 멱급수 전개를 갖는 어떤 해석 함수이다.

수열

f_0, f_1, f_2, \ldots

가

\deg f_n \le n

이고 모든 x, y에 대해 다음 컨볼루션 조건을 만족하면 이 수열을 ''컨볼루션 족''이라고 한다. 그리고 모든

n \ge 0

:

f_n(x+y) = f_n(x) f_0(y) + f_{n-1}(x) f_1(y) + \cdots + f_1(x) f_{n-1}(y) + f_0(x) f_n(y).

영이 아닌 컨볼루션 족에 대해, 이 정의는 수열이 위에 주어진 첫 번째 형태의 일반 생성 함수를 갖는 것과 동일하다는 것을 알 수 있다.

위에 표기된 컨볼루션 다항식 수열은 다음과 같은 특징을 갖는다.

수열 $n! \cdot f_n(x)$ 는 이항 형식이다.
수열의 특수한 값에는 $f_n(1) = [z^n]F(z)$ 및 $f_n(0) = \delta_{n,0}$ 이 포함된다.
임의의 (고정된) $x, y, t \isin \mathbb{C}$ 에 대해, 이러한 다항식은 다음과 같은 형태의 컨볼루션 공식을 만족한다.

\begin{align}f_n(x+y) & = \sum_{k=0}^n f_k(x) f_{n-k}(y) \\f_n(2x) & = \sum_{k=0}^n f_k(x) f_{n-k}(x) \\xn f_n(x+y) & = (x+y) \sum_{k=0}^n k f_k(x) f_{n-k}(y) \\\frac{(x+y) f_n(x+y+tn)}{x+y+tn} & = \sum_{k=0}^n \frac{x f_k(x+tk)}{x+tk} \frac{y f_{n-k}(y+t(n-k))}{y+t(n-k)}.\end{align}

컨볼루션 다항식 수열의 예로는 ''이항 멱급수'',

\mathcal{B}_t(z) = 1 + z\mathcal{B}_t(z)^t

, 소위 ''트리 다항식'', 벨 수,

B(n)

, 라게르 다항식, 및 스털링 컨볼루션 다항식이 있다.

5. 1. 연분수 표현

일반화된 연분수의 한 종류인 야코비 형식(J-분수)과 슈틸체스 형식(S-분수)은 특정 수열의 생성함수를 표현하는 또 다른 방법이다.^[21] 이 방법은 h번째 유리수 수렴자가 2h 차수 정확도를 가지는 거듭제곱 급수로 나타내어지며, 여러 특수한 일변수 및 이변수 수열에 대한 생성 함수(일반적으로 발산)를 표현한다.

야코비 형식 연분수(J-분수)는 다음 방정식과 같이 전개된다.

\begin{align}J^{[\infty]}(z) & = \cfrac{1}{1-c_1 z-\cfrac{\text{ab}_2 z^2}{1-c_2 z-\cfrac{\text{ab}_3 z^2}{\ddots}}} \\[4px]& = 1 + c_1 z + \left(\text{ab}_2+c_1^2\right) z^2 + \left(2 \text{ab}_2 c_1+c_1^3 + \text{ab}_2 c_2\right) z^3 + \cdots\end{align}

여기서 및 는 특정 응용 프로그램에 따라 달라지는 구성 요소 수열이고, 는 형식 변수이다.

z^n

의 계수 는 다음 행렬 방정식의 해에 해당한다.

\begin{bmatrix}k_{0,1} & k_{1,1} & 0 & 0 & \cdots \\ k_{0,2} & k_{1,2} & k_{2,2} & 0 & \cdots \\ k_{0,3} & k_{1,3} & k_{2,3} & k_{3,3} & \cdots \\ \vdots & \vdots & \vdots & \vdots \end{bmatrix} =\begin{bmatrix}k_{0,0} & 0 & 0 & 0 & \cdots \\ k_{0,1} & k_{1,1} & 0 & 0 & \cdots \\ k_{0,2} & k_{1,2} & k_{2,2} & 0 & \cdots \\ \vdots & \vdots & \vdots & \vdots \end{bmatrix} \cdot\begin{bmatrix}c_1 & 1 & 0 & 0 & \cdots \\ \text{ab}_2 & c_2 & 1 & 0 & \cdots \\ 0 & \text{ab}_3 & c_3 & 1 & \cdots \\ \vdots & \vdots & \vdots & \vdots \end{bmatrix},

여기서 , (), ()이며, 모든 정수 에 대해 다음 덧셈 공식이 성립한다.

j_{p+q} = k_{0,p} \cdot k_{0,q} + \sum_{i=1}^{\min(p, q)} \text{ab}_2 \cdots \text{ab}_{i+1} \times k_{i,p} \cdot k_{i,q}.

무한 J-분수 의 h차 수렴 함수는 다음과 같이 정의된다.

\operatorname{Conv}_h(z) := \frac{P_h(z)}{Q_h(z)} = j_0 + j_1 z + \cdots + j_{2h-1} z^{2h-1} + \sum_{n = 2h}^\infty \widetilde{j}_{h,n} z^n

여기서 와 는 재귀적으로 정의되는 수열이다.

\begin{align}P_h(z) & = (1-c_h z) P_{h-1}(z) - \text{ab}_h z^2 P_{h-2}(z) + \delta_{h,1} \\Q_h(z) & = (1-c_h z) Q_{h-1}(z) - \text{ab}_h z^2 Q_{h-2}(z) + (1-c_1 z) \delta_{h,1} + \delta_{0,1}.\end{align}

수렴 함수 의 유리성은 수열 이 만족하는 추가적인 유한 차분 방정식과 합동성을 의미하며, 에 대해 이면 다음과 같은 합동성을 갖는다.

j_n \equiv [z^n] \operatorname{Conv}_h(z) \pmod h,

다음 표는 , , 등 여러 특수한 경우의 수열에 대해, 계산적으로 발견되고 증명된^[22] 닫힌 형식의 공식을 제공한다. 여기서 이고, 매개변수

R, \alpha \isin \mathbb{Z}^+

및 는 미지수이며, 이러한 수열은 -Pochhammer 기호, Pochhammer 기호, 및 이항 계수로 정의된다.

$j_n$	$c_1$	$c_i (i \geq 2)$	$\mathrm{ab}_i (i \geq 2)$
$q^{n^2}$	$q$	$q^{2h-3}\left(q^{2h}+q^{2h-2}-1\right)$	$q^{6h-10}\left(q^{2h-2}-1\right)$
$(a; q)_n$	$1-a$	$q^{h-1} - a q^{h-2} \left(q^{h} + q^{h-1} - 1\right)$	$a q^{2h-4} \left(a q^{h-2}-1\right)\left(q^{h-1}-1\right)$
$\left(z q^{-n}; q\right)_n$	$\frac{q-z}{q}$	$\frac{q^h - z - qz + q^h z}{q^{2h-1}}$	$\frac{\left(q^{h-1}-1\right) \left(q^{h-1}-z\right) \cdot z}{q^{4h-5}}$
$\frac{(a; q)_n}{(b; q)_n}$	$\frac{1-a}{1-b}$	$\frac{q^{i-2}\left(q+ab q^{2i-3}+a(1-q^{i-1}-q^i)+b(q^{i}-q-1)\right)}{\left(1-bq^{2i-4}\right)\left(1-bq^{2i-2}\right)}$	$\frac{q^{2i-4}\left(1-bq^{i-3}\right)\left(1-aq^{i-2}\right)\left(a-bq^{i-2}\right)\left(1-q^{i-1}\right)}{\left(1-bq^{2i-5}\right)\left(1-bq^{2i-4}\right)^2\left(1-bq^{2i-3}\right)}$
$\alpha^n \cdot \left(\frac{R}{\alpha}\right)_n$	$R$	$R+2\alpha (i-1)$	$(i-1)\alpha\bigl(R+(i-2)\alpha\bigr)$
$(-1)^n \binom{x}{n}$	$-x$	$-\frac{(x+2(i-1)^2)}{(2i-1)(2i-3)}$	$\begin{cases}-\dfrac{(x-i+2)(x+i-1)}{4 \cdot (2i-3)^2} & \text{for }i \geq 3; \\[4px] -\frac{1}{2}x(x+1) & \text{for }i = 2. \end{cases}$
$(-1)^n \binom{x+n}{n}$	$-(x+1)$	$\frac{\bigl(x-2i(i-2)-1\bigr)}{(2i-1)(2i-3)}$	$\begin{cases}-\dfrac{(x-i+2)(x+i-1)}{4 \cdot (2i-3)^2} & \text{for }i \geq 3; \\[4px] -\frac{1}{2}x(x+1) & \text{for }i = 2. \end{cases}$

야코비 형식 J-분수로 정의된 급수의 수렴 반경은, 일반적으로 해당 수열의 일반 생성 함수의 멱급수 전개의 수렴 반경과 다르다.

6. 예시

생성함수는 1730년 아브라함 드 무아브르에 의해 처음 소개되어 일반적인 선형 점화식 문제 해결에 사용되었다.^[2] 조지 폴리아는 그의 저서 ''수학과 그럴듯한 추론''에서 라플라스가 "생성함수"라는 이름을 붙였지만, 오일러는 라플라스 이전부터 이 기법을 명칭 없이 사용했다고 언급했다.^[2] 오일러는 이 수학적 도구를 조합론 및 정수론의 여러 문제에 적용했다.

6. 1. 간단한 수열

Polynomials|다항식^영어은 유한 수열 또는 특정 지점 이후에 0이 되는 수열에 해당하는 일반 생성함수의 특별한 경우이다. 이는 많은 유한 수열이 생성함수로 유용하게 해석될 수 있다는 점에서 중요하다. 예를 들어, 푸앵카레 다항식 등이 있다.

기본적인 생성함수는 1, 1, 1, ... 인 상수 수열의 경우로, 이에 대한 일반 생성함수는 등비 급수이다.

:

\sum_{n=0}^\infty x^n= \frac{1}{1-x}.

초기 생성함수를 제곱하거나, 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은 이항 계수

\binom{n+2}2

이므로,

:

\sum_{n=0}^\infty\binom{n+2}2 x^n= \frac{1}{(1-x)^3}.

이항 계수 생성 수열의 선형 조합으로 제곱수 수열 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}.

6. 2. 제곱수

제곱수 수열의 일반 생성 함수는 다음과 같이 표현된다.

:

G(n^2;x) = \sum_{n=0}^\infty n^2x^n = \frac{x(x+1)}{(1-x)^3}

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

:

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

제곱수 수열의 생성 함수는 다음과 같다.

생성 함수 유형	방정식
일반 생성 함수	$G(n^2;x)=\sum_{n=0}^\infty n^2x^n = \frac{x(x+1)}{(1-x)^3}$
지수 생성 함수	$\operatorname{EG}(n^2;x)=\sum _{n=0}^\infty \frac{n^2x^n}{n!}=x(x+1)e^x$
벨 급수	$\operatorname{BG}_p\left(n^2;x\right)=\sum_{n=0}^\infty \left(p^{n}\right)^2x^n=\frac{1}{1-p^2x}$
디리클레 급수	$\operatorname{DG}\left(n^2;s\right)=\sum_{n=1}^\infty \frac{n^2}{n^s}=\zeta(s-2)$

여기서 $\zeta(s)$ 는 리만 제타 함수이다.

6. 3. 카탈랑 수

카탈랑 수의 일반 생성 함수는 다음과 같다.

:

G(C_n; x) = \frac{1-\sqrt{1-4x}}{2x}.

카탈랑 수의 생성 함수는 다음 공식을 만족한다.

:

C(z) = \frac{1-\sqrt{1-4z}}{2z} = \sum_{n = 0}^\infty \frac{1}{n+1}\binom{2n}{n} z^n\,.

6. 4. 다변수 생성함수

여러 변수의 생성 함수는 여러 개의 인덱스를 가진 배열로 일반화될 수 있다. 이러한 비다항식 이중 합의 예는 다변량 생성 함수 또는 슈퍼 생성 함수라고 한다. 두 변수의 경우, 이를 종종 이변량 생성 함수라고 한다.

2차원 배열 (여기서 과 은 자연수)의 일반 생성 함수는 다음과 같다.

:

G(a_{m,n};x,y)=\sum_{m,n=0}^\infty a_{m,n} x^m y^n.

예를 들어, 이 고정된 에 대한 이항 계수의 일반 생성 함수이므로, 모든 와 에 대한 이항 계수 를 생성하는 2변수 생성 함수를 생각해 볼 수 있다. 자체를 의 수열로 간주하고, 이러한 수열 값을 계수로 갖는 에서 생성 함수를 찾으면, 의 생성 함수는 다음과 같다.

:

\frac{1}{1-ay},

따라서 이항 계수의 생성 함수는 다음과 같다.

:

\sum_{n,k} \binom{n}{k} x^k y^n = \frac{1}{1-y-xy}.

이러한 예로는 다음의 이항 계수, 스털링 수, 오일러 수에 대한 두 변수 생성 함수가 있으며, 여기서 와 는 두 변수를 나타낸다.^[19]

:

\begin{align}e^{z+wz} & = \sum_{m,n \geq 0} \binom{n}{m} w^m \frac{z^n}{n!} \\[4px]e^{w(e^z-1)} & = \sum_{m,n \geq 0} \begin{Bmatrix} n \\ m \end{Bmatrix} w^m \frac{z^n}{n!} \\[4px]\frac{1}{(1-z)^w} & = \sum_{m,n \geq 0} \begin{bmatrix} n \\ m \end{bmatrix} w^m \frac{z^n}{n!} \\[4px]\frac{1-w}{e^{(w-1)z}-w} & = \sum_{m,n \geq 0} \left\langle\begin{matrix} n \\ m \end{matrix} \right\rangle w^m \frac{z^n}{n!} \\[4px]\frac{e^w-e^z}{w e^z-z e^w} &= \sum_{m,n \geq 0} \left\langle\begin{matrix} m+n+1 \\ m \end{matrix} \right\rangle \frac{w^m z^n}{(m+n+1)!}.\end{align}

다변수 생성 함수는 지정된 행 및 열 합계를 갖는 음이 아닌 정수의 분할표 수를 계산할 때 사용될 수 있다. 표에 개의 행과 개의 열이 있고, 행 합계는 , 열 합계는 라고 할 때, I. J. 굿(I. J. Good)에 따르면^[20] 이러한 테이블의 수는 다음의 계수이다.

:

x_1^{t_1}\cdots x_r^{t_r}y_1^{s_1}\cdots y_c^{s_c}

다음 식에서:

:

\prod_{i=1}^{r}\prod_{j=1}^c\frac{1}{1-x_iy_j}.

7. 응용

생성함수는 다음과 같은 용도로 사용된다.^[2]

점화 관계식으로 주어진 수열의 일반항을 찾는다. 예를 들어 피보나치 수의 일반항을 생성함수를 통해 구할 수 있다.
수열의 점화 관계를 찾는다. 생성 함수의 형태는 점화식을 암시할 수 있다.
수열 간의 관계를 찾는다. 두 수열의 생성 함수가 비슷한 형태를 가지면 수열 자체도 관련이 있을 수 있다.
수열의 점근적 거동을 탐구한다.
수열과 관련된 항등식을 증명한다.
조합론에서 열거 문제를 풀고 그 해법을 인코딩한다. 룩 다항식은 조합론에서 사용되는 예시이다.
무한 급수를 계산한다.

생성 함수는 합을 조작하고 합 사이의 항등식을 설정하는 몇 가지 방법을 제공한다.

가장 간단한 경우는 형태이다. 이 경우 해당 일반 생성 함수에 대해 임을 알 수 있다.

예를 들어, 형태를 조작할 수 있다. 여기서 는 조화수이다. 를 조화수의 일반 생성 함수라고 하면, 이므로, 이다.

을 사용하여 분자와의 합성곱을 통해 을 얻는다. 이는 로도 쓸 수 있다.

생성함수를 사용하여 수열을 연결하고 합을 조작하는 또 다른 예로, 임의의 수열 에 대해 두 개의 합 수열 과 을 정의하고, 모든 에 대해 두 번째 합을 첫 번째 합으로 표현할 수 있다.

먼저, 이항 변환을 사용하여 첫 번째 합에 대한 생성 함수를 로 작성한다. 수열 에 대한 생성 함수가 이므로, 두 번째 합에 대한 생성 함수를 로 작성할 수 있다.

특히, 이 수정된 합 생성 함수를 형태로 작성할 수 있다. 여기서 , , , 이고, 이다.

마지막으로, 두 번째 합을 첫 번째 합을 통해 다음과 같이 표현할 수 있다.

생성함수를 사용하여 합동식을 증명할 수 있다.^[25]

참조

_[1] 논문 Enumeration of Labeled graphs https://books.google[...] 1956
_[2] 서적 Fundamental Algorithms Addison-Wesley
_[3] 간행물
_[4] 웹사이트 Lambert series identity https://mathoverflow[...] 2017
_[5] 간행물
_[6] 간행물
_[7] 간행물
_[8] 서적 An Introduction to the Theory of Numbers https://archive.org/[...] Oxford University Press
_[9] 논문 Convolution Polynomials 1992
_[10] 논문 Combinatorial Sums and Finite Differences
_[11] arXiv Yet another table of integrals
_[12] 간행물
_[13] 간행물
_[14] 서적 Enumerative Combinatorics: Volume 2 https://books.google[...] Cambridge University Press
_[15] 간행물
_[16] 간행물
_[17] 간행물
_[18] 논문 Symbolic Summation Assists Combinatorics http://www.emis.de/j[...] 2007
_[19] 간행물
_[20] 논문 On applications of symmetric Dirichlet distributions and their mixtures to contingency tables
_[21] 논문 Combinatorial aspects of continued fractions http://algo.inria.fr[...]
_[21] 서적 Analytic Theory of Continued Fractions https://books.google[...] Dover 2018
_[22] arXiv Continued Fractions for Square Series Generating Functions
_[null] 논문 Jacobi-Type Continued Fractions for the Ordinary Generating Functions of Generalized Factorial Functions https://cs.uwaterloo[...]
_[22] arXiv Jacobi-Type Continued Fractions and Congruences for Binomial Coefficients Modulo Integers ''h'' ≥ 2
_[23] 간행물
_[24] 간행물
_[25] 간행물
_[26] 간행물
_[27] 서적 An Introduction to the Theory of Numbers
_[28] 간행물
_[29] Masters Approximations de séries génératrices et quelques conjectures Université du Québec à Montréal
_[30] 서적 The Art of Computer Programming, Volume 1 Fundamental Algorithms (Third Edition) Addison-Wesley
_[31] 논문 On applications of symmetric Dirichlet distributions and their mixtures to contingency tables
_[32] 서적 確率論及統計論 http://ebsa.ism.ac.j[...]
_[33] 서적 The Art of Computer Programming, Volume 1 Fundamental Algorithms (Third Edition) Addison-Wesley
_[34] 간행물

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com