| 이산수학 Discrete Mathematics | ||
| {{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px; word-break: keep-all" | 이론 | |
| <colbgcolor=#3CC> 기본 대상 | 수학기초론(수리논리학 · 집합론) · 수열 · 조합 · 알고리즘 · 확률 | |
| 다루는 대상과 주요 토픽 | ||
| 수열 | 등차수열(뛰어 세기) · 등비수열 · 계차수열 · 조화수열 · 귀납적 정의(점화식) · 급수 · 규칙과 대응 · 규칙 찾기 · 피보나치 수열 · 읽고 말하기 수열 · 생성함수 | |
| 조합 | 경우의 수(/공식) · 순열(완전 순열 · 염주 순열) · 치환 · 분할(분할수) · 최단거리 · 제1종 스털링 수 · 제2종 스털링 수 · 카탈랑 수 · 벨 수 · 라흐 수 · 포함·배제의 원리 · 더블 카운팅 · 조합론 | |
| 그래프 | 수형도(트리) · 인접행렬 · 마방진 · 마법진 · 한붓그리기(해밀턴 회로) · 쾨니히스베르크 다리 건너기 문제 | |
| 기타 | P-NP 문제미해결 · 4색정리 · 이항정리(파스칼의 삼각형) · 이산 푸리에 변환 · 비둘기 집의 원리 · 상트페테르부르크의 역설 · 투표의 역설 · 에르고딕 가설미해결 · 콜라츠 추측미해결 · 시행착오 (예상과 확인) · 불 논리 · 브라에스 역설 | |
| 관련 문서 | 논리학 관련 정보 · 수학 관련 정보 · 컴퓨터 관련 정보 · 틀:수학기초론 · 틀:통계학 · 틀:이론 컴퓨터 과학 | }}}}}}}}} |
1. 개요
조합론 등의 수학 분야에서 생성함수(generating function)란 수열에 대해 특정 함수를 생각하는 것으로, 가장 일반적인 버전은 수열 [math(\{a_n\}_{n \in \mathbb{Z}_{\ge 0}} )]의 생성함수를 다음처럼 정의하는 것이다.
[math(\displaystyle A(x) = \sum_{n=0}^{\infty} a_n x^n = a_0 + a_1 x + a_2 x^2 + \cdots )]
보통 생성함수라고 하면 이 일반생성함수(ordinary generating function)를 의미하고, 다른 종류의 생성함수도 생각할 수 있다. [math(x^n)]을 다른 것으로 대체해서 사용하는데, 이에 대해서는 아래의 '여러 가지 생성함수' 항목을 참고. 다만 같은 꼴의 연속함수와 구분하기 위해 최대 정수 함수를 사용하여 [math(A(\lfloor x\rfloor))]로 표기하기도 한다.
기본적인 쓰임은 수열의 정보를 다른 공간으로 옮겨서 단순하게 만들고, 함수를 풀어 역으로 수열에 대한 정보를 얻는 것이다. 조합론에서의 보통의 상황은 점화식이나 경우의 수 형태로 주어지는 미지의 수열을 푸는 것이 대부분. 중등 교과과정에는 없지만 이걸 활용하면 고교 수준의 점화식을 포함한 여러 수열/경우의 수 문제들을 비교적 초등적으로 풀 수 있기 때문에 수학 경시대회에서 종종 등장한다. 고급과정에서는 일반항을 완전히 풀지 못하는 더 어려운 식들도 생성함수를 해석적으로 분석해서 수열의 근사식을 얻는 경우도 많다.
미분방정식을 안다면 어찌 라플라스 변환과 비슷하다고 느낄 수 있을 것이다. 우선 컨셉도 비슷하고, 당장에 수많은 성질들이 (선형성, 함수의 곱과 합성곱 등) 겹친다. 이는 의도된 것으로, 실제로 역사에서도 라플라스가 라플라스 변환 이전에 먼저 생각한 것이 이 생성함수의 개념이었다. 이산적인 공간에서의 생성함수를 연속적인 공간으로 일반화한 것이 라플라스 변환이라고 생각할 수 있기 때문에, 라플라스 변환의 성질에서 생성함수의 성질이 따라나오는 것은 자연스럽다. 조합론에서 보는 생성함수와는 조금 다른 느낌이 있는 이 해석은 현대에 Z-변환(Z-transform)이란 이름으로 주로 공학 계열에서 많이 불리게 된다. 같은 대상을 묘사하지만 '생성함수'와 'Z-변환' 두 이름은 순수수학과 응용수학스러운 온도차이가 있다고 생각하면 될 것이다.
사소하지만 주의할 점은, 조합론에서의 생성함수는 함수가 아닐 수도 있다. 즉, 위에서 정의한 [math(A(x))]가 [math(0)]을 제외한 어떤 값 [math(x)]에 대해서 수렴하지 않아도, 저 생성함수는 항상 생각할 수 있다. 조합론에서 다루는 생성함수는 형식 멱급수(formal power series)로, 즉 급수의 수렴성은 완전히 무시하고 [math(x)]를 그저 기호로 보는 것이다. 저 형식 멱급수 위에서도 덧/뺄셈, 곱셈을 잘 생각할 수 있고(즉, 환이 된다) 첫 항이 [math(0)]이 아니면 나누기도 가능하다. 물론 일단 수렴성을 증명했으면 [math(x)]를 실수 혹은 복소수값으로 놓고 신나게 해석학을 하는 건 당연히 가능하다.
2. 조합론에서의 쓰임
2.1. 기본적인 성질
- 등차수열: [math( a_n = pn+q)]의 생성함수는 [math( \dfrac{px}{(1-x)^2} + \dfrac{q}{1-x} )]이다. 아래의 중복조합 공식의 특수한 경우.
- 등비수열[2]: [math( a_n = r^n )]의 생성함수는 [math( (1-rx)^{-1})]이다.
- 이항계수: [math(\displaystyle a_n = \binom{m}{n} )]의 생성함수는 [math((1+x)^m)]이다.
- 중복조합: [math(\displaystyle a_n = \binom{m+n-1}{n} )]의 생성함수는 [math((1-x)^{-m})]이다.
생성함수에선 다음의 세 성질이 기본으로 활용된다. 수열 [math(a_n)], [math(b_n)]의 생성함수를 각각 [math(A(x))], [math(B(x))]라고 하자. 그럼
- (선형성) [math(p A(x)+ q B(x))]에 대응되는 수열은 [math(\{p a_n + q b_n\})]이다.
- (평행이동) [math(x A(x))]에 대응되는 수열은 [math(\{a_{n-1}\} = (0,\,a_0,\,a_1,\,\cdots))]이다.
- (합성곱) [math(C(x)=A(x) B(x))]에 대응되는 수열은 이들의 합성곱(convolution) [math(\displaystyle c_n = \sum_{m=0}^{n} a_m b_{n-m} = a_n b_0 + a_{n-1} b_1 + \cdots + a_1 b_{n-1} + a_0 b_n)] 이다.
사실 많은 경우에서 생성함수는 매클로린 급수랑 다른 게 전혀 없다. 테일러 급수에서 성립하는 것은 형식멱급수에서도 적용 가능하기 때문에, 생성함수의 수렴 반경이 [math(0)]보다 크다면 생성함수에 대해 테일러 정리가 적용 가능하기 때문. 대신 그 반대는 성립하지 않는다.
조합론에서 생성함수의 진가는 이들의 조합적인 의미, 특히 합성곱의 의미와 연결된다. 수열 [math(a_n)], [math(b_n)]이 대략 [math(\mathscr{A})], [math(\mathscr{B})]에서 [math(n)]개를 뽑는 방법의 수라고 하면, 이들의 합성곱 [math(c_n)]은 [math(\mathscr{A})], [math(\mathscr{B})]에서 합쳐서 [math(n)]개를 뽑는 방법의 수가 된다. 이걸 이용해서 이항정리의 [math((1+x)^m)]은 사실 [math((1+x))]를 [math(m)]번 합성곱해서 나온 거라던지 (본질적으로 보면 이게 이항정리의 생성함수스러운 증명이다), 중복조합을 [math((1-x)^{-1} = 1 + x + x^2 + \cdots)]의 [math(m)]중 합성곱으로 해석한다던지 등등. 조합론을 배우다 보면 익숙해지는 기법이다.
2.2. 예시 1: 피보나치 수열
피보나치 수열은 다음의 점화식[math(\displaystyle f_n = \begin{cases} 0 & \text{if }n=0 \\ 1 & \text{if}\ n=1 \\ f_{n-1} + f_{n-2} & \text{if}\ n \ge 2\end{cases} )]
으로 주어지는 수열이다. 이 수열의 생성함수 [math(F(x))]는 다음과 같이 주어진다.
[math(\displaystyle F(x) = \frac{x}{1-x-x^2} )]
이는 수열 [math(f_{n-1})], [math(f_{n-2})]에 대응되는 생성함수가 각각 [math(x F(x))], [math(x^2 F(x))]로 주어져서, 이들의 차이인 [math(F(x) - x F(x) - x^2 F(x) )]의 항이 (점화식 때문에) 2차 이상으로는 사라지기 때문. 상수항과 1차항을 계산하면 [math(F(x) - x F(x) - x^2 F(x) = x)]임을 얻을 수 있다.
이제 이 [math(F(x))]에서 어떻게 [math(x^n)]계수를 뽑아낼까가 문제가 된다. 부분분수분해를 이용한 풀이는 다음과 같다. 우선 분모를 인수분해해
[math(\displaystyle 1-x-x^2 = (1-\alpha x)(1-\beta x))], [math((\alpha,\,\beta) = \left(\frac{1+ \sqrt{5}}{2},\,\frac{1-\sqrt{5}}{2}\right) )]
라 할 수 있다. 그리고 통상적인 부분분수분해로
[math(\displaystyle \frac{x}{(1-\alpha x)(1-\beta x)} = \frac{1}{\alpha - \beta} \left( \frac{1}{1 - \alpha x} - \frac{1}{1-\beta x} \right) )]
을 얻는다. 이제 [math(\displaystyle (1-\alpha x)^{-1} = \sum_n \alpha^n x^n )]을 생각하면 [math(F(x))]의 맥클로린 전개식으로
[math(\displaystyle f_n = \frac{1}{\alpha-\beta} (\alpha^n - \beta^n) = \frac{1}{\sqrt{5}} \left\{ \left(\frac{1+\sqrt{5}}{2}\right)^{n+1}-\left(\frac{1-\sqrt{5}}{2}\right)^{n+1} \right\} )]
을 구한다. 비네의 공식의 풀이.
한편 위 생성함수는 다음처럼 분석할 수도 있다. ([math(|x+x^2|<1)] 범위에서)
[math(\displaystyle F(x) = \frac{x}{1-x-x^2} = x \sum_{m=0}^{\infty} (x+x^2)^m )]
우변 중 [math(x(x+x^2)^m)]에서 [math(x^n)]의 계수는 [math( (1+x)^m)]에서 [math(x^{n-m-1})]의 계수와 같다. 따라서 피보나치 수열의 다음 일반항을 얻어낼 수도 있다.
[math(\displaystyle f_n = \sum_{\lfloor n/2\rfloor \le m \le n} \binom{m}{n-m-1} )]
이 식은 파스칼의 삼각형에서 기울어진 대각선 위의 숫자들의 합으로 해석할 수 있다.
2.3. 예시 2: 조화수
조화수는 다음의 점화식[math(\displaystyle H_n=\sum_{k=1}^{n}\frac1k=1+\frac12+\frac13+\cdots+\frac1n )]
로 주어지는 수열이다. 이 수열의 생성함수는 다음과 같이 주어진다.
[math(\displaystyle \sum_{n=1}^{\infty}H_nx^n=-\frac{\ln(1-x)}{(1-x)} )]
다음처럼 로그 함수의 매클로린 급수를 사용해서 얻을 수 있다.
[math(\displaystyle \begin{aligned}
\sum_{n=1}^{\infty}H_nx^n&=\sum_{n=1}^{\infty}\sum_{k=1}^{n}\frac1kx^n \\
&=\frac11x^1+\left(\frac11+\frac12\right)\!x^2+\left(\frac11+\frac12+\frac13\right)\!x^3+\cdots \\
&=\frac11(x^1+x^2+x^3+\cdots)+\frac12(x^2+x^3+\cdots)+\frac13(x^3+\cdots)+\cdots \\
&=\sum_{k=1}^{\infty}\frac1k(x^k+x^{k+1}+\cdots) \\
&=\sum_{k=1}^{\infty}\frac1k\frac{x^k}{1-x} \\
&=\frac1{1-x}\sum_{k=1}^{\infty}\frac{x^k}k \\
&=-\frac{\ln(1-x)}{(1-x)}
\end{aligned} )]
2.4. 점근적 분석
계수가 상수인 선형점화식이면 위의 피보나치 수열과 비슷한 방법으로 일반항을 풀어낼 수 있다. (점화식 문서도 참조) 다만 대부분의 점화식은 생성함수는 쉬워도 이렇게 일반항을 풀어내는 것은 불가능하다. 대신에 생성함수를 이용해서 항의 크기가 어느 정도인지를 어림하는 방법을 쓸 수가 있다.가장 큰 역할을 하는 것은 생성함수의 수렴반경이다. 만약 수열 [math(a_n)]의 생성함수 [math(A(x))]가 수렴반경 [math(r>0)]을 갖고 있으면, 아다마르 판정법[3]에 의해 [math(a_n)]이 '얼추' [math(r^{-n})] 정도의 크기를 갖는다고 생각할 수 있다. 물론 이게 [math(a_n \sim r^{-n})] [4]임을 의미하지는 않는다. 다음의 예시를 보면 분명하다.
[math(\displaystyle 1 + x + x^2 + \cdots = \frac{1}{1-x}, \quad 1 + 2x + 3x^2 + \cdots = \frac{1}{(1-x)^2} )]
다만, 일반적으로 생성함수에서 [math((1-x/r)^{-1})]이 몇번 곱해졌는지가 항의 크기를 좌우한다는 것은 맞다. 복소해석학 중 특히 유수(residue)에 대한 지식이 있다면 다음의 역변환을 생각할 수 있다.
[math(\displaystyle a_n = \frac{1}{2\pi i} \oint A(z) \frac{\mathrm{d}z}{z^{n+1}} )]
여기서 경로는 복소평면의 중심 [math(0)]점을 한바퀴 도는 어떤 경로라도 가능하다. 만약 [math(A(z))]를 수렴반경을 넘어 해석적 확장을 하는 것이 가능하다면 (쉬운 말로 표현하면 넓은 범위에서 정의되는 쉬운 식으로 나타내는 것이 가능하다면), [math(A(z))]의 극점(pole) 중 절대값이 가장 작은 곳에서 [math(A(z) z^{-n-1})]의 유수로 [math(a_n)]의 근사값을 구할 수 있다. 특히 극점이 [math(x=r)]이고 그 지수가 [math(k)]라면 [math(a_n \sim r^{-n} P_{k-1}(n))] ([math(P_{k-1})]: [math((k-1))]차 다항식)이라 말할 수 있다.
물론 해석적 확장이 가능하여 유수 공식을 사용 가능한 경우는 운좋은 경우에 속한다. [math(A(z))]가 수렴반경 바깥에서 정의되지 않으면 극점을 포함하는 적분경로를 잡을 수 없으므로 유수 공식을 쓰는 것은 불가능하다. 예를 들어 분할수의 생성함수
[math(\displaystyle P(x) = \sum_n p(n) x^n = \prod_k (1-x^{-k})^{-1} = \frac{1}{(1-x)(1-x^2)(1-x^3) \cdots} )]
는 수렴반경 바깥인 [math(|x| \ge 1)]의 영역으로 확장하는 것이 불가능하다. 이런 경우에는 수렴반경에 근접하는 원 위에서 적분을 하여 근사값을 구하고, [math(A(z))]가 가파르게 진동하는 (보통 무한개의) 구간을 분리해내어 주항을 찾아내는 노가다를 해야 한다. 이것을 하디-리틀우드 원 방법(circle method)이라 하고, 저 분할수의 경우는 원 방법과 모듈러 형식의 성질 등을 총동원하여 일반항 및 근사식(하디-라마누잔-라데마커 공식)을 구해내는 것이 가능하다고 한다. 정수론에서는 굉장히 중요한 방법으로, 골드바흐 추측 중 약한 추측을 증명하는 Vinogradov와 Helfgott의 풀이 기법이기도 하다.
3. Z-변환
Z-변환의 경우, 생성함수와 컨셉은 똑같지만 표기 및 관습에는 차이가 있다.- 양방향 수열, 즉 음의 정수 위에서도 정의된 수열 [math((\cdots,\,x_{-2},\,x_{-1},\,x_0,\,x_{1},\,x_{2},\,\cdots))]에 대해서 보통 생각한다.
- 변수는 보통 [math(z)]이다. Z-변환이니까.
- 통상의 경우 [math(x_n)]과 곱해지는 것은 [math(z^n)]이 아니라 [math(z^{-n})]이다.
(응?)극소수의 경우 [math(z^n)]을 곱하는 관습도 있다.
[math(\displaystyle \mathcal{Z} \{x\}(z) = \sum_{n=-\infty}^{\infty} x[n]\,z^{-n} )]
왜 [math(z^{-n})]을 곱하는지는 라플라스 변환과의 연관성 때문인데, 아래 절을 보면 분명해진다. 또한 Z-변환은 해석적인 쓰임새 때문에 조합에서의 생성함수와는 다르게 수렴 반경이 꽤 중요해진다.
3.1. 적분변환과의 연관성
이산적인 상황에서 라플라스 변환을 생각한 것이 바로 이 Z-변환이라 이해할 수 있다. 다음 두 식을 비교해보면 딱 봐도 비슷하다.[math(\displaystyle \begin{aligned} \mathcal{Z}\{x\} (e^{s}) &= \sum_{n} e^{-sn}x[n] \\ \mathcal{L}\{f\} (s) &= \int e^{-st} f(t)\,\mathrm{d}t \end{aligned})]
만약 스틸체스 적분을 알고 있다면 다음처럼 이 과정을 보다 엄밀하게 만들 수 있다.
[math(\displaystyle \begin{aligned} \sum_{n} e^{-sn}\,x[n] &= \int e^{-st}\,\mathrm{d}X(t) \\ X(t) &= \begin{cases} \sum_{0 \le n < t} x[n] & \text{if }t \ge 0 \\ -\sum_{-t < n < 0} x[n] & \text{if } t<0 \end{cases} \end{aligned} )]
어찌 되었건 보통 라플라스 변환이 연속적인 신호에 대해서 이루어진다면, 이것을 그대로 이산적인 신호에 대해 적용한 것이 Z-변환이라고 볼 수 있는 것이다. 이로써 따라나오는 사실들은 다음과 같은 것들이 있다.
- 라플라스 변환의 성질은 대개 Z-변환에서 그대로 성립한다. (평행이동, 합성곱 등등)
- 대신 라플라스 변환의 미분이 여기서는 차분, 즉 계차 [math(x[n]-x[n-1])]로 변경된다. 미분방정식의 라플라스 변환 풀이는 선형점화식의 풀이로 변형된다. 이쪽 업계에서는 차분방정식/계차방정식(difference equation) 이란 이름이 더 자주 쓰인다.
- 라플라스 변환의 [math(s)]항이 [math(e^{ts})] 세기의 감쇠항과 대응되는 것처럼, Z-변환의 [math(r)]항은 수열 중 [math(r^n)] 크기의 감쇠항과 대응된다. 이것이 보통 Z-변환에서 [math(z^{-n})]을 곱하는 이유이다.
3.2. 공학에서의 쓰임
라플라스 변환과 푸리에 변환이 주로 연속적인 신호 분석에 쓰였던 것만큼이나, Z-변환은 디지털 신호를 다루는 데에 사용될 수 있다. 당장 이산 시간 푸리에 변환이 이 Z-변환의 일종이다.혹은 연속적인 시스템을 수치적으로 계산할 때 쓰일 수도 있는데, 이산 푸리에 변환, 고속 푸리에 변환 등의 예시가 있다.
4. 여러 가지 생성함수
수열 [math(a_n)] 뒤에 [math(x^n)]이 아니라 다른 함수꼴을 곱해서 더하면 다양한 생성함수를 생각할 수 있고, 이 중 중요한 의미를 갖는 것들은 특정 이름이 붙는다. 여기 소개된 것 말고도 정말 수많은 종류의 생성함수들이 있다.4.1. 지수 생성함수
생성함수로 [math( \sum_n (a_n x^n)/n! )]을 생각하는 것을 지수 생성함수라 한다. 일반 생성함수처럼 선형성 등은 성립하지만, 다음과 같은 특수한 합성곱이 적용된다.[math(\displaystyle c_n = \sum_{m=0}^{n} \binom{n}{m} a_m b_{n-m} )]
만약 [math(a_n)], [math(b_n)]이 [math(\mathscr{A})], [math(\mathscr{B})]에서 [math(n)]개를 뽑아 줄세우는 방법의 수라고 한다면, 위의 [math(c_n)]은 [math(\mathscr{A})], [math(\mathscr{B})]를 합친 곳에서 [math(n)]개를 뽑아 줄세우는 방법의 수로 간주할 수 있다. 즉, 일반 생성함수가 조합 계열을 나타내는 데에 적합하다면 지수 생성함수는 순열 계열을 나타내는 데에 적합하다.
예시로 수열 [math(a_n=k^n)]는 지수생성함수 [math(e^{kx})]를 갖고 있는데, [math(\{1,\,2,\,\cdots,\,k\})]에서 [math(n)]개를 중복해서 뽑아 줄세우는 중복순열의 수로 생각할 수 있다. 이 맥락에서 곱셈 [math(e^{kx} e^{lx} = e^{(k+l)x})]는 [math(\{1,\,2,\,\cdots,\,k\})]와 [math(\{1',\,2',\,\cdots,\,l'\})]에서 [math(n)]개를 중복해서 뽑아 줄세우는 중복순열이 (당연하게도) [math((k+l)^n)]개라는 것과 대응된다.
4.2. 디리클레 급수
사실상 정수론에서만 쓰이는 생성함수의 일종으로, [math(\sum_n a_n n^{-s} )]를 생각한다. 여기서 [math(s)]는 복소변수이다. 함수의 모양 특성상 수렴반경이 원형이 아니라 [math(\Re(s)>k)]의 형태로 주어진다. 디리클레 급수의 변수가 [math(s)]가 된 것은 전적으로 정수론에서의 베른하르트 리만의 업적 때문이다.당장에 생각나는 예시는 보통 리만 가설의 리만 제타 함수
[math(\displaystyle \zeta(s) = 1 + \frac{1}{2^s} + \frac{1}{3^s} + \cdots )]
일 것이다. 실제로 이게 제일 원조기도 하고. 역사적으로 그 다음에 나온 디리클레 급수는 디리클레가 고안한 디리클레 지표(Dirichlet character)라 불리는 수열에 대한 것으로, 디리클레 지표에 대한 디리클레 급수를 보통 디리클레 L-급수라 부르기도 한다. '[math(an+b)]꼴 등차수열에서 [math(a)], [math(b)]가 서로소이면 무수히 많은 소수가 있다'는 디리클레의 정리를 증명할 때 사용되었다.
생성함수의 합성곱이 자연수의 합과 연관된 것과 대조적으로, 디리클레 급수는 정수의 곱셈 성질에 대한 정보를 품고 있다. 예로 디리클레 급수 버전의 합성곱은 디리클레 합성곱(Dirichlet convolution)이라 불리며 다음과 같이 주어진다.
[math(\displaystyle c_n = \sum_{d \vert n} a_d b_{n/d} = \sum_{n=xy} a_x b_y )]
보통 [math(c = (a * b))] 로 쓴다. 예시로 [math(1 * 1)] 같은 건 약수의 개수, [math( 1* n)]은 약수의 합이 된다! 이런 식으로 얻어낸 디리클레 급수들에 대해 위에 언급한 점근적 분석을 비슷하게 적용해서, 약수의 평균 개수나 총합, 소수의 개수 등의 결과를 얻는 것이 해석적 정수론의 주된 내용이다. 특히나 수많은 디리클레 급수들이 소수에 대한 곱으로 나타나지기 때문에, 이는 소수의 성질을 밝혀내는 데에 매우 유용하다.
디리클레 급수와 관련된 책으로는 <The General Theory of Dirichlet's Series>가 유명하다. 더 상세한 내용을 알고 싶을 때 참고하면 좋다.
4.3. 적률(모멘트) 생성함수
확률론에서는 확률 변수 [math(X)]에 대한 적률(모멘트) 생성함수를[math(\displaystyle M_X(t) = \mathbb{E}[e^{tX}] )]
로 정의한다. 여기서 [math(X)], [math(t)]는 보통 실수값 한정이다. 이름이 붙여진 이유는, 이 생성함수의 테일러 전개인 [math(\sum_{n=0}^{\infty} \mathbb{E}[X^n] (t^n/n!))]의 계수 [math(\mathbb{E}[X^n])]을 보통 [math(n)]차 모멘트라 부르기 때문. 물론 당연히 모든 모멘트가 존재해야 정의할 수 있다. 실제로 모멘트와 모멘트 생성함수는 확률변수보다는 확률분포에 고유한 것으로, 확률분포 [math(\mu)]에 대해서 [math(\displaystyle M_{\mu}(t) = \int e^{tx}\mathrm{d}\mu(x))]로 정의하는 것이 더욱 일반적이다.
생성함수의 합성곱 성질은 확률변수의 합에 대한 것으로 옮겨지는데, 정확히는 [math(X)], [math(Y)]가 독립이면 [math(M_{X+Y}(t) = M_X(t) M_Y(t))]가 성립한다. 이는 어찌 보면 생성함수의 조합적인 이해를 연속적이거나 일반적인 상황에 적용시켰다고 볼 수 있다. 주사위를 던질 때 등등 이산확률변수의 경우 이 모멘트 생성함수는 [math(e^t)]를 변수로 갖는 생성함수와 거의 취급이 동일해지기 때문. 이러한 이유로 중심극한정리 등의 증명에 핵심이 되는 내용이다.
코시 분포처럼 모멘트가 존재하지 않거나 심지어 평균이나 분산조차 없는 수많은 확률분포들이 있으며, 심지어 로그정규분포 등 모멘트가 모든 자연수에 대해 존재한다고 해서 적률생성함수가 없는 사례조차 있으므로, 나중 가면 특성함수(characteristic function)이라 불리는 [math( \varphi_X(t) = \mathbb{E} [e^{itX}])]를 더 자주 생각하는 편이다. 이건 어떤 확률변수나 분포이건 절대값 [math(1)] 안에서 놀기 때문.
4.4. 오일러 수열, 베르누이 수열 생성함수
[math(\displaystyle \begin{aligned} E_n &= \mathrm{sech}(\lfloor n \rfloor) \\
B_n &= \dfrac{\lfloor n \rfloor}{2} \left( \mathrm{coth} \left(\dfrac{\lfloor n \rfloor}{2} \right) - 1 \right)
\end{aligned} )]
쌍곡선 함수를 이용해서 만드는 수열. 특히 베르누이 수열은 테일러 급수와 엮여서 상당히 자주 등장하는 수열이다.
5. 관련 문서
[1] Ref : 3Blue1Brown, 생성함수를 이용해 집합의 개수를 세는 영상[2] 중복순열로도 볼 수 있다.[3] 복소계수 멱급수 [math(\sum a_n x^n)]의 수렴반경이 [math( \displaystyle r = ( \limsup |a_n|^{1/n} )^{-1} )]로 주어진다는 정리[4] [math(a_n \sim b_n)]은 보통 [math(\lim (a_n/b_n) = 1)]의 의미이다.