생성함수
1. 개요
조합론 등의 수학 분야에서 '''생성함수'''(generating function)란 수열에 대해 특정 함수를 생각하는 것으로, 가장 일반적인 버전은 수열 $$\{a_n\}_{n \in \mathbb{Z}_{\ge 0}} $$의 생성함수를 다음처럼 정의하는 것이다.
$$\displaystyle A(x) = \sum_{n=0}^{\infty} a_n x^n = a_0 + a_1 x + a_2 x^2 + \cdots $$
기본적인 쓰임은 수열의 정보를 다른 공간으로 옮겨서 단순하게 만들고, 함수를 풀어 역으로 수열에 대한 정보를 얻는 것이다. 조합론에서의 보통의 상황은 점화식이나 경우의 수 형태로 주어지는 미지의 수열을 푸는 것이 대부분. 중등 교과과정에는 없지만 이걸 활용하면 고교 수준의 점화식을 포함한 여러 수열/경우의 수 문제들을 비교적 초등적으로 풀 수 있기 때문에 수학 경시대회에서 종종 등장한다. 고급과정에서는 일반항을 완전히 풀지 못하는 더 어려운 식들도 생성함수를 해석적으로 분석해서 수열의 근사식을 얻는 경우도 많다.
미분방정식을 구경해본 위키러라면 어찌 라플라스 변환과 비슷하다고 느낄 수 있을 것이다. 우선 컨셉도 비슷하고, 당장에 수많은 성질들이 (선형성, 함수의 곱과 합성곱 등등) 겹친다. 이는 의도된 것으로, 실제로 역사에서도 라플라스가 라플라스 변환 이전에 먼저 생각한 것이 이 생성함수의 개념이었다. 이산적인 공간에서의 생성함수를 연속적인 공간으로 일반화한 것이 라플라스 변환이라고 생각할 수 있기 때문에, 라플라스 변환의 성질에서 생성함수의 성질이 따라나오는 것은 자연스럽다. 조합론에서 보는 생성함수와는 조금 다른 느낌이 있는 이 해석은 현대에 '''Z-변환'''(Z-transform)이란 이름으로 주로 공학 계열에서 많이 불리게 된다. 같은 대상을 묘사하지만 '생성함수'와 'Z-변환' 두 이름은 순수수학과 응용수학스러운 온도차이가 있다고 생각하면 될 것이다.
사소하지만 주의할 점은, 조합론에서의 생성함수는 함수가 아닐 수도 있다. 즉, 위에서 정의한 $$A(x)$$가 [math(0)]을 제외한 어떤 값 $$x$$에 대해서 수렴하지 않아도, 저 생성함수는 항상 생각할 수 있다. 조합론에서 다루는 생성함수는 '''형식 멱급수'''(formal power series)로, 즉 급수의 수렴성은 완전히 무시하고 $$x$$를 그저 기호로 보는 것이다. 저 형식 멱급수 위에서도 덧/뺄셈, 곱셈을 잘 생각할 수 있고(즉, 환이 된다) 첫 항이 [math(0)]이 아니면 나누기도 가능하다. 물론 일단 수렴성을 증명했으면 $$x$$를 실수 혹은 복소수값으로 놓고 신나게 해석학을 하는 건 당연히 가능하다.
2. 조합론에서의 쓰임
2.1. 기본적인 성질
- 등차수열: $$ a_n = pn+q$$의 생성함수는 $$ \dfrac{p}{1-x} + \dfrac{q}{(1-x)^2} $$이다. 아래의 중복조합 공식의 특수한 경우.
- 등비수열: $$ a_n = r^n $$의 생성함수는 $$ (1-rx)^{-1}$$이다.
- 이항계수: $$\displaystyle a_n = \binom{m}{n} $$의 생성함수는 $$(1+x)^m$$이다.
- 중복조합: $$\displaystyle a_n = \binom{m+n-1}{n} $$의 생성함수는 $$(1-x)^{-m}$$이다.
- (선형성) $$p A(x)+ q B(x)$$에 대응되는 수열은 $$\{p a_n + q b_n\}$$이다.
- (평행이동) $$x A(x)$$에 대응되는 수열은 $$\{a_{n-1}\} = (0,\,a_0,\,a_1,\,\cdots)$$이다.
- (합성곱) $$C(x)=A(x) B(x)$$에 대응되는 수열은 이들의 합성곱(convolution) $$\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$$ 이다.
조합론에서 생성함수의 진가는 이들의 조합적인 의미, 특히 합성곱의 의미와 연결된다. 수열 $$a_n$$, $$b_n$$이 대략 $$\mathscr{A}$$, $$\mathscr{B}$$에서 $$n$$개를 뽑는 방법의 수라고 하면, 이들의 합성곱 $$c_n$$은 $$\mathscr{A}$$, $$\mathscr{B}$$에서 합쳐서 $$n$$개를 뽑는 방법의 수가 된다. 이걸 이용해서 이항정리의 $$(1+x)^m$$은 사실 $$(1+x)$$를 $$m$$번 합성곱해서 나온 거라던지 (본질적으로 보면 이게 이항정리의 생성함수스러운 증명이다), 중복조합을 $$(1-x)^{-1} = 1 + x + x^2 + \cdots$$의 $$m$$중 합성곱으로 해석한다던지 등등. 조합론을 배우다 보면 익숙해지는 기법이다.
2.2. 예시 1: 피보나치 수열
피보나치 수열은 다음의 점화식
$$\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} $$
$$\displaystyle F(x) = \frac{x}{1-x-x^2} $$
이제 이 $$F(x)$$에서 어떻게 $$x^n$$계수를 뽑아낼까가 문제가 된다. 부분분수분해를 이용한 풀이는 다음과 같다. 우선 분모를 인수분해해
$$\displaystyle 1-x-x^2 = (1-\alpha x)(1-\beta x)$$, $$(\alpha,\,\beta) = \left(\frac{1+ \sqrt{5}}{2},\,\frac{1-\sqrt{5}}{2}\right) $$
$$\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) $$
$$\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\} $$
한편 위 생성함수는 다음처럼 분석할 수도 있다. ($$|x|+|x|^2<1$$ 범위에서)
$$\displaystyle F(x) = \frac{x}{1-x-x^2} = x \sum_{m=0}^{\infty} (x+x^2)^m $$
$$\displaystyle f_n = \sum_{\lfloor n/2\rfloor \le m \le n} \binom{m}{n-m-1} $$
2.3. 예시 2: 조화수(수학)
조화수(수학)는 다음의 점화식
$$\displaystyle H_n=\sum_{k=1}^{n}\frac1k=1+\frac12+\frac13+\cdots+\frac1n $$
$$\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. 점근적 분석
계수가 상수인 선형점화식이면 위의 피보나치 수열과 비슷한 방법으로 일반항을 풀어낼 수 있다. (점화식 문서도 참조) 다만 대부분의 점화식은 생성함수는 쉬워도 이렇게 일반항을 풀어내는 것은 불가능하다. 대신에 생성함수를 이용해서 항의 크기가 어느 정도인지를 어림하는 방법을 쓸 수가 있다.
가장 큰 역할을 하는 것은 생성함수의 수렴반경이다. 만약 수열 $$a_n$$의 생성함수 $$A(x)$$가 수렴반경 $$r>0$$을 갖고 있으면, 아다마르 판정법[1]에 의해 $$a_n$$이 '얼추' $$r^{-n}$$ 정도의 크기를 갖는다고 생각할 수 있다. 물론 이게 $$a_n \sim r^{-n}$$ [2]임을 의미하지는 않는다. 다음의 예시를 보면 분명하다.
$$\displaystyle 1 + x + x^2 + \cdots = \frac{1}{1-x}, \quad 1 + 2x + 3x^2 + \cdots = \frac{1}{(1-x)^2} $$
$$\displaystyle a_n = \frac{1}{2\pi i} \oint A(z) \frac{\mathrm{d}z}{z^{n+1}} $$
물론 해석적 확장이 가능하여 유수 공식을 사용 가능한 경우는 운좋은 경우에 속한다. $$A(z)$$가 수렴반경 바깥에서 정의되지 않으면 극점을 포함하는 적분경로를 잡을 수 없으므로 유수 공식을 쓰는 것은 불가능하다. 예를 들어 분할수의 생성함수
$$\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} $$
3. Z-변환
Z-변환의 경우, 생성함수와 컨셉은 똑같지만 표기 및 관습에는 차이가 있다.
- 양뱡향 수열, 즉 음의 정수 위에서도 정의된 수열 $$(\cdots,\,x_{-2},\,x_{-1},\,x_0,\,x_{1},\,x_{2},\,\cdots)$$에 대해서 보통 생각한다.
- 변수는 보통 $$z$$이다. Z-변환이니까.
- 통상의 경우 $$x_n$$과 곱해지는 것은 $$z^n$$이 아니라 $$z^{-n}$$이다. 극소수의 경우 $$z^n$$을 곱하는 관습도 있다.
$$\displaystyle \mathcal{Z} \{x\}(z) = \sum_{n=-\infty}^{\infty} x[n]\,z^{-n} $$
3.1. 적분변환과의 연관성
이산적인 상황에서 라플라스 변환을 생각한 것이 바로 이 Z-변환이라 이해할 수 있다. 다음 두 식을 비교해보면 딱 봐도 비슷하다.
$$\displaystyle \mathcal{Z}\{x\} (e^{s}) = \sum_{n} e^{-sn}x[n], \quad \displaystyle \mathcal{L}\{f\} (s) = \int e^{-st} f(t)\,\mathrm{d}t $$
$$\displaystyle \sum_{n} e^{-sn}\,x[n] = \int e^{-st}\,\mathrm{d}X(t), \quad 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} $$
- 라플라스 변환의 성질은 대개 Z-변환에서 그대로 성립한다. (평행이동, 합성곱 등등)
- 대신 라플라스 변환의 미분이 여기서는 차분, 즉 계차 $$x[n]-x[n-1]$$로 변경된다. 미분방정식의 라플라스 변환 풀이는 선형점화식의 풀이로 변형된다. 이쪽 업계에서는 차분방정식/계차방정식(difference equation) 이란 이름이 더 자주 쓰인다.
- 라플라스 변환의 $$s$$항이 $$e^{ts}$$ 세기의 감쇠항과 대응되는 것처럼, Z-변환의 $$r$$항은 수열 중 $$r^n$$ 크기의 감쇠항과 대응된다. 이것이 보통 Z-변환에서 $$z^{-n}$$을 곱하는 이유이다.
3.2. 공학에서의 쓰임
라플라스 변환과 푸리에 변환이 주로 연속적인 신호 분석에 쓰였던 것만큼이나, Z-변환은 디지털 신호를 다루는 데에 사용될 수 있다. 당장 이산 시간 푸리에 변환이 이 Z-변환의 일종이다.
혹은 연속적인 시스템을 수치적으로 계산할 때 쓰일 수도 있는데, 이산 푸리에 변환, 고속 푸리에 변환 등의 예시가 있다.
4. 여러 가지 생성함수
수열 $$a_n$$ 뒤에 $$x^n$$이 아니라 다른 함수꼴을 곱해서 더하면 다양한 생성함수를 생각할 수 있고, 이 중 중요한 의미를 갖는 것들은 특정 이름이 붙는다. 여기 소개된 것 말고도 정말 수많은 종류의 생성함수들이 있다.
4.1. 지수 생성함수
생성함수로 $$ \sum_n (a_n x^n)/n! $$을 생각하는 것을 지수 생성함수라 한다. 일반 생성함수처럼 선형성 등은 성립하지만, 다음과 같은 특수한 합성곱이 적용된다.
$$\displaystyle c_n = \sum_{m=0}^{n} \binom{n}{m} a_m b_{n-m} $$
예시로 수열 $$a_n=k^n$$는 지수생성함수 $$e^{kx}$$를 갖고 있는데, $$\{1,\,2,\,\cdots,\,k\}$$에서 $$n$$개를 중복해서 뽑아 줄세우는 중복순열의 수로 생각할 수 있다. 이 맥락에서 곱셈 $$e^{kx} e^{lx} = e^{(k+l)x}$$는 $$\{1,\,2,\,\cdots,\,k\}$$와 $$\{1',\,2',\,\cdots,\,l'\}$$에서 $$n$$개를 중복해서 뽑아 줄세우는 중복순열이 (당연하게도) $$(k+l)^n$$개라는 것과 대응된다.
4.2. 디리클레 급수
사실상 정수론에서만 쓰이는 생성함수의 일종으로, $$\sum_n a_n n^{-s} $$를 생각한다. 여기서 $$s$$는 복소변수이다. 함수의 모양 특성상 수렴반경이 원형이 아니라 $$\Re(s)>k$$의 형태로 주어진다. 디리클레 급수의 변수가 $$s$$가 된 것은 전적으로 정수론에서의 베른하르트 리만의 업적 때문이다.
당장에 생각나는 예시는 보통 리만 가설의 리만 제타 함수
$$\displaystyle \zeta(s) = 1 + \frac{1}{2^s} + \frac{1}{3^s} + \cdots $$
생성함수의 합성곱이 자연수의 합과 연관된 것과 대조적으로, 디리클레 급수는 정수의 곱셈 성질에 대한 정보를 품고 있다. 예로 디리클레 급수 버전의 합성곱은 디리클레 합성곱(Dirichlet convolution)이라 불리며 다음과 같이 주어진다.
$$\displaystyle c_n = \sum_{d \vert n} a_d b_{n/d} = \sum_{n=xy} a_x b_y $$
디리클레 급수와 관련된 책으로는 <The General Theory of Dirichlet's Series>가 유명하다. 더 상세한 내용을 알고 싶을 때 참고하면 좋다.
4.3. 적률(모멘트) 생성함수
확률론에서는 확률변수 $$X$$에 대한 적률(모멘트) 생성함수를
$$\displaystyle M_X(t) = \mathbb{E}[e^{tX}] $$
생성함수의 합성곱 성질은 확률변수의 합에 대한 것으로 옮겨지는데, 정확히는 $$X$$, $$Y$$가 독립이면 $$M_{X+Y}(t) = M_X(t) M_Y(t)$$가 성립한다. 이는 어찌 보면 생성함수의 조합적인 이해를 연속적이거나 일반적인 상황에 적용시켰다고 볼 수 있다. 주사위를 던질 때 등등 이산확률변수의 경우 이 모멘트 생성함수는 $$e^t$$를 변수로 갖는 생성함수와 거의 취급이 동일해지기 때문. 이러한 이유로 중심극한정리 등의 증명에 핵심이 되는 내용이다.
모멘트가 존재하지 않는, 심지어는 평균이나 분산조차 없는 수많은 확률분포들이 있으므로, 나중 가면 특성함수(characteristic function)이라 불리는 $$ \varphi_X(t) = \mathbb{E} [e^{itX}]$$를 더 자주 생각하는 편이다. 이건 어떤 확률변수나 분포이건 절대값 $$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} )]