생성함수

개요 — 동기·문제의식

생성함수는 수열을 하나의 형식적 거듭제곱급수로 묶어 다루는 언어다. 수열 $a_0,a_1,a_2,\dots$ 를 직접 나열하는 대신 $$A(x)=\sum_{n\ge0}a_nx^n$$ 으로 포장하면, 점화식·분해·합성·곱셈이 대수 조작으로 바뀐다.¹

그래프이론에서는 경로와 walk의 수, labeled tree의 수, 연결 그래프와 전체 그래프의 관계, 평면 tree와 Catalan 구조가 모두 생성함수로 자연스럽게 표현된다. Stanley EC2는 특히 exponential formula, tree enumeration, Lagrange inversion을 통해 이 관점을 체계화한다.²

이 페이지는 graphs basics and trees의 그래프 구조를 세는 쪽으로 확장하고, symmetric functions로 가는 열거조합론의 입구를 만든다.

직관

생성함수는 수열의 데이터베이스이면서 계산기다. 계수 $[x^n]A(x)$ 는 $n$번째 답을 꺼내는 명령이고, 곱 $A(x)B(x)$ 는 크기 $n$ 대상을 두 부분으로 나누는 모든 방법을 합산한다.

ordinary generating function은 unlabeled 또는 선형 크기 분해에 자주 쓰이고, exponential generating function은 labeled objects를 다룰 때 자연스럽다. labeled set을 두 블록으로 나누는 방법에는 binomial coefficient가 끼어들기 때문에 $n!$ 로 나눈 EGF가 곱셈을 깨끗하게 만든다.

정의

ordinary generating function (OGF): 수열 $(a_n)$ 의 OGF는 $$A(x)=\sum_{n\ge0}a_nx^n.$$ 계수 추출은 $[x^n]A(x)=a_n$ 으로 쓴다.

exponential generating function (EGF): 수열 $(a_n)$ 의 EGF는 $$\widehat A(x)=\sum_{n\ge0}a_n\frac{x^n}{n!}.$$ 라벨이 붙은 $n$-원소 집합 위 구조를 셀 때 자주 나타난다.

형식적 급수: 수렴반경보다 계수 조작이 중요하다. 조합론에서는 $x$ 를 작은 실수로 대입하기보다 계수들을 보존하는 기호로 다루는 경우가 많다.

recurrence solving: 점화식에 생성함수를 곱해 합하면, shift가 $x$ 곱셈으로 바뀌어 대수 방정식을 얻는다.

주요 정리

정리 1 (선형 점화식과 유리함수). 상수계수 선형 점화식을 만족하는 수열의 OGF는 유리함수다.

예. $F_0=0,F_1=1,F_n=F_{n-1}+F_{n-2}$ 라 하자. $F(x)=\sum_{n\ge0}F_nx^n$ 이면 $$F(x)=x+xF(x)+x^2F(x),$$ 따라서 $$F(x)=\frac{x}{1-x-x^2}.$$ 분모는 점화식의 characteristic polynomial을 반영한다.

정리 2 (곱셈 원리). $A(x)=\sum a_nx^n$, $B(x)=\sum b_nx^n$ 이면 $$[x^n]A(x)B(x)=\sum_{i+j=n}a_ib_j.$$

정리 3 (exponential formula). labeled structure가 connected components의 set으로 유일하게 분해되고, connected structures의 EGF가 $C(x)$ 이면 전체 structures의 EGF는 $$A(x)=\exp(C(x)).$$ ²

의미. 전체 graph는 connected components의 set이다. 모든 labeled graph의 EGF를 알면 connected labeled graph의 EGF는 logarithm으로 얻고, 반대로 connected class를 알면 exponential로 전체 class를 얻는다.

정리 4 (rooted labeled trees). rooted labeled tree 수 $r_n$ 의 EGF $R(x)=\sum_{n\ge1}r_nx^n/n!$ 는 $$R(x)=x\exp(R(x))$$ 을 만족하고, $r_n=n^{n-1}$ 이다.³

정리 5 (walk generating function). 유한 그래프의 인접행렬을 $A$ 라 하면, 길이 $k$ walk 수는 $A^k$ 에 들어 있고 형식적으로 $$\sum_{k\ge0}A^kx^k=(I-xA)^{-1}$$ 이다.⁴

의미. 그래프의 path-like 구조는 행렬 생성함수와 연결된다. 이는 spectral graph theory에서 eigenvalue로 walk growth를 읽는 관점으로 이어진다.

정리 6 (Lagrange inversion 안내). $Y=x\Phi(Y)$ 꼴의 함수방정식은 계수 $[x^n]Y(x)$ 를 닫힌 형태로 주는 Lagrange inversion으로 풀 수 있다.⁵

의미. tree는 재귀적으로 정의되기 때문에 생성함수 방정식이 자기 자신을 포함한다. Lagrange inversion은 그 재귀를 계수 공식으로 바꾸는 표준 도구다.

예제

예제 1 (경로 graph의 독립집합). path $P_n$ 의 independent set 수 $a_n$ 은 $a_n=a_{n-1}+a_{n-2}$ 를 만족한다. 마지막 정점을 쓰지 않거나, 쓰고 그 전 정점을 못 쓰는 두 경우로 나뉜다. 따라서 Fibonacci형 OGF가 나온다.

예제 2 (cycle의 독립집합). $C_n$ 의 독립집합은 첫 정점을 쓰는 경우와 쓰지 않는 경우로 나누어 path 문제로 환원한다. 작은 graph family도 생성함수로 체계적으로 세어진다.

예제 3 (walk 수). $A^3$ 의 $(i,j)$ 성분은 $v_i$ 에서 $v_j$ 로 가는 길이 3 walk 수다. 모든 길이의 walk를 모으면 $(I-xA)^{-1}$ 의 $(i,j)$ 성분이 된다.

예제 4 (plane binary trees). plane binary tree의 OGF $T(x)$ 는 $T=1+xT^2$ 를 만족한다. root가 없거나, root와 왼쪽·오른쪽 subtree 두 개로 나뉘기 때문이다. 계수는 Catalan 수다.

예제 5 (labeled rooted trees). rooted labeled tree는 $R=x\exp(R)$ 로 표현된다. 계수 추출 결과 $n^{n-1}$ 이 나오고, root를 잊으면 Cayley 수 $n^{n-2}$ 로 이어진다.

예제 6 (connected graph). $2^{\binom n2}$ 는 $n$개 labeled vertices 위의 모든 graph 수다. EGF의 logarithm을 취하면 connected labeled graph 수열을 얻을 수 있다.

예제 7 (set partition). block이 connected component처럼 작동하면 EGF에 exponential이 나타난다. Bell number의 EGF가 대표적이다.

예제 8 (Schur 함수로 가는 길). 단일 변수 생성함수에서 여러 변수와 대칭성을 함께 추적하면 symmetric functions가 등장한다. coefficient extraction이 partition과 tableau의 언어로 정교해진다.

흔한 오해와 함정

• 생성함수를 해석함수로만 생각하기 — 조합론에서는 수렴보다 형식적 계수 조작이 먼저다.
• OGF와 EGF를 섞기 — labeled set 분해에는 보통 EGF가 자연스럽고, sequence류에는 OGF가 자연스럽다.
• 곱셈의 순서를 잊기 — OGF 곱은 ordered decomposition인지 unordered decomposition인지 모델을 확인해야 한다.
• 초기조건을 빠뜨리기 — 점화식을 생성함수로 바꿀 때 작은 $n$ 항들이 분자를 결정한다.
• 함수방정식만 세우고 계수 추출을 미루기 — Lagrange inversion, partial fractions, singularity analysis 등 추출 도구가 함께 필요하다.
• 그래프의 path와 lattice path를 혼동하기 — 둘 다 path지만 세는 대상과 생성함수는 다를 수 있다.

큰 그림 / 연결

graphs basics and trees의 tree는 생성함수의 가장 좋은 실험장이다. tree는 root와 subtrees로 재귀 분해되고, forest는 set of trees로 분해된다.

spectral graph theory에서는 walk enumeration이 matrix generating function으로 이어진다. $A^k$ 의 계수와 eigenvalue는 그래프 위 이동의 성장률을 설명한다.

extremal and ramsey는 존재와 강제의 언어이고, 생성함수는 세기의 언어다. 같은 graph class라도 한쪽은 최대 간선 수를 묻고, 다른쪽은 몇 개인지 묻는다.

symmetric functions는 생성함수의 다변수·대칭화된 확장이다. Schur 함수, RSK, representation theory는 단순 수열보다 훨씬 많은 구조를 계수에 담는다.

stanley ec2는 이 페이지의 주 source다. Diestel이 graph structure를 제공한다면, Stanley는 그 structure를 세는 formal power series 도구를 제공한다.

연습문제

1. Fibonacci 수열의 OGF를 직접 유도하라.
2. $a_n=2a_{n-1}$, $a_0=1$ 의 OGF를 구하라.
3. $A(x)B(x)$ 의 계수 공식이 convolution임을 증명하라.
4. path $P_n$ 의 independent set 수가 Fibonacci 점화식을 만족함을 보이라.
5. $T=1+xT^2$ 에서 처음 다섯 계수를 계산하라.
6. $R=x\exp(R)$ 가 rooted labeled tree의 분해를 어떻게 표현하는지 설명하라.
7. 모든 labeled graph의 EGF에서 connected graph EGF가 logarithm으로 나오는 이유를 exponential formula로 설명하라.
8. $(I-xA)^{-1}$ 의 형식적 전개를 확인하라.
9. OGF와 EGF 중 어느 쪽을 써야 하는지 labeled set partition 예로 설명하라.

관련 개념

• graphs basics and trees — tree, forest, path의 구조적 출발점
• spectral graph theory — adjacency powers와 walk generating function
• symmetric functions — 다변수 대칭 생성함수의 세계
• extremal and ramsey — 세기와 강제의 대비
• stanley ec2 — 생성함수와 열거조합론의 주 source
• reading path diestel — 그래프론 뒤 열거조합론으로 넘어가는 경로

각주