Problem Solving과 생성함수
간혹 조합론 문제를 해결하다가 점화식이 안 나와서 좌절하고 있을 때, 이 문제는 생성함수를 이용하면 기계적으로 만들어낼 수 있다는 충격적인 코멘트를 받아 언젠가 공부해야지 마음먹고 있습니다. 아쉽게도 정규 교육과정에 포함되어있지 않아서인지 problem solving와 관련된 자료가 드물었습니다. 때문에 이 포스트를 작성하시로 하였습니다. 이 포스트는 생성함수는 무엇이고, problem solving에 적용할 수 있는 방법을 다룹니다.
생성함수란?
일반적으로, 어떤 수열 ${a_i} = (a_0, a_1, a_2, \cdots)$에 대하여,
\[f(x) = a_0 + a_1x + a_2x^2 + \cdots + a_nx^n + \cdots = \sum_{k=0}^{\infty} a_k x^k\]처럼 미지수의 각 항을 계수로 가지는 다항식(또는 멱급수)을 해당 수열의 생성함수 (generating function)이라고 합니다. 생각보다 정의가 간단합니다.
생성함수는 수열에 기원을 두고 있기 때문에 $\sum$ 등을 이용해 항을 풀어쓰기보다는 식으로 정리된 형태(closed-form)로 많이 표현합니다. 또, 생성함수의 목적은 각 항의 값을 알아내는데 있기 때문에 급수의 수렴성 등이 크게 중요하지 않으며, 변수 $x$는 그저 변수에 불과합니다.
생성함수의 계산
생성함수가 주어졌을 때 항을 계산하는 방법은 $a = 0$일 때의 테일러 전개를 하는 것입니다. 맥클로린 급수를 구하는 것과 동일합니다.
무한히 미분 가능한(smooth) 함수 $f\ : \mathbb{R} \to \mathbb{R}$ 가 주어졌을 때 함수 $f$의 맥클로린 급수 $T_f$는 다음과 같이 표현됩니다.
\[T_f(x) = \sum_{n=0}^{\infty}\frac{f^{(n)}(0)}{n!}x^n\]$f^{(n)}(a)$는 $x = a$일 때 $f$의 $n$계 도함수입니다. 미적분학과는 달리, 항에만 의미를 두기 때문에 수렴반경이 0보다 큰 이상 그 범위는 중요한 문제가 아닙니다. 임의의 생성함수에 대해 계속 미분을 해나가며 도함수의 값을 구해나가는 건 힘들 수 있겠지만, 일부 수열은 매우 깔끔한 생성함수를 가집니다.
생성함수의 예시
가장 기초가 되는 생성함수의 예시는 역시 수열이 $(1, 1, 1, \cdots)$일 때의 생성함수입니다.
\[\sum_{n=0}^{\infty} x^n = \frac{1}{1-x}\]미적분학 시간이라면 $\lvert x \rvert < 1$일 때만 수렴한다는 점을 강조하겠지만, 여기서는 중요하지 않습니다. 중요한 점은 수열이 다음과 같이 표현할 수 있다는 점입니다.
$x$는 변수에 불과하기에, 다양한 값으로 치환할 수 있습니다. $x \to ax\, (a \neq 0)$ 로 바꾸면 다음과 같습니다. 다음은 등비수열 $(a^0, a^1, a^2, \cdots)$의 생성함수입니다.
\[\sum_{n=0}^{\infty} (ax)^n = \frac{1}{1-ax}\]$x \to x^k\, (k \in \mathbb{N})$도 똑같습니다.
\[\sum_{n=0}^{\infty} x^{kn} = \frac{1}{1-x^k}\]예를 들어 $\dfrac{1}{1-x^2}$는 $(1, 0, 1, 0, 1, 0, \cdots)$의 생성함수입니다.
다시 $ \sum_{n=0}^{\infty} x^n $로 돌아가보겠습니다. 이를 미분해보면 익숙한 식이 나옵니다.
\[\sum_{n=0}^{\infty} (n+1)x^n = \frac{1}{(1-x)^2}\]$(1, 2, 3, 4, \cdots)$에 대한 생성함수를 만드는 데에 성공했습니다. 한 번 더 미분을 해보면…?
\[\sum_{n=0}^{\infty} \binom{n+2}{2} x^n = \frac{1}{(1-x)^3}\]이항 계수가 나왔습니다. 이를 일반화하면 다음과 같습니다.
\[\sum_{n=0}^{\infty} \binom{m+n-1}{n} x^n = \frac{1}{(1-x)^{m}}\]조합론에서 많이 본 계수가 튀어나왔습니다. 흔히 중복조합(multiset coefficient)이라 불리는 계수입니다. 주로 $m$ 종류의 물건 중복을 포함하여 $n$개를 뽑되 순서는 고려하지 않는 경우의 수로 표현됩니다. 즉, 중복조합의 생성함수가 이러한 형태로 나타납니다.
그럼 일반적인 이항 계수는 어떻게 표현될까요? 이항정리에 의해
\[\sum_{n=0}^{\infty} \binom{m}{n} x^n = (1+x)^{m}\]가 성립하므로, 바로 생성함수를 알 수 있게 됩니다 (일반적으로 $m < n$이면 $\binom{m}{n} = 0$으로 간주합니다).
생성함수의 합과 곱
생성함수의 합과 곱은 또다른 수열의 생성함수가 될 수 있습니다. $f(x)$가 수열 $(a_0, a_1, a_2, \cdots)$에 대한 생성함수고, $g(x)$가 수열 $(b_0, b_1, b_2, \cdots)$에 대한 생성함수일 때,
- $f(x) + g(x)$는 $c_n = a_n + b_n$꼴로 정의되는 수열의 생성함수이며,
- $f(x)g(x)$는 $c_n = \sum_{k=0}^{n} a_i b_{n-i}$꼴로 정의되는 수열의 생성함수입니다.
PS와 생성함수
생성함수를 이용하면 일부 조합론 문제들을 다른 시각에서 접근할 수 있습니다. 멱급수의 꼴로 만든 다음, 분자에는 $(1 \pm x^k)^n$꼴을 남겨서 이항 계수로 풀어쓰고, 분모에는 $(1-x^k)^n$꼴을 남겨서 중복 조합을 이용한 이항 계수로 풀어쓰는 것이 핵심입니다.
이후로 설명할 풀이는 상한 $n$과 소수 $p$에 대해 $0 \leq x, y \leq n$일 때 $\dbinom{x}{y} \pmod{p}$를 $O(n + \lg p)$ 등에 전처리하여 질의당 $O(1)$에 계산할 수 있음을 전제합니다.
BOJ 16725 다항 계수
다항식 $(1+x+\cdots+x^n)^m$의 $k$차 항의 계수를 구해야 합니다.
멱급수를 이용하여 식을 다음과 같이 변형할 수 있습니다.
\[\begin{align*} (1+x+\cdots+x^n)^m &= \frac{(1-x^{n+1})^m}{(1-x)^m} \\ &= (1-x^{n+1})^m \sum_{b=0}^{\infty} \binom{m+b-1}{b} x^b \\ &= \left(\sum_{a=0}^{m} (-1)^a \binom{m}{a} x^{(n+1)a}\right) \left(\sum_{b=0}^{\infty} \binom{m+b-1}{b} x^b \right) \\ \end{align*}\]첫 번째로 잘 알려진 공식인 $(a-b)^{m+1} = (a-b)(\sum_{i=0}^{m} a^{i}b^{m-i})$를 이용하였습니다. 이후 분모를 생성함수를 통해 합의 형태로 끌어내었습니다. 이러면 모든 $x$의 차수가 0 이상이 되어, 계수를 계산할 수 있게 됩니다. 우변의 첫 항의 차수가 $n+1$씩 증가하므로 $x^k$의 계수만 따지면
\[\sum_{i=0}^{\lfloor\frac{k}{n+1}\rfloor} (-1)^{i} \binom{m}{i} \binom{m+(k-i\cdot(n+1))-1}{m-1}\]가 됨을 알 수 있습니다. 시간복잡도 $O(\frac{k}{n+1})$ 정도에 계산할 수 있습니다. 위 식은 포함배제의 원리로도 이끌어낼 수 있습니다.
BOJ 13542 동전 구매하기
1원짜리 동전이 $n$종류가 있고, 2원짜리 동전이 $m$종류가 있을 때, 정확히 $k$원을 지불할 수 있는 경우의 수를 소수 $p$로 나눈 나머지를 구해야 합니다.
$k \leq 10^{12}$이기 때문에 효율적인 접근이 필요함을 알 수 있습니다. 이번에도 생성함수를 만들어보면 1원인 우표를 사는 경우의 생성함수는 $(1-x)^{-n}$이며, 2원인 우표를 사는 경우의 생성함수는 $(1-x^2)^{-m}$임을 알 수 있습니다. 이 둘을 조합하면, $k$원을 지불하여 살 수 있는 경우의 수로 이루어진 수열의 생성함수가 $(1-x)^{-n}(1-x^2)^{-m}$임을 알 수 있습니다. 1원짜리 동전으로 $t$원을 지불하면, 남은 2원짜리 동전으로 $k-t$원을 지불해야 하고, 계수는 경우의 수를 의미하기 때문입니다.
그러므로 비슷한 방식으로 식을 풀어쓸 수 있습니다.
\[\begin{align*} \frac{1}{(1-x)^n(1-x^2)^m} &= \frac{(1+x)^n}{(1-x)^{n} (1-x^2)^m (1+x)^n} \\ &= \frac{(1+x)^n}{(1-x^2)^{n+m}} \\ &= \left(\sum_{a=0}^{n}\binom{n}{a} x^a\right) \left(\sum_{b=0}^{\infty} \binom{n+m+b-1}{b} x^{2b}\right) \end{align*}\]우변의 첫 번째 식에 항이 $n+1$개밖에 없으므로 뒷쪽의 멱급수에서도 대응되는 항이 $n+1$개밖에 없습니다. 그러므로 $x^k$의 계수만 따지면
\[\sum_{i=0}^{n} \binom{n}{i} \binom{n+m+\frac{k-i}{2}-1}{n+m-1}\]가 됩니다 ($k-a$가 2의 배수일 때만 고려합니다). 이 문제에서는 이항 계수 $\binom{n}{m}$을 구할 때 $n$이 $10^{12}$까지 커질 수 있지만 법 $p$가 소수고 $10^6$ 이하라는 사실을 이용해 뤼카의 정리를 이용하여 이항 계수를 $p$로 나눈 나머지를 계산할 수 있습니다.
결론
생성함수의 응용이 생각보다 어렵지 않으면서도 식을 금방 유도할 수 있게 되어 흡족했습니다. 다만 다양한 조건을 고려해야 하는 조합론 문제라면 생성함수로 접근하기는 더 까다롭겠다는 생각이 들었습니다. 그럼에도 불구하고 생성함수는 이해하기 어렵지 않고 충분히 알아둘만한 개념이라고 생각됩니다. 생성함수를 통해 생성된 식의 조합적 의미를 탐구하는 것도 수학적 안목을 기르는데 도움이 될 것 같습니다.