第8章 高级计数技术 (Advanced Counting Techniques)

一、导读

1.1 本章学习目标

完成本章学习后，你将能够：

理解递推关系的概念，能够从实际问题中建立递推关系

掌握线性齐次递推关系的特征方程求解法

理解非齐次递推关系的求解方法

掌握生成函数的定义和基本性质

能够使用生成函数解决组合计数问题

理解分治算法的递推关系及其求解

掌握主定理的应用条件和步骤

将高级计数技术应用于算法分析和组合优化

理解包含-排除原理的高级应用

掌握Polya计数理论的基本思想

1.2 为什么本章如此重要

高级计数技术是分析复杂算法和解决困难组合问题的关键工具。

在算法分析中：归并排序、快速排序等分治算法的时间复杂度由递推关系描述。掌握求解方法是理解算法效率的基础。动态规划的状态转移方程本质上是递推关系。

在组合数学中：生成函数将序列转化为函数，利用微积分和代数工具解决计数问题。这种方法统一了多种看似不相关的计数技巧，是组合数学中最强大的工具之一。

在动态规划中：状态转移方程本质上是递推关系。理解递推有助于设计更高效的DP算法，如矩阵链乘法、最长公共子序列等。

在编译器设计中：语法分析器的状态数、解析树数量都涉及复杂计数。正则表达式引擎的实现依赖于有限自动机理论，其状态数计算需要高级计数技术。

在密码学中：某些攻击的复杂度分析需要求解递推关系。分组密码的安全性分析涉及布尔函数的非线性度计数。

在化学信息学中：分子异构体的计数使用Polya计数理论。化学物质的结构枚举需要生成函数方法。

在统计物理中：配分函数的计算涉及大量微观状态的计数。伊辛模型的解需要使用生成函数和递推关系。

1.3 核心问题引导

在学习本章之前，请思考以下问题：

斐波那契数列的通项公式如何推导？

为什么归并排序的时间复杂度是 O(n log n)？

什么是生成函数？它如何帮助解决计数问题？

递推关系 aₙ = aₙ₋₁ + aₙ₋₂ 与黄金比例有什么关系？

主定理的三个情况分别对应什么场景？

如何用生成函数计算掷骰子得到特定和的方式数？

非齐次递推关系与齐次递推关系的解法有什么不同？

卡特兰数的生成函数是什么？

什么是指数生成函数？它与普通生成函数有什么区别？

如何处理带有约束条件的计数问题？

二、核心概念详解

8.1 递推关系

定义

递推关系将序列的第n项表示为前面若干项的函数。

一般形式：aₙ = f(aₙ₋₁, aₙ₋₂, ..., aₙ₋ₖ, n)

需要k个初始条件才能唯一确定序列。

阶数：递推关系中涉及的最大下标差。例如 aₙ = aₙ₋₁ + aₙ₋₂ 是2阶递推。

线性 vs 非线性：如果f是各aᵢ的线性组合，则为线性递推；否则为非线性。

常系数 vs 变系数：如果系数不随n变化，则为常系数递推。

线性齐次递推关系

形式：aₙ = c₁aₙ₋₁ + c₂aₙ₋₂ + ... + cₖaₙ₋ₖ

其中cᵢ是常数，cₖ ≠ 0。

"线性"意味着各项都是一次的；"齐次"意味着没有与n有关的额外项（即右边为0）。

特征方程法

步骤：

写出特征方程：rᵏ - c₁rᵏ⁻¹ - c₂rᵏ⁻² - ... - cₖ = 0

求特征根 r₁, r₂, ..., rₘ（可能有重根）

根据根的情况写出通解

不同实根：如果特征方程有k个不同实根 r₁, r₂, ..., rₖ，则通解为：

$$a_n = \alpha_1 r_1^n + \alpha_2 r_2^n + ... + \alpha_k r_k^n$$

其中αᵢ由初始条件确定。

重根：如果r是m重根，则对应部分为：

$$(\alpha_1 + \alpha_2 n + ... + \alpha_m n^{m-1}) r^n$$

复根：如果特征方程有共轭复根 α ± βi，可以写为极坐标形式 re^(±iθ)，其中 r = √(α²+β²)，θ = arctan(β/α)。对应部分为：

$$r^n (A \cos(n\theta) + B \sin(n\theta))$$

或使用欧拉公式写为：

$$r^n (C_1 e^{in\theta} + C_2 e^{-in\theta})$$

求解步骤详解：

写出特征方程：将 aₙ = c₁aₙ₋₁ + ... + cₖaₙ₋ₖ 改写为 rᵏ - c₁rᵏ⁻¹ - ... - cₖ = 0

求解特征根：使用代数方法或数值方法求根

写出通解形式：根据根的类型（实根、重根、复根）写出通解

代入初始条件：解线性方程组确定系数

验证：检查所得公式是否满足递推关系和初始条件

示例：斐波那契数列

Fₙ = Fₙ₋₁ + Fₙ₋₂，F₀ = 0, F₁ = 1

步骤1：特征方程为 r² - r - 1 = 0

步骤2：特征根为 $r_1 = \frac{1+\sqrt{5}}{2} = \phi$（黄金比例≈1.618），$r_2 = \frac{1-\sqrt{5}}{2}$（≈-0.618）

步骤3：通解为 $F_n = \alpha_1 \phi^n + \alpha_2 r_2^n$

步骤4：代入初始条件：

• F₀ = 0: α₁ + α₂ = 0
• F₁ = 1: α₁φ + α₂r₂ = 1

由第一个方程得 α₂ = -α₁。代入第二个方程：

α₁(φ - r₂) = 1

α₁(√5) = 1

α₁ = 1/√5, α₂ = -1/√5

步骤5：因此：

$$F_n = \frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^n - \left(\frac{1-\sqrt{5}}{2}\right)^n\right]$$

这就是比内公式（Binet's Formula）。

验证：

• F₀ = (1/√5)(1 - 1) = 0 ✓
• F₁ = (1/√5)(φ - r₂) = (1/√5)(√5) = 1 ✓
• 检查递推：Fₙ = Fₙ₋₁ + Fₙ₋₂（略）

有趣性质：由于 |r₂| < 1，当n很大时，r₂ⁿ 趋近于0。因此 Fₙ ≈ φⁿ/√5。实际上，Fₙ 是最接近 φⁿ/√5 的整数。

黄金比例的联系：lim_{n→∞} F_{n+1}/F_n = φ。这解释了为什么自然界中许多生长模式（如向日葵种子排列、鹦鹉螺壳螺旋）都与斐波那契数列相关。

更多示例

示例1：求解 aₙ = 3aₙ₋₁ - 2aₙ₋₂，a₀ = 1, a₁ = 3

特征方程：r² - 3r + 2 = 0

因式分解：(r-1)(r-2) = 0

特征根：r₁ = 1, r₂ = 2

通解：aₙ = α₁·1ⁿ + α₂·2ⁿ = α₁ + α₂·2ⁿ

代入初始条件：

a₀ = 1: α₁ + α₂ = 1

a₁ = 3: α₁ + 2α₂ = 3

解得：α₂ = 2, α₁ = -1

因此：aₙ = -1 + 2·2ⁿ = 2ⁿ⁺¹ - 1

验证：a₀ = 2-1 = 1 ✓, a₁ = 4-1 = 3 ✓, a₂ = 3×3-2×1 = 7 = 8-1 ✓

示例2：求解 aₙ = 2aₙ₋₁ - aₙ₋₂，a₀ = 0, a₁ = 1

特征方程：r² - 2r + 1 = 0

因式分解：(r-1)² = 0

特征根：r = 1（二重根）

通解：aₙ = (α₁ + α₂n)·1ⁿ = α₁ + α₂n

代入初始条件：

a₀ = 0: α₁ = 0

a₁ = 1: α₂ = 1

因此：aₙ = n

验证：aₙ = 2(n-1) - (n-2) = 2n-2-n+2 = n ✓

这个例子展示了重根情况的处理。

8.2 非齐次递推关系

形式

aₙ = c₁aₙ₋₁ + c₂aₙ₋₂ + ... + cₖaₙ₋ₖ + f(n)

其中f(n)是与n有关的函数（称为"驱动项"或"非齐次项"）。

求解方法

通解 = 齐次解 + 特解

求齐次解：忽略f(n)，用特征方程法求解，得到 aₙ^(h)

求特解：根据f(n)的形式猜测特解形式 aₙ^(p)，代入原方程确定系数

合并：aₙ = aₙ^(h) + aₙ^(p)

代入初始条件：确定齐次解中的系数

常见f(n)的特解形式：

重要规则：如果猜测形式与齐次解重复（即猜测形式的底数是特征根），需要乘以n的适当幂次使其线性无关。

示例：如果f(n) = 2ⁿ，而2是特征方程的单根，则特解形式应为 An·2ⁿ 而不是 A·2ⁿ。

示例详解

示例1：求解 aₙ = 2aₙ₋₁ + 3ⁿ，a₀ = 1

步骤1：齐次解

齐次方程：aₙ = 2aₙ₋₁

特征方程：r - 2 = 0，r = 2

齐次解：aₙ^(h) = α·2ⁿ

步骤2：特解

f(n) = 3ⁿ，猜测 aₙ^(p) = A·3ⁿ

（3不是特征根，所以不需要乘以n）

代入原方程：

A·3ⁿ = 2A·3ⁿ⁻¹ + 3ⁿ

A·3ⁿ = (2A/3)·3ⁿ + 3ⁿ

A = 2A/3 + 1

A/3 = 1

A = 3

所以 aₙ^(p) = 3·3ⁿ = 3ⁿ⁺¹

步骤3：通解

aₙ = α·2ⁿ + 3ⁿ⁺¹

步骤4：代入初始条件

a₀ = 1: α + 3 = 1，α = -2

最终解：aₙ = -2·2ⁿ + 3ⁿ⁺¹ = 3ⁿ⁺¹ - 2ⁿ⁺¹

验证：

a₀ = 3 - 2 = 1 ✓

a₁ = 9 - 4 = 5

检查递推：a₁ = 2a₀ + 3¹ = 2×1 + 3 = 5 ✓

示例2：求解 aₙ = 2aₙ₋₁ + n，a₀ = 1

步骤1：齐次解同上：aₙ^(h) = α·2ⁿ

步骤2：特解

f(n) = n 是一次多项式，猜测 aₙ^(p) = An + B

（1不是特征根2，所以不需要调整）

代入原方程：

An + B = 2[A(n-1) + B] + n

An + B = 2An - 2A + 2B + n

An + B = (2A+1)n + (2B-2A)

比较系数：

A = 2A + 1 → A = -1

B = 2B - 2A → B = 2B + 2 → B = -2

所以 aₙ^(p) = -n - 2

步骤3：通解

aₙ = α·2ⁿ - n - 2

步骤4：代入初始条件

a₀ = 1: α - 2 = 1，α = 3

最终解：aₙ = 3·2ⁿ - n - 2

验证：

a₀ = 3 - 0 - 2 = 1 ✓

a₁ = 6 - 1 - 2 = 3

检查递推：a₁ = 2a₀ + 1 = 2×1 + 1 = 3 ✓

示例3：求解 aₙ = 2aₙ₋₁ + 2ⁿ，a₀ = 1

注意：这里 f(n) = 2ⁿ，而2是特征根。

步骤1：齐次解：aₙ^(h) = α·2ⁿ

步骤2：特解

由于2是特征根，猜测 aₙ^(p) = An·2ⁿ（乘以n）

代入原方程：

An·2ⁿ = 2A(n-1)·2ⁿ⁻¹ + 2ⁿ

An·2ⁿ = A(n-1)·2ⁿ + 2ⁿ

An = A(n-1) + 1

An = An - A + 1

0 = -A + 1

A = 1

所以 aₙ^(p) = n·2ⁿ

步骤3：通解

aₙ = α·2ⁿ + n·2ⁿ = (α + n)·2ⁿ

步骤4：代入初始条件

a₀ = 1: α·1 = 1，α = 1

最终解：aₙ = (1 + n)·2ⁿ

验证：

a₀ = 1·1 = 1 ✓

a₁ = 2·2 = 4

检查递推：a₁ = 2a₀ + 2¹ = 2×1 + 2 = 4 ✓

8.3 分治递推关系

形式

T(n) = aT(n/b) + f(n)

其中a ≥ 1, b > 1是常数。

这类递推关系描述分治算法：将问题分为a个子问题，每个规模为n/b，合并代价为f(n)。

假设：通常假设n是b的幂，或者使用向上/向下取整。对于渐近分析，这些细节通常不影响结果。

主定理（Master Theorem）

对于 T(n) = aT(n/b) + Θ(nᵈ)，其中 d ≥ 0：

令 $c = \log_b a$（即 a = bᶜ）

情况1：如果 d < c（即 f(n) 增长较慢），则 T(n) = Θ(nᶜ)

情况2：如果 d = c（即 f(n) 与 nᶜ 同阶），则 T(n) = Θ(nᶜ log n)

情况3：如果 d > c（即 f(n) 增长较快），则 T(n) = Θ(nᵈ)

记忆技巧：比较 nᵈ 和 n^(log_b a) = a^(log_b n)，取主导项。如果两者相当，则多一个log因子。

直观解释：

• 情况1：叶子层主导（子问题数量增长快于合并代价）
• 情况2：各层代价相当
• 情况3：根层主导（合并代价增长快于子问题数量）

应用示例

归并排序：T(n) = 2T(n/2) + Θ(n)

• a = 2, b = 2, d = 1
• c = log₂2 = 1 = d
• 情况2：T(n) = Θ(n log n)

解释：归并排序将数组分为两半，递归排序每半，然后线性时间合并。递归树有log n层，每层总代价为n。

二分搜索：T(n) = T(n/2) + Θ(1)

• a = 1, b = 2, d = 0
• c = log₂1 = 0 = d
• 情况2：T(n) = Θ(log n)

解释：二分搜索每次将搜索空间减半，常数时间比较。递归深度为log n。

Strassen矩阵乘法：T(n) = 7T(n/2) + Θ(n²)

• a = 7, b = 2, d = 2
• c = log₂7 ≈ 2.81 > d
• 情况1：T(n) = Θ(n^log₂⁷) ≈ Θ(n²·⁸¹)

解释：Strassen算法将n×n矩阵乘法分解为7个n/2×n/2的子问题，加上O(n²)的加减法。相比朴素算法的O(n³)，这是一个改进。

Karatsuba大整数乘法：T(n) = 3T(n/2) + Θ(n)

• a = 3, b = 2, d = 1
• c = log₂3 ≈ 1.585 > d
• 情况1：T(n) = Θ(n^log₂³) ≈ Θ(n¹·⁵⁸⁵)

解释：Karatsuba算法将两个n位数的乘法分解为3个n/2位数的乘法，加上线性时间的加减法和移位。相比朴素算法的O(n²)，这是一个改进。

快速排序（最坏情况）：T(n) = T(n-1) + Θ(n)

• 这不是标准分治形式（子问题规模不是n/b）
• 展开：T(n) = T(n-1) + n = T(n-2) + (n-1) + n = ... = T(0) + 1 + 2 + ... + n = Θ(n²)

快速排序（平均情况）：T(n) = (2/n)Σ_{k=0}^{n-1} T(k) + Θ(n)

• 这需要更复杂的分析，结果为 T(n) = Θ(n log n)

主定理的证明思路

考虑递归树：

• 第0层（根）：代价 f(n) = nᵈ
• 第1层：a个子问题，每个规模n/b，总代价 a·(n/b)ᵈ = nᵈ·(a/bᵈ)
• 第2层：a²个子问题，每个规模n/b²，总代价 a²·(n/b²)ᵈ = nᵈ·(a/bᵈ)²
• ...
• 第i层：总代价 nᵈ·(a/bᵈ)ⁱ

令 r = a/bᵈ = bᶜ/bᵈ = bᶜ⁻ᵈ。

情况1：d < c，即 r > 1

总代价 = nᵈ · Σ_{i=0}^{log_b n} rⁱ = nᵈ · (r^{log_b n + 1} - 1)/(r - 1)

= nᵈ · Θ(r^{log_b n}) = nᵈ · Θ(n^{log_b r}) = nᵈ · Θ(n^{c-d}) = Θ(nᶜ)

情况2：d = c，即 r = 1

总代价 = nᵈ · Σ_{i=0}^{log_b n} 1 = nᵈ · (log_b n + 1) = Θ(nᵈ log n) = Θ(nᶜ log n)

情况3：d > c，即 r < 1

总代价 = nᵈ · Σ_{i=0}^{∞} rⁱ = nᵈ · 1/(1-r) = Θ(nᵈ)（几何级数收敛）

主定理的局限性

主定理不适用于以下情况：

• 子问题规模不均匀（如 T(n) = T(n/3) + T(2n/3) + O(n)）
• f(n) 不是多项式形式（如 f(n) = n log n）
• a 或 b 不是常数

对于这些情况，需要使用其他方法，如递归树展开、代换法等。

Akra-Bazzi定理：主定理的推广，可以处理更一般的分治递推关系。

8.4 生成函数

定义

序列 {aₙ} 的普通生成函数（OGF）是形式幂级数：

$$A(x) = \sum_{n=0}^{\infty} a_n x^n = a_0 + a_1 x + a_2 x^2 + ...$$

指数生成函数（EGF）是：

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

我们主要讨论普通生成函数。

形式幂级数：我们不关心收敛性，只关心系数的代数运算。生成函数是一种"编码"序列的工具。

基本生成函数

推导斐波那契生成函数：

设 F(x) = Σ Fₙxⁿ，其中 F₀=0, F₁=1, Fₙ=Fₙ₋₁+Fₙ₋₂。

xF(x) = Σ Fₙxⁿ⁺¹ = Σ Fₙ₋₁xⁿ

x²F(x) = Σ Fₙxⁿ⁺² = Σ Fₙ₋₂xⁿ

F(x) - xF(x) - x²F(x) = F₀ + (F₁-F₀)x + Σ_{n≥2}(Fₙ-Fₙ₋₁-Fₙ₋₂)xⁿ

= 0 + 1·x + 0

= x

因此 F(x)(1-x-x²) = x，即 F(x) = x/(1-x-x²)。∎

生成函数的运算

加法：A(x) + B(x) 对应序列逐项相加 {aₙ + bₙ}

乘法（卷积）：A(x)B(x) 的系数 cₙ = Σᵢ₌₀ⁿ aᵢbₙ₋ᵢ

解释：乘法对应卷积，这在组合问题中非常有用。例如，两个骰子的和的分布可以通过乘法得到。

移位：xᵏA(x) 对应序列右移k位，前k项为0

微分：A'(x) = Σ naₙxⁿ⁻¹，对应序列 {(n+1)aₙ₊₁}

积分：∫A(x)dx = Σ aₙxⁿ⁺¹/(n+1)，对应序列 {aₙ₋₁/n}

复合：A(B(x)) 在某些情况下有用，如卡特兰数的推导

应用示例

问题1：求掷两个六面骰子得到和为7的方式数。

解：单个骰子的生成函数为 x + x² + x³ + x⁴ + x⁵ + x⁶ = x(1-x⁶)/(1-x)。

两个骰子的生成函数为 [x(1-x⁶)/(1-x)]²。

我们关心 x⁷ 的系数。展开：

[x(1-x⁶)/(1-x)]² = x²(1-2x⁶+x¹²)/(1-x)²

= x²(1-2x⁶+x¹²) · Σ_{n=0}^{∞} (n+1)xⁿ

x⁷ 的系数来自：

• x² · 1 · (5+1)x⁵ 的系数：6
• x² · (-2x⁶) · (0+1)x⁰ 的系数：-2

总计：6 - 2 = 4？等等，这不对。

让我重新计算。实际上，直接展开 (x+x²+...+x⁶)² 更简单：

(x+x²+...+x⁶)² = x² + 2x³ + 3x⁴ + 4x⁵ + 5x⁶ + 6x⁷ + 5x⁸ + ...

x⁷ 的系数为 6，对应 6 种方式：(1,6), (2,5), (3,4), (4,3), (5,2), (6,1)。✓

问题2：求不定方程 x₁ + x₂ + x₃ = 10 的非负整数解的个数。

解：每个变量的生成函数为 1 + x + x² + ... = 1/(1-x)。

三个变量的生成函数为 [1/(1-x)]³ = 1/(1-x)³。

x¹⁰ 的系数为 C(10+3-1, 3-1) = C(12, 2) = 66。

这与我们之前用星与棒方法得到的结果一致。

问题3：求用1元和2元硬币凑成n元的方式数。

解：设aₙ为方式数。

1元硬币的生成函数：1 + x + x² + ... = 1/(1-x)

2元硬币的生成函数：1 + x² + x⁴ + ... = 1/(1-x²)

总生成函数：A(x) = 1/[(1-x)(1-x²)]

使用部分分式分解：

A(x) = 1/[(1-x)(1-x²)] = 1/[(1-x)²(1+x)]

= A/(1-x) + B/(1-x)² + C/(1+x)

解得：A = 1/4, B = 1/2, C = 1/4

A(x) = (1/4)/(1-x) + (1/2)/(1-x)² + (1/4)/(1+x)

展开：

= (1/4)Σxⁿ + (1/2)Σ(n+1)xⁿ + (1/4)Σ(-1)ⁿxⁿ

aₙ = (1/4) + (1/2)(n+1) + (1/4)(-1)ⁿ

= (n+1)/2 + [1+(-1)ⁿ]/4

当n为偶数时：aₙ = (n+1)/2 + 1/2 = (n+2)/2

当n为奇数时：aₙ = (n+1)/2 + 0 = (n+1)/2

统一写作：aₙ = ⌊n/2⌋ + 1

验证：

• n=0: 1种（不用硬币）✓
• n=1: 1种（1个1元）✓
• n=2: 2种（2个1元或1个2元）✓
• n=3: 2种（3个1元或1个1元+1个2元）✓
• n=4: 3种（4个1元，2个1元+1个2元，2个2元）✓

8.5 卡特兰数的生成函数

卡特兰数 Cₙ 满足递推关系：

$$C_n = \sum_{i=0}^{n-1} C_i C_{n-1-i}, \quad C_0 = 1$$

设生成函数为 C(x) = Σ Cₙxⁿ。

由递推关系可得：

$$C(x) = 1 + xC(x)^2$$

推导：

C(x) = C₀ + C₁x + C₂x² + ...

= 1 + Σ_{n≥1} [Σ_{i=0}^{n-1} CᵢCₙ₋₁₋ᵢ] xⁿ

= 1 + x Σ_{n≥1} [Σ_{i=0}^{n-1} CᵢCₙ₋₁₋ᵢ] xⁿ⁻¹

注意到 Σ_{i=0}^{n-1} CᵢCₙ₋₁₋ᵢ 是 C(x)² 中 xⁿ⁻¹ 的系数。因此：

C(x) = 1 + xC(x)²

解这个二次方程：

xC(x)² - C(x) + 1 = 0

$$C(x) = \frac{1 \pm \sqrt{1-4x}}{2x}$$

取合适的符号（保证C(0)=1）：

$$C(x) = \frac{1 - \sqrt{1-4x}}{2x}$$

展开√(1-4x)使用广义二项式定理：

$$\sqrt{1-4x} = \sum_{n=0}^{\infty} \binom{1/2}{n} (-4x)^n$$

其中 $\binom{1/2}{n} = \frac{(1/2)(1/2-1)\cdots(1/2-n+1)}{n!}$

经过计算可得：

$$C_n = \frac{1}{n+1}\binom{2n}{n}$$

8.6 Polya计数理论简介

问题：如何计算在对称群作用下的不同着色方案数？

Burnside引理：不同着色数等于所有群元素的不动点数的平均值。

$$N = \frac{1}{|G|} \sum_{g \in G} |X^g|$$

其中 X^g 是在置换 g 作用下保持不变的着色集合。

Polya计数定理：使用循环指标多项式可以更系统地计算。

对于置换群G，循环指标为：

$$Z_G(x_1, x_2, ..., x_n) = \frac{1}{|G|} \sum_{g \in G} x_1^{j_1(g)} x_2^{j_2(g)} \cdots x_n^{j_n(g)}$$

其中 jₖ(g) 是置换 g 中长度为 k 的循环的数量。

应用：计算项链着色、分子异构体等。

示例：正方形的顶点用2种颜色着色，考虑旋转对称，有多少种不同的着色？

旋转群有4个元素：0°, 90°, 180°, 270°。

• 0°（恒等）：4个1-循环，贡献 x₁⁴
• 90°：1个4-循环，贡献 x₄
• 180°：2个2-循环，贡献 x₂²
• 270°：1个4-循环，贡献 x₄

循环指标：Z = (1/4)(x₁⁴ + 2x₄ + x₂²)

代入 xᵢ = 2（2种颜色）：

N = (1/4)(2⁴ + 2·2 + 2²) = (1/4)(16 + 4 + 4) = 6

验证：手动枚举确实有6种不同的着色。

三、程序员的视角

3.1 在计算机科学中的应用

算法分析

• 归并排序：T(n) = 2T(n/2) + O(n) → Θ(n log n)
• 快速排序（平均）：T(n) = (2/n)ΣT(k) + O(n) → Θ(n log n)
• 二叉树遍历：T(n) = 2T(n/2) + O(1) → Θ(n)
• Strassen矩阵乘法：T(n) = 7T(n/2) + O(n²) → O(n²·⁸¹)
• Karatsuba乘法：T(n) = 3T(n/2) + O(n) → O(n¹·⁵⁸⁵)

动态规划

状态转移方程是递推关系的离散版本。理解递推有助于设计DP。

• 斐波那契：dp[i] = dp[i-1] + dp[i-2]
• 最长公共子序列：dp[i][j] = dp[i-1][j-1] + 1 或 max(dp[i-1][j], dp[i][j-1])
• 矩阵链乘法：dp[i][j] = min(dp[i][k] + dp[k+1][j] + cost)

组合枚举

生成函数用于计算组合对象的数量，如合法括号序列、二叉树数量。

编译器设计

• 正则表达式引擎：DFA状态数计算
• 语法分析：Catalan数表示解析树数量

3.2 常见陷阱与误区

主定理适用条件

主定理仅适用于 T(n) = aT(n/b) + f(n) 形式。如果子问题规模不均匀（如 T(n) = T(n/3) + T(2n/3) + O(n)），主定理不适用。

处理方法：使用递归树或代换法。

特征方程的重根

重根时需要乘以n的幂次，容易遗漏。

检查方法：确保通解中的各项线性无关。

生成函数的收敛性

生成函数作为形式幂级数，不需要考虑收敛性。但如果用于数值计算，需要注意收敛半径。

收敛半径：对于有理生成函数 P(x)/Q(x)，收敛半径是最小的根的模。

特解形式的选择

如果猜测的特解形式与齐次解重复，需要乘以n的适当幂次。

规则：如果猜测形式的底数是m重特征根，则乘以nᵐ。

3.3 与其他层级的联系

• 硬件层：递归电路的深度和大小
• 操作系统层：递归调用的栈深度和内存使用
• 网络层：分治路由算法的复杂度
• 应用层：组合优化问题的解空间大小

四、代码实战

8.1 递推关系求解器

"""
递推关系求解工具
"""

import math
from sympy import symbols, solve, Function


def solve_linear_homogeneous(coeffs, initial_conditions):
    """
    求解线性齐次递推关系
    
    参数:
        coeffs: 系数列表 [c1, c2, ..., ck]
        initial_conditions: 初始条件 [a0, a1, ..., ak-1]
    
    返回: 通解表达式（符号形式）
    """
    k = len(coeffs)
    n = symbols('n')
    
    # 构建特征方程
    r = symbols('r')
    char_eq = r**k
    for i, c in enumerate(coeffs):
        char_eq -= c * r**(k - 1 - i)
    
    # 求解特征根
    roots = solve(char_eq, r)
    
    print(f"特征方程: {char_eq} = 0")
    print(f"特征根: {roots}")
    
    # 构建通解
    alphas = symbols(f'alpha:{k}')
    general_solution = sum(alphas[i] * roots[i]**n for i in range(k))
    
    print(f"通解形式: {general_solution}")
    
    return general_solution, roots


def fibonacci_closed_form(n):
    """
    斐波那契数列的通项公式（比内公式）
    """
    phi = (1 + math.sqrt(5)) / 2
    psi = (1 - math.sqrt(5)) / 2
    
    return (phi**n - psi**n) / math.sqrt(5)


def compute_recurrence_sequence(coeffs, initial_conditions, num_terms):
    """
    计算递推序列的前num_terms项
    
    参数:
        coeffs: 系数列表
        initial_conditions: 初始条件
        num_terms: 要计算的项数
    """
    k = len(coeffs)
    sequence = list(initial_conditions[:k])
    
    for n in range(k, num_terms):
        next_val = sum(coeffs[i] * sequence[n - 1 - i] for i in range(k))
        sequence.append(next_val)
    
    return sequence


def solve_nonhomogeneous_example():
    """求解非齐次递推关系示例"""
    
    print("\n=== 非齐次递推示例 ===")
    
    # a_n = 2a_{n-1} + 3^n, a_0 = 1
    # 理论解: a_n = 3^{n+1} - 2^{n+1}
    
    coeffs = [2]
    initials = [1]
    
    seq = compute_recurrence_sequence(coeffs, initials, 10)
    print(f"a_n = 2a_(n-1) + 3^n, a_0 = 1")
    print(f"递推计算: {seq}")
    
    theoretical = [3**(n+1) - 2**(n+1) for n in range(10)]
    print(f"理论值:   {theoretical}")
    print(f"匹配: {seq == theoretical}")


def demonstrate_recurrence():
    """演示递推关系求解"""
    
    print("=== 斐波那契数列 ===")
    
    # 递推计算
    fib_seq = compute_recurrence_sequence([1, 1], [0, 1], 15)
    print(f"递推计算: {fib_seq}")
    
    # 通项公式验证
    print("\n通项公式验证:")
    for n in range(10):
        closed = round(fibonacci_closed_form(n))
        recursive = fib_seq[n]
        match = "✓" if closed == recursive else "✗"
        print(f"  F({n}): 通项={closed}, 递推={recursive} {match}")
    
    print("\n=== 线性齐次递推 ===")
    
    # a_n = 3a_{n-1} - 2a_{n-2}, a_0=1, a_1=3
    coeffs = [3, -2]
    initials = [1, 3]
    
    seq = compute_recurrence_sequence(coeffs, initials, 10)
    print(f"a_n = 3a_(n-1) - 2a_(n-2), a_0=1, a_1=3")
    print(f"序列: {seq}")
    
    # 理论解: a_n = 2^n + 1
    theoretical = [2**n + 1 for n in range(10)]
    print(f"理论值: {theoretical}")
    print(f"匹配: {seq == theoretical}")
    
    solve_nonhomogeneous_example()


if __name__ == "__main__":
    demonstrate_recurrence()

8.2 主定理计算器

"""
主定理应用工具
"""

import math


def master_theorem(a, b, d):
    """
    应用主定理求解 T(n) = aT(n/b) + Theta(n^d)
    
    参数:
        a: 子问题数量
        b: 子问题规模缩小因子
        d: 合并代价的多项式次数
    
    返回: 复杂度描述
    """
    c = math.log(a, b)
    
    print(f"T(n) = {a}T(n/{b}) + Theta(n^{d})")
    print(f"log_b(a) = log_{b}({a}) = {c:.4f}")
    
    if abs(d - c) < 1e-9:  # d == c
        result = f"Theta(n^{d} log n)"
        case = "情况2"
    elif d < c:
        result = f"Theta(n^{c:.4f})"
        case = "情况1"
    else:  # d > c
        result = f"Theta(n^{d})"
        case = "情况3"
    
    print(f"d={d}, c={c:.4f}: {case}")
    print(f"结果: {result}")
    print()
    
    return result


def analyze_algorithms():
    """分析常见算法的递推关系"""
    
    print("=== 常见算法的主定理分析 ===\n")
    
    algorithms = [
        ("归并排序", 2, 2, 1),
        ("二分搜索", 1, 2, 0),
        ("Strassen矩阵乘法", 7, 2, 2),
        ("Karatsuba大整数乘法", 3, 2, 1),
        ("朴素最大子数组分治", 2, 2, 1),
        ("三分搜索", 2, 3, 0),
    ]
    
    for name, a, b, d in algorithms:
        print(f"--- {name} ---")
        master_theorem(a, b, d)


if __name__ == "__main__":
    analyze_algorithms()

8.3 生成函数应用

"""
生成函数应用：组合计数
"""

from collections import defaultdict


def catalan_number(n):
    """
    计算第n个卡特兰数
    
    C_n = binom(2n, n) / (n+1)
    """
    import math
    return math.comb(2*n, n) // (n + 1)


def dice_sum_ways(num_dice, faces=6):
    """
    计算掷num_dice个faces面骰子得到各种和的方式数
    
    使用动态规划方法（等价于生成函数卷积）
    """
    # 动态规划方法
    dp = defaultdict(int)
    dp[0] = 1
    
    for _ in range(num_dice):
        new_dp = defaultdict(int)
        for current_sum, ways in dp.items():
            for face in range(1, faces + 1):
                new_dp[current_sum + face] += ways
        dp = new_dp
    
    return dict(dp)


def coin_change_ways(amount, coins=[1, 2]):
    """
    计算用给定面额硬币凑成amount元的方式数
    
    使用生成函数思想（动态规划实现）
    """
    dp = [0] * (amount + 1)
    dp[0] = 1
    
    for coin in coins:
        for i in range(coin, amount + 1):
            dp[i] += dp[i - coin]
    
    return dp[amount]


def demonstrate_generating_functions():
    """演示生成函数应用"""
    
    print("=== 卡特兰数 ===")
    for n in range(12):
        print(f"  C_{n} = {catalan_number(n)}")
    
    print("\n=== 骰子和的方式数 ===")
    
    num_dice = 2
    ways = dice_sum_ways(num_dice)
    
    print(f"{num_dice}个六面骰子:")
    min_sum = num_dice
    max_sum = num_dice * 6
    
    for s in range(min_sum, max_sum + 1):
        w = ways.get(s, 0)
        print(f"  和={s}: {w}种方式")
    
    total_ways = sum(ways.values())
    print(f"\n总方式数: {total_ways} (= 6^{num_dice} = {6**num_dice})")
    
    print("\n=== 硬币找零 ===")
    
    for amount in range(11):
        w = coin_change_ways(amount, [1, 2])
        print(f"  凑成{amount}元（1元和2元）: {w}种方式")
    
    # 验证公式: floor(n/2) + 1
    for amount in range(11):
        formula = amount // 2 + 1
        computed = coin_change_ways(amount, [1, 2])
        match = "✓" if formula == computed else "✗"
        print(f"  {amount}: 公式={formula}, 计算={computed} {match}")


if __name__ == "__main__":
    demonstrate_generating_functions()

五、深入思考

5.1 历史背景

生成函数由亚伯拉罕·棣莫弗和莱昂哈德·欧拉发展。乔治·波利亚将生成函数应用于组合枚举。主定理由Jon Bentley、Dorothea Haken等人系统化，并在CLRS教材中广泛传播。

赫伯特·威尔夫的《Generatingfunctionology》是生成函数领域的经典著作，书名巧妙地将"生成函数"和"ology"结合。

5.2 前沿方向

• 符号计算：使用计算机代数系统（如Mathematica、SymPy）自动求解递推关系
• 渐近分析：更精确地估计序列的增长率，使用 saddle-point 方法
• q-模拟：引入参数q的组合恒等式，与量子群和统计物理相关
• 解析组合学：使用复分析研究生成函数的奇点，获得精确的渐近估计
• 自动化证明：使用计算机辅助证明组合恒等式（如Zeilberger算法）

5.3 延伸阅读

• 《Concrete Mathematics》by Graham, Knuth, Patashnik
• 《Analytic Combinatorics》by Philippe Flajolet and Robert Sedgewick
• 《Generatingfunctionology》by Herbert S. Wilf
• 《The Art of Computer Programming, Vol. 4A》by Donald E. Knuth
• 《Enumerative Combinatorics》by Richard P. Stanley

六、实验笔记

实验1：递推关系可视化工具

目标：可视化递推关系的求解过程。

任务：

输入递推关系系数和初始条件

绘制序列前N项

显示特征根和通解形式

比较理论值和递推计算值

可视化递归树

提交物：可运行的程序、可视化图表、分析报告。

扩展挑战：

• 支持非线性递推
• 自动生成LaTeX格式的解题步骤
• 实现递归树的交互式探索

实验2：生成函数探索

目标：通过编程探索生成函数的性质。

任务：

实现常见序列的生成函数

验证生成函数的运算性质（加法、乘法、微分）

使用生成函数解决组合计数问题

可视化生成函数的系数

实现部分分式分解

提交物：源代码、实验报告、可视化输出。

扩展挑战：

• 实现符号生成函数操作
• 自动识别序列的生成函数
• 应用到实际组合问题

实验3：算法复杂度分析器

目标：自动分析分治算法的时间复杂度。

任务：

解析算法描述提取递推关系

应用主定理判断复杂度

对于不适用的情况，使用递归树方法

可视化递归树和各层代价

生成分析报告

提交物：源代码、测试用例、分析报告。

扩展挑战：

• 支持更复杂的递推形式
• 实现Akra-Bazzi定理
• 集成到IDE中作为插件

七、本章小结

本章介绍了高级计数技术。递推关系是描述序列的有力工具，线性齐次递推关系可通过特征方程法求解。特征根的类型（不同实根、重根、复根）决定了通解的形式。

非齐次递推关系的解由齐次解和特解组成。特解的形式取决于非齐次项f(n)，需要根据f(n)的类型进行猜测。如果猜测形式与齐次解重复，需要乘以n的适当幂次。

分治递推关系 T(n) = aT(n/b) + f(n) 常用主定理求解，根据 f(n) 相对于 n^(log_b a) 的增长率分为三种情况。主定理是分析分治算法复杂度的强大工具，但有适用范围限制。

生成函数将序列转化为形式幂级数，利用代数和分析工具解决计数问题。卷积对应序列的卷积，微分对应加权序列。生成函数方法统一了多种计数技巧，是组合数学的核心工具。

卡特兰数是一个重要的计数序列，出现在括号匹配、二叉树计数等多个场景中。其生成函数满足二次方程，可以导出闭式公式。

这些技术在算法分析、组合数学、概率论和物理学中有广泛应用。掌握这些工具能够提升解决复杂计数问题的能力。

八、习题

习题1（基础）：求解递推关系 aₙ = 4aₙ₋₁ - 4aₙ₋₂，a₀=1, a₁=4。

习题2（基础）：使用主定理求解 T(n) = 8T(n/2) + n²。

习题3（中等）：证明斐波那契数列的生成函数是 x/(1-x-x²)。

习题4（中等）：求解非齐次递推关系 aₙ = 2aₙ₋₁ + n，a₀=1。

习题5（中等）：有多少种方式用1元和2元硬币凑成n元？建立递推关系并求解。

习题6（较难）：研究阿克曼函数的增长率，为什么它增长如此之快？

习题7（较难）：使用生成函数证明范德蒙德恒等式。

习题8（挑战）：求解递推关系 aₙ = aₙ₋₁ + 2aₙ₋₂ + 3ⁿ，a₀=0, a₁=1。

习题9（挑战）：研究并实现一个通用的递推关系求解器（支持线性齐次和非齐次）。

习题10（开放）：选择一个算法（如FFT、矩阵链乘法、最优二叉搜索树），分析其递推关系并撰写报告。包括：

• 算法描述和递推关系的建立
• 求解过程和结果
• 与其他算法的比较
• 实际应用场景