생성함수(Generating function)

수열 $a_0, a_1, a_2, \ldots$를 식 하나에 담아 봅시다. x의 거듭제곱을 '칸'으로 삼아 $a_n$을 $x^n$ 칸에 적어 두는 것입니다: $A(x) = a_0 + a_1x + a_2x^2 + \cdots$. 이것이 생성함수입니다. x에 값을 넣으려는 것이 아니라 계수들을 한데 묶어 다루려는 것이라서, 수렴⁠(convergence)⁠을 따지지 않는 '형식적' 거듭제곱급수라고도 부릅니다.

이렇게 담으면 세기가 곱셈이 됩니다. $x^a \cdot x^b = x^{a+b}$이므로, 두 식을 곱하면 지수가 더해지고 같은 지수에 이르는 방법들이 계수로 모입니다. 주사위 하나는 $x + x^2 + \cdots + x^6$(눈 1~6이 한 가지씩)이고, 주사위 k개의 눈의 합이 m이 되는 경우의 수⁠(number of cases)⁠는 이 식을 k제곱한 것의 $x^m$ 계수입니다.

보기: , 주사위 수 (주사위에서만). $x^m$의 계수, m = :

등비급수⁠(geometric series)⁠가 열쇠입니다. 등비급수 $\frac1{1-x} = 1 + x + x^2 + \cdots$는 '같은 것을 몇 개든 고른다'는 뜻입니다. 2원짜리 동전을 몇 개 쓸지는 $1 + x^2 + x^4 + \cdots = \frac1{1-x^2}$입니다. 그래서 1원, 2원, 5원짜리 동전으로 m원을 내는 방법의 수는 $\frac1{(1-x)(1-x^2)(1-x^5)}$의 $x^m$ 계수입니다. 동전 종류를 모든 자연수⁠(natural number)⁠로 넓히면 분할수⁠(partition number)⁠의 생성함수 $\prod_k \frac1{1-x^k}$가 되고, 똑같은 물건 n개를 k개 상자에 나누는 별과 막대⁠(stars and bars)⁠의 답 $\binom{n+k-1}{k-1}$은 $(1-x)^{-k}$의 $x^n$ 계수입니다. $(1+x)^n$의 계수는 물론 이항계수⁠(binomial coefficient)⁠입니다.

점화식⁠(recurrence relation)⁠ 풀기. 피보나치 수열⁠(Fibonacci sequence)⁠의 점화식 $F_n = F_{n-1} + F_{n-2}\ (F_0 = 0,\ F_1 = 1)$을 생성함수로 옮기면 $F(x) = xF(x) + x^2F(x) + x$, 곧 $F(x) = \frac{x}{1-x-x^2}$입니다. 분모를 인수분해해 부분분수⁠(partial fractions)⁠로 나누면 등비급수 두 개의 합이 되고, 거기서 황금비⁠(golden ratio)⁠가 들어간 일반항이 바로 나옵니다. 이제 x를 실제 수로 보면, 이 급수의 수렴반경⁠(radius of convergence)⁠은 원점에서 가장 가까운 분모의 근 $1/\varphi \approx 0.618$이고, 그 역수⁠(inverse)⁠ φ가 계수의 증가율(이웃한 항의 비가 다가가는 값)입니다. 카탈랑 수⁠(Catalan number)⁠의 생성함수는 이차방정식 $C(x) = 1 + xC(x)^2$을 풀어 얻습니다.

확률⁠(probability)⁠로. 확률분포⁠(probability distribution)⁠도 생성함수로 담습니다. 주사위 그림의 막대를 $6^k$로 나누면 눈의 합의 분포입니다. k가 커질수록 막대들의 윤곽이 종 모양(정규분포⁠, normal distribution⁠)에 가까워지는 것이 중심극한정리⁠(central limit theorem)⁠가 말하는 현상입니다. 0, 1, 2, … 가운데 값을 갖고 서로 영향을 주지 않는(독립⁠(independence)⁠인) 확률변수⁠(random variable)⁠들을 더하는 일은, 각 분포의 생성함수를 곱하는 일이 됩니다. 두 생성함수를 곱하면 $x^m$의 계수는 $\sum_i a_i b_{m-i}$, 곧 합이 m이 되는 모든 짝의 곱을 모은 것이 되는데, 이 연산을 합성곱⁠(convolution)⁠이라 합니다. 합성곱은 푸리에 해석으로 옮기면 성분끼리의 그냥 곱셈으로 바뀝니다.

이어지는 곳. 오일러는 1740년대에 자연수를 더 작은 수들의 합으로 쪼개는 분할 문제를 생성함수로 다루었고, 라플라스는 확률론에 생성함수를 체계적으로 썼습니다. 지금도 알고리즘⁠(algorithm)⁠의 평균⁠(mean)⁠ 걸음 수를 세고 그 증가 속도(점근 표기법⁠(asymptotic notation)⁠)를 어림할 때 생성함수가 기본 도구입니다.

프로그래밍에서 리스트나 나무 같은 타입⁠(type)⁠의 값을 크기별로 세는 대수적 자료형⁠(algebraic data type)⁠의 셈도 생성함수입니다. 예를 들어 이진 나무의 타입은 동형⁠(isomorphism)⁠ $T\cong 1 + T\times T$를 만족하고 이 전단사⁠(bijective)⁠가 마디 수를 지키므로 생성함수가 $T(x) = 1 + x\,T(x)^2$을 만족하는데, 그 동형이 어디서 오는지는 시작 대수의 람벡 보조정리⁠(lemma)⁠가 알려 줍니다.