第十六章：生成函數
生成函數是解決組合計數問題的最強大工具之一。它將一個序列轉化為一個形式冪級數，使我們能夠利用代數運算（如加法、乘法、微積分）來處理計數問題。
16.1 定義
對於序列 $a_0, a_1, a_2, \dots$，其生成函數 (Generating Function) 定義為：
$G(x) = a_0 + a_1x + a_2x^2 + a_3x^3 + \dots$
$G(x) = a_0 + a_1x + a_2x^2 + a_3x^3 + \dots$
關鍵在於將係數 $a_n$ 視為我們關心的計數結果。例如，對於序列 $1, 1, 1, \dots$，其生成函數是幾何級數 $\frac{1}{1-x}$。
🧪 生成函數詞典
點擊左邊的序列，查看其對應的封閉形式生成函數。
常見序列
- 1, 1, 1, ... (全為1)
- 1, 2, 3, 4, ... (自然數)
- 1, 0, 1, 0, ... (交替)
- 1, c, c^2, c^3, ... (幾何)
- 1, -1, 1, -1, ...
- 1, 2, 3, 2, 1, 0...
生成函數 $G(x)$
請選擇左側序列...
16.4 應用：求解斐波那契數列
斐波那契數列定義為 $F_0=0, F_1=1, F_n = F_{n-1} + F_{n-2}$。我們可以利用生成函數求出其通項公式。
教材來源：Mathematics for Computer Science (Lehman, Leighton, Meyer)