普林斯顿算法分析笔记（二）
最终结果：
C(2n, n) ~ 4^n / sqrt(πn)
这是一个非常简洁而强大的渐近估计。
实际应用：二叉树编码
这个理论结果有直接的实际意义。考虑用二进制串编码一个有 n 个内部节点的二叉树。
-
信息论下界：不同的二叉树数量是卡特兰数
C(2n, n)/(n+1) ~ 4^n / (sqrt(π) * n^(3/2))。要唯一表示所有树，至少需要log2(数量)个比特。 -
计算比特数：
log2(4^n / (sqrt(π) * n^(3/2))) = 2n - (3/2) log2 n - O(1) -
实践意义：对于一个有100万个内部节点的树，至少需要约
2 * 10^6 - (3/2) * log2(10^6) ≈ 2,000,000 - 30比特。而存在一种简单的先序遍历编码方法，恰好使用2n比特。这意味着该编码方案非常接近理论最优值（仅多出约30比特），程序员可以放心使用。
这个例子生动地展示了渐近分析如何将复杂的离散函数转化为清晰、实用的工程指导。
总结
本节课中我们一起学习了处理有限和渐近分析的三种核心技术：尾部边界法、最大项主导法和积分近似法（欧拉-麦克劳林公式）。我们通过斯特林公式推导了中心二项式系数 C(2n, n) ~ 4^n / sqrt(πn) 的经典近似，并看到了该结果在二叉树编码问题中的直接应用。掌握这些技术，能够帮助我们将算法分析中出现的复杂和式，转化为简洁、可用的渐近估计。
018：二元渐近分析 📊
在本节课中，我们将学习渐近分析的一个复杂扩展，即涉及两个变量的情况。这在算法分析中经常出现。我们将探讨如何处理这类二元函数，并学习几个关键函数的渐近近似方法。
概述
许多算法分析问题涉及两个变量：问题规模 n 和成本 k。这导致我们得到包含这两个变量的复杂表达式，且它们可能独立变化，带来了分析上的挑战。主要困难在于，变量的相对值可能很重要，这使得处理整个值域上的求和更具挑战性。幸运的是，与调和数和斯特林数类似，有几个基本的二元函数会反复出现，我们将重点学习它们的渐近性质。
二元函数的挑战与示例
上一节我们介绍了单变量渐近分析。本节中，我们来看看当函数依赖于两个变量 n 和 k 时的情况。
分析这类函数的主要挑战在于，函数的行为可能强烈依赖于 k 相对于 n 的值。例如，当 k 很小时，函数值可能接近 1；而当 k 接近 n 时，函数值可能指数级地小。我们需要一种能覆盖整个值域的分析方法。
以下是两个在算法分析中常见的二元函数示例：
-
二项分布：
C(n, k) = n! / (k! (n-k)!)-
当
k=0时，约为1 / sqrt(pi * n / 2)。 -
当
k很大时，值指数级小。
-
-
拉马努金 Q 分布：
Q(n, k) = n! / ((n-k)! * n^k)-
当
k=0时，值为 1。 -
当
k接近n时，值指数级小。
-
这些函数展示了我们在分析二元函数时所面临的挑战类型。
可视化二元函数行为
为了理解二元函数的行为，我们可以借助图形。对于每个固定的 k 值，我们将函数值视为 n 的函数并绘制成曲线。通常，为了在同一图中比较，我们会用 2^n 等因子进行缩放。
对于二项式系数，随着 n 增大，这个离散的二元分布会收敛到正态分布，可以用一个简单的数学函数（曲线）来描述。我们的数学分析目标就是得到这个简单描述。
同样，拉马努金 Q 分布也有类似的特征曲线：当 k 较小时接近 1，在 k 接近 n/2 时变得极小。二元渐近分析的目标就是为任意 k 值找到定义这条曲线的函数。
拉马努金 Q 分布的渐近推导
现在，让我们首先详细看看拉马努金 Q 分布的渐近推导。这个计算是卡特兰数计算的扩展，只是现在我们多了一个变量 k。
第一步：应用取对数技巧（X log trick）
我们首先对表达式取对数：
log Q(n, k) = log(n!) - log((n-k)!) - k * log(n)
第二步：应用斯特林公式
对 log(n!) 和 log((n-k)!) 使用斯特林近似：
log(n!) = (n + 1/2) * log(n) - n + log(sqrt(2*pi)) + O(1/n)
对 log((n-k)!) 使用类似公式，并将 O(1/(n-k)) 覆盖为 O(1/n)。
第三步：代数化简与抵消
代入后，进行代数运算。许多项会抵消，例如 -n + n，log(sqrt(2*pi)) 等。利用 log(n-k) = log(n) + log(1 - k/n) 进行展开。最终我们得到：
log Q(n, k) ≈ -(n - k + 1/2) * log(1 - k/n) - k * log(n) （简化后形式）
第四步：展开对数项
对 log(1 - k/n) 进行泰勒展开：
log(1 - k/n) = - (k/n) - (k^2)/(2n^2) + O(k^3 / n^3)
将其代入并化简。关键的抵消发生后，我们得到：
log Q(n, k) ≈ - (k^2) / (2n) + O(k/n) + O(k^3 / n^2)
第五步：指数化得到最终近似
因此，Q(n, k) ≈ e^{- (k^2) / (2n)}，误差项由 O(k/n) 和 O(k^3 / n^2) 控制。
这个推导表明，对于相对较小的 k（例如 k = O(n^{2/5})），Q(n, k) 可以很好地用 e^{- (k^2) / (2n)} 来近似。这正是我们在图中看到的曲线。
二项分布的渐近推导
二项分布的推导过程与 Q 分布非常相似，同样依赖于斯特林公式和细致的代数运算。
以下是推导的关键步骤概要：
-
对
C(n, k)应用取对数技巧。 -
对
log(n!),log(k!),log((n-k)!)应用斯特林公式。 -
利用展开式
log(n ± k) = log(n) + log(1 ± k/n)处理变量k。 -
进行大量的代数化简和抵消。例如，
2n项等会抵消。 -
对
log(1 ± k/n)进行展开，并组合项。我们会遇到(n+1/2) * [log(1 - k/n) + log(1 + k/n)]和k * [log(1 + k/n) - log(1 - k/n)]这样的形式。 -
这些和与差可以分别渐近地简化为
-k^2 / n^2和-2k / n等项（包含O(k^3/n^2)误差）。 -
代入并化简后，取指数，得到著名的正态近似（德莫弗-拉普拉斯定理）：
C(n, k) / 2^n ≈ (e^{- (k^2) / n}) / sqrt(pi * n)或者更常见的形式：
C(n, k) ≈ (2^n / sqrt(pi * n)) * e^{- (k^2) / n}
这个近似在 k 的很大一个范围内（直到约 n^(3/4)）都是准确的。当 k 更大时，项本身已经非常小，可以用其他方法证明。
这个推导虽然涉及大量运算，但本质上是初等代数。掌握它对于理解二元渐近分析至关重要。
泊松近似及其他
同样的技术（取对数技巧加斯特林公式）也可以导出著名的泊松近似。当概率 p = λ/n 很小，且 n 很大时，二项分布 C(n, k) * p^k * (1-p)^{n-k} 近似为 (λ^k * e^{-λ}) / k!。
我们将在具体算法应用的上下文中讨论它。目前，从数学角度应认识到，相同的技术可以产生这类近似。
对于之前讨论的 Q 分布，我们有 Q(n, k) ≈ e^{-k^2 / (2n)}，在 k 较小时精度很高。这些二元渐近近似在算法分析及其他领域都极为重要。使用像 e^{-k^2 / n} 这样的标准数学函数，通常比处理精确但繁琐的阶乘表示要容易得多。
处理二元函数的求和：拉普拉斯方法
接下来的挑战是，当我们需要对这类二元函数求和时该怎么办？例如，考虑拉马努金 Q 函数，它是 Q 分布对所有 k 的求和：Q(n) = Σ_k Q(n, k)。这本质上是求曲线下的面积。
挑战在于，我们需要在求和的不同部分使用不同的近似：在 k 小的地方值接近 1，在 k 大的地方值可忽略。这就是我们需要二元渐近分析的原因，以确保能在整个值域上获得良好的估计来近似求和。
通用方法：拉普拉斯方法
以下是该方法的示意图：
-
尾部截断：函数的尾部通常很小。我们将求和范围限制在主要贡献区域（例如
k < k0）。 -
核心近似：在限制后的范围内，使用我们得到的良好渐近近似（例如
e^{-k^2/(2n)}）。 -
范围扩展与积分近似：有趣的是，这个近似函数本身在尾部也是指数级小的。因此，我们可以安全地将求和范围从
0到k0扩展回0到∞，因为添加的尾部贡献可忽略。现在，对连续近似函数的求和可以近似为一个积分。 -
计算积分：计算该积分，得到整个和的一个简洁近似。
应用于 Q(n) 函数
对于 Q(n) = Σ_{k=0}^n Q(n, k)：
-
选择
k0如n^{2/3}，可以证明原函数的尾部Σ_{k>k0} Q(n, k)指数级小。 -
对于
k ≤ k0，使用近似Q(n, k) ≈ e^{-k^2/(2n)}。 -
将近似函数的求和范围扩展到无穷：
Σ_{k=0}^∞ e^{-k^2/(2n)}。 -
用积分近似该求和：
∫_{0}^{∞} e^{-x^2/(2n)} dx = sqrt(pi * n / 2)。
因此，我们得到 Q(n) ≈ sqrt(pi * n / 2)。这是一个非常有用的结果，原始的 Q(n) 定义计算可能很困难，但这个渐近近似给出了一个简单可用的表达式。
总结与练习
本节课中，我们一起学习了二元渐近分析。我们看到了分析两个变量函数的挑战，并通过具体推导，学习了如何获得二项分布和拉马努金 Q 分布等关键函数的渐近近似。我们还介绍了处理这类函数求和的拉普拉斯方法。
为了巩固理解，你可以尝试以下练习：
-
练习 1（指数级小的比较）：对于不同的
α和β（0<β<α<1），比较α^n和β^n。理解“指数级小”的含义。 -
练习 2（推导另一个函数）：在教材中，还有一个拉马努金 P 函数（或 R 函数）：
P(n) = Σ_k (n-k)^k * (n-k)! / n!。尝试模仿 Q 函数的推导步骤，证明P(n) ≈ sqrt(pi * n / 2)。这将极大地帮助你测试对这部分内容的理解。 -
编程练习：编写一个程序，计算并输出
log2(C(n, k))的值，并思考如何利用本节课的知识来实现。 -
阅读：详细阅读教材中关于渐近分析的章节，以获取更多细节和示例。
在下一讲中，我们将把前面几讲所学的所有内容整合起来，看看它们如何共同构成解析组合学的基础，以便我们将其应用于算法分析。
019：符号方法入门 🧮
在本节课中，我们将学习解析组合学的入门知识。解析组合学是研究大型组合结构的定量分析的一种“微积分”。它建立在生成函数等概念之上，为我们分析算法和组合结构提供了一个连贯的起点。通过本节课，你将了解解析组合学的基本框架，特别是其核心部分——符号方法。
概述
解析组合学是研究大型组合结构的定量分析的一种方法。它的基本流程是：从组合构造出发，通过符号转移定理得到生成函数方程，最后利用解析转移定理获得系数的渐近估计。这种方法使我们能够避免许多繁琐的计算，直接得到结果。
符号方法
符号方法是解析组合学的起点。它主要用于定义组合构造，并将其翻译为生成函数方程。其基本步骤如下：
-
定义一个组合对象的类。
-
定义对象的大小。
-
定义其生成函数，其系数用于计数相同大小的对象。
-
定义允许我们构造性地定义对象的操作。
-
为每个构造操作提供对应的生成函数操作翻译规则。
我们使用大写字母表示组合类，用绝对值符号表示大小，生成函数则使用相同字母（通常为 Z 的函数）。
组合类与原子
一个组合类是一个对象集合及其大小函数。我们需要一些基础构件来开始构造，这些基础构件称为原子，即大小为1的对象。为了方便递归定义，我们还会引入一个大小为0的中性对象。
以下是几个简单的组合类例子：
-
自然数：可以看作是一系列原子的序列。每个大小只有一个对象。其普通生成函数为
1/(1 - z)。 -
比特串：由0或1比特组成的序列。长度为
n的比特串有2^n个。其普通生成函数为1/(1 - 2z)。 -
二叉树：要么为空，要么是一个节点连接两棵（有序的）二叉树。其计数序列是卡特兰数，生成函数满足
T(z) = 1 + z * T(z)^2。
无标号类的构造
对于无标号类，我们主要使用三种基本构造。假设 A 和 B 是无标号组合类：
-
不相交并 (
A + B)：包含来自A和B的对象副本。 -
笛卡尔积 (
A × B)：包含来自A和B的对象的有序对。 -
序列 (
SEQ(A))：包含来自A的对象的序列。
转移定理
符号方法的核心是转移定理。它允许我们将组合构造直接翻译为生成函数上的操作：
-
不相交并：生成函数为
A(z) + B(z)。 -
笛卡尔积：生成函数为
A(z) * B(z)。 -
序列：生成函数为
1 / (1 - A(z))。
这些定理的证明基于生成函数计数的基本思想。例如，对于笛卡尔积，由于组合对象由来自 A 和 B 的各一个独立部分组成，其大小的生成函数自然就是两者生成函数的乘积。
应用示例
上一节我们介绍了符号方法的基本构造和转移定理，本节中我们来看看如何应用它们解决具体问题。
示例1：二叉树（按内部节点计数）
以下是分析一个组合类的标准步骤：
-
定义类：所有二叉树的类
T。 -
定义大小：树
t中内部节点的数量|t|。 -
定义生成函数：
T(z) = Σ_{t∈T} z^{|t|}。 -
定义原子：
-
外部节点
□（大小 0）：生成函数 = 1。 -
内部节点
•（大小 1）：生成函数 =z。
-
-
组合构造：一棵二叉树要么是一个外部节点，要么是一个（左子树，内部节点，右子树）的笛卡尔积。用符号表示为：
T = □ + (T × • × T) -
应用转移定理：将构造翻译为生成函数方程。
-
□对应1。 -
(T × • × T)对应T(z) * z * T(z) = z * T(z)^2。 -
因此，方程是：
T(z) = 1 + z * T(z)^2。
-
这个方程与我们之前通过其他方法得到的完全一致，但推导过程更加系统和机械化。
示例2：二叉树（按外部节点计数）
同一个组合结构，如果采用不同的“大小”定义，就会得到不同的组合类和生成函数。
-
定义类：所有二叉树的类
T_□（注意类名变化，以示区分）。 -
定义大小：树
t中外部节点的数量。 -
定义生成函数：
T_□(z) = Σ_{t∈T_□} z^{|t|}。 -
定义原子：
-
外部节点
□（大小 1）：生成函数 =z。 -
内部节点
•（大小 0）：生成函数 =1。
-
-
组合构造：与之前相同：
T_□ = □ + (T_□ × • × T_□)。 -
应用转移定理：
-
□对应z。 -
(T_□ × • × T_□)对应T_□(z) * 1 * T_□(z) = T_□(z)^2。 -
因此，方程是：
T_□(z) = z + T_□(z)^2。
-
可以验证，T_□(z) = z * T(z)，这证明了具有 n 个外部节点的二叉树数量等于具有 n-1 个内部节点的二叉树数量。
示例3：比特串
我们已知比特串的生成函数是 1/(1-2z)。用符号方法可以轻松得到：
-
原子：比特
0和1，大小均为1，生成函数均为z。 -
构造：一个比特串是
0或1的序列。即B = SEQ(Z_0 + Z_1)。 -
转移：
Z_0 + Z_1的生成函数是z + z = 2z。序列的生成函数是1/(1 - 2z)。
另一种构造方式是：一个比特串要么是空的，要么是一个比特 (0 或 1) 后接一个比特串。即 B = ε + (Z_0 + Z_1) × B。转移后得到方程 B(z) = 1 + 2z * B(z)，解得 B(z) = 1/(1-2z)。这展示了同一个类可以有多种等价的构造方式。
示例4：不含连续两个0的比特串
这是一个更具实际意义的问题。我们想计算长度为 n 且不含“00”子串的比特串数量。
-
定义类：所有不含“00”的比特串的类
B_{00}。 -
大小：比特串的长度。
-
原子：比特
0和1（生成函数均为z），以及空串ε（生成函数为1）。 -
构造：需要仔细思考如何描述这个受限的类。一种有效的描述是：
-
一个不含“00”的串，要么是空的，要么是单个
0，要么是单个1，要么是01后接一个不含“00”的串。 -
用符号表示：
B_{00} = ε + Z_0 + Z_1 + (Z_0 × Z_1) × B_{00}。
-
-
应用转移定理：
-
ε对应1。 -
Z_0和Z_1各对应z。 -
(Z_0 × Z_1)对应z * z = z^2。 -
因此，生成函数方程为：
B_{00}(z) = 1 + z + z + z^2 * B_{00}(z) = 1 + 2z + z^2 * B_{00}(z)。
-
-
求解生成函数：解得
B_{00}(z) = (1 + 2z) / (1 - z - z^2)。
这个生成函数对应斐波那契数列的某种变形。提取系数后可以发现，长度为 n 且不含“00”的比特串数量正是斐波那契数 F_{n+2}。这个例子表明，符号方法可以轻松处理带有约束条件的组合类。
总结
本节课中我们一起学习了解析组合学及其核心工具——符号方法。我们了解到：
-
解析组合学通过组合构造 → 生成函数 → 系数渐近的流程来系统分析组合结构。
-
符号方法提供了一套将组合构造（如并、积、序列）机械地翻译为生成函数方程的规则。
-
我们通过二叉树、比特串以及受限比特串等例子，实践了如何定义组合类、选择原子、进行构造并应用转移定理得到生成函数方程。
符号方法的优势在于其系统性和可扩展性。一旦掌握了基本规则，我们就能以统一的方式处理大量复杂的计数问题，而无需每次都从头进行繁琐的求和与卷积运算。在后续课程中，我们将在此基础上，学习如何从生成函数中提取系数（即计数序列），并处理更复杂的标号组合对象。
020：带标签对象 🏷️
在本节课中，我们将学习组合类中一个重要的类别：带标签对象。我们将解释带标签对象与之前讨论的无标签对象的区别，并探讨一些有趣的问题。
带标签组合类
带标签组合类中的对象由原子构成，但我们认为这些原子是彼此不同的。为了明确这一点，我们为它们加上标签。通常，我们考虑用整数 1 到 n 来标记它们。
从原理上讲，对于无标签对象，这两个对象可能因为结构不同而被视为不同。但对于带标签对象，不同的标记方式会产生不同的对象。例如，一个正方形有两种不同的标记方式。在左边的标记中，1 连接到 2 和 4；在右边的标记中，1 连接到 3 和 4，它们是不同的。对于右边的对象，标记方式的数量并不总是显而易见的，实际上有四种方式，因为连接到所有其他点的点可以是 1、2、3 或 4。
因此，在研究不同对象的数量时，标签带来了巨大的差异，因为它提供了更多的可能性。事实上，在处理带标签对象时，我们使用指数生成函数，随着学习的深入，这一点会变得清晰。
基本示例
让我们看一些带标签对象的基本简单示例。
瓮 🏺
一个“瓮”是一组带标签的原子。它是一个集合，顺序无关紧要。同样，每种类型只有一个。我们稍后会看到为什么使用这种定义，届时会非常清楚。
由于每种类型只有一个，我们使用指数生成函数。瓮的指数生成函数是 e^z。因为每种大小的对象只有一个，求和 Σ (z^n / n!) 的结果就是 e^z。这是第一个基本示例。
排列 🔄
排列是带标签原子的一个序列。“序列”意味着顺序很重要，原子是带标签的，因此原子的每一种可能排序都会产生一个不同的对象。
-
大小为 2 的对象有 2 个：1,2 或 2,1。
-
大小为 3 的对象有 6 个。
-
大小为 4 的对象有 24 个，依此类推。
那么排列的指数生成函数是什么？大小为 n 的排列有 n! 个，因此指数生成函数是 n! 除以 n! 再乘以 z^n，这简化为 Σ z^n，即 1 / (1 - z)。
这是另一个基本的组合类。n! 的作用是防止生成函数因排序带来的所有不同可能性而增长过快。
环 🔁
一个“环”是带标签原子的一个循环序列。所有元素连接成一个环，但每种类型的数量更少。实际上，如果你研究一下，固定最大或最小的元素，你会发现其他元素构成一个排列，因此计数序列是 (n-1)!。
那么环的指数生成函数是什么？它是 Σ ((n-1)! * z^n) / n!，其中除了一个 1/n 项外，其他项都抵消了。所以结果是 ln(1 / (1 - z))。这是另一个基本的组合类。
解析组合学的特点是从这类极其简单的推导和类开始，然后以有趣的方式组合它们，为感兴趣的解析问题提供答案。
带标签类的运算
笛卡尔积运算的类比是什么？对于带标签类来说，这要复杂得多。
当我们取两个类的乘积时，例如第一个例子，我们称之为星积。取 {1,2,3} 的星积，我们会得到大小为 4 的对象，但它们必须用 1 到 4 编号。组合学要求我们进行 1 到 4 的编号，但要以所有一致的方式进行。在这个例子中，第二个参数是一个递增序列，因此重新编号时，我们必须为每种可能性按递增顺序分配标签。
这是一个更复杂的例子，我们取一个 2-环和一个 3-环的星积。同样，我们得到由 5 个原子组成的对象，具有一个 2-环和一个 3-环的结构，但原子必须用 1 到 5 编号，并且我们必须以所有可能的方式进行。在这种情况下，你可以选择任何标签。标记 2-环只有一种方式，然后你可以从 5 个中选择 2 个（即 C(5,2) 种方式）来标记 2-环。标记完 2-环后，你取剩余的标签分配给 3-环，但必须保持一致并保持顺序。
这就是星积运算：以所有一致的方式重新标记。当我们进入应用部分时，我们会看到这不仅仅是直观的，而且是处理带标签对象的基础。
对于带标签对象，由于我们可以区分顺序，我们有更多的基本构造，我们将使用更丰富的运算集。实际上，我在这里介绍的带标签和无标签的构造只是开始，研究仍在继续，人们已经开发出比我在这里介绍的更多的构造。
构造与转移定理
我们讨论了“加”运算，它和以前一样，取 A 和 B 中对象的副本，但以所有一致的方式重新标记。“星积”是取有序对副本的运算。
“序列”类似于我们对无标签所做的，它是 A + (A ★ A) + (A ★ A ★ A) + …，但你可以有像瓮那样的对象集合，也可以有排列成循环序列的对象，等等。
这些是我们可以使用的构造，一个更丰富的构造集，它引出了更丰富的对象类别。同样重要的是，我们有一个转移定理。
如果我们有组合类并且知道它们的指数生成函数，那么无论我们从该列表中选择什么运算，我们都会知道该运算结果的指数生成函数。
和以前一样：
-
如果做不相交并集，我们得到生成函数的和。
-
如果做带标签星积，我们得到生成函数的积。
-
如果做 k 个对象的序列，它类似于 A(z)^k。
-
任意数量对象的序列是求和，即 1 / (1 - A(z))。
-
如果有一个集合（大小为 k），它是 A(z)^k / k!。
-
任意大小的集合是这些的和，即 e^{A(z)}。
-
环是 A(z)^k / k。
-
任意长度的环是 ln(1 / (1 - A(z)))。
因此，如果我们知道一个组合类的生成函数，并执行这些运算之一，我们就知道结果的生成函数。这是极其强大的。转移定理是符号方法的基础。
基本对象的构造
让我们使用这些运算来看基本对象的基本构造。
-
瓮：瓮是原子的一个集合。根据集合的转移定理，这立即转化为 e^z。正如我们所见，这给出了计数序列 u_n = 1。
-
环：环是原子的一个环。同样，根据转移定理，生成函数是 ln(1 / (1 - z))，因此计数序列是 n! 乘以该式中 z^n 的系数，即 (n-1)!。
-
排列：和比特串一样，有两种不同的方式来定义排列。
-
你可以说排列是原子的一个序列。然后根据转移定理立即得出，排列的生成函数必须是 1 / (1 - z)。
-
或者你可以说，排列要么是空的，要么是一个原子与一个排列的星积，这将生成所有可能的排列。这立即转化为 P(z) = 1 + z * P(z)。解出 P(z) 得到相同的结果。然后计数序列是 n! 乘以该式中 z^n 的系数，即 n!。
-
这些只是一些基本构造的起点。
转移定理的证明同样直接来自定义以及我们之前讨论过的生成函数计数方法。
-
加：它们分离成不相交的集合，这立即给出结果。
-
星积：它是我们之前见过的那种卷积。为了进行所有不同的重新标记，我们从 A 中取一个 α，从 B 中取一个 β。重新标记的方式数是 C(α+β, α)。然后，由 α 和 β 组成的对象的大小是 z^(α+β)，分母是 (α+β)!。如果你进行这个复杂的求和，(α+β)! 会抵消，你可以分离出 z^α/α! 和 z^β/β! 来得到它又是一个乘积。这是一个复杂的卷积，但这是我们唯一需要做的一次。
对于其他运算，虽然涉及一些数学，但原理很简单。正如我们之前所见，A(z)^k 是 k-序列的指数生成函数。如果你把它们全部加起来，对于任意长度的序列，你得到 1/(1-A(z))。但如果你有所有大小为 n 的 k-序列，那么每个大小为 n 的 k-环会出现 k 次（每个循环方向一次）。这意味着 A(z)^k / k 是 k-环的指数生成函数。然后对所有 k 求和，就得到任意长度环的结果。类似地，如果你有所有大小为 n 的 k-序列，所有集合会出现 k! 次。这意味着 A(z)^k / k! 是大小为 n 的 k-集合数的指数生成函数。然后对所有 k 求和，就得到任意集合的结果，即 e^{A(z)}。
这些值得研究，但它们非常直接，源于定义和生成函数计数的基本思想。
一个有趣的例子：环的集合
现在我们来看一个更有趣的例子。我们有这些运算，可以以各种有趣的方式组合它们。实际上，正如我们将在第二部分看到的，组合这些基本运算的每一种方式都引出了人们详细研究过的组合类，但我们也可以加入更多运算。
这是一个著名的例子：带标签原子的环集合有多少种？例如，对于三个原子，你可以有一个大小为 3 的环，有两种不同的标记方式；或者你可以有一个大小为 1 的环和另一个大小为 2 的环，有三种标记可能性；或者你可以有三个大小为 1 的环。总共有 6 个带标签原子的环集合。如果你计算出四个原子的情况，右边是所有可能性：四个单例环，或一个大小为 4 的环（有 6 种标记方式），或者介于两者之间的东西。你可能认出了这些数字，是的，n 个带标签原子的环集合有 n! 个。接下来我们将看看如何从解析组合学中了解到这一点。
这不仅具有指导意义，还为我们解决原本无法解决的问题奠定了基础。
让我们使用常规方法。我们必须阐明我们的类是什么。P* 是所有原子环集合的类。原子数量是大小。像往常一样，指数生成函数将系数 [z^n/n!] 联系在一起，即 n 个原子的环集合的数量。原子只是带标签的原子，对于带标签类，这总是一样的。
我们的构造是什么？它只不过是说：原子的环集合就是原子的环集合。数学上就是这么说的，根据转移定理，它立即转化为：环的生成函数是 ln(1/(1-z))，某物的集合是 e 的该函数次幂。结果就是 1/(1-z)。因此计数序列是 n!，这与排列相同。同样，这是一个非常快的结果，它直接来自组合描述：一个环的集合，我们可以立即从转移定理得到环集合的生成函数。
这是一个众所周知的组合双射：一个排列就是一个环的集合。要看到这一点，可以从任何地方开始。例如，从 4 开始。在这个排列中，我们查看序列中该位置的索引（即排列中的第 4 个条目），它说是 10，所以我们转到 10。10 处的条目是 6，所以我们转到 6。6 处的条目是 15，所以我们转到 15。关键是从这个例子中可以看到，最终你会回到起点。这就是一个环。我们可以像这样描述它：从 4 到 10 到 6 到 15 回到 4。如果你这样做，如果已经处理过一个项就忽略它，否则继续这个过程，你可以将任何排列转换为一组环。弄清楚如何从一组环重建一个排列是一个值得做的练习，但这是一个著名的双射。
实际问题：错位排列
这引出了我们的第一个实际问题，你可能不知道答案，或者你可能知道，因为这是一个经典问题。但我们会遇到一个你可能不知道答案的问题。
这就是错位排列问题，一个来自 18 世纪的著名问题。当时它是这样表述的：有 n 个人去看歌剧，他们把帽子留在衣帽间的架子上，但帽子看起来都一样。当他们离开时，每个人都随机拿一顶帽子。问题是：没有人拿到自己帽子的概率是多少？
用组合学术语来说，我们称之为错位排列。没有人拿到自己的帽子，意味着没有单例环。拿到自己的帽子意味着如果你在位置 4，你拿到的是第 4 项。这是一个单例环。所以问题是：一个排列是错位排列的概率是多少？或者有多少个错位排列？作为一个有趣的旁注，几个世纪以来，这个问题以许多不同的方式被提出。那是经典的歌剧方式。有些人说，教授随机发回考试，没有人拿到自己考试的概率是多少？许多人在组合学课上用这种方式提出问题。或者一个更有趣的方式是“醉酒的水手”：一群有点醉的水手回家后随机睡在船舱里，没有人睡在自己船舱的概率是多少？或者对大学生更相关的是，住在单间宿舍的学生也喝醉了，没有人最终睡在自己房间的概率是多少？这都是同一个问题。为了解决这个问题，我们想要计算错位排列的数量。
错位排列就是没有单例环的排列。这是我们环集合的表格，其中带有单例环的排列被灰显了。对于大小为 4 的排列，有 9 个排列没有单例环。因此，没有人拿到自己帽子的概率是 9/24。
这个序列可能不熟悉，让我们看看如何用符号方法分析它。
我们将按照常规步骤进行。定义 D 为所有错位排列的类。大小是原子数。标准的带标签原子。生成函数总是指数生成函数。那么组合构造是什么？
一种表述方式是：错位排列是一个长度大于 1 的环的集合。排列是原子的环集合。这个排除了长度为 1 的环。这立即转化，所以错位排列（没有单例环的排列）就是它所说的。
因此，“集合”运算是 e^{某函数}。长度大于 1 的环的生成函数是什么？所有环的生成函数是 z + z^2/2 + z^3/3 + …，我们只是去掉第一项 z。所以立即转化，那就是 ln(1/(1-z)) - z。这个无穷级数正是 ln(1/(1-z)) - z。如果我们简化它，得到 e^{-z} / (1-z)。
这是生成函数的直接转化。另一种推导方式可能更容易理解：我们可以说，一个排列是单例环的集合与一个错位排列的（星）积。然后这立即转化为 e^z * D(z) = 1/(1-z)，解出 D(z) 得到相同的结果。
因此，符号方法给了我们生成函数。现在，从这个函数中提取系数有点复杂。我们实际上已经在关于渐近分析的讲座中做过了。
结果是它渐近于 1/e。让我们看看其中的每个元素。首先，由于我们想要概率，使用指数生成函数很方便，因为概率的分母是 n!，所以我们利用了这一点。这不是巧合，但在这种情况下，它确实有效。为了得到概率，我们只需查看生成函数中 z^n 的系数（不需要再乘以 n!，因为它会被约掉）。所以概率是 D_n / n!。那个系数是什么？它是 e^{-z} 和 1/(1-z) 的卷积。你只需进行卷积，z^n 的系数是 Σ_{k=0}^{n} (-1)^k / k!。这是一个直接的卷积，然后这个求和我们在渐近分析讲座中作为“尾界”的例子研究过，以证明它渐近于 1/e，并且非常接近 1/e。
在本讲座的最后，我们将看一种更简单的方法来得到这个结果。但符号方法让我们到达那里，并为这类问题提供了实用的解决方案。实际上，如果你去参加派对，喝醉了，最终随机进入一个房间，你有相当好的概率（约 36%）没有人最终睡在自己的房间。或者，也许告诉你父母这个问题的方式是：当学生毕业并把帽子扔向空中，每个人随机接住一顶帽子，没有人拿回自己帽子的概率是 36%。实际上，你的父母或租赁公司可能希望你拿回自己的帽子。这就引出了广义错位排列的概念。如果你随机拿到一顶帽子，你总是可以通过跟随环来拿回自己的帽子。例如，学生 4 拿到了 10 的帽子，她可以去找 10；10 拿到了 6 的帽子，然后她可以去找 6；6 拿到了 15 的帽子，然后她可以去找 15；15 那里有她的帽子。所以跟随环可以让你拿回帽子。
现在我们有一个更普遍的问题：所有环的长度都大于 M 的概率是多少？也就是说，每个人都必须至少与 M 个朋友或 M 个随机的人交谈才能拿回帽子。这就是广义错位排列问题：所有环的长度都大于 M 的概率是多少？
这个问题分析起来要困难得多，但使用符号方法，我们可以直接得到生成函数。它只是推广我刚才给出的论证。D_sub_M 是所有广义错位排列（没有长度小于或等于 M 的环）的类。其他一切相同。
构造是：它是长度大于 M 的环的集合。这直接转化为生成函数：你从 z^(M+1)/(M+1) 项开始。或者，它是 ln(1/(1-z)) 减去 z + z^2/2 + … + z^M/M。
简化后，我们得到 e^{-z - z^2/2 - … - z^M/M} / (1-z)。这就是我们从符号方法立即得到的生成函数。
非常简单，如果没有这种符号方法，你可能很难自己得到这个生成函数。当然，因为符号方法背后的原理很简单，所以做这些事情是可能的，但符号方法确实让它变得连孩子都能做。
这就是生成函数方程。现在要找到这个问题的答案，我们需要从这个方程中提取系数。这个就不那么明显了，它将是一个更复杂的卷积。尝试从那个函数中提取系数，这将激发我们思考：如何找到系数？如何估计那个复杂函数中 z^n 的系数？这将激发解析组合学的第二部分：解析转移定理。
但这是对带标签对象符号方法的基本介绍。
本节课总结：在本节课中，我们一起学习了带标签组合对象的基本概念。我们了解了带标签与无标签对象的区别，认识了瓮、排列、环等基本带标签类及其指数生成函数。我们介绍了处理带标签类时更丰富的构造运算（如星积、集合、序列、环）以及强大的转移定理，它能将组合构造直接转化为生成函数方程。最后，我们应用符号方法解决了经典的错位排列问题，并推广到更一般的广义错位排列，展示了符号方法在将复杂组合问题转化为可分析的生成函数方面的强大能力。这为后续学习解析方法（如系数提取和渐近分析）奠定了基础。
021：系数渐近分析 📊
在本节课中，我们将学习如何通过生成函数来估计系数，特别是利用符号方法轻松获得生成函数后，如何进一步得到其系数的渐近估计。我们将介绍一个强大的工具——收敛半径转移定理，并通过实例展示其应用。
概述
上一节我们介绍了生成函数及其符号方法。本节中，我们来看看如何从生成函数中提取系数的渐近信息。幸运的是，我们通常可以通过通用的“转移定理”立即获得系数渐近估计。
转移定理简介
我们已经见过一些适用于许多情况的转移定理例子。
-
泰勒定理：这是一个转移定理。如果你有一个生成函数 F(z)，并且知道它的导数，那么 F(z) 中 z^n 的系数就是 F 在零点处的 n 阶导数除以 n!。对于许多函数，这是我们提取系数、开始处理生成函数的方式。
-
有理函数：我们在生成函数和渐近分析的讲座中讨论过这个例子。为了简化，本幻灯片展示一个特例。如果 F(z) 和 G(z) 是多项式，那么比值 F(z)/G(z) 中 z^n 的系数取决于分母的最大根。如果 1/β 是该根，则表达式 β * F(1/β) / G’(β) * β^n 给出了系数的渐近形式，其增长类似于 β^n。如果该根的重数为1，这就是常数项；如果重数更高，则有一个更复杂的公式。
以上是两个转移定理的例子。接下来我想讨论的是所谓的“收敛半径转移定理”，它涵盖了我们今天讨论的许多问题以及其他问题。实际上，我们在现实生活中使用的大多数转移定理都基于复分析渐近，我们将在第二部分详细讨论。但收敛半径定理适用于许多情况，有助于在这个层面上对解析组合学进行连贯的处理。
收敛半径转移定理
以下是定理内容。这个定理的核心思想是，函数 1/(1-z) 经常出现在我们发展的组合结构中。这里将其推广为 (1-z)^α，其中 α 不一定是整数，唯一的限制是它不能是零或负整数。在某种意义上，它推广了我之前做的比值情况（那时 G(z) 是多项式），现在它是 (1-z) 的 α 次幂。
定理：设 F(z) 在 |z| < 1 内解析，且 α 不是 0, -1, -2, …。那么，F(z)/(1-z)^α 中 z^n 的系数渐近于 F(1) * C(n+α-1, n)。这进一步渐近于 F(1) * n^(α-1) / Γ(α)。
这里，Γ(α) 是一个常数，我稍后会讨论。
我现在不进行证明，因为大多数人只想应用这个定理而不是证明它。但证明并不难，它本质上是一个涉及广义二项式定理的卷积，并且由于级数收敛，前 n 项系数的和以指数速度收敛于 F(1)。这是第一部分证明的简要描述。第二部分是标准的渐近分析，只是使用了广义二项式系数和 Γ 函数的定义。
Γ 函数简介
如果你不知道 Γ 函数是什么，这里有一个非常简要的总结：它是推广阶乘函数的一种方式，在解析组合学和算法分析中扮演重要角色，因为它出现在像这样的转移定理中。
对于实数 z，定义函数 Γ(z) = ∫_0^∞ t^(z-1) e^(-t) dt。这个函数具有我们期望的推广阶乘的性质。
例如：
-
Γ(α+1) = α * Γ(α)，就像 n! = n * (n-1)!。
-
计算可得 Γ(1) = 1，因此 Γ(n+1) 恰好等于 n!。所以对于整数，它与阶乘匹配。
-
但它对任何 α 都满足这个性质，且 Γ(1)=1。
-
对我们来说经常出现的一个值是 Γ(1/2)。如果你想计算 Γ(1/2)，令 z=1/2，你会得到类似正态分布积分的形式，计算结果为 √π。
所以，Γ(1/2) = √π 是一个我们需要知道的值，因为我们在 α = 1/2（例如 √(1-z)）的情况下应用这个定理。
这是一个转移定理，适用于某个函数与 (1-z)^α 的卷积，而这种情况经常出现。
定理的推广
更一般地，如果收敛半径大于某个 ρ，且 ρ ≠ 0（这实际上就是将定理应用于 z/ρ，在定理中代入 z/ρ），那么我们会得到稍微更一般的形式：1/(1 - z/ρ)^α，这会在渐近式中提出一个 ρ^n 因子。
所以，这个推论才是我们真正感兴趣的。
定理应用实例
如果生成函数具有那种形式，我们就知道其渐近性质。这适用于本讲座到目前为止讨论的两个主要问题。
1. 卡特兰数
对于卡特兰数，T(z) = (1 - √(1-4z)) / (2z)。这里有一个小复杂之处，因为第一项必须消去，但忽略这一点，我们使用的是 α = -1/2（分母中是 √(1-4z) = (1-4z)^(1/2)，所以整体是 (1-4z)^(-1/2) 的形式），并且 ρ = 1/4。那么，F(z) 在这种情况下只是前面的常数 1/2。
因此，我们最终需要 Γ(-1/2)，根据 Γ(α+1) = αΓ(α)，它等于 -2Γ(1/2) = -2√π。代入所有值，也许最容易理解的方法是两边乘以 z，然后精确应用这些公式。完成计算以证明这个转移定理立即给出了卡特兰数的渐近形式并不困难。
所以，一个转移定理（符号方法）得到生成函数，另一个转移定理（解析的）得到系数的渐近估计。
2. 错位排列问题
同样的定理也适用于广义错位排列问题。对于错位排列，我们有这个复杂的函数，但在这个转移定理下并不复杂：我们有 α = 1，ρ = 1，我们的函数 F(z) 是 e^(-z - z^2/2 - … - z^m/m)。我们需要做的就是计算 F(1)，即 e^(-1 - 1/2 - … - 1/m) = e^(-H_m)，其中 H_m 是调和数。这立即给出了渐近估计 ~ e^(-H_m) / n!。
所以，对于第一个问题（卡特兰数），需要很多计算才能得到结果；对于第二个问题（错位排列），我们甚至不知道如何直接得到结果，但通过这个解析转移定理，我们可以立即得到结果。
更广阔的图景：通用定律
这仅仅是个开始。第二部分将致力于探讨基于复分析渐近的转移定理所能得出的真正通用定律。这里只提一个例子（有很多技术细节），让你有个概念：
如果你有一个组合构造系统，包含许多类别，它们通过一系列操作（用 Op0, Op1, … 表示，这些操作可以是序列、乘积等）相互作用，你可以创建一整套组合构造的线性系统。一个非常简单的特例是二叉树：T = Z + Z * T * T。你可以有更复杂的东西，比如循环、集合的二叉树等等。
一个由组合类组成的完整系统，一整套组合构造，通过符号方法可以立即转移为一个生成函数方程组。
这很好，但这些生成函数方程可能相当复杂且难以求解。然而，实际上有一种称为 Gröbner 基消元法 的方法，可以将所有这些方程简化为一个单一的生成函数方程。不仅如此，还有一个称为 Drmota–Lalley–Woods 定理 的定理表明，该方程有一个显式解（在复数域中涉及平方根）。还有一个称为 奇点分析 的过程，可以立即给出一个简单的渐近形式。
因此，任何 这样的组合构造，其对象数量的渐近形式都是 A / (2√π) * n^(-3/2) * B^n，其中 A 和 B 是我们可以从构造中显式计算出的常数。
这是一个惊人的通用定律。你可以在较旧的数学文献中找到数百篇得出这类结果的论文，而这一过程就涵盖了它们。这只是我们在解析组合学中看到的众多通用定律中的一个例子。
总结
本节课中，我们一起学习了系数渐近分析的核心方法。我们介绍了如何利用转移定理，特别是收敛半径转移定理，从生成函数直接获得系数的渐近估计。通过卡特兰数和错位排列的例子，我们看到了该定理的强大与便捷。最后，我们展望了基于复分析的更通用定律，它们能够为一大类组合结构提供统一的渐近形式，展现了解析组合学的深刻与优美。
022：视角与展望 📊
在本节课中，我们将对解析组合学这门强大的“微积分”进行总结与展望。我们将回顾其核心流程，对比传统方法与解析组合学方法的差异，并了解其在后续课程中的广泛应用。
概述
解析组合学为我们研究各种大型组合结构提供了一套非常有效的定量分析框架。其核心流程始终如一：从一个组合构造出发，推导出对应的生成函数，最终通过复渐近分析得到系数渐近式。通常，我们甚至无需显式求解生成函数，仅凭方程的形式就能应用转移定理，直接获得我们感兴趣的渐近结果。
传统方法与解析组合学对比
上一节我们介绍了生成函数的威力，本节中我们来看看解析组合学如何简化分析过程。
回想一下我们在前四讲中讨论的内容与本次讲座的对比。
-
以二叉树计数为例：传统方法需要一整页幻灯片来从递推关系推导涉及卷积的生成函数。然后展开该生成函数涉及使用二项式系数进行复杂计算，才能得到卡特兰数的精确形式。接着，我们还需使用斯特林近似进行渐近分析，这同样涉及大量计算。第一次接触这些步骤时，你会觉得每一步都充满了复杂的计算，尽管每一步本身是直接的。
-
解析组合学方法：使用解析组合学，我们不再进行那些计算。我们只需建立组合构造，得到生成函数方程，然后应用转移定理即可获得我们感兴趣的渐近结果。这些结果通常非常精确，足以满足实际应用需求。
再以错位排列为例，传统方法的计算过于复杂，我们甚至没有展示计算过程。但通过解析组合学，我们可以立即得到系数渐近式。
解析组合学的特点与应用范式
这是一个能体现解析组合学特点的典型例子。我们从一个基本构造（排列是环的集合）出发，稍作修改即可得到答案。这非常普遍：
-
基础构造：我们从一些希望研究的基本事物（如排列、树、字符串）开始。它们要么是初等的，要么是平凡的，要么符合我们的直觉，我们理解它们。但我们尝试从解析组合学的角度来理解它们。
-
复合构造：然后我们可以有复合构造，例如一组环、集合的序列等等。我介绍的只是部分构造，实际上还有很多其他可用的构造。这些构造能告诉我们关于结构的信息（例如排列作为环的集合），实际上许多经典组合学问题都可以用这种方式处理。
-
变体与推广：接下来是变体，例如推广错位排列或添加其他参数。可能性几乎是无限的。不仅如此，当我们得到一个生成函数方程时，通常存在一个普适定律能直接给出渐近结果。原则上，你可以通过精确结果再进行渐近分析（因为解析组合学的基础是一系列非常简单的技术），但如果你的目标就是渐近结果，何必多此一举呢？
这是一个非常标准的范式。此外，组合参数也可以处理，我们将会看到很多例子。这意味着我们不仅仅是计数事物，还在计数事物的属性。
处理组合参数：以二叉树叶子节点为例
在关于生成函数的讲座中，我们讨论了“累计成本”的概念。我们不是使用概率来计算平均值，而是计算所有结构中的总成本，然后相除。这将寻找随机对象中某个属性的期望值问题，简化为两个计数问题。
以下是寻找二叉树中叶子节点平均数量的步骤：
-
计数对象总数：使用标准流程计数二叉树，得到卡特兰数的估计。
-
计数总成本：符号方法同样适用于二元生成函数。因此，相同的构造将给出总成本（即所有树中的叶子总数）的显式方程。你只需用另一个变量跟踪叶子节点，相同的构造流程依然适用。
-
求导与计算：像我们之前所做的那样，求导并在1处取值，即可得到所有树中的叶子总数。我们将再次得到一个显式结果，并且也有直接的转移定理。
-
相除得平均值：我们无需深入细节。有了这两个渐近结果，我们只需相除，就得到了
n/4这个结果。同样，我们可以在不展示之前所有细节的情况下完成这一切。
核心流程总结
现在，在学习了多个例子之后，这张幻灯片可能更容易理解了。
在解析组合学中，我们：
-
从组合构造开始。
-
使用符号转移定理得到生成函数。生成函数是研究的核心对象，因为我们通过组合构造转移到它们。
-
使用解析转移定理从生成函数中提取系数。
原则上，我们可以在标准尺度上以任何精度进行此操作，并且也能处理各种变体。
课程展望与练习
在接下来的课程中，我们将看到解析组合学的许多应用。首先我们将研究树，然后是排列（实际上可以表示为某种标记树），接着是比特串及其相关的数据结构，以及映射这些迷人的结构。这些都在算法分析中有广泛应用。
为了巩固你对这些材料的理解，以下是一些练习：
-
练习 5.1：有多少个长度为
n的比特串中不出现三个连续的零？这是一个尝试应用这些技术的好练习。 -
关于树的练习：再次演练解析组合学的步骤，解决类似问题。这里二叉树的大小是总节点数（内部和外部）。总节点数总是奇数。请为此得到一个表达式。
-
关于排列的练习：如果所有环的长度都是奇数呢？这是一个简单的问题。
-
关于树参数的练习：图中的红色节点有两个内部子节点，蓝色节点有一个内部和一个外部子节点。红色节点和蓝色节点的平均数量是多少？我们已经知道叶子节点的平均数量是
n/4，这是类似的问题。
对于下一讲，如果你能写出这些练习的解决方案，并阅读教材中关于解析组合学的章节，你将对我们从下一讲开始的算法分析基础有很好的理解。
总结
本节课中，我们一起学习了解析组合学的核心视角与强大之处。我们了解到，它将复杂的组合计数与渐近分析，系统化地转化为基于构造、生成函数和转移定理的流畅流程，极大地简化了分析工作，并为后续研究树、排列、字符串等复杂结构及其在算法分析中的应用奠定了坚实基础。
023：树与森林 🌲
在本节课中，我们将学习树与森林的基本概念。这是课程下半部分关于应用主题的第一讲。我们将从回顾二叉树开始，然后扩展到更一般的树和森林的定义，并学习如何使用解析组合学的方法来研究它们。
二叉树回顾 🌳
上一节我们介绍了二叉树。二叉树由一个外部节点，或一个内部节点及其两个子树（顺序重要）构成。顶部是根节点，根节点可以有两个子树作为其子节点。底部的节点称为叶子节点，其两个子节点均为外部节点。我们通常用圆圈表示内部节点，用小方框表示外部节点。
节点的深度从根节点（深度为0）开始计算，根节点的子节点深度为1，以此类推。树的高度是树中最深节点的深度。
我们之前研究的一个问题是：具有 n 个内部节点的二叉树有多少种？答案是卡特兰数。我们使用符号方法进行了推导，其核心步骤如下：
-
生成函数：
B(z) = Σ_{对象 b ∈ B} z^{size(b)}，其中size计算内部节点的数量。 -
组合构造：二叉树
B的定义可以符号化表示为：B = ε + (● × B × B)。其中ε代表空树（外部节点），●代表一个内部节点。 -
转移定理：上述构造直接转化为生成函数方程：
B(z) = 1 + z * B(z)^2。 -
求解：解此方程可得
B(z) = (1 - sqrt(1 - 4z)) / (2z)，其系数渐近估计为卡特兰数。
这是对二叉树符号方法的快速回顾，为我们今天要处理的不同问题设定了背景。
树与森林的定义 🌲➡️🌳🌳
现在，我们来看更一般的数学概念。经典的树概念通常基于森林。
-
森林 是一组树的序列。
-
树 是一个称为根的节点，连接到森林中所有树的根。
这是一个递归定义：森林是树的序列（可以为空）；树是一个根节点，连接到其子森林中所有树的根。因此，一个根节点可以有任意数量（包括零个）的子节点。没有子节点的节点称为叶子节点。
节点的深度和树的高度定义与二叉树相同。与二叉树不同，一般树没有显式的“外部节点”概念。
一个立即出现的问题是枚举：具有 n 个节点的森林有多少种？下图展示了具有1、2、3、4个节点的所有森林。
你可以立即认出，卡特兰数再次出现了。例如，有5种具有3个节点的森林。同样，树是根节点连接到一个森林，因此具有 n 个节点的树的数量，等于具有 n-1 个节点的森林的数量，其数值也是卡特兰数（平移后）。
解析组合学推导 📊
接下来，我们使用解析组合学来推导树和森林的生成函数。我们将严格遵循之前概述的基本步骤。
定义两个组合类：
-
F: 所有森林的类，大小函数为节点数。 -
G: 所有树的类，大小函数为节点数。
我们的原子是节点，其生成函数为 z。
根据定义，我们可以直接得到组合构造：
-
森林是树的序列：
F = SEQ(G) -
树是根节点加上一个森林：
G = ● × F
应用转移定理，我们立即得到它们的普通生成函数方程：
-
F(z) = 1 / (1 - G(z)) -
G(z) = z * F(z)
现在我们来解这个方程组。将第二个方程代入第一个：
F(z) = 1 / (1 - z * F(z))
整理得：F(z) - z * F(z)^2 = 1
这正是卡特兰数的生成函数方程。因此，具有 n 个节点的森林数等于具有 n 个节点的二叉树数（卡特兰数）。具有 n 个节点的树数则等于具有 n-1 个节点的森林数。
双射：森林与二叉树的对应关系 🔄
从解析角度看，我们得到了结果。但在组合学中，当发现两个类枚举结果完全相同时，我们通常希望找到一个双射，即两个类中每个成员之间的一一对应关系。这种双射很重要，因为它为我们提供了一种在计算机中方便地表示森林和树的方法。
以下是该双射的规则：每个具有 n 个节点的森林都精确对应一个具有 n 个节点的二叉树。
森林中的节点可以有多个孩子，而二叉树中的节点恰好有两个孩子（左、右）。对应的方式是：对于森林中的每个节点，我们将其连接到它的第一个孩子（作为二叉树的左孩子）和它的下一个兄弟（作为二叉树的右孩子）。
另一种更容易理解的方式是旋转对应。如果你将二叉树顺时针旋转45度，并将右孩子边视为“兄弟”关系，你就会看到森林的结构。
这种表示法在计算机中非常有用，因为二叉树很容易用内存块表示（每个节点包含信息和两个子指针），而森林中每个节点的子节点数量可变，在某些计算环境中可能不方便处理。
树的绘制算法 🎨
作为补充，我们思考一下绘制二叉树的算法。展示这个是因为我将展示许多二叉树，而编写绘制二叉树的程序对每个人都是一个有价值的练习。
最自然且常用的方法（特别是在讨论排序和搜索算法时）如下：
-
Y坐标：很简单，就是节点的深度。通常我们从根节点在顶部开始，所以
y = 高度 - 深度。 -
X坐标：最简单的方法是递归地执行树的中序遍历，并在每次访问节点时分配X坐标。递归程序可以这样定义：根节点的X坐标是其左子树中的节点数加1。右子树中所有节点的X坐标都大于此值。
这种方法有两个优点：第一，通过中序遍历很容易分配坐标；第二，它能将树中的节点很好地间隔开。通常我们在绘制大型二叉树时会省略外部节点。
但这种方法有一个问题：对于某些类型的树（特别是表示一般树的二叉树），可能会产生冗长而分散注意力的边。有时我们会采用另一种方法：在每一层，我们将该层的节点均匀分布，并以根节点为中心。这种绘制方式很有用，因为它能展示树的“轮廓”，即每层有多少节点，这在某些分析中是一个有趣的属性。
下图是使用第一种方法绘制的随机二叉树示例。
当你观察随机二叉树时，它们拥有许多不同的形状。随机树或随机森林也会呈现出各种各样有趣的形态。
我们面临的挑战，也是我展示这些大型二叉树的原因，就是我们需要以某种方式（例如对所有树进行平均）从解析角度描述这种行为。令人惊讶的是，我们能够在这方面取得很大进展，而这正是我们现在要开始做的事情。
总结 📝
本节课中，我们一起学习了树与森林的基本概念。我们从二叉树的回顾开始，然后定义了一般意义上的树和森林。我们使用解析组合学的方法推导出它们的生成函数，并确认其数量由卡特兰数给出。我们还探讨了森林与二叉树之间重要的双射关系，这为计算机表示提供了便利。最后，我们简要介绍了树的绘制算法。这些基础为我们后续分析树的更多参数和行为做好了准备。
024：二叉搜索树 🧮
在本节课中，我们将要学习计算机科学中的一个经典且重要的数据结构——二叉搜索树。我们将了解它的基本概念、工作原理，以及它与纯组合数学中的随机二叉树有何不同。
概述
二叉搜索树是一种用于实现符号表（或称字典）的基础数据结构。它允许我们高效地插入、查找和删除与键相关联的数据。其核心思想是利用二叉树的结构，并遵循一个简单的排序规则：对于任意节点，其左子树中的所有键都小于该节点的键，其右子树中的所有键都大于该节点的键。
数据结构定义
二叉搜索树由节点构成。每个节点包含一个键、一个关联的值，以及指向其左子树和右子树的引用。
在Java中，我们可以用以下代码定义一个节点：
class Node<Key, Value> {
Key key;
Value val;
Node left;
Node right;
}
这个定义体现了二叉搜索树的递归结构：一个树要么为空（null），要么是一个根节点，该节点连接着两个更小的二叉搜索树（左子树和右子树）。
查找操作 🔍
查找操作是二叉搜索树的核心功能之一。其算法非常直观，利用了树的有序性。
以下是查找操作的递归实现逻辑：
-
从根节点开始。
-
将目标键与当前节点的键进行比较。
-
如果目标键小于当前节点的键，则递归地在左子树中继续查找。
-
如果目标键大于当前节点的键，则递归地在右子树中继续查找。
-
如果目标键等于当前节点的键，则查找成功，返回该节点关联的值。
-
如果到达一个空链接（
null），则说明键不存在于树中，返回null。
这个过程就像在一个有序的列表中执行二分查找，但数据是以树形结构组织的。
插入操作 ➕
插入操作与查找操作紧密相关。其基本思想是：先执行一次查找。如果找到了键，则更新其关联的值；如果未找到（最终到达一个空链接），则在该位置创建一个新节点。
以下是插入操作的递归实现逻辑：
-
从根节点开始递归查找插入位置。
-
如果当前节点为
null，说明到达了应插入的位置，在此处创建一个新节点并返回。 -
否则，比较键值：
-
若新键较小，则递归地在左子树中插入。
-
若新键较大，则递归地在右子树中插入。
-
-
递归调用返回后，将返回的（可能是新的）子树链接回当前节点。
通过这种递归方式，新节点被自然地“挂”到了树中正确的位置。
树的形状与性能分析 ⚖️
上一节我们介绍了插入和查找的基本操作，本节中我们来看看一个关键问题：二叉搜索树的性能。
二叉搜索树的性能高度依赖于树的形状，而树的形状又完全由键被插入的顺序决定。
-
最佳情况：如果键以完全平衡的顺序插入，树的高度约为 log₂ N。此时查找和插入的时间复杂度为 O(log N)，效率极高。
-
最坏情况：如果键按严格递增或递减的顺序插入，树会退化成一条链表，高度为 N。此时查找和插入的时间复杂度退化为 O(N)，效率很低。
对于一个包含海量数据（如百万或十亿级）的符号表，O(log N)和O(N)的性能差异是决定性的，可能直接导致一个应用可行或不可行。
随机二叉搜索树模型 🎲
为了进行理论分析，我们通常假设键是以随机顺序插入的。这是一个合理的模型，在许多实际场景中能得到验证。
在随机插入的假设下，生成的二叉搜索树趋向于相对平衡，这与纯组合数学中的“随机二叉树”模型有本质区别。
-
随机二叉搜索树模型：输入是一个随机的排列（共
N!种可能）。树形是排列的属性。 -
卡塔兰随机二叉树模型：每个具体的树形结构（共
C_N种，C_N为卡塔兰数）是等概率出现的。
这两种模型产生的树形分布截然不同。随机二叉搜索树更可能产生平衡的树形。
树形与排列的映射关系 🔗
理解为何随机二叉搜索树更平衡的关键，在于探究有多少种不同的插入排列会生成同一个树形。
对于一个给定的树形T，设其左子树有L个节点，右子树有R个节点。那么，能生成树形T的排列数量P(T)满足以下递归公式：
P(T) = (L+R choose L) * P(T_left) * P(T_right)
其中，(L+R choose L)是二项式系数，表示将左子树和右子树的节点在插入序列中交错混合的方式数。
这个公式揭示了一个重要事实：当左右子树大小接近（即树更平衡）时，二项式系数(L+R choose L)的值远大于子树大小悬殊时的情况。因此，平衡的树形对应着更多的插入排列，从而在随机插入模型下出现的概率也更高。
两种模型的概率分布对比 📊
我们可以通过根节点秩（即根节点是第几小的元素）的概率分布来直观对比两种模型。
-
在随机BST模型中：根节点是插入序列的第一个元素。由于序列是随机的，任何键成为根节点的概率都是1/N。这是一个均匀分布。
-
在卡塔兰随机树模型中：每个树形等可能。根节点秩为
k的概率由卡塔兰分布给出。该分布的质量高度集中在边缘（即k接近1或N），意味着树极有可能非常不平衡。事实上，至少有一个子树为空的概率约为1/2。
下图展示了卡塔兰分布的形状，清晰表明了其不平衡性。
总结
本节课中我们一起学习了二叉搜索树这一核心数据结构。
我们首先了解了它的定义和用于实现符号表的目的。接着，我们详细探讨了其查找和插入操作的递归算法。然后，我们深入分析了决定其性能的关键因素——树的形状，并引入了随机二叉搜索树作为分析模型。
最后，我们通过比较随机BST模型和卡塔兰随机树模型，从原理上解释了为何在实际的随机插入下，二叉搜索树倾向于保持相对平衡。核心结论是：平衡的树形对应着指数级更多的插入序列，因此在随机模型中出现的概率远高于不平衡的树形。这为二叉搜索树在实践中良好的平均性能提供了理论依据。
025：路径长度分析 📊
在本节课中，我们将要学习二叉树中路径长度的分析。路径长度是衡量树中节点到根节点平均距离的重要指标，它直接关系到二叉搜索算法等算法的性能预测。
概述
我们将首先定义内部路径长度和外部路径长度，并探讨它们之间的递归关系。接着，我们会分析两种不同类型的树：随机二叉树和由随机排列构建的二叉搜索树。通过解析组合数学的方法，我们将推导出它们平均路径长度的渐近表达式，并比较两者的差异。
二叉树路径长度定义 🌳
在二叉树中，每个节点都有一个深度，即从根节点到该节点的路径上的边数。
-
内部路径长度 定义为所有内部节点（非叶子节点）的深度之和。
-
外部路径长度 定义为所有外部节点（空链接或叶子节点下的虚拟节点）的深度之和。
计算内部路径长度的方法是：统计每一层的节点数，将层数与该层节点数相乘，然后对所有层求和。例如，若第1层有2个节点，第2层有4个节点，则内部路径长度贡献为 1*2 + 2*4 + ...。
上一节我们介绍了路径长度的基本概念，本节中我们来看看路径长度之间的一些基本递归关系。
路径长度的递归关系 🔄
设一棵二叉树 T，其左子树为 TL，右子树为 TR。我们用 size(T) 表示内部节点数，xsize(T) 表示外部节点数，IPL(T) 表示内部路径长度，XPL(T) 表示外部路径长度。
以下是它们之间的递归关系：
-
内部节点数:
size(T) = size(TL) + size(TR) + 1（根节点计为1） -
外部节点数:
xsize(T) = xsize(TL) + xsize(TR) -
内部路径长度:
IPL(T) = IPL(TL) + IPL(TR) + (size(TL) + size(TR))- 解释：左右子树的路径长度之和，还需要为左右子树中的每一个节点额外加上从根到该子树的这条边（即深度+1）。
-
外部路径长度:
XPL(T) = XPL(TL) + XPL(TR) + (xsize(TL) + xsize(TR))- 解释：原理与内部路径长度类似，为每个外部节点加上连接其子树的边。
从这些递归关系出发，可以证明两个简单而重要的恒等式：
-
外部节点数 = 内部节点数 + 1。 (
xsize(T) = size(T) + 1) -
外部路径长度 = 内部路径长度 + 2 * 内部节点数。 (
XPL(T) = IPL(T) + 2*size(T))
这些关系是后续分析的基础。
理解了路径长度的基本性质后，我们进入核心内容：分析随机二叉树的平均路径长度。
随机二叉树的平均路径长度 🎲
我们的第一个问题是：对于一个所有树形等概率出现的随机二叉树（树形总数由卡特兰数给出），其平均内部路径长度是多少？这描述了树中节点平均离根有多远。
我们使用解析组合学中的累积计数法。定义：
-
T(z)：二叉树计数的生成函数（卡特兰生成函数）。T(z) = (1 - sqrt(1-4z)) / (2z)。 -
Q(z)：累积成本生成函数。Q(z) = Σ_{所有树T} IPL(T) * z^{size(T)}。
我们目标是求平均内部路径长度 E[IPL] = [z^n]Q(z) / [z^n]T(z)，即 Q(z) 中 z^n 的系数除以 T(z) 中 z^n 的系数。
关键步骤是利用递归关系建立 Q(z) 与 T(z) 的方程。根据定义 IPL(T) = IPL(TL) + IPL(TR) + (size(TL)+size(TR))，可以推导出生成函数满足的方程：
Q(z) = 2z T(z) Q(z) + z T'(z) T(z)
这是一个关于 Q(z) 的方程。代入已知的 T(z) 及其导数 T'(z)，并利用关系 1 - 2z T(z) = sqrt(1-4z) 进行化简，最终可以解出 Q(z) 的显式表达式。
通过分析 Q(z) 的系数，我们得到所有大小为 n 的二叉树的内部路径长度总和渐近于 4^n。将其除以大小为 n 的二叉树数量（卡特兰数 ~ 4^n / (n^{3/2} sqrt(π))），得到平均内部路径长度的渐近表达式：
平均内部路径长度 ~ n * sqrt(πn)
这是一个精确的渐近结果。对于一个有1万个节点的树，平均深度约为 sqrt(π*10000) ≈ 177。这表明在随机二叉树中，节点平均离根的距离与 sqrt(n) 成正比。
分析完随机二叉树，我们转向在算法中更常见的结构：由随机排列构建的二叉搜索树。
随机二叉搜索树的平均路径长度 🔍
现在考虑二叉搜索树，它由随机排列顺序插入空树构建而成。我们想分析由此得到的BST的平均内部路径长度。
此时，计数对象是排列。大小为 n 的排列有 n! 个。我们定义：
-
P(z)：排列的指数型生成函数。P(z) = 1/(1-z)。 -
C(z)：累积成本的指数型生成函数。C(z) = Σ_{所有排列σ} IPL(BST(σ)) * z^{|σ|} / |σ|!。
这里有一个技巧：由于概率空间是均匀分布的排列（概率为 1/n!），而EGF系数自带 1/n!，因此平均路径长度恰好就是 C(z) 中 z^n 的系数，无需额外除法。
接下来，我们利用BST的递归结构建立方程。对于一个排列，其第一个元素是树根，剩余元素根据与根的大小关系分成左右子排列，分别构建左右子树。路径长度满足：IPL(σ) = IPL(σ_L) + IPL(σ_R) + (|σ_L| + |σ_R|)。
将这个递归关系代入 C(z) 的定义，并进行一系列化简（包括对生成函数求导以消除分母中的阶乘项），最终得到一个关于 C(z) 的微分方程：
C'(z) = 2C(z)/(1-z) + 2/(1-z)^3
这是一个一阶线性微分方程，可以通过积分因子法求解。解得：
C(z) = 2/(1-z)^2 * ln(1/(1-z)) - 2/(1-z)^2
展开 C(z) 的幂级数，提取 z^n 的系数，即可得到平均内部路径长度的渐近表达式：
平均内部路径长度 ~ 2n ln n
因此，在由随机排列构建的BST中，节点的平均深度与 log n 成正比，这远优于随机二叉树的 sqrt(n)。这是因为随机排列更倾向于产生平衡的BST。
这个结果与快速排序的平均比较次数密切相关。事实上，快速排序的递归划分过程与BST的构建过程存在双射关系，快速排序的平均比较次数恰好等于随机BST的外部路径长度。
其他参数与总结 📝
上述分析路径长度的方法可以推广到许多其他树参数，例如计算叶子节点数量等。书中提供了相关练习。
一个更复杂但同样重要的问题是树的高度（最远节点的深度）。其分析更为 intricate，但已知结果如下：
-
随机二叉树的平均高度约为
2 * sqrt(πn)，大约是平均路径长度的两倍。 -
随机BST的平均高度约为
c * ln n，其中常数c ≈ 4.31，也大约是平均路径长度的两倍。
本节课总结：
我们一起学习了二叉树路径长度的分析。我们定义了内部和外部路径长度，并推导了其递归关系。利用解析组合学，我们分别分析了随机二叉树和随机二叉搜索树的平均内部路径长度，得到了截然不同的渐近结果：~ n√(πn) 与 ~ 2n ln n。这深刻揭示了不同随机模型下树结构的差异，并建立了与快速排序算法的有趣联系。这种方法为分析各种树参数提供了强大工具。
026：其他树类型 🌳
在本节课中，我们将探讨算法分析中除二叉搜索树之外的其他树结构。我们将了解数学和计算机科学中定义的各种树类型，并简要介绍一些高级概念和未解决的问题，为后续的深入学习做准备。
自由树、有根树与有序树
上一节我们重点讨论了二叉搜索树。本节中，我们来看看数学中更基础的树分类。
在经典数学中，研究者们定义了以下几种基本树结构：
-
自由树：一个无环的连通图。它没有指定的根节点，子节点顺序也不重要。
-
有根树：在自由树的基础上，指定一个根节点。子树的顺序仍然不重要。
-
有序树：在计算机实现中，我们通常需要一种具体的表示方式，因此会为子树指定一个顺序。我们之前讨论的树本质上都是有序树。
下图清晰地展示了这几种树的区别（以5个节点的树为例）：
以下是具体说明：
-
5个节点的自由树只有3种不同的结构。
-
如果指定根节点（成为有根树），不考虑子树顺序，则有9种不同的结构。
-
如果进一步考虑子树顺序（成为有序树），则有14种不同的结构，这个数字恰好是卡特兰数。
这些不同类型的树各自对应着不同的计数问题。人们已经解决了其中许多问题。此外，还可以为节点添加标签，考虑标签的顺序等，从而衍生出更多种类的问题。我们将在解析组合学（课程第二部分）中详细研究这些问题。
算法中的其他树结构
在算法领域，也会自然衍生出多种树结构变体。
以下是几种常见的变体：
-
T叉树：每个节点恰好有T个子节点。
-
T受限树：每个节点最多有T个子节点，但不一定恰好是T个。
-
2-3树：这是符号表实现中的首选方法之一。它的特点是一个节点可以包含多个键。这种结构看似奇特，但可以方便地用二叉树表示。我们稍后会简要说明。
所有这些变体都会引发出枚举问题（例如，对于给定的T和节点数n，有多少种不同的树？）。仅仅以上提到的，我们就已经涉及了十多种树类型。这强调了我们需要像解析组合学这样的通用工具，它可以帮助我们获得问题的解，而无需深入每个变体的具体细节。这也是为什么我们需要之前讨论过（并且后续会继续深入）的通用定理。
你或许已经发现，用生成函数来描述这些结构是相当直接的。我们可以轻松地将二叉树的定义构造推广到三叉树、四叉树等。一旦能做到这一点，我们就得到了一个生成函数方程。虽然其中许多方程不像卡特兰数方程那样容易求解或进行渐近分析，但我们将学习处理它们的技术。至少，我相信本课程的学员已经确信，我们可以为所有这些结构快速建立生成函数。
当然，这将是课程第二部分的重要主题。
平衡树与一个未解问题
我想最后讨论一个与我们所学内容相关的未解问题。
在实际应用中，我们不能仅仅依赖“键以随机顺序插入”这个假设来保证算法性能。键的插入顺序可能并非随机，因此我们需要有性能保证的方法。基于树的平衡树方法就是满足这一需求的首选方案。
平衡树是首选方案，因为其搜索代码极其简单（事实上，你可以用二叉搜索树来表示平衡树，大部分代码都相同，仅在插入时有一点额外开销）。在《算法》一书的3.3节有详细描述。通过这点额外开销，可以保证无论键以何种顺序插入，树的高度都将小于2 log n，即小于最优高度的两倍。大多数算法使用2-3树或2-3-4树表示，它们可以直接转换为二叉树。
例如，下图展示了一种具体的平衡树——左倾红黑树（LLRB），它是《算法》书中详细描述的一种2-3树表示。无需深入细节，你可以看到它的二叉树表示，其中有时一个节点包含两个键，但可以通过一个带有特殊链接的左倾节点来表示。
因此，我们得到了一种带有少量额外开销（需要以特定方式维护那些链接）的二叉树，但它目前是符号表实现的首选方法。
现在的问题是：尽管我们有性能保证，但如果假设键是随机插入的（因为这仍然是一个合理的模型），我们仍然想知道其性能表现。如果能够证明平衡树在随机键下的平均高度渐近于 log n（系数为1），那将比系数为2快一倍。在大型计算的内循环中，速度提升一倍是非常重要的。所以，我们仍然希望知道这个问题的答案：由随机排列构建的平衡树的平均成本是多少？
这其实不是树的属性，而是排列和算法的属性。树只是数据的容器。
我们课程标志所用的图表就与这个问题相关。有一种叫做AVL树的平衡树，它也表示一种二叉树。下图是随机AVL树中根节点秩为K的概率的归一化图（这里的“随机”是指所有合法的AVL树等可能出现，就像随机的卡特兰树模型一样，你可以定义什么是AVL树，建立生成函数关系并生成此图）。
这个图的意义在于它显示：有时根节点在中间，但有时它像1/3、2/3处，有两个峰值。这是一幅非常引人入胜的图。请记住，对于随机二叉树，我们有卡特兰分布，根节点更可能偏向一边（不平衡）。对于随机排列构建的二叉搜索树，分布是平坦的。而这个图看起来不错，因为它至少试图让根节点靠近中间，但我们仍然面临从分析上描述它的挑战。这是一个尚未解决的问题。
对于左倾红黑树（LLRB），经验图似乎也具有一些相似的特征，但我们仍然远未理解如何确定由随机排列构建的树（无论是AVL树还是2-3树）的路径长度。2-3树已经用解析组合学进行过研究，我们将在第二部分简要提及。
练习与实验建议
以上是对其他树类型的简要概述。现在，我将介绍一些你可以在下次课前进行的练习。
有许多关于树枚举的练习，可以帮助你检验使用符号方法解决枚举问题的熟练程度。
练习1：无单节点树的森林
我们有很多森林，但可能只关心那些没有仅包含单个节点的树的森林。问题是：在n个节点的森林中，这样的森林所占的比例是多少？
草图显示，对于n=1,2,3,4，答案分别是0, 1/2, 2/5, 3/7。请尝试找出其渐近公式。
这再次体现了符号方法的魅力：你可以基于基本推导进行修改，其基本结构仍然成立，从而得到一个可以求渐近或显式解的生成函数方程。这是练习此技巧的好机会。
练习2：完美平衡二叉搜索树的概率
这是一个基于我们对排列和二叉搜索树观察的计算：得到一棵完美平衡的二叉搜索树的概率是多少？这是一个有趣的计算练习。
练习3：随机二叉搜索树的节点类型统计
这与我们之前对树参数的分析思路相同，但对象是由随机排列构建的二叉搜索树。
-
红色曲线：两个子节点都是内部节点的内部节点的平均数量。
-
蓝色曲线：一个子节点是内部节点，另一个是外部节点的内部节点的平均数量。
在第五讲中，我们针对随机卡特兰树得到了该问题的解（常数比例）。现在请计算随机二叉搜索树的对应结果，并与第五讲的结果进行比较。
实验建议
有些人可能想运行一些实验来验证我们讨论的数学结果。
-
例如，生成一些随机排列，构建二叉搜索树，观察你得到的平均高度，并验证它是否接近 2 ln n。进行这样的验证总是很有价值的。
-
编程实现可能有点工作量，但对程序员来说应该不是问题。更难一点的是尝试对随机二叉树做同样的事情，比较内部路径长度和 S(n)，看看它们有多接近，n需要多大才能进入渐近区间等等。运行实验总是值得的，有些人可能会乐在其中。
最后，为了检查你对材料的理解，尝试解答一些我给出的练习题是一个好主意。
本节课中我们一起学习了自由树、有根树和有序树的区别，了解了算法中如T叉树、平衡树等其他树结构变体，并接触了一个关于平衡树平均性能的未解问题。这些内容为我们后续深入学习解析组合学和应用这些结构解决实际问题奠定了基础。
027：基础概念
概述
在本节课中，我们将要学习排列（Permutations）这一基础组合结构。排列在算法分析中有着广泛的应用。我们将从标记结构的角度，使用指数生成函数来研究排列的基本性质、表示方法及其在算法（如排序和密码学）中的应用。
排列的基本定义与表示
上一节我们介绍了无标记结构（如树）及其普通生成函数。本节中，我们来看看标记结构——排列，并将使用指数生成函数进行分析。
排列可以理解为对一组元素的重新排序。一个经典的比喻是：有N个编号为1到N的学生参加派对，派对结束后，每个学生随机进入一个编号为1到N的房间。按学生编号顺序记录其所在的房间号，就得到了一个1到N的随机序列，即一个排列。
从解析组合学的角度看，排列是由标记原子构成的序列，其中每种不同的顺序都视为不同的排列。因此，n个元素的排列总数是 n!。
从生成函数的角度，排列的指数生成函数（EGF） 为：
P(z) = Σ_{n≥0} n! * (z^n / n!) = Σ_{n≥0} z^n = 1 / (1 - z)
这是因为计数序列是 n!，而EGF中的归一化因子也是 1/n!，两者相消。
排列的逆
排列可以看作是从集合 {1, 2, …, n} 到自身的一个一一映射（双射）。例如，学生到房间的映射。这个映射的逆，称为排列的逆，它描述了房间到学生的映射。
计算排列的逆是一个简单的过程。以下是其核心思想与代码实现：
核心思想：如果原排列 a 表示 学生i 去了 房间a[i]，那么其逆排列 b 就表示 房间j 里住的是 学生b[j]。我们只需遍历原排列，将值作为索引，将索引作为值填入新数组即可。
代码示例（基于0索引数组调整）：
int[] inverse(int[] a) {
int n = a.length;
int[] b = new int[n];
for (int i = 0; i < n; i++) {
// a[i] 是1-based的房间号，转换为0-based索引
// i+1 是1-based的学生号，存入逆数组
b[a[i] - 1] = i + 1;
}
return b;
}
计算示例：对于排列 a = [8, 1, 3, 7, 6, 2, 9, 4, 5]（表示1->8, 2->1, …），其逆排列 b 的计算过程如下：
-
a[0]=8->b[7] = 1 -
a[1]=1->b[0] = 2 -
a[2]=3->b[2] = 3 -
依此类推，最终得到逆排列
b = [2, 6, 3, 8, 9, 5, 4, 1, 7]。
排列的应用：简单替换密码
排列的逆在密码学中有直接应用，例如简单的替换密码。
加密过程：
-
生成一个字母表（如A-Z）的随机排列作为密钥。
-
将明文中的每个字母，根据该排列映射为另一个字母，生成密文。
解密过程：
-
接收方持有相同的随机排列（密钥）。
-
为了解密，需要使用该排列的逆排列。
-
将密文中的每个字母，根据逆排列映射回原来的字母，即可恢复明文。
示例：
-
密钥（随机排列）：A->W, B->J, C->L, D->N, E->I, …, Z->?
-
明文：
ATTACK AT DAWN -
加密（A->W, T->P, C->L）：密文为
WPPWKL WN NW?S -
解密：使用逆排列（W->A, P->T, L->C, …）将密文恢复为明文。
注意：单纯的替换密码由于每个明文字符总是映射到同一个密文字符，容易通过频率分析被破解，因此现代密码系统中它通常只作为复杂算法的一部分。
排列的网格表示与逆
排列可以用一个 N×N 的网格来直观表示：
表示方法：对于排列 a（第i列的学生去了第a[i]行的房间），我们在网格的第 a[i] 行、第 i 列放置一个标记块。
性质：如果我们按行顺序读取标记块所在的列，读出的序列正好是原排列的逆排列。
原理：网格表示本质上是原排列的矩阵表示。求排列的逆，在几何上等价于对这个矩阵进行转置。原矩阵中 (行, 列) = (a[i], i) 的块，在转置后变为 (i, a[i])，这正好对应逆排列中“房间a[i]对应学生i”的关系。
排列的循环分解
在解析组合学中，我们介绍过排列的循环分解。这是分析排列性质的一个强大工具。
概念：从一个位置 i 开始，跟随映射 i -> a[i] -> a[a[i]] -> ...，最终会回到 i，形成一个循环。对排列中所有元素进行此操作，可将整个排列分解为若干个不相交的循环。
示例：排列 a = [9, 12, 11, 10, 5, 6, 15, 4, 1, 14, 3, 2, 16, 13, 7, 8] 可以分解为循环：(1 9)(2 12)(3 11)(4 10 14 13 16 8)(5)(6)(7 15)。
循环分解有助于我们分析排列的许多性质，例如后续将讨论的排序算法分析。
符号方法与生成函数
我们使用符号方法来系统地研究排列及其变体。符号方法为标记组合类建立了一系列组合构造与指数生成函数运算之间的对应关系。
对于排列类 P，其组合构造可以描述为：一个排列要么是空的，要么是由一个原子（最小元素）与一个排列的“星积”构成。
用符号表示为：P = ε + Z ★ P
这个构造直接翻译成指数生成函数的方程：
P(z) = 1 + z * P(z)
解这个方程，得到：
P(z) = 1 / (1 - z)
这与我们之前得到的指数生成函数一致，并且提取系数 [z^n] P(z) = n!，验证了排列的计数。
排列在排序算法分析中的应用
排序算法（如快速排序、归并排序）是排列的一个重要应用场景。要精确分析这些算法的性能，我们需要一个合理的输入模型。
核心模型：假设算法的输入是一个随机排列。即，所有 n! 种可能的输入顺序出现的概率相等。
模型合理性：即使原始输入是有序或逆序的，我们也可以在排序前先对输入进行一次随机排列。这样，排序算法实际处理的输入就严格符合随机排列模型。这使得基于排列的数学分析能够精确预测算法的平均性能。
生成随机排列：正确生成均匀随机排列至关重要。一个经典且正确的方法是 Knuth Shuffle（或称 Fisher-Yates Shuffle）。
算法步骤：
-
初始化数组为
[1, 2, ..., n]。 -
从
i = 0遍历到n-2：-
在
[i, n-1]范围内随机选择一个索引r。 -
交换数组中
i和r位置的元素。
-
代码实现：
void shuffle(int[] a) {
int n = a.length;
for (int i = 0; i < n; i++) {
// 随机生成一个介于 i 和 n-1 之间的整数 r
int r = i + (int) (Math.random() * (n - i));
// 交换 a[i] 和 a[r]
int temp = a[i];
a[i] = a[r];
a[r] = temp;
}
}
算法正确性：第一次循环，任何元素被选到第一位的概率是 1/n。第二次循环，在剩余元素中任何元素被选到第二位的概率是 1/(n-1)，依此类推。因此，生成任何特定排列的概率都是 1/n!，满足均匀随机的要求。
总结
本节课中我们一起学习了排列的基础知识。我们首先回顾了排列作为标记结构的定义及其指数生成函数。然后，我们探讨了排列的逆及其计算方法，并看到了它在简单密码系统中的应用。我们还介绍了排列的网格表示和循环分解这两种有用的视角。接着，我们运用符号方法，从组合构造的角度重新推导了排列的生成函数。最后，我们强调了随机排列模型在排序算法分析中的核心作用，并学习了如何正确生成均匀随机排列（Knuth Shuffle）。这些概念为后续深入分析排列的各种性质及其在算法中的具体应用奠定了坚实的基础。
028：循环集合
概述
在本节课中，我们将学习如何分析具有特定循环长度限制的排列。我们将从回顾排列的循环集合表示开始，然后深入探讨对合（Involutions）这一特殊排列，并学习如何计算其数量。最后，我们将通过一个著名的“100囚徒问题”来展示这些概念的实际应用。
回顾：带循环长度限制的排列
在第五讲介绍排列时，我们将其视为循环的集合，并对循环长度施加了限制。我们通过解析组合学的方法研究了这类问题。
排列的符号化构造是“循环的集合”。根据标记对象的符号转移定理，这意味着其生成函数满足：对于“集合”操作，其生成函数是指数形式；对于“循环”操作，其生成函数是自然对数。
因此，排列的生成函数 P(z) 为：
P(z) = e^{ln(1/(1-z))} = 1/(1-z)
所以，其计数序列（系数乘以 n!）是 n!。
如果我们想将同样的分析扩展到计算错排（derangements）的数量，即没有长度为1的循环（单循环）的排列，我们只需将循环长度限制为大于1。这对应于在 ln(1/(1-z)) 中减去 z 项。
另一种看法是，其生成函数为 e^{-z} / (1-z)。其 z^n 的系数（乘以 n!）是一个卷积和，渐近于 1/e。
接着，我们推广到“广义错排”，即限制不允许出现长度小于等于某个参数 M 的短循环。其生成函数是 e^{-z - z^2/2 - … - z^M/M} / (1-z)。我们证明了其渐近形式是 n! / e^{H_M}，其中 H_M 是调和数。
以上是我们介绍解析组合学时，关于带循环长度限制的排列的回顾。现在，我们将探讨另一个类似性质的问题。
对合：定义与性质
上一节我们回顾了带限制的排列，本节中我们来看看对合。对合是一种排列，其中所有循环的长度必须很短，具体来说，只能是长度1或2。
在长度为4的24个排列中，只有10个排列的所有循环长度均为1或2。其他排列要么包含一个长度为3的循环，要么包含一个长度为4的循环。类似地，在大小为3的排列中，只有4个不包含任何3循环。
对合是有趣的组合对象，有许多应用。一种理解方式是再次考虑逆排列。排列是一个从数字1到n到自身的映射，其逆就是这个映射的逆。那么对合的逆是什么？如果你计算一个对合的逆，你会发现它等于自身。从循环表示来看，在一个2循环中移动一步，再移动一步就会回到起点；在1循环中则保持不动。因此，对合是其自身的逆。
在点阵表示中，1循环对应于对角线上的元素，而2循环必须是对称的（例如，1映射到9，9映射到1）。如果你转置这个矩阵，会得到相同的结果。所以，对合是其自身的逆，这从点阵表示中可以立即看出。
对合的应用：互易密码
在应用方面，有“互易密码”的概念。如果使用一个对合进行加密，那么你可以用同一台机器进行加密和解密。一个著名的例子是二战期间德国使用的恩尼格玛密码机。其组件之一就是一个对合。
其思想是，我们有字母A到Z。如果我们用于加密的排列是一个对合，那么我们就不需要计算逆排列，因为对合就是其自身的逆。因此，我们不需要单独的解密表。如果我们有明文，得到密文（例如A变为D），那么要解密，我们使用相同的对合排列，它会将D变回A，K变回T，等等。
虽然它仍然容易受到字符频率分析攻击，但作为密码机的一个组件，它被证明非常有用，因为它可以极大地增加密码分析者需要考虑的可能性数量。恩尼格玛密码机就是这样使用的。
例如，如果你想知道有多少种不同的恩尼格玛设置，你就需要了解如何枚举对合。关于恩尼格玛密码分析的著名故事涉及艾伦·图灵等人，值得一读。
热身：仅由2循环组成的排列
作为热身，我们先看看完全由2循环组成的排列数量。
大小为2的排列只有一个，全是2循环。大小为3的排列中有3个全是2循环，依此类推。
一个例子是ROT13，这是世界上最弱的加密系统，它只是将字母旋转13个位置（A变为N，N变为A，B变为O，O变为B，等等）。由于它只包含2循环，所以它是一个互易密码，你可以使用同一个表进行加密和解密。
那么，完全由2循环组成的排列有多少个？我们称这种排列为 R，它就是“2循环的集合”。2循环的生成函数是 e{z2/2}。因此，其生成函数就是 e{z2/2}。我们想要的是其中 z^n 的系数乘以 n!。
由于只有 z^2 项，所以当 n 为偶数时，数量为 (n/2)!；当 n 为奇数时，数量为0。我们可以用斯特林公式来近似其渐近行为。这是解析组合学和渐近分析中非常简单直接的应用。
对合的计数与渐近分析
那么对合呢？其构造非常相似。对合是“1循环的集合”与“2循环的集合”的并集。也就是说，对合是所有循环长度均为1或2的排列。
这直接导出其生成函数为 e^{z + z2/2}**。其中，**ez 对应1循环，e{z2/2} 对应2循环。
现在，我们想从中提取系数。z^n 的系数（乘以 n!）是多少？这会得到一个离散和：
I_n = n! * Σ_{k=0}^{⌊n/2⌋} 1 / (k! * 2^k * (n-2k)!)
这个和的渐近分析更为复杂。它包含一个平方根和 e 的四次方根，是一个看起来相当复杂的函数。这可以通过求和的拉普拉斯方法得到，即找出求和式中权重最大的部分，用积分进行估计，并限制尾项。我们也可以在后续课程中通过复渐近分析直接得到答案。
因此，通过解析组合学，我们可以直接得到这样的结果，尽管其渐近分析绝非易事。
推广：无长循环的排列
如果我们像处理错排那样，将循环长度参数化为 M，情况会如何？
现在的构造是：对合是“1循环的集合”与“2循环的集合”……直到“M循环的集合”的并集。其生成函数直接来自符号方法：
e^{z + z^2/2 + ... + z^M/M}
这个生成函数系数的渐近推导是我们解析组合学书籍中最困难的推导之一，但通过解析组合学，我们仍然可以知道其渐近形式。
示例：计算特定系数
在某些应用中，你可能不需要推导完整的渐近形式。作为一个例子，我们来看一个练习。
假设我们想知道长度为10的排列中，有多少个没有长度大于5的循环。这个问题的答案就是下面这个生成函数中 z^10 的系数：
e^{z + z^2/2 + z^3/3 + z^4/4 + z^5/5}
或者写成另一种形式：
e^{ln(1/(1-z)) - (z^6/6 + z^7/7 + ...)} = (1/(1-z)) * e^{-(z^6/6 + z^7/7 + ...)}
这里的关键思想是，如果我们用泰勒定理展开这些指数项，我们只需要保留可能贡献到 z^10 系数的项。例如，e{-z6/6} 我们只需要展开到 1 - z^6/6，因为 z^12 及更高次项乘以任何东西都会超过 z^10，不会影响系数。
同样，对于 1/(1-z)，我们只需要保留前10项。然后进行交叉相乘，只保留那些乘积次数等于或低于10的项。通过这种推导，你可以有效地计算出特定问题的系数。
应用：100囚徒问题
现在，我们将应用这些概念来考虑一个被称为“100囚徒问题”的难题，这曾是谷歌的一道面试题。
故事是这样的：有100名囚犯，每人有一张唯一的身份卡，编号从1到100。卡片被收集起来，随机打乱顺序，放入一个有100个编号抽屉的柜子中，每个抽屉一张卡。
囚犯们一个接一个被允许进入房间，每人最多可以打开50个抽屉，查看里面的卡片，然后关上。出来后，他必须说出自己编号所在的抽屉。如果所有囚犯都找到了自己的编号，他们都将被释放；如果任何一人失败，他们都将被处决。
起初，一位数学家囚犯A认为这毫无希望，因为每人随机开抽屉找到自己卡片的概率是1/2，100人都成功的概率是 2^{-100}，微乎其微。
但另一位懂解析组合学的囚犯B提出了一个策略，声称至少有约31%的成功率。这个策略是什么？
策略是：每名囚犯都应遵循“循环追踪”策略。具体来说，编号为 i 的囚犯首先打开第 i 个抽屉。如果里面的卡片编号是 j，那么他接下来就打开第 j 个抽屉，以此类推，直到找到自己的卡片编号，或者直到打开了50个抽屉。
这个策略何时成功？当且仅当代表卡片放置的排列没有长度超过50的长循环时，所有囚犯都能在50步内找到自己的卡片。
那么，一个随机排列没有长度大于50的循环的概率是多少？这正是我们刚刚讨论的生成函数 e^{z + z^2/2 + … + z^50/50} 中 z^100 的系数（乘以 100!）。通过计算（类似于我们之前的练习），这个概率大约是 1 - (H_{100} - H_{50})，其中 H_n 是第n个调和数。这个值约等于 1 - ln(2) ≈ 0.306…，即大约31%。这就是100囚徒问题的解决方案，也是排列循环结构研究的一个应用。
总结
本节课中，我们一起学习了：
-
回顾了使用解析组合学分析带循环长度限制的排列。
-
深入探讨了对合这种特殊排列，其所有循环长度仅为1或2，并且是其自身的逆。
-
学习了对合的生成函数 e^{z + z^2/2}，并讨论了其系数提取和渐近分析的复杂性。
-
将概念推广到“无长循环”的排列。
-
通过一个具体计算示例，展示了如何高效计算特定生成函数的系数。
-
最后，应用循环结构的知识，精彩地解决了著名的“100囚徒问题”，展示了理论在解决实际问题中的强大力量。
029：左右极小值
在本节课中，我们将学习如何分析排列的特定属性，特别是“左右极小值”这一参数。我们将使用生成函数和组合构造的方法来计算随机排列中左右极小值的平均数量，并揭示其与排列中循环数量的深刻联系。
概述
上一节我们介绍了分析树结构参数的一般方法。本节中，我们将把这种方法应用到排列上，分析一个称为“左右极小值”的参数。这个参数与选择排序等基础算法相关，也是理解排列组合性质的一个经典例子。
左右极小值的定义
一个排列中的“左右极小值”是指，该元素比其左侧的所有元素都要小。
例如，在排列 S O R T I N G E A 中：
-
S是第一个元素，因此是第一个极小值。 -
随后遇到
O和R，它们都比S大。 -
接着遇到
I，它比左侧的S, O, R都小，因此是第二个极小值。 -
以此类推，
G和E不是极小值，最后的A比左侧所有元素都小，是又一个极小值。
因此，该排列共有 5 个左右极小值。
在算法中，例如选择排序，这个数量对应于在查找最小元素过程中更新“当前最小值”变量的次数。
分析目标
我们的目标是计算：在一个大小为 n 的随机排列中，左右极小值数量的期望值。
以下是 n=3 和 n=4 时所有排列及其左右极小值数量的示例：
-
n=3时，总累积成本为 11，平均值为 11/6 ≈ 1.833。 -
n=4时，总累积成本为 50，平均值为 50/24 ≈ 2.083。
使用生成函数进行分析
我们将使用指数型累积生成函数。定义生成函数 B(z) 为：
B(z) = Σ (对于所有排列P) [ LRM§ * z^{|P|} / |P|! ]
其中 LRM(P) 是排列 P 中左右极小值的数量，|P| 是排列的大小。
对于排列，n! 既是归一化因子，也是大小为 n 的排列总数。因此，如果我们从 B(z) 中提取 z^n 的系数，得到的就是 B_n / n!，这正是大小为 n 的排列中左右极小值的平均数量。
组合构造与方程推导
分析的关键在于找到一个合适的组合构造。对于排列，我们使用“星积”构造：给定一个大小为 n 的排列 P，我们可以通过插入一个新元素（并重新编号）来构造 n+1 个大小为 n+1 的新排列。
观察发现，在这 n+1 个新排列中：
-
有
n个排列的左右极小值数量与原排列P相同。 -
有
1个排列（即新元素1被放在末尾的排列）的左右极小值数量比原排列P多 1。
将这个构造应用到生成函数 B(z) 的求和定义中，我们可以推导出 B(z) 必须满足的函数方程：
(n+1) * LRM§ + 1 对应于新构造排列的成本贡献。
经过代数化简（详细步骤涉及对求和的重组与已知生成函数的识别），我们得到：
B(z) = (1/(1-z)) * log(1/(1-z))
提取结果
函数 log(1/(1-z)) 是调和数 H_n 的普通生成函数。而乘以 1/(1-z) 相当于对系数进行前缀和操作。
因此，从 B(z) 中提取 z^n 的系数，我们直接得到大小为 n 的排列中左右极小值的平均数量为：
H_n = 1 + 1/2 + 1/3 + … + 1/n
这与我们之前计算的小数值 (H_3≈1.833, H_4≈2.083) 相符。
与排列循环数量的联系
一个有趣的现象是，随机排列中循环数量的平均值也是调和数 H_n。这是因为我们可以为“左右极小值”和“循环”建立一一对应（双射）关系。
对应规则如下：
-
从循环到排列：找出每个循环中的最小元素（称为“领导者”）。按领导者从大到小的顺序写出所有循环，且不标记循环的起止。结果便是一个唯一的排列，其左右极小值正是这些领导者。
-
从排列到循环：找出排列中的所有左右极小值。这些极小值就是循环的领导者。从一个领导者开始，向右读取直到遇到下一个更小的元素（即下一个领导者），这之间的所有元素（包括起始领导者）构成一个循环。
这个著名的对应关系直接证明了：在任意排列中，左右极小值的数量等于循环的数量。
总结
本节课中我们一起学习了：
-
定义了排列的“左右极小值”参数，并理解了其算法背景。
-
使用指数型累积生成函数 B(z) 和“星积”组合构造，推导出了生成函数方程。
-
通过求解方程，得出随机排列中左右极小值数量的平均值为第
n个调和数 H_n。 -
揭示了一个重要的组合事实：通过一个精巧的双射，排列中左右极小值的数量恒等于其循环分解中的循环数量，这解释了二者平均值相同的原因。
这种方法——定义参数、建立生成函数、利用组合构造推导函数方程、求解并解释结果——是解析组合学中分析参数分布的核心策略。
030：其他参数示例
在本节课中，我们将继续学习排列参数的例子，以加深对基本方法的理解，并进一步熟悉排列的性质。我们将分析“单循环数”和“逆序数”这两个参数，并了解它们在算法分析中的应用。
单循环数
上一节我们讨论了循环数和左右最小值，本节我们来看看排列中的“单循环数”。一个“单循环”是指一个元素映射到自身的循环，例如在排列 (1)(2 3) 中，元素 1 构成了一个单循环。
我们的目标是计算一个大小为 n 的随机排列中，单循环的平均数量。通过观察小例子（n=2, 3, 4），我们发现平均值似乎总是 1。接下来，我们将用生成函数法来证明这一点。
我们使用与计算循环数时相同的构造方法：对于一个大小为 p 的排列，通过将新元素 p+1 插入到每个可能位置，生成 p+1 个大小为 p+1 的新排列。
分析的关键在于计算新排列集合中的单循环总数。设原排列 P 有 cycle1(P) 个单循环。在构造出的新排列中：
-
每个原排列的单循环在新排列中依然存在，贡献了
(p+1) * cycle1(P)个单循环。 -
当我们把新元素
p+1单独作为一个单循环插入时，会为每个新排列增加一个单循环，总共增加p+1个。 -
但是，如果原排列中某个位置
i本身是单循环，当我们把p+1插入到i之前时，i就不再是单循环了（它和p+1形成了一个二元循环）。这种情况在原排列的每个单循环上都会发生一次，因此总共需要减去cycle1(P)个单循环。
因此，新排列集合中的单循环总数为：(p+1) * cycle1(P) + (p+1) - cycle1(P) = p * cycle1(P) + (p+1)。
设 B(z) 是单循环数的指数生成函数（EGF）。应用上述构造，我们得到以下方程：
B(z) = z * B'(z) + 1/(1-z)
这里，对 z^(p+1)/(p+1)! 求导消去了分母中的 (p+1)，得到了 z^p/p!，从而引入了导数项 B'(z)。
解这个微分方程：
B'(z) = 1/(1-z)^2
积分得：
B(z) = 1/(1-z)
1/(1-z) 展开后 z^n 的系数是 1。因此，大小为 n 的随机排列中，单循环的平均数量为 1。
一个直观的应用是“学生与房间”问题：如果每个人随机进入一个房间，平均恰好有一个人进入自己原来的房间。
为了巩固对此方法的理解，你可以尝试计算随机排列中二元循环（或更一般的 r-元循环）的平均数量，答案分别是 1/2 和 1/r。
逆序数
现在，我们转向另一个重要参数：逆序数。一个逆序是指排列中一个“顺序错误”的数对，更准确地说，对于每个位置，我们计算其左侧比它大的元素个数，所有这些计数的总和就是逆序数。
例如，在排列 [1, 2, 4, 3] 中，只有 (4,3) 是逆序，所以逆序数为 1。在 [2, 1, 4, 3] 中，逆序对有 (2,1) 和 (4,3)，逆序数为 2。
计算小例子（n=3, 4）的逆序总数并求平均，我们发现平均值似乎在增长。逆序数的一个直接应用是分析插入排序算法。
插入排序的工作方式如下：它遍历数组，对于每个位置 i，确保 i 之前的元素已排序。当处理一个新元素时，它不断与左侧更大的元素交换，直到到达正确位置。交换的次数正好等于排列的逆序数。因此，了解随机排列的逆序数对于分析插入排序的性能至关重要。在实践中，当递归排序算法（如快速排序、归并排序）处理小规模子数组时，通常会切换到更高效的插入排序，这需要我们对逆序数有准确的估计。
为了分析逆序数，我们使用一种新的构造方法：从一个大小为 p 的排列出发，通过将新元素 p+1（这里我们使用 n）插入到所有 p+1 个可能的位置（从最右到最左），来生成大小为 p+1 的新排列。
这个构造的关键观察是：当我们将新元素从右向左移动插入时，每向左移动一个位置，就会为所有位于它右侧的元素增加一个逆序（因为新元素现在位于它们左侧且更大）。因此，第一个插入位置（最右）不增加新逆序，第二个位置增加1个新逆序，第三个增加2个，以此类推，直到最左位置增加 p 个新逆序。
设原排列 P 的逆序数为 inv(P)。那么，新排列集合中的逆序总数为：
-
所有原排列的逆序数被复制了
p+1次：(p+1) * inv(P)。 -
额外增加的逆序数总和为：
0 + 1 + 2 + ... + p = p(p+1)/2。
因此，总数为：(p+1) * inv(P) + p(p+1)/2。
设 B(z) 是逆序数的指数生成函数。应用构造并整理，我们得到方程：
B(z) = z * B(z) + (1/2) * z^2 / (1-z)^2
这里，z * B(z) 对应第一项，(1/2) * z^2 / (1-z)^2 对应第二项（求和 k*z^k 的生成函数是 z/(1-z)^2，再乘以 z/2）。
解这个方程：
B(z) = (1/2) * z^2 / ((1-z)^3)
我们知道 1/(1-z)^3 的展开式中 z^n 的系数是 C(n+2, 2) = (n+2)(n+1)/2。因此，B(z) 中 z^n 的系数（即逆序数的总和）为 (1/2) * (n-1)n/2 = n(n-1)/4。由于有 n! 个排列，平均逆序数为：
平均逆序数 = [n(n-1)/4] / n! * n! = n(n-1)/4
所以，大小为 n 的随机排列中，平均逆序数为 n(n-1)/4。这验证了我们从 n=3 和 n=4 观察到的情况。
总结
本节课中我们一起学习了排列的两个重要参数：单循环数和逆序数。
-
我们证明了单循环的平均数量恒为 1，这与直观的“学生房间”问题相符。
-
我们推导出逆序数的平均值为 n(n-1)/4，并解释了它在分析插入排序算法性能中的关键作用。
-
我们再次运用了生成函数和组合构造（插入新元素）这一强大方法，展示了如何处理不同的参数和递归关系。
排列还有许多其他有趣的性质可以类似地分析，例如上升、下降、峰值、游程和递增子序列等。掌握这些基本方法，是分析更复杂算法行为的重要基础。
031：BGF与分布 📊
在本节课中，我们将学习如何使用解析组合学中的双变量生成函数方法来分析组合结构中的参数。我们将看到，这种方法比之前讨论的构造性推导更为简洁和强大，能够轻松地计算参数的平均值，甚至研究其完整分布。
概述
上一节我们介绍了通过构造性方法分析排列中循环数量的平均值。本节中，我们来看看如何使用解析组合学中的符号方法和双变量生成函数来更优雅地解决这类问题。这种方法不仅能简化计算，还能自然地扩展到对参数分布的深入分析。
双变量生成函数的基本思想
对于组合类，我们不仅关心对象的大小，还关心与之关联的参数（或成本）。双变量生成函数可以同时编码这两种信息。
-
对于标记类（如排列），其指数型双变量生成函数定义为：
B(z, u) = Σ_{对象ω} (z^{|ω|} / |ω|!) * u^{cost(ω)}其中
z标记大小，u标记参数成本。 -
其核心恒等式是：大小为
n、参数值为k的对象数量A_{n,k}可以从生成函数中提取：A_{n,k} = n! * [z^n u^k] B(z, u)
从BGF计算参数平均值
一个关键技巧是，参数的平均值可以通过对BGF进行一个简单的操作得到。
-
参数的平均值计算公式为：
平均值 = [z^n] (∂B(z, u)/∂u |_{u=1}) -
推导逻辑：对
B(z, u)关于u求导并令u=1，会得到系数为Σ_k k * A_{n,k}的生成函数，再除以n!即得平均值。
应用：排列的平均循环数
现在，我们使用BGF重新推导排列的平均循环数。
-
符号方法构造：一个排列是循环的集合。我们用变量
u来标记每个循环。排列 = SET( u * CYCLE(Z) ) -
通过转移定理得到BGF：根据符号方法的转移定理，
CYCLE对应log(1/(1-z))，SET对应指数函数。因此，BGF 立即可以写出：B(z, u) = exp( u * log(1/(1-z)) ) = (1/(1-z))^u -
计算平均值：我们要求
∂B/∂u在u=1处的值。∂B/∂u = (1/(1-z))^u * log(1/(1-z))令
u=1，得到：∂B/∂u |_{u=1} = (1/(1-z)) * log(1/(1-z)) -
提取系数：我们知道
[z^n] (1/(1-z)) = 1，且log(1/(1-z))的系数是调和数H_n。通过卷积，(1/(1-z)) * log(1/(1-z))的z^n系数正是H_n。因此，大小为n的排列的平均循环数就是第n个调和数H_n。
可以看到，使用符号方法和BGF，我们无需任何复杂的构造和求和，几步就得到了结果。
另一个例子：指定长度的循环数
我们也可以轻松分析其他参数，例如长度为 r 的循环的平均数量。
-
符号方法构造：一个排列是所有循环的集合。我们可以将其表示为：非长度为
r的循环的集合，加上被u标记的长度为r的循环的集合。排列 = SET( CYCLE_{≠r}(Z) + u * CYCLE_{=r}(Z) )其中
CYCLE_{=r}(Z) = Z^r / r。 -
通过转移定理得到BGF：
B(z, u) = exp( log(1/(1-z)) - z^r/r + u * (z^r/r) ) = (1/(1-z)) * exp( (u-1) * z^r / r ) -
计算平均值：对
u求导并令u=1：∂B/∂u |_{u=1} = (1/(1-z)) * (z^r / r) -
提取系数：当
n ≥ r时，[z^n] (1/(1-z)) * (z^r / r) = 1/r。这意味着，在足够大的排列中，长度为r的循环的平均数量是1/r。
BGF与分布：第一类斯特林数
双变量生成函数的力量远不止于计算平均值。它包含了参数分布的完整信息。
-
排列中具有
k个循环的计数被称为第一类斯特林数，记作[n k]。 -
我们之前得到的BGF
B(z, u) = (1/(1-z))^u正是第一类斯特林数的指数生成函数：B(z, u) = Σ_{n≥0} ( Σ_{k} [n k] u^k ) * (z^n / n!) -
从这个生成函数出发，可以推导出许多恒等式和递推关系。例如，将其视为
u的函数，对固定的n，系数[z^n/n!] B(z, u)是一个u的n次多项式：[z^n/n!] (1/(1-z))^u = u(u+1)(u+2)...(u+n-1) / n!这个多项式的系数正是第一类斯特林数。
-
在解析组合学中，还可以进一步研究当
n很大时，循环数的极限分布。可以证明，在适当的缩放下，这个分布趋近于正态分布。
练习与下节预告
为了巩固理解，可以尝试以下练习：
以下是三个推荐的练习题目：
-
研究排列：一个
n个元素的排列是由这些元素的一个子集形成的序列（元素可重复使用）。请研究排列的组合解释和生成函数。 -
对合中的逆序数：计算对合（满足
p = p^{-1}的排列）中逆序的平均数量。 -
循环长度分布：证明在随机排列中，长度为
r的循环数渐近服从参数为1/r的泊松分布。
在下一讲之前，请阅读教材第七章。该章节内容详实，你可以选择性地深入阅读感兴趣的参数分析部分。始终建议通过生成随机排列并进行模拟实验，来验证我们推导出的数学结果（如平均循环数、指定长度循环数的分布等）。同时，练习将解题过程清晰地书写下来也是很好的学习方式。
总结
本节课中我们一起学习了：
-
双变量生成函数 的概念，它同时编码了组合对象的大小和参数信息。
-
如何利用BGF和简单的求导运算
(∂/∂u)|_{u=1}来计算参数的平均值。 -
符号方法与BGF的结合如何极大地简化分析过程，让我们能够直接从组合构造得到生成函数方程。
-
BGF包含了参数的完整分布信息，例如第一类斯特林数，并且可用于研究参数的渐近分布。
这就是关于排列的BGF与分布分析。通过引入双变量生成函数和符号方法，我们获得了一个强大而统一的框架，用于分析组合结构中的各种参数，这将是第二部分课程中的重要工具。
032：受限比特串 🔢
在本节课中，我们将学习如何使用解析组合学的方法，分析包含特定限制或模式的随机比特串。我们将重点关注如何计算一个随机比特串中不出现特定模式（例如连续的零）的概率，以及首次出现该模式的期望等待时间。
符号方法回顾 📝
上一节我们介绍了符号方法的基本思想。本节中，我们来看看如何将其应用于比特串。
所有长度为 n 的二进制串的数量是 2^n。我们可以用符号方法构造这个组合类 B：一个二进制串是比特（0或1）的一个序列。
使用符号方法的转换定理，我们得到其普通生成函数（OGF）为：
B(z) = 1 / (1 - 2z)
z^n 的系数即为 2^n。
我们也可以用递归的方式来定义：一个比特串要么是空的，要么是一个比特后跟一个比特串。这能得到相同的结果。
无连续零的比特串 🔗
现在，我们考虑一个更具体的问题：有多少个长度为 n 的比特串没有两个连续的零？
我们可以这样构造此类比特串：
-
它是空的，或者
-
它是一个单独的零，或者
-
它是一个1，或者
-
它是一个“01”后跟一个“没有两个连续零的比特串”。
这个构造直接翻译成生成函数方程：
B0(z) = 1 + z + (z + z^2) * B0(z)
解这个方程，我们得到：
B0(z) = (1 + z) / (1 - z - z^2)
这个生成函数 z^n 的系数正是斐波那契数。通过分析分母多项式的最大根（即黄金比例 φ ≈ 1.618），我们可以得到系数的渐近表达式。
推广：无连续P个零的比特串 📈
上一节我们处理了无两个连续零的情况。本节中，我们将其推广到无连续 P 个零的情况。
构造方式类似：
- 一个“无连续
P个零的串”是一个长度小于P的零串，后跟一个空串或一个1，再后跟一个“无连续P个零的串”。
这翻译成生成函数方程：
Bp(z) = (1 + z + ... + z^{p-1}) * (1 + Bp(z))
求解得到：
Bp(z) = (1 - z^p) / (1 - 2z + z^{p+1})
同样，z^n 的系数渐近于一个常数乘以 α^n，其中 α 是分母多项式 1 - 2z + z^{p+1} 的最大实根。
从计数到概率与期望 ⏳
我们不仅关心计数，更关心随机比特串的性质。通过评估生成函数，我们可以计算概率和期望。
以下是关键结论：
-
不存在连续P个零的概率：在一个长度为
n的随机比特串中，不出现连续P个零的概率近似为(α/2)^n，其中α是上述多项式的最大根。 -
首次出现的期望等待时间：在随机比特串中，首次出现连续
P个零的位置的期望值是2^{p+1} - 2。这是一个精确的公式。
对于不同的 P 值，结果差异很大：
-
P=1（无单个零）：期望等待时间仅为2，在长串中几乎不可能没有零。 -
P=2：期望等待时间约为6。 -
P=3：期望等待时间约为14。 -
P=4：期望等待时间约为30。 -
P=6：期望等待时间约为126，在100位的串中仍有相当概率不出现连续6个零。
这些统计数据可用于测试数据的随机性。
任意指定模式与自相关多项式 🧩
上一节我们分析了连续的零。本节中我们来看看更一般的模式，例如“001”。
一个反直觉的现象是：不同模式的等待时间不同。例如，在随机比特串中，首次出现“0001”的平均等待时间远短于首次出现“0000”的时间。
这是因为模式自身可能存在重叠或自相关。我们引入自相关多项式来刻画这一性质。
对于一个给定的模式 P（例如1010110），其自相关多项式通过将模式与自身滑动对齐来构造：每当模式尾部的若干位与头部的若干位匹配时，就在多项式中加入一项 z^k，其中 k 是滑动的距离。
例如，模式 1010110 的自相关多项式为 1 + z^5 + z^7。
处理任意模式的通用方法 🛠️
我们定义两个组合类：
-
S_P：完全不包含模式P的比特串。 -
T_P：以模式P结尾，且内部再无其他P的比特串。
基于对这两个类的观察，我们可以建立两个组合构造方程，并进而得到它们的生成函数方程：
-
S_P + T_P = ε + (S_P × {0,1}) -
S_P × P(z) = T_P × Q(z)，其中Q(z)就是模式P的自相关多项式。
解这个方程组，我们得到 S_P 的生成函数为：
S_P(z) = Q(z) / (z^p + (1-2z)Q(z))
其中 p 是模式长度，Q(z) 是其自相关多项式。
对于任何模式，我们都可以代入其 Q(z)，得到一个有理生成函数。分析其分母的最大根，就能得到不含该模式的比特串数量的渐近估计，以及相关的概率和期望值。
四比特模式示例 📊
所有可能的4比特模式可以根据其自相关多项式分为几类。下表展示了不同模式的等待时间差异：
| 模式 | 自相关多项式 Q(z) | 期望等待时间 (位) |
| :— | :— | :— |
| 0000 | 1 + z + z^2 + z^3 | 30 |
| 1111 | 1 + z + z^2 + z^3 | 30 |
| 0001 | 1 + z^3 | 16 |
| 0011 | 1 + z^2 | 16 |
| 0111 | 1 + z | 16 |
| 0010 | 1 | 16 |
| 0110 | 1 | 16 |
| 1011 | 1 | 16 |
可以看出，等待连续4个相同比特（0000或1111）所需的时间，大约是等待其他6种4比特模式的两倍。这意味着，在100位的随机串中，完全找不到0000的概率，比找不到0001的概率要高出约100倍。
总结 🎯
本节课中我们一起学习了：
-
使用符号方法为受限比特串（如无连续零）建立生成函数。
-
通过分析生成函数分母的最大根，得到计数的渐近结果。
-
将生成函数在特定点求值，计算出不存在某模式的概率和首次出现的期望等待时间。
-
引入了自相关多项式的概念，它编码了模式自我重叠的特性。
-
建立了一个通用框架，可以处理任意指定模式的计数与概率问题，并发现不同模式的等待时间存在显著差异。
这些技术将组合对象的构造、生成函数的推导与渐近分析紧密结合，是解析组合学的经典应用。
033：符号方法与形式语言 🧮
在本节课中，我们将简要探讨符号方法与计算机科学中形式语言之间的关系。我们将看到，符号方法为计数形式语言中的字符串数量提供了一个系统性的框架。
符号方法与形式语言
上一节我们介绍了符号方法在组合结构计数中的应用。本节中，我们来看看符号方法与形式语言理论的联系。
一个形式语言是一个字符串的集合。一个自然的问题是：在一个给定的语言中，长度为 n 的字符串有多少个？答案是，我们可以使用普通生成函数（OGF）来枚举它们，并且本质上可以使用符号方法，或者将符号方法视为解决此类问题的一种途径。这是一种非常系统化的方法。
在计数时，一个关键问题是歧义性。通常，在形式语言中，我们只关心指定集合，而一个特定的字符串可能有不止一种推导方式。这是理解形式语言和构建编译器等的关键问题。如果存在多种推导字符串的方式，我们将计算所有可能的推导方式。因此，我们希望处理无歧义的语言。
正则表达式与有理生成函数
以下是正则表达式与生成函数的关系。
正则表达式使用连接（concatenation）、或（or）和星号（star）操作来指定形式语言。定理指出：如果你有两个正则表达式（RE）的枚举OGF，那么：
-
取“或”操作时，OGF是和。
-
取“连接”操作时，OGF是积。
-
取“星号”操作时，OGF是
1/(1 - G(z))。
这与符号方法的证明完全相同，只是记法不同，前提是正则表达式是无歧义的。
这表明，一个无歧义正则表达式的OGF是有理的（即两个多项式的比值）。因为无论你如何应用这些操作，最终得到的OGF都是两个多项式的比值。
另一种表述是：枚举正则语言的OGF是有理的。对于任何正则语言（例如，存在有限状态自动机的语言），存在一个著名的构造（克莱尼定理的细节）可以给出一个无歧义的正则表达式。如果存在无歧义的正则表达式，那么其OGF就是有理的。
这是一个思考枚举问题的有趣方式，因为人们可能更熟悉正则表达式，但需要注意歧义性问题。
示例：不含连续两个0的二进制字符串
用正则表达式语言表示，这是一个无歧义的推导：
RE = (1 + 01)* (ε + 0)
应用上述定理，对于星号部分得到 1/(1 - (z + z^2))，尾部部分就是 (1 + z)。最终得到的OGF与我们使用符号方法得到的结果相同，当然是一个有理函数（两个多项式的比值）。
示例：表示3的倍数的二进制字符串
这是一个著名的例子，可以使用具有三个状态的有限状态机来描述。可以为其推导出一个正则表达式。表示3的倍数的二进制字符串有多少个？我们可以将定理应用于该正则表达式，得到一个有理函数。经过简化，可以得到一个简单的多项式比值。这个生成函数可以通过部分分式展开，其系数渐近于 (2^n - 1)/3。这正是我们所期望的：总共有 2^n 个字符串（忽略前导零的细节），大约三分之一是3的倍数。
这是一个枚举正则语言的典型例子，它本质上就是符号方法，只是使用了不同的记法。
上下文无关语言与代数生成函数
类似地，对于上下文无关语言（CFG），我们使用非终结符以及“或”和“连接”操作。同样的思想也适用于符号方法，关键仍然是确保无歧义性。现在情况更复杂，因为我们有多个方程。文中讨论指出，枚举无歧义上下文无关文法的OGF是代数的。
代数函数是指满足一个系数为有理数的多项式方程的函数。这仅仅是从我们用来构建这些生成函数的基本规则自然推导出来的结果。
实际上，我们之前考虑的所有构造（使用不同记法）都是无歧义的上下文无关文法。
示例：二叉树
这是二叉树作为一种上下文无关文法的描述：
T = ○ + ○ T T
那么其OGF将满足 T(z) = z + z * T(z)^2，这是一个代数方程。
示例：不含连续两个0的比特串
用上下文无关文法表示它稍微复杂一些，但本质上并不难，只是记法不同。
由于歧义性，并非所有上下文无关文法都对应我们可以用这种方式枚举的组合类。同样，并非符号方法中考虑的所有构造都是上下文无关文法，因为我们除了连接和“或”之外还使用了许多其他操作。然而，在许多情况下它们是相同的，了解这一点是有价值的。
应用：随机游走的计数
以下是随机游走计数的例子。
随机游走是加号（+）和减号（-）字符的序列，在随机游走、所谓的赌徒破产问题以及某些排序算法的研究中都有应用。
从加号和减号字符序列的概念出发，会产生各种自然问题，例如：长度为 n 的不同游走有多少？或者，有多少长度为 n 的游走，其每个前缀中加号都多于减号（即始终保持在基线之上）？
在此背景下研究随机游走的关键是找到一种无歧义的分解方式。
-
定义类
U：游走始终保持在基线之上（加号始终多于减号）。- 构造方式：要么只是一个
+；要么是一个U，后接另一个U，然后是一个-。
- 构造方式：要么只是一个
-
类似地，定义类
D：游走始终保持在基线之下。 -
利用
U和D，可以定义从零开始并在零结束的随机游走类S：-
要么是一个
U，后接一个-，然后是一个S； -
要么是一个
D，后接一个+，然后是一个S； -
或者是空游走
ε。
-
这正好是一个使用这三种构造的上下文无关文法，它无歧义地分解了从原点开始并结束于原点的随机游走。
由于这是一个上下文无关语言，我们可以使用符号方法来得到生成函数方程。这次，我们有三个方程和三个未知数。联立求解这些方程（实际上类似于树的方程），最终结果是：此类游走的数量是 C(2n, n)（即第 n 个卡特兰数乘以某个因子）。虽然有很多更简单的方法可以证明这个结果，但这种方法可以推广到解决文本中讨论的许多更复杂的类似问题。
总结
本节课中，我们一起学习了符号方法与形式语言理论之间的联系。我们看到：
-
对于无歧义的正则表达式，其枚举生成函数是有理的。
-
对于无歧义的上下文无关文法，其枚举生成函数是代数的。
-
符号方法为计数形式语言中的字符串提供了一个强大而系统化的框架，关键在于处理歧义性。
-
我们通过随机游走的例子，展示了如何将组合结构分解为无歧义的上下文无关文法，并利用符号方法得到生成函数方程进行计数。
这为我们分析更复杂的算法和数据结构（例如接下来要看的字典树）奠定了坚实的基础。
034：字典树
概述
在本节课中，我们将要学习一种称为“字典树”的数据结构。字典树是一类组合对象，近年来因其在计算机领域的应用而受到广泛研究。它拥有非常丰富且有趣的分析特性。我们将首先介绍字典树是什么及其应用，然后再探讨其分析。
什么是字典树？🌳
上一节我们介绍了字典树的基本概念，本节中我们来看看它的具体定义。
一种理解字典树的方式是将其视为一棵二叉树，其中某些外部节点被标记。黑色的节点称为“空节点”，白色的节点称为“非空节点”。规则是：在叶子节点中，不能有两个空节点互为兄弟节点。也就是说，如果一个节点是空节点，那么它的兄弟节点不能是空节点。
实际上，你可以尝试给出字典树的递归定义作为练习。
字典树最常用的理解方式是：它代表一组比特字符串。每个非空外部节点代表一个比特字符串。通过从根节点到该节点的路径来获取这个字符串：向左走记为0，向右走记为1。
例如，路径“左、左、右、右、左”会到达一个非空外部节点，该节点代表的比特字符串就是 00110。另一个节点代表的比特字符串是 1010。
空节点则有不同的解释。例如，如果我们连续向右走四次再向左，会到达一个空节点。这意味着，在字典树所代表的字符串集合中，没有以该路径为前缀的字符串。因此，字典树代表了一组比特字符串，而空节点则代表了所有未被包含的字符串的前缀。
另一种理解方式是：字典树递归地表示了字符串集合。左边的子树代表所有以0开头的字符串（去掉开头的0），右边的子树代表所有以1开头的字符串（去掉开头的1）。
这仅适用于“无前缀”的字符串集合，即集合中没有任何一个字符串是另一个字符串的前缀。我们可以通过使用空和非空内部节点来处理更一般的情况，但在典型的应用中，处理无前缀集合就足够了。例如，所有长度固定的比特字符串集合就是无前缀的，因为所有字符串长度相同且互不相同。
字典树的应用 💡
字典树有非常广泛的应用。在算法书籍中，你可以找到用于排序、字符串键的简单表以及后缀数组的字典树代码。它在经典数据压缩算法（如霍夫曼编码和LZW压缩）中扮演着角色。我们还将看到字典树如何用于理解决策、冲突解决和领导者选举算法。如今，字典树在网络系统、生物信息学、互联网搜索和各种商业数据处理中都非常重要。这是一个常被忽视但极其重要的数据结构。
应用一：符号表
字典树最基本的应用之一是作为符号表。它代表一组比特字符串，因此我们可以基于定义实现搜索算法。
搜索算法的基本思想是：如果待查键的首位比特是0，则向左走；如果是1，则向右走。然后递归地使用剩余的字符串。
-
如果最终到达一个空外部节点，则表示该键不在集合中。
-
如果到达一个非空外部节点且正好用完了所有比特，则报告搜索成功。
例如，在示例字典树中搜索 0011：从0开始向左，下一个0向左，下一个1向右，下一个1向右。此时字符串结束，且位于一个非空外部节点，因此搜索成功。搜索 10110 则会遇到空节点，表示搜索失败。
插入算法则是通过搜索直到遇到一个空外部节点。如果中途遇到内部节点或非空外部节点，可能意味着存在前缀冲突，需要特殊处理。对于要插入的新键，最终会到达一个空节点。然后，对于键中剩余的每个比特，我们添加一个新的内部节点，其中一个子节点是空外部节点，另一个子节点则根据比特值（0左1右）指向一个新的节点或最终的非空节点。例如，插入 01110 的过程就如上所述。
当然，存在一些变体（如使用指针记录尾部），但最简单的版本通常就很有效。一个自然的问题是：这些空外部节点似乎浪费了空间。因此，我们需要分析字典树的空间占用，这在实际应用中非常重要。
应用二：子字符串搜索
另一个重要应用是子字符串搜索。假设我们有一个给定的长字符串（例如基因组序列，可能长达数十亿个字符），我们需要快速判断一个特定的子串是否存在于该字符串中。
解决方案是构建一个后缀字典树。思路是：对于给定的字符串，考虑其所有后缀（从每个位置开始到结尾的子串）。如果原字符串长度为 n，则有 n 个后缀。我们将这些后缀作为独立的字符串插入到一个字典树中，这就构成了后缀字典树。这是一个无前缀集合。
此后，字典树的每个内部节点都对应原字符串的某个子串。要查询子串 X 是否存在，只需使用 X 的字符遍历字典树。如果能遍历完 X 并到达一个非空节点（或内部节点），则 X 存在；如果中途遇到空节点，则 X 不存在。例如，查询 AC 可以成功找到，而查询 TGA 则会失败。这是一个利用字典树回答子串查询的简洁算法。
应用三：领导者选举算法
字典树还可以作为算法的模型，例如分布式领导者选举算法。在分布式系统中，一组个体需要选举出一个领导者。
算法过程如下：每个参与者独立地抛硬币。
-
将抛得1的视为胜者，进入下一轮；抛得0的视为败者，被淘汰。
-
剩余胜者再次抛硬币，重复此过程。
-
直到只剩下一名胜者，该胜者即为领导者。
这个过程可能失败：如果某一轮所有参与者都抛得0，则没有胜者，选举失败。
这个选举过程恰好可以映射到一棵随机字典树中。选举的轮数对应于字典树中最右侧路径的长度。选举失败的概率则对应于随机字典树中最右侧路径以空节点结尾的概率。这里的“随机字典树”模型，通常指通过向初始为空的字典树中插入无限长的随机比特串所得到的结构。
总结
本节课中我们一起学习了字典树这一重要的数据结构。我们首先了解了字典树的定义，它是一类用于表示比特字符串集合的二叉树变体。接着，我们探讨了字典树的三个主要应用：作为高效的符号表实现、用于快速子字符串搜索的后缀字典树，以及作为分布式领导者选举算法的模型。这些应用展示了字典树在计算机科学多个领域的实用性和重要性，也为我们后续分析其性能参数（如搜索时间、空间占用、路径长度等）提供了动机和背景。
035：字典树参数分析 📊
在本节课中，我们将学习如何分析字典树（Trie）的关键性能参数，包括空间占用、搜索成本和“领导者选举”路径长度。我们将从递归关系入手，推导出平均外部路径长度的精确公式，并揭示其背后有趣的渐近行为和周期性波动。
概述
字典树参数的分析是算法分析中最具挑战性也最有趣的部分之一。理解这些参数是评估当前许多大规模基础设施应用性能的基础。我们将重点关注三个核心参数：空间占用、搜索成本和领导者选举路径长度。本节将详细分析平均外部路径长度（即搜索成本），其他参数将作为练习。
字典树参数定义
在深入分析之前，我们先明确要分析的三个核心参数。
-
空间占用：这由字典树中外部节点的总数决定。如果你知道所表示的字符串数量，就能计算出额外（空）节点的数量。空节点的数量代表了实际使用的额外空间。
-
搜索成本：与二叉搜索树类似，搜索成本由外部路径长度决定，即从根节点到所有外部节点的距离之和。其平均值就是平均搜索成本。
-
领导者选举：如前所述，这是最右侧路径的长度。
值得注意的是，即使一半的节点是空的，也只会略微增加搜索成本。这是字典树高效的原因之一：存在大量空节点对搜索成本的影响并不大。
分析模型
为了进行分析，我们采用一个标准且易于处理的模型。
最常用的模型是：假设字典树是通过插入 n 个无限的随机比特串构建的。这些字符串最终会在某个位置产生差异，而字典树正是根据这些前导位的差异来区分它们。从分析的角度看，这是一个合理的模型，因为我们可以假设在每个节点，我们都以相等的概率随机向左或向右移动。研究表明，这个模型能很好地拟合真实数据。
建立递归关系
我们的分析起点与二叉搜索树的分析类似，但存在关键差异。
对于一个包含 n 个字符串的字典树，假设左边有 k 个字符串，右边则有 n - k 个。差异主要有两点：
-
左边有 k 个节点的概率不同。对于二叉搜索树，这个概率是
1/n；而对于字典树，由于是随机比特串，这个概率服从二项分布。 -
可能出现左边有 0 个节点、右边有 n 个节点的情况（反之亦然）。这是由字典树的定义直接导致的，它使得递归式稍微复杂一些。
由此，我们得到底部所示的递归式。当你有 n 个随机字符串时，其中 k 个以比特 0 开头的概率是 (n choose k) / 2^n。因此，字典树的外部路径长度 C_n 满足以下递归关系：
C_n = n + (1 / 2^n) * Σ (n choose k) * (C_k + C_{n-k})， 对 k 从 0 到 n 求和
需要注意的是，当 k = 0 时，右边会出现 C_n 项，这是处理时需要小心的一点。
-
二叉搜索树：左边有 k 个节点的概率是
1/n（均匀分布）。 -
随机卡特兰树：该概率服从卡特兰分布。
-
字典树：该概率服从二项分布
(n choose k) / 2^n。
这个递归式是我们计算小数值或分布的基础，也是我们想要求解的目标。二项分布的特性（峰值在 n/2 附近）暗示字典树的结构通常是相当平衡的。
求解递归式：生成函数法
我们将使用指数生成函数来求解这个递归式。
将递归式两边除以 n!，然后对所有的 n 求和，我们得到指数生成函数 C(z) 满足的方程。利用 n choose k 产生的卷积形式，经过不太复杂的计算，可以验证以下公式：
C(z) = z * e^{z/2} * C(z/2) + (1 - z) * e^z
这是一个关于生成函数的简单方程，它是 e^{z/2} 和 C(z/2) 的卷积。虽然由于参数 z/2 的存在，它不能直接显式求解，但我们可以通过迭代来处理。
迭代求解与显式公式
通过反复将 C(z/2) 的方程代入自身，我们可以进行迭代。
经过几步迭代后，可以观察到模式：我们将得到 z * e^z 乘以一系列项的和，这些项涉及 z/2, z/4, z/8, ...。最终，在无穷迭代后（需要证明剩余项趋于零），我们得到了平均外部路径长度生成函数的显式公式。
从这个显式公式中提取 z^n 的系数（再乘以 n!），我们得到平均外部路径长度 C_n 的显式公式：
C_n / n = Σ_{j≥0} (1 - (1 - 1/2^j)^{n-1})
这个公式仍然包含一个无穷和，我们需要进一步处理它以理解其渐近行为。
渐近分析：揭示周期性
我们使用基本的分析方法来刻画这个和式的行为。更完整的解析刻画需要复分析方法（将在课程第二部分讨论）。
利用近似 (1 - 1/2^j)^{n-1} ≈ e^{-n/2^j}，我们关注以下和式：
Σ_{j≥0} (1 - e^{-n/2^j})
为了分析它，我们将和式在 j = floor(log₂ n) 处拆分为两部分：
-
当
j < floor(log₂ n)时，2^j远小于n，e^{-n/2^j}非常小，项(1 - e^{-n/2^j})接近 1。 -
当
j ≥ floor(log₂ n)时，2^j大于等于n，e^{-n/2^j}接近 1，项(1 - e^{-n/2^j})接近 0。
通过变量替换和合并，最终我们可以将 C_n / n 表示为：
C_n / n = log₂ n + F({log₂ n}) + o(1)
其中 {log₂ n} 表示 log₂ n 的小数部分。函数 F(x) 是一个在 0 到 1 之间平滑振荡的周期函数，但其振幅非常小（大约 10^{-6} 量级）。
这是一个令人惊奇的发现：一个看似自然的、涉及整数成本的递归关系，其解竟然包含一个微小的周期性振荡项。当我们学习到复分析和梅林变换时，会发现这种周期性在基于比特串性质的算法（如字典树）分析中经常出现，并且有完美的数学解释。
分析结果与应用
应用上述分析结果，并观察字典树得到的分布，可以发现它比二叉搜索树的分布更紧密地集中在中心（即更平衡）。
以下是此类分析得到的关键结果引用：
-
额外空间：大约有 44% 的外部节点是空的。
-
期望搜索成本：大约为 n log₂ n，即需要检查的比特数。这是一个非常有竞争力的、可接受的搜索成本。
-
领导者选举：这将作为一个练习。
总结
本节课中，我们一起深入分析了字典树的性能参数。我们从定义核心参数和建立分析模型开始，推导了平均外部路径长度的递归式，并利用生成函数法进行求解。通过渐近分析，我们不仅证明了搜索成本主要项为 n log₂ n，还揭示了一个隐藏的、振幅极小的周期性波动。最后，我们总结了字典树的空间和搜索效率，说明了其在处理大规模字符串数据时的实用性和竞争力。对于领导者选举路径长度的分析，则留给大家作为练习。
036：习题与巩固
在本节课中，我们将通过一系列习题来巩固对本章内容的理解。这些习题涵盖了随机比特串、随机打字机模型以及领导者选举算法的分析，旨在帮助你将理论知识应用于具体问题。
8.3 随机比特串中的连续零
openEuler 是由开放原子开源基金会孵化的全场景开源操作系统项目，面向数字基础设施四大核心场景（服务器、云计算、边缘计算、嵌入式），全面支持 ARM、x86、RISC-V、loongArch、PowerPC、SW-64 等多样性计算架构
更多推荐
2
0- 0
已为社区贡献51条内容
所有评论(0)