Generating Function And Recurrence Rela

官官方信息技术老师·16 页·深入（追求细节与边界）·0 次浏览·2 天前
✦ Generating Function And Recurrence Rela信息技术Generating Function Andsummay
生成函数递推关系组合数学离散分析

Generating Function 與遞推關係

从递推式到封闭公式，掌握系数提取与渐近分析

按 空格/→ 演示下一步

1 / 16 页

全部页面点击任意一页，跳回舞台从这页播放

生成函数递推关系组合数学离散分析

Generating Function 與遞推關係

从递推式到封闭公式，掌握系数提取与渐近分析

1第 1 页 · Generating Function 與遞推關係

什麼是生成函數

前頁我們看到了序列與遞推關係常常綁在一起——但更根本的問題是：給定一個序列 {aₙ}，能不能把它打包成一個代數物件？

本質
把序列的每一項 aₙ 當作某個冪級數中 xⁿ 的係數
形式定義 OGF
G(x) = a₀ + a₁x + a₂x² + ⋯ = Σaₙxⁿ，n 從 0 起
無損對應
在形式冪級數意義下，序列與生成函數一一對應，不丟資訊
運算轉譯
序列的離散操作（移位、卷積）變成函數上的代數操作（×x、×G）
圖書館的書籍索引对应 →生成函數

每本書=序列項 aₙ；分類編號=x 的冪次 n；整本索引=G(x)；讀回任一項=取 xⁿ 係數

G(x)=∑n=0∞anxnG(x) = \sum_{n=0}^{\infty} a_n x^n
2第 2 页 · 什麼是生成函數

生成函數的兩種形態

普通生成函數 OGF 與指數生成函數 EGF 的對比

生成函數的兩種形態
普通生成函數 OGF 與指數生成函數 EGF 的對比
3第 3 页 · 生成函數的兩種形態

生成函數的三大本領

上页我们知道生成函数有普通型和指数型两张脸，但手里有了这个工具，到底能干什么？答案有三件大事。

求通项公式
把序列对应的幂级数还原为封闭表达式，告别递推式一个个算
解递推关系
把递推变成关于 G(x) 的代数方程，求解后读出系数
解决计数问题
把组合约束翻译成 G(x) 的乘积，要啥个数就读 x^n 的系数
翻译官对应 →生成函数

序列说「递推」和「计数」，函数说「方程」和「系数」——两边话不通，它来翻

an=[xn] G(x)a_n = [x^n]\, G(x)
4第 4 页 · 生成函數的三大本領

解遞推關係的完整流程

這五步把遞推關係逐步轉成可直接讀出的通項公式。

1
列出方程
依題目條件寫出相鄰項之間的遞推關係
2
乘上xⁿ
給每項標上冪次，將序列轉成冪級數形式
3
全範圍求和
把所有 n 的項相加，形成生成函數方程
4
解函數方程
整理並求出生成函數的封閉形式
5
提取係數
取 A(x) 的 xⁿ 係數，得到序列通項
5第 5 页 · 解遞推關係的完整流程

Hanoi 問題的規則回顧

前頁展示了生成函數解遞推的完整流程，但要落實它，我們需要一個能自然導出遞推式的經典問題——河內塔。先把規則釐清。

場景設定
三根柱子 A、B、C；n 個大小相異的盤子初始全部疊在 A 上，大盤在下、小盤在上
移動約束
每次只能動一個盤子；任何時刻大盤都不能壓在小盤上方
起終目標
把所有 n 個盤子從 A 搬至 C，B 柱僅作為暫存中繼
書架疊書对应 →大盤不可壓小盤

厚書壓薄書會把書脊壓壞——盤子也是，越小越嬌貴，必須留在上面

H(n)=2 H(n−1)+1,H(1)=1H(n) = 2\,H(n-1) + 1,\quad H(1) = 1
6第 6 页 · Hanoi 問題的規則回顧

Hanoi 的遞推邏輯圖

讀法：fk 代表把 k 盤從來源移到目標；葉節點是最小盤直動，樹中間層的最大盤僅動一次。

图解渲染中…
a2：f2：把 2 盤從來源移到目標的子任務a8：盤3 為最大盤，整棵樹僅動這一次a4：盤1 為最小盤，葉節點直動
7第 7 页 · Hanoi 的遞推邏輯圖

遞推關係的精確推導

前頁用 Hanoi 問題建立了 a(n) = 2a(n−1)+1、a(1)=1 的遞推。這頁就一步步把 A(x) 解出來，看看生成函數如何把遞推『解開』成封閉式。

代入遞推
把 A(x)=Σa(n)xⁿ 中 n≥2 項用 2a(n−1)+1 替換，a(1) 單獨保留
指數平移
把 2a(n−1)xⁿ 改寫成 2x·Σa(m)xᵐ，讓 A(x) 自己出現
解代數方程
移項得 (1−2x)A(x)=x/(1−x)，解出有理式 A(x)
部分分式展開
拆成 1/(1−2x)−1/(1−x)，逐項讀出 a(n)=2ⁿ−1
解聯立代數方程对应 →提取並分解 A(x)

把含 A(x) 的等式當普通方程，先孤立再拆成幾何級數

A(x)=x(1−x)(1−2x)=11−2x−11−x⇒a(n)=2n−1A(x)=\dfrac{x}{(1-x)(1-2x)}=\dfrac{1}{1-2x}-\dfrac{1}{1-x}\Rightarrow a(n)=2^n-1
8第 8 页 · 遞推關係的精確推導

生成函數法五步解題

生成函數解遞推，固定五步走完，從包裝序列到讀回閉式。

1
設生成函數
把 aₙ 包成 A(x)=Σaₙxⁿ，把序列問題變成函數問題
2
兩邊乘 xⁿ
對遞推式兩側同乘 xⁿ，讓求和後的指數一致
3
對 n 求和
從 n 起始值到無窮，把離散遞推化為無窮級數等式
4
化簡為 A(x)
把 Σaₙxⁿ 等項合併回 A(x)，得到 A(x) 的封閉方程
5
展開取係數
將 A(x) 展開成冪級數，讀回 aₙ 的閉式表達
9第 9 页 · 生成函數法五步解題

Hanoi 生成函數推導圖

從遞推式出發，沿箭頭順序完成六步代數推導，得到封閉解。

图解渲染中…
a1：a(n) = 2·a(n-1) + 1，a(1)=1a3：(1-2x)·A(x) = x/(1-x)a4：A(x) = 1/(1-2x) - 1/(1-x)a6：a(n) = 2^n - 1
10第 10 页 · Hanoi 生成函數推導圖

三柱 vs 四柱的複雜度鴻溝

多一根柱子，递推从有精确公式跌入只能靠算法逼近的困境。

三柱 Hanoi
  • 递推：T(n) = 2T(n−1) + 1
  • 封闭解：T(n) = 2ⁿ − 1（精确）
  • 复杂度：Θ(2ⁿ)，纯指数
  • 求解：直接展开递推即可
四柱 Hanoi
  • 递推：min_k [2T(k) + 2ⁿ⁻ᵏ − 1]
  • 封闭解：无封闭表达式
  • 复杂度：亚指数级（远小于 2ⁿ）
  • 求解：必须枚举 k 找最优
三柱可代公式秒解；四柱无封闭解，只能数值逼近最优。
11第 11 页 · 三柱 vs 四柱的複雜度鴻溝

Frame-Stewart 算法的思想

上頁看到四柱比三柱快得多，但「快」是靠什麼策略實現的？1975年 Frame 與 Stewart 提出了一個三階段拆分法，至今仍是四柱 Hanoi 的最佳算法。

三階段拆分
把 n 個盤子拆成「前 k」和「後 n−k」兩批，分三步走完
階段一：預部署
用四柱把頂部 k 個盤子暫時移到輔助柱，騰出一根柱子
階段二：主力搬運
僅用三柱把剩下的 n−k 個盤子直接送到目標柱
階段三：合流
再用四柱把輔助柱上的 k 個盤子疊回目標柱
最優 k 隨 n 變
k 太小等於沒省，k 太大反而浪費，需取使總步數最小的值
搬家先寄小件到倉庫对应 →Frame-Stewart 三階段

小件先寄（階段一）→ 大件直送（階段二）→ 小件取回（階段三）

T(n)=min⁡1≤k<n[2 T(k)+2n−k−1]T(n)=\min_{1\le k<n}\bigl[2\,T(k)+2^{n-k}-1\bigr]
12第 12 页 · Frame-Stewart 算法的思想

Frame-Stewart 的遞推樹

上為 n=6 拆解樹；下為 n=1~6 對應最優 k* 速查表。

图解渲染中…
A：遞推根：n=6, 選最優 k*=3, 共 17 步B：上段 T(k,4)：頂盤用 4 柱C：中段 2^(n-k)-1：底盤用 3 柱D：下段 T(k,4)：回收頂盤到終點
13第 13 页 · Frame-Stewart 的遞推樹

生成函數方法地圖

  • ✓生成函數 = 編碼→運算→解碼，把序列壓進函數空間
  • ✓五步解題是套路，變形化簡才是真正考驗
  • ✓Hanoi 證明：算法改進遠勝硬體升級
  • ✓遞推結構決定工具選型
  • ✓最優分組策略是四柱降複雜度的根源
延伸主题：指數生成函數處理排列生成函數與漸近分析偏微分方程的母函數解法
14第 14 页 · 生成函數方法地圖

核心概念自測

点击作答

將遞推式 aₙ = 2aₙ₋₁ + n（n≥1）兩邊同乘 xⁿ 並對 n 從 1 起求和，其中 A(x)=∑aₙxⁿ。右端 aₙ₋₁·xⁿ 對應的生成函數表達為？

15第 15 页 · 核心概念自測

課後思考

先獨立思考，再看參考答案。三問覆蓋核心回顧、應用深化與邊界探索。

1生成函數把遞推關係變成「係數提取」，本質上完成了怎樣的翻譯？為什麼這種翻譯對線性遞推特別有效？

参考答案本質是「序列運算 → 冪級數運算」的翻譯：移位變乘 x、常數倍變係數乘法、捲積變冪級數乘法。線性遞推恰好落在這個代數閉包內，所以可被統一解出。

2Frame-Stewart 至今沒有閉式解，這是否暗示四柱 Hanoi 的最優結構無法被任何「簡潔」的生成函數捕捉？

参考答案是的。Frame-Stewart 的最優拆分點 k(n) 隨 n 變動，遞推本身含 min 算子，無法寫成單一代數恆等式。這暗示問題的本質是「分段最優」而非「全域閉式」。

3若遞推項變成非線性（如 aₙ = aₙ₋₁² + 1），生成函數五步法在哪一步最先斷裂？

参考答案第一步列方程就斷裂。冪級數乘法雖然封閉（兩冪級數相乘仍是冪級數），但 aₙ₋₁² 對應的是「已知係數的非線性組合」——無法用 G(x) 的代數表達式封閉寫出。

16第 16 页 · 課後思考