생성 함수 – 학습

1강 수열을 다항식으로: 생성 함수 공식

생성 함수란

수열 $(a_0, a_1, a_2, \dots)$ 를 형식적 멱급수의 계수로 인코딩한 것이 생성 함수다.

$A(x) = \sum_{n \ge 0} a_n x^n$

여기서 $$x$$ 는 대입하는 변수가 아니라 "계수를 줄 세우는 표지(bookkeeping)"다. 수열 연산이 다항식 연산으로 번역되는 것이 위력이다.

기본 사전

수열 연산	생성 함수 연산
$$a_n + b_n$$	$$A(x) + B(x)$$
합성곱 $\sum_k a_k b_{n-k}$	$A(x)\,B(x)$
이동 $a_{n-1}$	$x\,A(x)$
$n\ a_n$	$x\ A'(x)$
부분합 $\sum_{k\le n} a_k$	$\dfrac{A(x)}{1-x}$

가장 중요한 닫힌 형:

$\sum_{n\ge 0} x^n = \frac{1}{1-x}, \qquad \sum_{n\ge 0}\binom{n+k}{k}x^n = \frac{1}{(1-x)^{k+1}}$

점화식 풀기

피보나치 $f_n = f_{n-1} + f_{n-2}$ , $$f_0 = 0, f_1 = 1$$ . 생성 함수를 $$F(x)$$ 라 하면

$F(x) = xF(x) + x^2 F(x) + x \;\Rightarrow\; F(x) = \frac{x}{1 - x - x^2}.$

부분분수로 분해하면 비네 공식 $f_n = \frac{1}{\sqrt5}(\varphi^n - \psi^n)$ 이 곧바로 나온다. 점화식 → 유리함수 → 닫힌 형의 전형적 흐름이다.

지수 생성 함수(EGF)

순서가 있는 구조(배열, 라벨 그래프)에는 지수 생성 함수가 자연스럽다.

$\hat{A}(x) = \sum_{n\ge 0} a_n \frac{x^n}{n!}$

EGF의 곱은 "라벨을 두 그룹으로 나누는" 합성곱:

$[x^n]\,\hat A \hat B = \sum_k \binom{n}{k} a_k b_{n-k}.$

예: 순열의 EGF는 $\sum n!\,x^n/n! = 1/(1-x)$ , 교란순열(derangement)의 EGF는 $e^{-x}/(1-x)$ .

조합 항등식의 기계화

$\sum_{k} \binom{n}{k}\binom{m}{p-k} = \binom{n+m}{p}$

는 $(1+x)^n (1+x)^m = (1+x)^{n+m}$ 의 $$x^p$$ 계수 비교일 뿐이다. 복잡한 합을 "다항식 곱의 한 계수"로 보는 훈련이 핵심이다.

정리

수열 ↔ 멱급수. 연산이 대수 연산으로 번역된다.
선형 점화식 → 유리 생성 함수 → 닫힌 형/행렬거듭제곱.
OGF는 비라벨, EGF는 라벨 구조.

다음 강의에서 실제 카운팅 문제에 생성 함수를 적용한다.

2강 생성 함수로 푸는 카운팅 공식

동전 교환: 분할 수

액면 $\{1, 5, 10\}$ 로 금액 $$n$$ 을 만드는 방법 수는

$\frac{1}{(1-x)(1-x^5)(1-x^{10})}$

의 $$x^n$$ 계수다. 각 인자 $\frac{1}{1-x^c} = 1 + x^c + x^{2c} + \cdots$ 가 "동전 $$c$$ 를 0개, 1개, ... 쓴다"를 뜻한다. 곱은 곧 합성곱이고, 코드로는 무한 등비급수를 한 동전씩 누적하는 배낭 DP가 된다.

vector<long long> coins = {1, 5, 10};
vector<long long> cnt(N + 1, 0);
cnt[0] = 1;
for (long long c : coins)
    for (int v = c; v <= N; v++)      // 1/(1-x^c)와의 곱
        cnt[v] += cnt[v - c];
// cnt[n] = 답

카탈란 수: 자기 참조 점화식

이진 트리 / 괄호 문자열의 카탈란 수 $$C_n$$ 은 $C(x) = 1 + x\,C(x)^2$ 를 만족한다(루트 + 좌/우 부트리의 합성곱). 이차방정식을 풀면

$C(x) = \frac{1 - \sqrt{1 - 4x}}{2x}, \qquad C_n = \frac{1}{n+1}\binom{2n}{n}.$

생성 함수 방정식이 곧 닫힌 형을 준다.

다항식 곱과 FFT

여러 생성 함수의 곱이 필요하면 NTT로 $O(N \log N)$ 합성곱을 쓴다. 예: 주사위 $$k$$ 개를 던져 합이 $$s$$ 가 되는 경우 수는

$(x + x^2 + \cdots + x^6)^k$

의 $$x^s$$ 계수. $$k$$ 가 크면 $\log k$ 번의 제곱-곱(이진 거듭제곱 + NTT)으로 처리한다.

// poly: NTT 기반 다항식 곱 poly_mul(a, b)
vector<long long> die = {0,1,1,1,1,1,1};   // x..x^6
vector<long long> res = {1};
for (; k; k >>= 1) {
    if (k & 1) res = poly_mul(res, die);
    die = poly_mul(die, die);
}
// res[s] = 합이 s가 되는 경우 수

지수 생성 함수 응용: 집합 분할

집합을 비어 있지 않은 블록으로 나누는 EGF: 한 블록은 $$e^x - 1$$ , $$k$$ 개 블록(순서 무시)은 $\frac{(e^x-1)^k}{k!}$ . 모든 $$k$$ 를 더하면

$\exp(e^x - 1) = \sum_n B_n \frac{x^n}{n!}$

가 벨 수 $$B_n$$ 의 EGF다. "구조 = exp(연결 조각)"이라는 exponential formula 의 사례다.

부분분수로 빠른 점화

선형 점화식의 생성 함수 $\frac{P(x)}{Q(x)}$ 에서 $$Q$$ 의 근으로 부분분수 분해하면 $a_n = \sum_i c_i r_i^n$ 꼴. 단, 정수 모듈러 환경에서는 근이 없을 수 있어, 보통 Kitamasa / Berlekekamp-Massey 로 점화 계수를 복원한 뒤 행렬 없이 $O(d \log d \log n)$ 에 $$a_n$$ 을 구한다.

연습 체크리스트

무게 제약 배낭을 "다항식 곱"으로 재해석하기.
자기 참조 구조(트리/괄호)에 이차 생성 함수 방정식 세우기.
큰 지수의 합성곱을 이진 거듭제곱 + NTT로.
라벨 구조에는 EGF, exp/log 변환 고려.

생성 함수는 "셈 문제를 대수 문제로 바꾸는 번역기"다. 식을 먼저 세우고, 계수 추출은 도구(FFT/부분분수/Kitamasa)에 맡겨라.

수열 연산	생성 함수 연산
$\(a_n + b_n\)$	$\(A(x) + B(x)\)$
합성곱 $\sum_k a_k b_{n-k}$	$A(x)\,B(x)$
이동 $a_{n-1}$	$x\,A(x)$
$n\ a_n$	$x\ A'(x)$
부분합 $\sum_{k\le n} a_k$	$\dfrac{A(x)}{1-x}$