Bóna · 枚举与解析组合学导论 · 第 4 章 排列的计数

4.3　循环结构与指数生成函数Cycle structure and exponential generating functions

本页为译文 + 高中讲解合一：黑色正文为忠实翻译；彩色框（目标 / 例 / 分步推演 / 自测）与配图为面向高中生的详解，逐步推演、举例、画图，不用比喻。

稍加思考，我们就能明白：上一章学过的指数公式（exponential formula）对排列计数是非常有用的。事实上，一个排列（permutation）无非就是把集合 \([n]\) 拆分成任意多个非空块（block），再在每一个块上取一个循环（cycle）。我们尤其关心下面这条定理 4.34，它是定理 3.33 在排列情形下的对应版本。

本节目标把排列按“循环长度”来分类计数。核心工具是指数生成函数（exponential generating function，简称 EGF）：只要规定好“允许出现哪些长度的循环”（用集合 \(C\) 表示），就能用一条统一的指数公式，把满足条件的排列个数一次性装进一个生成函数里。随后再从这个生成函数中“读出”系数，就得到了具体的计数公式。本节会用它重新算出对合（involution）、错位排列（derangement）以及“全是偶长循环”的排列个数。

先复习：什么是循环记号把排列 \(p\) 看成 \([n]=\{1,2,\dots,n\}\) 到自身的双射。从某个元素出发，反复施加 \(p\)，会兜回起点，形成一个循环。例如 \(p=(3\,2\,4)(5\,1)\) 表示 \(3\to2\to4\to3\) 与 \(5\to1\to5\)。一个排列就是把 \([n]\) 切成若干非空块，再让每块自成一个循环。循环长度就是块里元素的个数。
排列 \(p=(3\,2\,4)(5\,1)\) 的循环结构 3 2 4 长度 3 的循环 5 1 长度 2 的循环
同一个排列由两个循环组成：长度分别是 \(3\) 与 \(2\)。本节就是要按“出现了哪些循环长度”来给排列分类计数。
定理 4.34 设 \(C\) 是任意一个正整数集合，并设 \(g_C(n)\) 为长度为 \(n\)、其所有循环长度都属于 \(C\) 的排列个数。则 \[\tag{4.10}G_C(x)=\sum_{n\ge 0}g_C(n)\,\frac{x^n}{n!}=\exp\!\left(\sum_{n\in C}\frac{x^n}{n}\right).\]
证明. 证明与定理 3.33 的证明相似，但并不完全相同。我们把 \([n]\) 划分成若干块。对于大小为 \(m\) 的一个块，若 \(m\notin C\)，令 \(a(m)=0\)；否则令 \(a(m)=(m-1)!\)。换句话说，\(a(m)\) 就是在一个 \(m\) 元块上取一个允许的循环的方法数。于是 \[A(x)=\sum_{n\ge 1}a(n)\,\frac{x^n}{n!}=\sum_{n\in C}\frac{x^n}{n}\] 就是“第一项任务（在块上放循环）的方法数”的指数生成函数，再由指数公式即得结论。♦
为什么 \(a(m)=(m-1)!\)把 \(m\) 个固定的元素排成一个长度为 \(m\) 的循环，有多少种方法？先把它们排成一行有 \(m!\) 种；但同一个循环可以从任一元素起读，\(m\) 种起点读出的是同一个循环，所以要除以 \(m\)，得 \(m!/m=(m-1)!\) 种。又因为 \(\dfrac{(m-1)!}{m!}=\dfrac1m\)，在指数生成函数里第 \(m\) 项的系数恰好是 \(\dfrac{1}{m}\)，这正是 \(\sum_{n\in C}\dfrac{x^n}{n}\) 中每一项的来历。
例（\(m=3\) 时数一数） 在 \(\{a,b,c\}\) 上能排出几个不同的 \(3\)-循环？答案 \((3-1)!=2\) 个：\((a\,b\,c)\) 与 \((a\,c\,b)\)。验证：\((a\,b\,c)=(b\,c\,a)=(c\,a\,b)\) 是同一个，\((a\,c\,b)=(c\,b\,a)=(b\,a\,c)\) 是另一个，恰好两类。

我们从一个非常基础的例子开始。开始之前，提醒读者：\(\dfrac{1}{1-x}=\sum_{n\ge 0}x^n\)，对两边积分便得到等式 \[\ln(1-x)^{-1}=\sum_{n=1}^{\infty}\frac{x^n}{n}.\]

例 4.35 设 \(C\) 为全体正整数之集。则 \[G_C(x)=\exp\!\left(\sum_{n=1}^{\infty}\frac{x^n}{n}\right)=\exp\!\big(\ln(1-x)^{-1}\big)=\frac{1}{1-x}=\sum_{n\ge 0}x^n.\] 于是 \(G_C(x)\) 中 \(x^n\) 的系数为 \(1\)，从而 \(x^n/n!\) 的系数为 \(n!\)。这一点毫不意外，因为它说的正是：若允许所有循环长度，则长度为 \(n\) 的排列共有 \(n!\) 个。
  1. 取 \(C=\) 全体正整数，求和号 \(\sum_{n\in C}\dfrac{x^n}{n}\) 就跑遍 \(n=1,2,3,\dots\)，正好是 \(\ln(1-x)^{-1}\)。
  2. 外面套一个 \(\exp\)，与对数互相抵消：\(\exp(\ln(1-x)^{-1})=(1-x)^{-1}\)。
  3. 把 \(\dfrac{1}{1-x}\) 展开成几何级数 \(\sum_{n\ge0}x^n\)，所以 \(x^n\) 前的系数是 \(1\)。
  4. 但 \(G_C\) 是指数生成函数，记 \(g_C(n)\) 为 \(x^n/n!\) 的系数；由 \([x^n]G_C=1=\dfrac{g_C(n)}{n!}\) 得 \(g_C(n)=n!\)，即所有 \(n\) 元排列。♦

下面的例子展示了定理 4.34 的一个典型应用。称排列 \(p\) 为对合（involution），若 \(p^2\) 是恒等排列。不言而喻，\(p\) 是对合当且仅当 \(p\) 中所有循环的长度都是 \(1\) 或 \(2\)。让我们用新技术来计算长度为 \(n\) 的对合个数。

为什么对合 \(\Leftrightarrow\) 循环长度 \(\le 2\)\(p^2\) 是恒等，意味着对每个 \(x\) 都有 \(p(p(x))=x\)。若 \(x\) 所在循环长度为 \(1\)（不动点 \(p(x)=x\)）或 \(2\)（\(x\leftrightarrow y\) 对换），施加两次自然回到 \(x\)。若某循环长度 \(\ge 3\)，比如 \(x\to y\to z\to\cdots\)，则 \(p^2(x)=z\ne x\)，矛盾。故对合恰好对应“只由不动点和对换组成”的排列。
例 4.36 长度为 \(n\) 的对合总数为 \[f(n)=\sum_{i=0}^{\lfloor n/2\rfloor}\binom{n}{2i}\,(2i-1)!!,\] 其中约定 \((-1)!!=1\)。
解. 我们对 \(C=\{1,2\}\) 应用定理 4.34。于是 \[G_C(x)=\exp\!\left(x+\frac{x^2}{2}\right)=\left(\sum_{k\ge 0}\frac{x^k}{k!}\right)\cdot\left(\sum_{i\ge 0}\frac{x^{2i}}{i!\,2^i}\right).\] 注意右边 \(x^n\) 的系数等于 \(\displaystyle\sum_{i=0}^{\lfloor n/2\rfloor}\frac{1}{(n-2i)!\cdot i!\cdot 2^i}\)。再观察到 \(\dfrac{(2i)!}{i!\,2^i}=(2i-1)!!\)，结论即得。♦
  1. \(C=\{1,2\}\)，所以 \(\sum_{n\in C}\dfrac{x^n}{n}=\dfrac{x^1}{1}+\dfrac{x^2}{2}=x+\dfrac{x^2}{2}\)，于是 \(G_C(x)=\exp\!\big(x+\tfrac{x^2}{2}\big)\)。
  2. 用 \(\exp(A+B)=\exp A\cdot\exp B\) 拆开：\(\exp(x)=\sum_k \dfrac{x^k}{k!}\)（管不动点），\(\exp(\tfrac{x^2}{2})=\sum_i\dfrac{x^{2i}}{i!\,2^i}\)（管对换）。
  3. 两级数相乘，凑出 \(x^n\)：取第一个里的 \(x^{n-2i}\) 与第二个里的 \(x^{2i}\)，系数为 \(\dfrac{1}{(n-2i)!}\cdot\dfrac{1}{i!\,2^i}\)，对 \(i\) 求和。
  4. 把它乘以 \(n!\)（因为要的是 \(x^n/n!\) 的系数）： \[f(n)=\sum_{i}\frac{n!}{(n-2i)!\,i!\,2^i}=\sum_i\binom{n}{2i}\frac{(2i)!}{i!\,2^i}=\sum_i\binom{n}{2i}(2i-1)!!.\]
  5. 这正好对应组合解释：先从 \(n\) 个元素里选 \(2i\) 个去配对（\(\binom{n}{2i}\) 种），再把这 \(2i\) 个两两配成对换（\((2i-1)!!\) 种），其余 \(n-2i\) 个都是不动点。♦
\(n=4\) 时的全部对合：\(f(4)=1+6+3=10\) 个 \(i=0\)：全是不动点 1 种 \(i=1\)：一对对换 + 两不动点 \(\binom{4}{2}\cdot1=6\) 种 \(i=2\)：两对对换 \(\binom{4}{4}\cdot3!!=3\) 种
\(n=4\)：按对换的对数 \(i=0,1,2\) 分类，分别有 \(1,6,3\) 个，合计 \(10\)，与公式 \(f(4)=\sum_i\binom{4}{2i}(2i-1)!!\) 完全吻合。

带着这份新知识，我们重新证明在 2.4.3.4 节中证过的错位排列（derangement）个数公式。回忆：错位排列是没有 \(1\)-循环（即没有不动点 fixed point）的排列。这一次，我们不必再诉诸容斥原理（principle of inclusion-exclusion）那略显繁琐的计算。

事实上，取 \(C=\mathbb{P}\setminus\{1\}\)（全体正整数去掉 \(1\)）。那么定理 4.34 给出 \[G_C(x)=\exp\!\left(\sum_{n\ge 2}\frac{x^n}{n}\right)=\exp\!\big(\log(1-x)^{-1}-x\big)=\frac{e^{-x}}{1-x}.\] 换句话说，我们得到 \[G_C(x)=\sum_{n=1}^{\infty}\left(\sum_{i=0}^{n}\frac{(-1)^i}{i!}\right)x^n,\] 所以 \(G_C(x)\) 中 \(x^n/n!\) 的系数为 \[\tag{4.11}n!\cdot\sum_{i=0}^{n}\frac{(-1)^i}{i!},\] 这与我们在 2.4.3.4 节所证的完全一致。注意，当 \(n\to\infty\) 时，和式 \(\sum_{i=0}^{n}\dfrac{(-1)^i}{i!}\) 收敛到 \(e^{-1}\)。也就是说，对很大的 \(n\)，超过三分之一的 \(n\)-排列是无不动点的，即错位排列。

  1. “没有 \(1\)-循环”等价于允许的循环长度为 \(2,3,4,\dots\)，即 \(C=\{2,3,4,\dots\}\)。
  2. \(\sum_{n\ge2}\dfrac{x^n}{n}=\Big(\sum_{n\ge1}\dfrac{x^n}{n}\Big)-x=\ln(1-x)^{-1}-x\)（把缺掉的 \(n=1\) 项 \(x\) 减去）。
  3. 取指数：\(\exp\!\big(\ln(1-x)^{-1}-x\big)=\dfrac{e^{-x}}{1-x}\)。
  4. 把 \(e^{-x}=\sum_i\dfrac{(-1)^i}{i!}x^i\) 与 \(\dfrac{1}{1-x}=\sum_j x^j\) 相乘，\(x^n\) 的系数是 \(\sum_{i=0}^n\dfrac{(-1)^i}{i!}\)，再乘 \(n!\) 即得 (4.11)。♦
数字验证（\(n=3\)） 由 (4.11)，错位排列数 \(=3!\big(1-1+\tfrac12-\tfrac16\big)=6\cdot\tfrac13=2\)。\([3]\) 上确有 \(2\) 个无不动点排列：\(231\) 与 \(312\)。

把 (4.11) 与引理 4.12 的结果相比较，我们发现一个令人惊讶的事实：对任意 \(n\ge 1\)，长度为 \(n\) 的错位排列个数等于长度为 \(n\) 的反错排（desarrangement）个数。这非常有趣，因为错位排列是用排列的循环定义的，而反错排是用单行记号（one-line notation）定义的。回忆：称排列 \(p\) 为反错排，若 \(p\) 的第一个上升（ascent）出现在偶数位置上，或者 \(p\) 是递减的 \(n\)-排列且 \(n\) 为偶数。

名词对照上升：单行记号中相邻两位满足 \(p_i<p_{i+1}\) 的位置 \(i\)。“第一个上升在偶数位”意思是：从左往右第一次出现“后一个比前一个大”发生在第 \(2,4,6,\dots\) 位。错位排列看循环（无不动点）；反错排看单行的升降模式。两者定义方式完全不同，个数却处处相等——这正需要一个双射证明。

如此漂亮的恒等式当然值得一个双射证明。一旦我们找到对“典范循环记号”（canonical cycle notation）的恰当修改，这样的证明就相当容易找到。

设 \(p\) 为任一长度为 \(n\) 的错位排列。我们把 \(p\) 写成循环记号，使得：每个循环把它最小的元素放在第二个位置；并且各循环按其最小元素的递减顺序排列。定义 \(f(p)\) 为把 \(p\) 去掉所有括号后得到的单行记号排列。

例 4.37 若 \(p=(3\,2\,4)(5\,1)\)，则 \(f(p)=32451\)。若 \(p=(4\,3)(2\,1\,5)\)，则 \(f(p)=43215\)。
去括号映射 \(f\)：循环记号 → 单行记号 ( 3 2 4 ) ( 5 1 ) ⟶ 3 2 4 5 1 最小元在每循环第 2 位；循环按最小元递减排列 擦掉括号即得
规则化的循环记号去掉括号后，恰好成为一个反错排；这个对应是可逆的。
定理 4.38 上面定义的“去括号映射” \(f\) 是从全体长度为 \(n\) 的错位排列之集 \(D_n\) 到全体长度为 \(n\) 的反错排之集 \(J_n\) 的一个双射（bijection）。
证明. 首先证明 \(f\) 确实映入 \(J_n\)，即 \(f(p)\) 总是一个反错排。\(p\) 的第一个循环 \(C\) 把它的最小元素 \(x\) 放在第二位，所以若 \(C\) 含有第三个元素 \(y\)，则 \(y>x\)，于是 \(f(p)\) 的第一个上升出现在第二位，从而 \(f(p)\) 是反错排。若 \(C\) 只含两个元素，而第二个循环 \(C'\) 的首元素大于 \(x\)，则证毕；否则对 \(C'\) 重复对 \(C\) 所作的论证。如此继续下去，一旦遇到一个含有两个以上元素的循环，或一个其首元素大于前一循环末（第二）元素的循环，我们就会停下，并在某个偶数位置找到 \(f(p)\) 的第一个上升。唯一不出现这两种情形的情况，是所有循环长度都为 \(2\)、且它们里的元素越来越小：此时必有 \(n=2k\) 且 \[p=(2k\;\;2k-1)(2k-2\;\;2k-3)\cdots(2\;1),\] 于是 \(f(p)\) 是长度为 \(2k\) 的递减排列，它也是一个反错排。

接下来证明 \(f:D_n\to J_n\) 是双射，办法是证明它有逆映射。设 \(q\in J_n\)，写成单行记号 \(q=q_1q_2\cdots q_n\)。我们要找到唯一的 \(p\in D_n\) 使 \(f(p)=q\)。由 \(f\) 的定义可知，若 \(q_i=1\)，则 \(p\) 的最后一个循环必为 \((q_{i-1}\,q_i\cdots q_n)\)，因为 \(1\) 总是最后一个循环的最小元素。由于 \(q\) 是反错排，不可能 \(i=3\)（否则 \(q\) 的第一个上升将在第一位或第三位）；于是当字符串 \(q'=q_1q_2\cdots q_{i-2}\) 非空时，它的长度至少为 \(2\)。因此我们可以对 \(q'\) 重复同样的论证，即：从“它的最小元素之前的那个元素”开始，找到它的最后一个循环。如此迭代，直到 \(q\) 被全部拆成循环，便得到 \(q\) 的（唯一）原像。唯一性来自这样的事实：\(f\) 不改变各元素从左到右的次序，而在我们精心选定的条件下，循环无法在别处开始。因此 \(f\) 确为双射。♦
逆映射怎么找（直观）给定反错排 \(q\)，从右往左识别循环：找到 \(1\) 所在位置，它前一个元素就是最后一个循环的“起点”，于是把“起点到末尾”这一段括成最后一个循环；剩下的前缀再重复这个过程。因为最小元素总固定放在循环第二位，且循环按最小元递减排列，每一步切法是唯一的——这就保证了可逆。
用例 4.37 反着走一遍 取 \(q=32451\)。\(1\) 在第 \(5\) 位，前一个是第 \(4\) 位的 \(5\)，故最后一个循环是 \((5\,1)\)；剩下 \(q'=324\)，其中最小元 \(2\) 前面是 \(3\)，故循环为 \((3\,2\,4)\)。拼起来 \(p=(3\,2\,4)(5\,1)\)，与原排列一致。

上面错位排列的例子虽是经典，但它针对的是一个特殊情形：允许的循环长度集 \(C\) 只比“全体正整数”少了一个元素。为了让读者更欣赏指数公式作为排列计数工具的威力，我们再给出一个涉及无限集 \(C\) 的例子。

例 4.39 每个循环长度都为偶数的 \(n\)-排列个数：当 \(n\) 为奇数时为零；当 \(n=2m\) 时为 \[\mathrm{even}(2m)=1^2\cdot 3^2\cdots(2m-1)^2=\big(1\cdot 3\cdots(2m-1)\big)^2=(2m-1)!!^2.\]
解. 我们对 \(C=\) 全体偶正整数 应用定理 4.34。于是定理 4.34 给出 \[G_C(x)=\exp\!\left(\sum_{m=1}^{\infty}\frac{x^{2m}}{2m}\right).\] 注意右边与形式幂级数 \(\exp(\ln(1-x)^{-1})\) 非常相似，只是把 \(x\) 换成了 \(x^2\)，又把 \(\exp\) 的自变量除以了 \(2\)。因此 \[G_C(x)=\exp\!\left(\frac{1}{2}\ln(1-x^2)^{-1}\right)=\frac{1}{\sqrt{1-x^2}}.\] 于是我们将把数 \(\mathrm{even}(2m)\) 求作 \(\dfrac{1}{\sqrt{1-x^2}}\) 中 \(\dfrac{x^{2m}}{(2m)!}\) 的系数。无需任何计算即可看出 \(\mathrm{even}(2m+1)=0\)，因为若干偶数之和不可能是奇数。为计算 \(\mathrm{even}(2m)\)，我们使用二项式定理（binomial theorem）： \[\begin{aligned} G_C(x)&=\frac{1}{\sqrt{1-x^2}}=(1-x^2)^{-1/2}=\sum_{m\ge 0}\binom{-1/2}{m}(-1)^m x^{2m}\\ &=\sum_{m\ge 0}(-1)^m\frac{(-1/2)(-3/2)\cdots(-(2m-1)/2)}{m!}x^{2m}=\sum_{m\ge 0}\frac{(2m-1)!!}{m!\,2^m}x^{2m}. \end{aligned}\] 所以 \(G_C(x)\) 中 \(x^{2m}\) 的系数为 \(\dfrac{(2m-1)!!}{m!\,2^m}\)；从而 \(\dfrac{x^{2m}}{(2m)!}\) 的系数为它的 \((2m)!\) 倍。换言之，正如所言，它确实等于 \((2m-1)!!^2\)。♦
  1. \(C=\{2,4,6,\dots\}\)，故 \(\sum_{n\in C}\dfrac{x^n}{n}=\sum_{m\ge1}\dfrac{x^{2m}}{2m}=\dfrac12\sum_{m\ge1}\dfrac{(x^2)^m}{m}=\dfrac12\ln(1-x^2)^{-1}\)。
  2. 取指数：\(\exp\!\big(\tfrac12\ln(1-x^2)^{-1}\big)=(1-x^2)^{-1/2}=\dfrac{1}{\sqrt{1-x^2}}\)。
  3. 用广义二项式定理展开 \((1-x^2)^{-1/2}\)，化简广义二项系数得 \(x^{2m}\) 系数 \(\dfrac{(2m-1)!!}{m!\,2^m}\)。
  4. 乘以 \((2m)!\)。利用 \((2m)!=2^m\,m!\,(2m-1)!!\)，得 \[\mathrm{even}(2m)=(2m)!\cdot\frac{(2m-1)!!}{m!\,2^m}=(2m-1)!!^2.\]♦
数字验证（\(n=2\) 与 \(n=4\)） \(m=1\)：\(\mathrm{even}(2)=(1!!)^2=1\)，确实 \([2]\) 上只有 \((1\,2)\) 这一个全偶长循环排列。\(m=2\)：\(\mathrm{even}(4)=(3!!)^2=(1\cdot3)^2=9\)。即 \([4]\) 上恰有 \(9\) 个排列，其循环要么是一个 \(4\)-循环（共 \(3!=6\) 个），要么是两个 \(2\)-循环（共 \(3\) 个），合计 \(6+3=9\)，吻合。
即时自测
  1. 由一个 \(1\)-循环和一个 \((n-1)\)-循环组成的长度为 \(n\) 的排列有多少个？
  2. 有多少个长度为 \(n\) 的排列，使得元素 \(1\) 与 \(2\) 在同一个循环中，而元素 \(3\) 在另一个循环中？
  3. 有多少个长度为 \(n\) 的排列，使得元素 \(1\) 在一个 \(2\)-循环中，且元素 \(2\) 也在一个 \(2\)-循环中？

返回 全书目录