04.2 生成函數：把數列變成多項式的魔法#

Euler 的發明：為了「分拆整數」#

1740 年代，Euler 面對一個用當時工具無法下手的問題：整數分拆（integer partition）——把 $n$ 寫成正整數之和的方法數。例如 $4 = 4 = 3+1 = 2+2 = 2+1+1 = 1+1+1+1$ ，故 $p(4) = 5$ 。分拆沒有明顯的遞迴式、沒有特徵方程、沒有排列組合公式。

Euler 的天才一步：不問 $p(n)$ 本身，而問整條數列。定義

\[P(x) = \sum_{n=0}^{\infty} p(n)\, x^n,\]

他發現這個形式冪級數可以像多項式一樣相乘——乘法對應的分類恰好是分拆的結構分解。這一「形式化的把戲」後來發展成組合學的通用機器，並在 1960 年代由 Knuth 引入演算法分析，成為平均複雜度分析的標準工具（參見 Sedgewick–Flajolet《Analysis of Algorithms》）。

哲學宣告：生成函數是「曬衣繩」——我們把數列掛上去（係數位），用多項式的代數運算搬動、組合它們，最後再從係數位把答案取回來。 $x$ 是形式的，不必收斂、不必代入數值。

基本操作字典#

數列操作	生成函數操作
$a_n$	$A(x) = \sum a_n x^n$
$b_n = a_{n+1}$	$(A(x) - a_0)/x$
$b_n = a_n + c_n$	$A(x) + C(x)$
$b_n = \sum_{k=0}^n a_k c_{n-k}$ （捲積）	$A(x)\,C(x)$
$b_n = n\,a_n$	$x A'(x)$
選 0 或 1 次	$1 + x$
選任意多次	$\frac{1}{1-x}$
選偶數次	$\frac{1}{1-x^2}$

捲積是核心： $\sum_k a_k c_{n-k}$ 正是「第一步佔 $k$ 、其餘佔 $n-k$ 」的分類計數——乘法法則（03.1）與加法法則在生成函數世界裡就是乘法與加法。

範例：幾何級數家族#

\[\frac{1}{1-x} = 1 + x + x^2 + \cdots, \qquad \frac{1}{(1-x)^m} = \sum_{n \ge 0} \binom{n+m-1}{m-1} x^n.\]

第二式是「 $n$ 個相同物品放入 $m$ 個不同盒」（重複組合，stars and bars）的生成函數——組合學最基本的計數在代數上只是一次「取倒數」。

生成函數解遞迴#

Fibonacci 完整示範#

設 $F(x) = \sum_{n\ge0} F_n x^n$ ， $F_0 = 0, F_1 = 1$ 。把 $F_n = F_{n-1} + F_{n-2}$ （ $n \ge 2$ ）兩邊乘 $x^n$ 對 $n \ge 2$ 求和：

\[F(x) - x = x\,(F(x) - F_0) + x^2 F(x)$$ $$F(x) = \frac{x}{1 - x - x^2}.\]

部分分式分解（特徵根 $\varphi, \psi$ 又出現了！）：

\[F(x) = \frac{1}{\sqrt5}\left(\frac{1}{1-\varphi x} - \frac{1}{1-\psi x}\right),\]

讀出係數即得 Binet 公式 $F_n = \frac{\varphi^n - \psi^n}{\sqrt5}$ ——03 章的特徵方程法在這裡以部分分式的面目重現，兩種方法是同一件事的兩種語言。

漢諾塔再訪#

$T_n = 2T_{n-1} + 1$ ， $T_0 = 0$ ：

\[T(x) - 0 = 2x\,T(x) + \frac{x}{1-x} \implies T(x) = \frac{x}{(1-x)(1-2x)}.\]

部分分式： $T(x) = \frac{-1}{1-x} + \frac{1}{1-2x}$ ，故 $T_n = 2^n - 1$ 。與 04.1 的迭代法相比，生成函數路線機械化了：不用靈感，只按流程。

Catalan 數的三行證明#

合法括號串滿足結構方程「合法串 = $(A)B$ ， $A, B$ 皆合法」：

\[C(x) = 1 + x\,C(x)^2 \implies C(x) = \frac{1 - \sqrt{1-4x}}{2x},\]

取展開 $C(x) = \sum_{n\ge0} \frac{1}{n+1}\binom{2n}{n} x^n$ ，即 $C_n = \frac{1}{n+1}\binom{2n}{n}$ 。04.1 章說「遞迴是文法」，這裡看到：文法（結構方程）直接變成代數方程。

from fractions import Fraction

def poly_mult(a, b, terms):
    return [sum(a[k]*b[n-k] for k in range(min(n, len(a)-1) + 1)
                if n - k < len(b)) for n in range(terms)]

# 驗證：1/(1-x-x^2) 的前 10 項係數 = Fibonacci
F = [0, 1]
for _ in range(8): F.append(F[-1] + F[-2])
one = [1] + [0]*15
denom = [1, -1, -1]
# (1-x-x^2) * F(x) 應等於 x
prod = poly_mult(denom, F, 10)
print(prod)   # [0, 1, 0, 0, ..., 0] ✓

# 驗證 Catalan：C(x) = 1 + x C(x)^2
C = [1]
for _ in range(9):
    C2 = poly_mult(C, C, 10)
    C = [1] + [C2[i-1] if i < len(C2) else 0 for i in range(1, 10)]
from math import comb
assert all(C[n] == comb(2*n, n)//(n+1) for n in range(10))
print("Catalan 驗證通過：", C[:6])

乘法計數 I：整數分拆#

Euler 的分拆生成函數#

每個正整數 $k$ 「可選用任意多次」，貢獻 $\frac{1}{1-x^k}$ ，全部相乘：

\[\sum_{n\ge0} p(n) x^n = \prod_{k=1}^{\infty} \frac{1}{1-x^k}.\]

逐項檢驗： $x^4$ 的係數來自 $4, 2+2, 3+1, 2+1+1, 1+1+1+1$ 的選法，恰 5 種。無窮乘積壓縮了「任意多件、任意規格」的全部組合邏輯。

限制版一學就會： - 各部分互異： $\prod_k (1 + x^k)$ 。 - 只用奇數部分： $\prod_{k \text{ 奇}} \frac{1}{1-x^k}$ 。

Euler 用部分分式與三角恆等操作證明驚人的定理性質：

Euler 恆等式（1748）：把 $n$ 分拆成互異部分的方法數 = 分拆成奇數部分的方法數。

生成函數證明：互異分拆 $\prod_k (1+x^k) = \prod_k \frac{1-x^{2k}}{1-x^k} = \prod_{k \text{ 奇}} \frac{1}{1-x^k}$ ——奇數因子上下相消。 $\blacksquare$

一個純組合的事實，被代數「算」了出來；今日它已有雙射證明（Glaisher 對應），兩種證明的對照正是本課程的方法論主題。

乘法計數 II：指數生成函數（EGF）#

排列與標號物件要除以 $n!$ ——於是改用指數生成函數：

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

它的乘法正是標號結構的組合：兩個標號集交錯合併的方法數由 $\binom{n}{k}$ 捕捉，恰被 $\frac{x^n}{n!}$ 的分母吸收。

範例：錯位排列的 EGF#

\[\hat D(x) = \sum_n D_n \frac{x^n}{n!} = \frac{e^{-x}}{1-x}.\]

證明：一個「全錯位」排列的循環結構不含 1-循環；而任意排列的 EGF 是 $e^{\sum_k x^k/k} = \frac{1}{1-x}$ （因 $\frac{x^k}{k}$ 對應 $k$ -循環的貢獻）。禁用 1-循環即把 $e^x$ 那一項拿掉。讀出係數： $[x^n]\,\frac{e^{-x}}{1-x} = \sum_{k=0}^n \frac{(-1)^k}{k!}$ ，即 $D_n = n!\sum_k \frac{(-1)^k}{k!}$ ——與 03.3 的容斥答案完全吻合。 $\blacksquare$

三大計數傳統就此合流：容斥（03.3）、遞迴（04.1）、生成函數（本節）給出同一個 $D_n$ 。理解它們的等價與分工，是組合學素養的分水嶺。

機率與演算法分析的入口#

生成函數還是機率母函數：若 $X$ 取非負整數值且 $P(X = k) = a_k$ ，則 $A(x) = \sum a_k x^k$ 滿足

\[E[X] = A'(1), \qquad \text{Var}(X) = A''(1) + A'(1) - A'(1)^2.\]

例：擲兩骰子和的母函數 $\left(\frac{x + x^2 + \cdots + x^6}{6}\right)^2$ ，對 $x$ 求導在 $x=1$ 處取值即期望值 7。這套技術在 04.3 節分析隨機演算法（如快排的平均比較次數 $\approx 2n \ln n$ ）時是標準配備。

章末小結#

生成函數把數列掛在 $x^n$ 的係數上：加法對應分類，乘法對應兩階段選擇，求導對應加權。
解線性遞迴：化為有理函數、部分分式、讀係數——與特徵方程法異曲同工。
結構方程（如 $C = 1 + xC^2$ ）直接翻譯成代數方程，是組合文法的機器化。
普通生成函數管「多重集」（分拆），指數生成函數管「標號結構」（排列、循環）。
Euler 恆等式示範「代數推出組合事實」；錯位排列示範「三法合流」。

下一步#

生成函數讓我們能「算出」遞迴的封閉式與漸近行為，但工程上更常問的是：這個演算法到底要多快？ $n$ 放大十倍，時間放大幾倍？下一節「04.3 演算法複雜度初探」把計數工具收攏為大 $O$ 、 $\Theta$ 、 $\Omega$ 記號，推導 Master 定理，並用 $n!$ 、 $2^n$ 、 $n \log n$ 的增長賽跑，解釋為何 P vs NP 是本世紀最重要的未解問題——離散數學的「可操作性」將在此收網。

數列操作	生成函數操作
\(a_n\)	\(A(x) = \sum a_n x^n\)
\(b_n = a_{n+1}\)	\((A(x) - a_0)/x\)
\(b_n = a_n + c_n\)	\(A(x) + C(x)\)
\(b_n = \sum_{k=0}^n a_k c_{n-k}\) （捲積）	\(A(x)\,C(x)\)
\(b_n = n\,a_n\)	\(x A'(x)\)
選 0 或 1 次	\(1 + x\)
選任意多次	\(\frac{1}{1-x}\)
選偶數次	\(\frac{1}{1-x^2}\)