随机排列问题 - Pre-rice 的博客

定义

关系（relation）：设集合 $𝐴$ 和 $𝐵$ ， $𝐴 \times 𝐵$ （直积）的任意一个子集 $𝑅$ 都称为从 $𝐴$ 到 $𝐵$ 的一个（二元）关系。集合 $𝐴$ 到自身的关系，称为集合 $𝐴$ 上的（二元）关系。

函数 / 映射（function / mapping）：设 $𝑓$ 是从集合 $𝐴$ 到 $𝐵$ 的关系，若对于 $𝐴$ 中的每一个元素， $𝐵$ 中都存在唯一的一个元素与之对应，则称 $𝑓$ 为函数（或称映射）。若 $𝑓 (𝑥_{1}) = 𝑓 (𝑥_{2}) \Rightarrow 𝑥_{1} = 𝑥_{2}$ （一对一），则称 $𝑓$ 为单射（injection）；若对于 $𝐵$ 中的每一个元素， $𝐴$ 中都至少存在一个元素与之对应，则称 $𝑓$ 为满射（surjection）。

双射 / 一一对应（bijection / one-to-one correspondence）：同时满足单射和满射的映射。

函数（狭义）：从数到数的映射。
泛函（functional）：从函数到数的映射，核心应用是变分法。
算子（operator）：从函数到函数的映射，这里的函数是函数空间，或者更一般的向量空间。

变换（transformation）：非空集合到自身的映射。若无特别说明，本文讨论的都是有限集上的变换。

置换（permutation）：非空集合到自身的双射。大小为 n 的集合上定义的置换称为 n 元置换（n-permutation）。

随机排列：在 n 个元素的全排列（全部元素按顺序排列的所有情况）中等概率地任选其一。

本质上，随机排列可视为集合 ${1, 2, \dots, 𝑛}$ 到自身的随机双射，所以随机排列也被称为随机置换。它们的英文都是 Random permutation，不过中文语境下“排列”更侧重于强调结果，“置换”更侧重于强调变换过程。

具体情境中，构成双射的两组元素可以被赋予具体的含义。在排列的一般语境下，一组元素的含义是另一组元素的位置，只需显式写出元素的排列顺序，位置便隐含其中。还有许多表面看似不同的情境，本质仍是随机双射，因此也属于随机排列问题的范畴。

接下来我们主要研究三类问题：

不动点问题：研究随机排列的不动点。
环问题：把双射视为指针、随机排列视为指针的一种分配，研究指针形成的环结构与元素间的环关系。
变换问题：在排列之间定义变换，研究由此形成的变换关系图。

不动点问题

不动点（fixed point）：满足 $𝑓 (𝑥) = 𝑥$ 的点 $𝑥$ 称为函数 $𝑓 (𝑥)$ 的不动点。随机排列的不动点即排列后处于原位上的元素。

错排数（derangement number）：所有元素都不在原位上的排列被称为错排。n 个元素的全排列中错排的数量被称为错排数 $𝐷 (𝑛)$ 。

错排数的求法

如何求错排数 $𝐷 (𝑛)$ ？等价地问，随机排列中不动点的数量为 0 的概率 $𝑃 (𝑛)$ 为多少？

递推法

n 个元素错排。设位置 1 上的元素为 k ，分两种情况讨论：

若位置 k 上的元素为 1 ：剩余 n - 2 个位置错排有 $𝐷 (𝑛 - 2)$ 种可能；
若位置 k 上的元素不为 1 ：交换位置 1 和 k 上的元素，使得元素 k 在位置 k 上，此时元素 1 必然不在位置 1 上，相当于除了 k 外的 n - 1 个元素恰好构成一个错排，有 $𝐷 (𝑛 - 1)$ 种可能。

把这两种情况相加，而 k 又有 n - 1 种可能的取值，故可以列出递推式 $𝐷 (𝑛) = (𝑛 - 1) (𝐷 (𝑛 - 1) + 𝐷 (𝑛 - 2))$ 。

第二种情况的解法很巧妙：事实上，我们是通过“交换位置 1 和 k 上的元素”这一映射方式，把“位置 1 上的元素为 k ，且位置 k 上的元素不为 1”的情形与“除了 k 外的 n - 1 个元素进行错排”的情形建立起了一一对应，从而转换了求解的目标。一一对应是组合计数中最重要的思想之一，后文还会反复用到。

然后求解这个递推式：

记 n 个元素的随机排列恰为错排的概率 $𝑃 (𝑛) = \frac{𝐷 (𝑛)}{𝑛!}$ 。

代入递推式得 $𝑛 𝑃 (𝑛)$ $= (𝑛 - 1) 𝑃 (𝑛 - 1) + 𝑃 (𝑛 - 2)$ 。

移项并整理成相邻项之差的形式 $𝑃 (𝑛) - 𝑃 (𝑛 - 1)$ $= - \frac{1}{𝑛} (𝑃 (𝑛 - 1) - 𝑃 (𝑛 - 2))$ 。

由初始条件 $𝑃 (0) = 1$ 、 $𝑃 (1) = 0$ ，逐次迭代可得 $𝑃 (𝑛) - 𝑃 (𝑛 - 1)$ $= \frac{{(- 1)}^{𝑛}}{𝑛!}$ 。

再从 $𝑃 (0)$ 起逐项累加，便得 $𝑃 (𝑛) = \sum_{𝑖 = 0}^{𝑛} \frac{{(- 1)}^{𝑖}}{𝑖!}$ 。

当然这只是其中一种方法，采用其它的方式变形求解，或者直接使用数学归纳法，也是可以的。

容斥原理法

用容斥原理可以更直接地推出错排数。下面仅对容斥原理的核心思想做简单的介绍，细节请自行了解。

容斥原理通过交替加减各集合的交集来消除重复计数，从而精确求得集合并集的元素数量。其证明的精髓，是通过二项式定理（binomial theorem），证明交集的每个部分（由是否属于各个集合确定不同的部分）都在系列加减后被不重不漏地计入一次。

不重不漏计数的练习：把正八/六/二十面体的每个面剖分为 $𝑛^{2}$ 个彼此相同且与原面相似的子图形，求两个相对的顶点间由各子图形的边连成的最短路径的数目。

极限

由函数 $𝑒^{𝑥}$ 的泰勒展开式， ${lim}_{𝑛 \to \infty} 𝑃 (𝑛) = \sum_{𝑖 = 0}^{\infty} \frac{{(- 1)}^{𝑖}}{𝑖!} = \frac{1}{𝑒}$ 。

不动点的个数

我们刚刚求出了随机排列中不动点数为 0 的概率。事实上，不动点数是一个随机变量 $𝑋_{𝑛}$ ，我们可以进一步研究它的分布列（probability distribution）、期望（expectation）和方差（variance）。

分布列

利用容斥原理，同样可以写出完整的分布列 $𝑃 (𝑋_{𝑛} = 𝑘) = 𝐶_{𝑛}^{𝑘} \cdot \frac{𝐷 (𝑛 - 𝑘)}{𝑛!} = \frac{𝑃 (𝑛 - 𝑘)}{𝑘!}$ 。然而直接从分布列求期望和方差显然并非明智之举。

期望

由期望的线性性（可加性），易得期望为 1 。

具体证明，可以定义指示变量（indicator variable） $𝐼_{𝑖}$ ：当元素 i 在原位时为 1，否则为 0 。有 $𝑋_{𝑛}$ $= \sum_{𝑖 = 1}^{𝑛} 𝐼_{𝑖}$ ，则 $𝐸 (𝑋_{𝑛})$ $= \sum_{𝑖 = 1}^{𝑛} 𝐸 (𝐼_{𝑖})$ $= \sum_{𝑖 = 1}^{𝑛} \frac{1}{𝑛} = 1$ 。

函数线性性的本质是满足叠加原理，即和的函数等于函数的和。期望算子是满足该性质的典型线性映射。期望的线性性非常强大，它不要求随机变量相互独立，可以将复杂系统的期望求解降维至个体期望的简单线性组合，是概率论中最重要的工具之一。

方差

求方差时，仍然可以采用指示变量法。

根据随机变量和的方差公式，有 $𝑉 𝑎 𝑟 (𝑋_{𝑛})$ $= \sum_{𝑖 = 1}^{𝑛} 𝑉 𝑎 𝑟 (𝐼_{𝑖}) + 2 \sum_{1 \leq 𝑖 < 𝑗 \leq 𝑛} 𝐶 𝑜 𝑣 (𝐼_{𝑖}, 𝐼_{𝑗})$ 。其中：

单个变量的方差 $𝑉 𝑎 𝑟 (𝐼_{𝑖})$ $= \frac{1}{𝑛} \cdot (1 - \frac{1}{𝑛})$ $= \frac{𝑛 - 1}{𝑛^{2}}$ ；
两个变量之间的协方差（covariance） $𝐶 𝑜 𝑣 (𝐼_{𝑖}, 𝐼_{𝑗})$ $= 𝐸 (𝐼_{𝑖} 𝐼_{𝑗}) - 𝐸 (𝐼_{𝑖}) 𝐸 (𝐼_{𝑗})$ $= \frac{1}{𝑛 (𝑛 - 1)} - \frac{1}{𝑛^{2}}$ $= \frac{1}{𝑛^{2} (𝑛 - 1)}$ 。

代入得 $𝑉 𝑎 𝑟 (𝑋_{𝑛}) = 1$ 。方差居然也是 1 。

极限

事实上，由 $𝑃 (𝑋_{𝑛} = 𝑘) = \frac{𝑃 (𝑛 - 𝑘)}{𝑘!}$ ，并利用 ${lim}_{𝑛 \to \infty} 𝑃 (𝑛 - 𝑘) = \frac{1}{𝑒}$ ，可得 ${lim}_{𝑛 \to \infty} 𝑃 (𝑋_{𝑛} = 𝑘) = \frac{𝑒^{- 1}}{𝑘!}$ 。也就是说，n 趋于无穷大时，不动点数的分布趋于参数为 1 的泊松分布（Poisson distribution）。期望与方差相等，也正是泊松分布的特性之一。

直观理解：n 足够大时，每个元素是否为不动点几乎可视为独立事件，则不动点数近似服从二项分布 $𝐵 (𝑛, \frac{1}{𝑛})$ ，从而趋于参数为 1 的泊松分布。

环问题

引入

接龙游戏

把写有 n 个人名字的 n 张卡片随机分发给这 n 个人，卡片上的人名指示持有者“下一人”是谁，按此顺序依次接龙。这一游戏把所有人自然而然地分成了若干个环。若某张卡片写的是持有者本人的名字，则他直接指向自己，单独形成一环。

在环问题中，我们把置换中每个元素的函数值视为指向后继元素的一根指针（有向边）。先想清楚一个基本事实：为什么每个元素都必定落在某个环上？（包括自环，即不动点）

轮换

若置换 $𝑓$ 把某 k 个互异的元素 $𝑖_{1}, 𝑖_{2}, \dots, 𝑖_{𝑘}$ 循环移动，即 $𝑓 (𝑖_{1}) = 𝑖_{2}, 𝑓 (𝑖_{2}) = 𝑖_{3}, \dots, 𝑓 (𝑖_{𝑘}) = 𝑖_{1}$ ，而对其余所有元素保持不变，则称 $𝑓$ 为一个 k-轮换（k-cycle），通常记作 $(𝑖_{1}, 𝑖_{2}, \dots, 𝑖_{𝑘})$ 。

若两个轮换移动的元素集合互不相交，则称这两个轮换不相交。

置换的轮换分解

任何置换都可以唯一地分解成若干个互不相交的轮换的乘积（复合）。分解中轮换的个数称为该置换的轮换数（number of cycles）。

注意：置换的乘积不满足交换律。

将置换定义域集合中的元素作为顶点（vertex），把置换表示为一个各顶点入度与出度均为 1 的有向图（directed graph），则置换的轮换分解就等价于将该有向图分解为若干个互不相交的有向环（directed cycle）。我们后续都从图论的视角去分析置换的环结构。

任一元素所在环长的分布列

从选定元素出发，逐一追踪后继元素，直到回到自身构成闭环。使用乘法原理或直接计数即可得出：任一元素所在的环长服从均匀分布（uniform distribution）。

推广：在所有元素中指定若干标记元素，则任一元素所在环中含指定标记元素的个数，同样服从均匀分布（原问题即相当于把所有元素都视为标记元素）。

理解：忽略非标记元素、只考虑标记元素间的环关系，与考虑所有元素间的环关系，二者的本质概率结构是相同的。由于各元素等价，指针掠过若干非标记元素、首次落到标记元素上时，仍然是均匀随机选择，因此可以等价地看成“直接在标记元素之间形成指针”。

这一仅考虑标记元素的视角可以极大地简便计算，在后面有广泛的应用。

探寻本质概率结构，巧妙地找到最优的“视角”，拨开题面的迷雾，直达问题的核心，然后发现：一切原来如此简单！这正是概率的迷人之处。数学的分支大多研究某类抽象的数学对象，而概率研究的是随机事件——这一与真实世界的运行（从某种视角来看，世界就是不断发生的随机事件）密切接轨的抽象数学概念，因此我们天然地具备对概率的直觉，很多概率论中的概念或定理我们能够自发地认知 / 习得。

两元素同环的概率

分布列+全概率法

按照其中某一元素所在环长（已知分布列）分类，然后应用全概率公式（law of total probability）求解。

直接递推法

直接追踪其中某一元素的后继链：一旦命中另一元素即知两元素同环，一旦绕回该元素自身即知两元素不同环，否则继续考虑后继元素。整个追踪过程对“命中另一元素”与“绕回自身”两个结局对称（二者在每一步发生的概率都相等），故二者的概率均为 $\frac{1}{2}$ 。

标记元素法

应用之前的结论，只考虑这两个元素，直接秒杀。（其实“直接递推法”中不断后推、直到遇到两个标记元素之一的过程，就相当于重新证明了标记元素的结论）

一一对应法

交换两个元素的指针（即函数值，情境中即两人互换卡片），同环与不同环的情形在此操作下一一对应，故两种情形数量相等。

一一对应法的练习（高考题变式）：现有分别写着数字 1~2n 的 2n 张卡片。甲持有其中写着奇数的 n 张卡片，乙持有其中写着偶数的 n 张卡片。两人进行 n 轮比赛，在每轮比赛中，两人各自从自己持有的卡片中随机选择一张，并比较所选卡片上的数字大小，数字大的一方获胜。每张卡片只能使用一次。证明：甲的获胜轮数为对称分布（symmetric distribution）。（可导出：n 为偶数时，甲的获胜次数不小于 $\frac{𝑛}{2}$ 的概率为 $\frac{1}{2}$ 。高考题即 n = 4 的特例。）

环个数的期望

递推法

设有 n 个元素时，环个数（轮换数）的期望为 $𝐸 (𝑛)$ 。

任取一元素，其所在环长在 $1, 2, \dots, 𝑛$ 上均匀分布。若所在环长为 i ，则所在环贡献 1 个环，剩余 n - i 个元素平均再形成 $𝐸 (𝑛 - 𝑖)$ 个环。

由全期望公式（law of total expectation）可列出递推式： $𝐸 (𝑛) = 1 + \frac{1}{𝑛} \sum_{𝑖 = 0}^{𝑛 - 1} 𝐸 (𝑖)$ ，即 $𝑛 𝐸 (𝑛) = 𝑛 + \sum_{𝑖 = 0}^{𝑛 - 1} 𝐸 (𝑖)$ 。

差分得 $𝑛 𝐸 (𝑛) - (𝑛 - 1) 𝐸 (𝑛 - 1) = 1 + 𝐸 (𝑛 - 1)$ ，即 $𝐸 (𝑛) - 𝐸 (𝑛 - 1) = \frac{1}{𝑛}$ 。逐项累加即得 $𝐸 (𝑛) = \sum_{𝑖 = 1}^{𝑛} \frac{1}{𝑖}$ 。

按环长分类 + 期望可加法

长度为 i 的环的期望个数，等于选定 i 个元素构成一个环的概率 $\frac{(𝑖 - 1)!}{𝐴_{𝑛}^{𝑖}}$ （这 i 个元素成环的方法数，除以这 i 个元素的排列数），乘以选取这 i 个元素的方法数 $𝐶_{𝑛}^{𝑖}$ 。结果为 $\frac{1}{𝑖}$ ，与 n 无关。

再将各个长度的环的期望个数相加，就可以得到环的总个数的期望。（该方法其实用到了两层期望的线性性）

按起点分类 + 期望可加法

定义环的“起点”：环上序号最小的元素。

环的个数即为起点的个数，而起点总数的期望就等于每个元素成为起点的概率（该元素期望贡献的起点个数）之和。

指定元素成为起点的概率：标记元素法。把比指定元素 k 小的元素 $1, 2, \dots, 𝑘 - 1$ 视为标记元素，则元素 k 成为起点，当且仅当它所在的环不含任何标记元素；而 k 所在环含有标记元素的个数在 $0, 1, \dots, 𝑘 - 1$ 上均匀分布，故概率为 $\frac{1}{𝑘}$ 。
指定元素所在环起点的分布列和期望：仍用标记元素法。元素 k 所在环起点为 i（ $𝑖 < 𝑘$ ），当且仅当标记元素 $1, 2, \dots, 𝑖$ 中仅有元素 i 在 k 所在的环上。其概率等于，环上标记元素个数恰为 1 的概率 $\frac{1}{𝑖 + 1}$ ，乘以该标记元素恰为 i 的概率 $\frac{1}{𝑖}$ ，即 $\frac{1}{𝑖 (𝑖 + 1)}$ ；而起点恰为 k 的概率即 k 自身成为起点的概率 $\frac{1}{𝑘}$ 。两种情况结合可得环起点期望 $𝐸 (𝑘) = \sum_{𝑖 = 1}^{𝑘} \frac{1}{𝑖}$ 。

调和级数

环个数期望和环起点期望都恰为调和数（harmonic number） $𝐻_{𝑛} = \sum_{𝑖 = 1}^{𝑛} \frac{1}{𝑖}$ ，即调和级数（harmonic series） $\sum_{𝑖 = 1}^{\infty} \frac{1}{𝑖}$ 的第 n 个部分和。这里简单介绍调和级数的一些神奇性质。

容易证明，调和级数发散。（p 级数当且仅当 $𝑝 > 1$ 时收敛的一个特例）

你可以尝试证明： $\exists 𝛿, \forall 𝑛 : ln 𝑛 + 𝛿 < 𝐻_{𝑛} < ln (𝑛 + 1) + 𝛿$ 。这说明，调和数与自然对数的差值收敛于一个常数！这个常数就是欧拉常数 $𝛾 \approx 0.577$ 。

欧拉常数虽然不如 $𝜋$ 、 $𝑒$ 那么出名，却也是数学中的重要常数之一，它与素数分布、黎曼 $𝜁$ 函数等深层数论问题紧密相连。有趣的是，我们至今甚至不知道它究竟是有理数还是无理数。

环个数的分布列和方差

第一类斯特林数

（无符号）第一类斯特林数 $𝑐 (𝑛, 𝑘)$ 定义为：将 n 个元素排成 k 个环的方法数。于是环个数 $𝐾_{𝑛}$ 的分布列可以表示为 $𝑃 (𝐾_{𝑛} = 𝑘) = \frac{𝑐 (𝑛, 𝑘)}{𝑛!}$ 。

第一类斯特林数满足递推式： $𝑐 (𝑛, 𝑘)$ $= 𝑐 (𝑛 - 1, 𝑘 - 1) + (𝑛 - 1) 𝑐 (𝑛 - 1, 𝑘)$ 。
理解：考虑其中某个指定元素，它要么单独成环，要么成为其余 n - 1 个元素之一的后继而插入现有的环中。

遗憾的是，第一类斯特林数并没有简单的通项公式（closed-form formula）。那么这一递推式又能为我们解决什么问题呢？答案是：我们需要使用一个强大的数学工具——生成函数（母函数）。

生成函数的定义

对于数列 ${𝑎_{𝑘}}_{𝑘 = 0}^{\infty}$ ，定义它的生成函数（generating function） $𝐺 (𝑥)$ $= \sum_{𝑘 = 0}^{\infty} 𝑎_{𝑘} \cdot 𝑥^{𝑘}$ 。

对于取值为非负整数的随机变量（random variable）X，定义它的概率生成函数（probability generating function） $𝐺_{𝑋} (𝑡)$ $= 𝐸 (𝑡^{𝑋})$ $= \sum_{𝑘 = 0}^{\infty} 𝑃 (𝑋 = 𝑘) \cdot 𝑡^{𝑘}$ 。有 $𝐺_{𝑋} (1) = 1$ ， $𝐺_{𝑋}' (1)$ $= 𝐸 (𝑋)$ ， $𝐺_{𝑋} ″ (1)$ $= 𝐸 (𝑋 (𝑋 - 1))$ $= 𝐸 (𝑋^{2}) - 𝐺_{𝑋}' (1)$ 。

用生成函数推导轮换数的期望和方差

我们得到的递推式虽然不能推出分布列的通项公式，却能求出生成函数的表达式，从而推导出轮换数 $𝐾_{𝑛}$ 的期望和方差。

把第一类斯特林数视作关于 k 的数列 ${𝑐 (𝑛, 𝑘)}_{𝑘 = 0}^{\infty}$ 。由递推式，其生成函数 $𝐺_{𝑛} (𝑥)$ 满足 $𝐺_{𝑛} (𝑥)$ $= \sum_{𝑘 = 0}^{\infty} 𝑐 (𝑛, 𝑘) \cdot 𝑥^{𝑘}$ $= \sum_{𝑘 = 0}^{\infty} [𝑐 (𝑛 - 1, 𝑘 - 1) + (𝑛 - 1) 𝑐 (𝑛 - 1, 𝑘)] \cdot 𝑥^{𝑘}$ $= 𝑥 \cdot \sum_{𝑘 = 0}^{\infty} 𝑐 (𝑛 - 1, 𝑘 - 1) \cdot 𝑥^{𝑘 - 1} + (𝑛 - 1) \cdot \sum_{𝑘 = 0}^{\infty} 𝑐 (𝑛 - 1, 𝑘) \cdot 𝑥^{𝑘}$ $= (𝑥 + 𝑛 - 1) 𝐺_{𝑛 - 1} (𝑥)$ ，递推得 $𝐺_{𝑛} (𝑥)$ $= (𝑥 + 𝑛 - 1) (𝑥 + 𝑛 - 2) \dots (𝑥 + 1) 𝑥$ ，即上升阶乘 $\frac{(𝑥 + 𝑛 - 1)!}{(𝑥 - 1)!}$ 。

则 $𝐾_{𝑛}$ 的概率生成函数 $𝐺_{𝐾_{𝑛}} (𝑡)$ $= \frac{𝐺_{𝑛} (𝑡)}{𝑛!}$ $= \frac{(𝑡 + 𝑛 - 1)!}{(𝑡 - 1)! 𝑛!}$ $= 𝐶_{𝑡 + 𝑛 - 1}^{𝑛}$ 。

接下来对 $𝐺_{𝐾_{𝑛}} (𝑡)$ 进行求导并赋值即可。这里分享一个技巧：注意到 $𝐺_{𝐾_{𝑛}} (𝑡)$ 是一个连续乘积的形式，因此我们可以采用对数求导法（logarithmic differentiation）来简化导数的计算。

先对函数取自然对数，得 $ln (𝐺_{𝐾_{𝑛}} (𝑡))$ $= - ln (𝑛!) + \sum_{𝑘 = 𝑡}^{𝑡 + 𝑛 - 1} ln (𝑘)$ ；
再对等式两边求导，得 $\frac{𝐺_{𝐾_{𝑛}}' (𝑡)}{𝐺_{𝐾_{𝑛}} (𝑡)}$ $= \sum_{𝑘 = 𝑡}^{𝑡 + 𝑛 - 1} \frac{1}{𝑘}$ ，以及 $\frac{𝐺_{𝐾_{𝑛}} ″ (𝑡) \cdot 𝐺_{𝐾_{𝑛}} (𝑡) - {(𝐺_{𝐾_{𝑛}}' (𝑡))}^{2}}{𝐺_{𝐾_{𝑛}}^{2} (𝑡)}$ $= - \sum_{𝑘 = 𝑡}^{𝑡 + 𝑛 - 1} \frac{1}{𝑘^{2}}$ ；
最后代入 $𝑡 = 1$ ，得 $𝐸 (𝐾_{𝑛})$ $= 𝐺_{𝐾_{𝑛}}^{'} (1)$ $= \sum_{𝑘 = 1}^{𝑛} \frac{1}{𝑘} = 𝐻_{𝑛}$ ， $𝐺_{𝐾_{𝑛}} ″ (1) - {(𝐻_{𝑛})}^{2}$ $= - \sum_{𝑘 = 1}^{𝑛} \frac{1}{𝑘^{2}}$ $= - 𝐻_{𝑛}^{(2)}$ ， $𝑉 𝑎 𝑟 (𝐾_{𝑛})$ $= 𝐸 (𝐾_{𝑛}^{2}) - {𝐸 (𝐾_{𝑛})}^{2}$ $= 𝐺_{𝐾_{𝑛}} ″ (1) + 𝐺_{𝐾_{𝑛}}' (1) - {(𝐻_{𝑛})}^{2}$ $= 𝐻_{𝑛} - 𝐻_{𝑛}^{(2)}$ 。其中 $𝐻_{𝑛}^{(2)} =$ $\sum_{𝑖 = 1}^{𝑛} \frac{1}{𝑖^{2}}$ 是二阶调和数（second-order harmonic number）。

理解生成函数

经过上面的应用，你应该能初步感受到生成函数的威力了。

生成函数的本质，是把数列问题或分布列问题转化为函数问题：化递推式为函数方程，化随机变量卷积为函数乘积，化概率计算为函数求导和赋值，等等。此外，生成函数在组合计数等领域中也有广泛的应用，感兴趣可以自行了解。

初次接触生成函数时，你多半会觉得莫名其妙；但当你用趁手后，就会觉得不过如此。它不过是描述和求解问题的一种工具、一种分析框架，帮助我们把问题转化成更易于分析的形式后再去求解。

我们最早接触的这类工具或许是方程（equation）。在方程出现之前，问题只能靠一步步流式的算术推理来推进，思路稍长便难以理清；有了方程之后，我们不再直接去推导未知数，而是把它先用一个字母表示（这一步我们早已习以为常，但对初次接触方程的人来说同样是莫名其妙的），便能将题设条件直接翻译成含未知数的等式，再按等量关系作形式运算，就能轻松地解出未知数。

我想通过这个类比告诉你，生成函数和方程一样，都是把复杂问题映射到具有简单规则的代数空间中、借由形式运算来求解的工具。这样的工具还有很多——例如控制理论中的传递函数（transfer function），就用简单的代数函数描述了系统状态的复杂微分方程。

用指示变量法求方差

我们曾经用指示变量法求出过不动点数的方差，其实环个数的方差也可以通过该方法求解。

这其中最关键的洞察是：每个元素是否成为起点，是相互独立的事件。下面给出一种证明方法。

事实上，我们可以通过逐一添加元素 $1, 2, \dots, 𝑛$ 的办法，来等价构造一个随机排列：每次添加新元素 i 时，都让它的后继在已有元素（包括它自己）中均匀随机地选取，就可以维持排列的均匀随机性。用数学归纳法可以严格证明，最终构造出的排列的确是均匀随机的。

关键在于，这一构造中，元素 i 在添加时成为自环的概率固定为 $\frac{1}{𝑖}$ ，这与前 i - 1 个元素的排列方式完全无关。而 i 在添加时成为自环，就等价于它在最终的随机排列中是起点（后续添加的元素标号都比 i 大）。因此，元素 i 是否为起点与前面的元素是否为起点是相互独立的。

其实，我们在递推第一类斯特林数时，也是利用的这一过程。只不过一个采取的是计数视角，一个采取的是概率视角。
这一过程其实是中国餐馆过程（Chinese restaurant process）的一个特例。

这里需要区分两个容易混淆的概念：相互独立（mutually independent）与两两独立（pairwise independent）。

两两独立：任意两个事件之间互不影响。对随机变量而言，两两独立 $\Rightarrow$ 任意两个随机变量间的协方差为 0 $\Rightarrow$ 随机变量和的方差等于各自方差的和。
相互独立：任意多个事件交集的概率，都等于各自概率的乘积。相互独立是两两独立的充分不必要条件。

接下来的证明就很简单了。定义指示变量 $𝐼_{𝑖}$ ：当元素 i 是起点时为 1，否则为 0 。则 $𝑉 𝑎 𝑟 (𝐾_{𝑛})$ $= 𝑉 𝑎 𝑟 (\sum_{𝑖 = 1}^{𝑛} 𝐼_{𝑖})$ $= \sum_{𝑖 = 1}^{𝑛} 𝑉 𝑎 𝑟 (𝐼_{𝑖})$ $= \sum_{𝑖 = 1}^{𝑛} (\frac{1}{𝑖}) (1 - \frac{1}{𝑖})$ $= 𝐻_{𝑛} - 𝐻_{𝑛}^{(2)}$ 。

对比我们求方差的两种方法：指示变量法更加简洁而精彩，但需要构造和巧思；生成函数法则是用统一且确定的框架进行分析，更加普适和实用。

变换问题

置换的对换分解

对换（transposition）：只交换一对元素位置（函数值）的置换，即 2-轮换。

置换的对换分解：任何置换都可以分解为一系列对换的乘积。

分解方式有很多。最简单的方法，就是每次把一个元素调整到原位上。（选择排序法）当然，也可以先把置换分解为轮换，再把轮换分解为对换。
置换的对换长度（transposition length）：最短对换分解的长度。
置换的对换长度至多为多少？等价地问，两个排列间通过对换互相转化的最小对换次数至多为多少？更进一步地，如何求出一个给定置换的对换长度？对换长度为某个特定值的置换一共有多少种？
- 第一个问题，可用“证明上界 + 构造达到上界的例子”直接解决；但要回答后面的问题，我们需要更本质地考察对换对排列结构的影响。

排列的奇偶性

定义奇排列（odd permutation）：可经奇数次对换变为原排列的排列（可分解为奇数个对换之积的置换），同理可定义偶排列（even permutation）。

证明：奇排列与偶排列构成对排列的一个划分（partition，即不交且覆盖）。

覆盖性已由置换的对换分解保证；只需再证明：同一置换的任何对换分解，所含对换个数的奇偶性都相同。
考虑本质结构：排列的环个数。交换同环的两个元素，会“拆环”，使环个数加一；交换不同环的两个元素，会“并环”，使环个数减一。因此每做一次对换，环个数的奇偶性恰好翻转一次。
由此可证明奇排列与偶排列不交，同时，上一节留下的问题也迎刃而解。我们还能得到一个有趣结论：n 元置换的对换长度与轮换数之和为 n 。

证明：奇排列数 = 偶排列数。

马上想到一一对应法，对排列做任意一个对换即可。

上述奇偶性的分析都是从环结构的角度考虑的，但这并非唯一的角度。

从矩阵的角度看：每个置换都可以表示为一个矩阵，而对换矩阵的行列式为 −1 ，故每次对换都会改变置换矩阵行列式的正负性。
从逆序数的角度看：每次对换都会改变逆序数的奇偶性，这也可作为排列奇偶性的判据。
逆序数还能轻松解决一些其它的问题。例如，如果每次只能交换相邻的两个元素，则两个排列间互相转化的最小对换次数至多为多少？（冒泡排序法）

在一个排列中，若一个较大的数排在一个较小的数的前面，则称这两个数构成一个逆序（inversion）；排列中逆序的总个数称为这个排列的逆序数（inversion number）。

变换函数图与变换关系图

我们在研究环问题时，曾经把置换表示成了一个各顶点入度与出度均为 1 的有向图。其实，集合上的变换，乃至集合上的二元关系，都可以用有向图来描述和分析。

图的形式化定义：图 $𝐺$ 是一个有序二元组 $𝐺 = (𝑉, 𝐸)$ ，其中：

$𝑉$ ：顶点集，是一个非空集合，其中的元素称为顶点（vertex）或节点（node）。
$𝐸$ ：边集，刻画顶点之间的连接关系，其中的元素称为边（edge）。
若边是顶点的无序对 ${𝑢, 𝑣}$ ，则称图为无向图（undirected graph）；若边是顶点的有序对 $⟨ 𝑢, 𝑣 ⟩$ ，则称图为有向图（directed graph）。其中 $𝑢, 𝑣 \in 𝑉$ 。

变换是非空集合到自身的一个映射。把集合中的元素作为节点、把映射关系画成有向边，就得到一个各顶点出度均为 1 的有向图——这样的图称为函数图（functional graph）。函数图与变换一一对应，本质上是同一个数学对象的两种刻画方式。我们不妨把一个变换对应的函数图称为它的变换函数图。

在非空集合上定义一类变换（例如，全排列集合上的一切对换），它们构成非空集合到自身的一个（二元）关系。同理，也可以把集合上的变换关系表示为一个有向图，我们不妨称之为变换关系图。

通过研究集合在一个或一类变换下，变换函数图或变换关系图的性质（如路径长、可达性、连通性等），我们就能分析出变换的某些特性，这是研究变换本质结构的绝佳视角。

图论、群论的基础知识都非常值得学习，它们为研究许多问题提供了全新的视角。

接下来我们来看一个简单的例子。

对于置换 $𝑓$ ，必然存在正整数 k 使得 $𝑓^{𝑘}$ 为恒等变换（identity transformation）；满足条件的 k 的最小值称为置换 $𝑓$ 的阶数（order）。

如何证明 k 的存在性？考虑全体 n 元置换组成的集合 $𝑆_{𝑛}$ 。 $𝑓$ 在 $𝑆_{𝑛}$ 上定义了一个变换 $𝐹$ ： $\forall 𝑔 \in 𝑆_{𝑛} ， 𝐹 (𝑔) = 𝑓 \circ 𝑔$ 。由于 $𝑓$ 可逆， $𝐹$ 是一个双射，即 $𝐹$ 构成 $𝑆_{𝑛}$ 上的一个 $𝑛!$ 元置换，其变换函数图可以分解为若干个等长的环。于是从任意顶点出发，沿着有向边移动（即反复应用 $𝑓$ ）若干次后必然能回到原点（即恒等变换），环长即为置换的阶数，且必然是顶点数 n！的因数。（注意这里出现了两个层次的置换，需要仔细想清楚）
从另一个角度考虑：把置换分解为轮换之积，则各轮换阶数的最小公倍数就是置换的阶数。

变换问题拓展

整数环变换问题

把 n 个整数围成一个环。定义变换：任选一个元素，将它减 2，并使相邻的两个元素分别加 1 。研究：两个状态可以通过若干次变换互相转换的充要条件。

要证明两个状态不能互相转换，只需构造一个变换不变量（invariant），然后证明这个不变量在两个状态不等。要证明两个状态可以互相转换，则需具体构造一个变换过程或者间接证明其存在性。

法一：构造变换过程

原问题其实等价于，求环上的数 ${𝑎_{𝑖}}_{𝑖 = 1}^{𝑛}$ 可以通过若干次变换全部化为 0 的充要条件。

重要思想：构造“打包操作”，即把一系列变换组合为一个重要操作，后续就可以直接应用该操作更方便地进行变换。

其实，打包抽象是一个很重要的理念。它的本质是把一系列基础元素整合成整体后，就只从整体的角度去考虑问题，而不再细究其中的底层原理。一层层的打包抽象让我们得以方便地去认知复杂的系统。例如计算机架构，就是这样一层层的抽象。生物学也是一个典型的例子。

让我们分析变换可以叠加出哪些有用的打包操作。为方便，就用 $(1, - 2, 1)$ 来表示这个变换。

先在相邻的两个位置分别应用一次变换，得到 $(1, - 1, - 1, 1)$ 。

若在连续三个位置分别应用一次（即在刚刚的基础上，旁边再应用一次），就得到 $(1, - 1, 0, - 1, 1)$ 。

如此反复就能看出：一次变换可以把 $(- 1, 1)$ 向右移动一格，或把 $(1, - 1)$ 向左移动一格，它就像波一样可以沿着环一直传播下去。也就是说，我们可以在任意位置应用 $(1, - 1)$ ，再在另一个位置应用 $(- 1, 1)$ 。这一打包操作可以让我们专注地应用 $(1, - 1)$ 来处理某一位置，而把同步产生的 $(- 1, 1)$ 像工业废弃物一样统一丢到另一边去。

如果让它们一直背向传播、直至绕一圈再次交叠，便能产生 $(- 1, 2, - 1)$ ，即原变换的逆变换（inverse transformation）。这一点非常重要：它让我们在考虑变换数目时时不必区分正负。

注意到，若把 $(- 1, 1)$ 在每个位置各应用一次，它们会相互抵消；而这 n 次操作同步产生的 $(1, - 1)$ 我们可以统一叠加起来，合成 $(𝑛, - 𝑛)$ 。再把 $(𝑛, - 𝑛)$ 进行叠加传播，我们就又解锁了一个打包操作：在任意两个位置分别 $(+ 𝑛)$ 与 $(- 𝑛)$ 。它只作用于两个元素，可以让我们很方便地进行收尾处理。

有了这些打包操作，具体的构造就水到渠成了：先应用 $(- 1, 1)$ 依次把 $𝑎_{1}, 𝑎_{2}, \dots, 𝑎_{𝑛 - 2}$ 化为 0 ，同步产生的 $(1, - 1)$ 全部丢到 $𝑎_{𝑛 - 1}$ 与 $𝑎_{𝑛}$ 上，最后再用 $(𝑛, - 𝑛)$ 把这两个元素一并化为 0 即可。

其实不使用 $(- 1, 1, \dots, 1, - 1)$ 这个打包操作也是可以的，直接应用 $(1, - 2, 1)$ 及它的逆变换也能够逐一把 $𝑎_{1}, 𝑎_{2}, \dots, 𝑎_{𝑛 - 2}$ 化为 0 。只不过这种做法会让每次变换都牵扯三个相邻元素，使得逐一归零的过程中，相邻元素变得越来越复杂；不过列出前面几次变换的结果，也很容易找到规律，再使用数学归纳法证明即可。

结果很简洁美妙。 $\sum_{𝑖 = 1}^{𝑛} 𝑎_{𝑖} = 0$ 且 $\sum_{𝑖 = 1}^{𝑛} 𝑖 𝑎_{𝑖} \equiv 0$ $(mod 𝑛)$ 。

法二：方程组整数解分析

我们直接设位置 $𝑖$ 上做 $𝑢_{𝑖}$ 次操作，叠加后消除目标差 $𝑑_{𝑖}$ 。则只需满足方程组： $𝑑_{𝑖} = 𝑢_{𝑖 - 1} - 2 𝑢_{𝑖} + 𝑢_{𝑖 + 1} ，$ $𝑖 = 0, 1, \dots, 𝑛 - 1$ 。

这其实是一个二阶差分方程，可以写成 $𝑑_{𝑖} = (𝑢_{𝑖 + 1} - 𝑢_{𝑖}) - (𝑢_{𝑖} - 𝑢_{𝑖 - 1})$ ，令 $𝑣_{𝑖} = 𝑢_{𝑖} - 𝑢_{𝑖 - 1}$ ，则 $𝑑_{𝑖} = 𝑣_{𝑖 + 1} - 𝑣_{𝑖}$ 。

这是一阶差分方程，逐项累加得 $𝑣_{𝑘} = 𝑣_{0} + \sum_{𝑖 = 0}^{𝑘 - 1} 𝑑_{𝑖}$ 。记 $𝑠_{𝑘} = \sum_{𝑖 = 0}^{𝑘 - 1} 𝑑_{𝑖}$ ，则 $𝑣_{𝑘} = 𝑣_{0} + 𝑠_{𝑘}$ 。

由环闭合条件得 $𝑣_{𝑛} = 𝑣_{0}$ ，所以必须有 $\sum_{𝑖 = 0}^{𝑛 - 1} 𝑑_{𝑖} = 0$ ，这是第一个条件。

同理，由 $𝑣_{𝑖} = 𝑢_{𝑖} - 𝑢_{𝑖 - 1}$ 可得 $𝑢$ 是 $𝑣$ 的前缀和。而 $𝑢$ 也必须在环上闭合，则 $\sum_{𝑘 = 0}^{𝑛 - 1} 𝑣_{𝑘} = 0$ 。

代入 $𝑣_{𝑘} = 𝑣_{0} + 𝑠_{𝑘}$ ，得到 $𝑛 𝑣_{0} + \sum_{𝑘 = 0}^{𝑛 - 1} 𝑠_{𝑘} = 0$ ，则 $𝑣_{0} = - \frac{1}{𝑛} \sum_{𝑘 = 0}^{𝑛 - 1} 𝑠_{𝑘}$ 。

而 $𝑣_{0}$ 必须是整数，于是 $\sum_{𝑘 = 0}^{𝑛 - 1} 𝑠_{𝑘}$ 必须能被 $𝑛$ 整除。

而 $\sum_{𝑘 = 0}^{𝑛 - 1} 𝑠_{𝑘}$ $= \sum_{𝑘 = 0}^{𝑛 - 1} \sum_{𝑖 = 0}^{𝑘 - 1} 𝑑_{𝑖}$ $= \sum_{𝑖 = 0}^{𝑛 - 1} (𝑛 - 1 - 𝑖) 𝑑_{𝑖}$ 。再结合 $\sum_{𝑖 = 0}^{𝑛 - 1} 𝑑_{𝑖} = 0$ ，整除条件便等价于 $\sum_{𝑖 = 0}^{𝑛 - 1} 𝑖 𝑑_{𝑖} \equiv 0 (mod 𝑛)$ ，即第二个条件。

最后，还需要处理好负数情况：构造逆变换即可。

变式：还是这个变换，但定义在无穷数列 ${𝑎_{𝑖}}_{𝑖 = 0}^{\infty}$ 上而不是环上。不过这种情境下必须直接规定可以逆变换了，因为逆变换不再能通过多次变换叠加出来。

这一情境下，生成函数就可以大展身手了。每次对数列的变换即相当于对生成函数加或减 $1 - 2 𝑥 + 𝑥^{2}$ 的 $𝑥^{𝑘}$ 倍（ $𝑘 \in ℕ$ ），则多次变换就相当于加上任意一个包含因式 $1 - 2 𝑥 + 𝑥^{2}$ 的整系数多项式。换言之，生成函数的差值为整系数且包含这一因式就是两个数列可以互相变换的充要条件。更进一步地， $1 - 2 𝑥 + 𝑥^{2} = {(1 - 𝑥)}^{2}$ ，则包含该因式等价于生成函数及其导数在 1 处的值为 0 。

其实有个细节严格来说需要证明：包含因式 $1 - 2 𝑥 + 𝑥^{2}$ 的整系数多项式，一定可以表示为 $1 - 2 𝑥 + 𝑥^{2}$ 乘以另一个整系数多项式。

这次，我们通过把数列与其生成函数联系起来，将难以分析的数列变换问题转化成易于分析的多项式问题。更进一步地，对于任何类似的变换我们都能够统一地进行分析了，而不需要分别对每一种变换都构造一个变换过程。甚至再把问题拓展到二维格点上的变换，采用多变量生成函数（multivariate generating function）也能解决。

魔方变换问题

先看一个简单的问题：三阶魔方共有多少种状态？

魔方整体在空间中的朝向并不产生新的状态，因此我们可以先定中心块的朝向。剩下需要确定的是 8 个角块与 12 个棱块的位置和朝向。你可能会自然地列出 $8! \times 3^{8} \times 12! \times 2^{12}$ ，但这其实是个常见误区：题目要计数的应该是能复原的魔方状态，而刚刚列出的状态中，大部分都是无法复原的——如果你尝试过复原拆开后再乱拼的魔方，可以很快意识到这一点。大致说来，拧角、翻棱与换棱这三种非法操作都会让魔方陷入无法复原的状态（后两种情况在复原四阶魔方的过程中就可能出现，但是四阶魔方有特殊公式可以解决），因此总数要除以 $3 \times 2 \times 2$ 。这样算下来，三阶魔方的总状态数约为 $4.3 \times 10^{19}$ 种。

证明：对一个已经复原的魔方反复做同一个公式，必然可以回到复原状态。

你或许能敏锐地意识到：魔方的全部状态在这一公式的作用下构成一个置换，则它的变换函数图必然是若干个环的结构，环上任意一点沿边前行总能绕回自身。同理也有，回到复原状态需要做这一公式的次数必然是魔方总状态数的因数。

如何看一眼就判断魔方能否被复原？可以通过构造变换不变量来实现。

如何严谨地证明某个状态能复原？最直接的办法是观察整个复原过程。还有没有别的办法，比如借助矩阵？

数字串异或变换问题

在 0/1 构成的长为 n 的数字串的集合上定义变换：数字串的每一位变为它与下一位求异或的值（最后一位的下一位视为首位）。研究变换函数图的结构。

我们曾总结过置换的变换函数图的结构特点：每个弱连通分量都是一个有向环。而一般函数图的结构特点是：每个弱连通分量（weakly connected component）都包含一个有向环，环上的每个节点都作为根节点，挂着若干棵内向树（边指向环上根节点的有根树）。

从动力系统的视角看，从任意一个顶点出发，沿着有向边反复迭代，最终必然进入该连通分量内唯一的有向环并做周期运动。

回到具体问题。这个图共有 $2^{𝑛}$ 个节点：每个节点出度为 1 ，入度可能为 0 或 2 ，根据数字串各位之和的奇偶性可以判定。

$𝑛 = 2^{𝑘}$ 时，整个图弱连通，只含一个自环（全 0 数字串），上面挂着一棵高度（根节点到最远叶子节点间的边的条数）为 n 的树。即任一数字串经至多 n 次变换后都会变为全 0 。

如何证明？先把环拆开成一条直线，两侧用 0 填充。从单个 1 出发反复应用变换，会演化出一个自相似的三角——它其实是杨辉三角的奇偶版本（这一自相似三角还给出了判断组合数奇偶性的简单方法）。单个 1 演化到第 $2^{𝑘}$ 步时（此时位于三角形的一条边上），所得构型只有两端为 1 ，中间全为 0 ；而 $2^{𝑘}$ 恰等于环长 n 时，把环接上，则两端的 1 也相消为 0 。由于该变换在布尔代数中是线性的，由叠加原理，任意数字串经至多 n 次变换后也会变为全 0 。

对于一般的 n 有结论：图中所有树的高度都等于 n 的形如 $2^{𝑘}$ 的最大因子。环的数量和长度也有系统的方法可以解出，但涉及高等代数和抽象代数的复杂理论，感兴趣可以自行了解。

这个问题实际上是初等元胞自动机的一类环上变体，是一个初等的动力系统问题。

动力系统（dynamical system）是研究系统状态在给定规则下随时间演化规律的数学分支。

初等元胞自动机（elementary cellular automaton，ECA）是最简单的离散动力系统，定义在一维空间和离散时间上，由无数个相同的元胞组成。所有元胞排成一条无限延伸的直线，每个元胞在任一时刻的状态只有 0/1 两种，且元胞下一时刻的状态仅由它自身以及左、右两个邻居的当前状态决定。

由于一个元胞和它左右两个邻居的状态组合共有 8 种，规则需要为每一种组合指定中心元胞的下一状态是 0 还是 1 。将这 8 种组合对应的新状态（0 或 1）按特定顺序排列，形成一个 8 位的二进制数。将其转换为十进制，就得到了该规则的沃尔夫勒姆代码，范围在 0 到 255 之间。不同的规则会产生完全不同的演化情形。其中，规则 110 被证明是图灵完备的。这展现出极其简单的局部规则也能涌现出惊人的复杂全局行为。

元胞自动机（cellular automaton）则定义在任意维数上，满足时空离散、空间平移对称、状态更新同步且局部。

康威生命游戏是最著名、影响力最大的二维元胞自动机模型。它也是图灵完备的。

可以说，一个元胞自动机就是一个小小的模拟宇宙。通过简单的宇宙规则，世界就能演化出极其多彩的状态。