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

4.5　生成函数在排列计数中的高级应用Advanced applications of generating functions to permutation enumeration

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

我们来考虑几个计数问题。在这些问题中，生成函数（generating function）仍然非常有用，但我们必须以一些此前未曾见过的方式来使用它们。

本节目标前面几节里，我们用生成函数“装”住一列数，再读它的系数。本节要展示一个新招数：对一个已知的多项式恒等式两边求导，然后再代入 \(x=1\)，从而一次性算出“所有排列里圈（cycle）的总数”和“平均每个排列有几个圈”。关键在于看出：求导以后冒出来的那个系数 \(k\cdot c(n,k)\)，在组合上正好就是“贡献了多少个圈”。

4.5.1　导数的组合意义

在定理 4.21 中，我们证明了一个有趣的公式：对任意固定的正整数 \(n\)，有 \[\tag{4.14}\sum_{k=1}^{n} c(n,k)\,x^{k}=x(x+1)\cdots(x+n-1).\] 这里 \(c(n,k)\) 是第一类无符号 Stirling 数（signless Stirling number of the first kind），即长度为 \(n\)、恰好含 \(k\) 个圈的排列的个数。

先把 (4.14) 验算一遍（取 \(n=3\)） 长度为 \(3\) 的排列共有 \(3!=6\) 个，按圈的个数分类：
  1. 恰含 \(1\) 个圈（即一个长度为 \(3\) 的圈）的有 \(2\) 个，所以 \(c(3,1)=2\)。
  2. 恰含 \(2\) 个圈（一个长度 \(2\) 的圈加一个固定点）的有 \(3\) 个，所以 \(c(3,2)=3\)。
  3. 恰含 \(3\) 个圈（三个固定点，即恒等排列）的只有 \(1\) 个，所以 \(c(3,3)=1\)。
代入左边：\(2x+3x^{2}+1\cdot x^{3}\)。右边：\(x(x+1)(x+2)=x(x^{2}+3x+2)=x^{3}+3x^{2}+2x\)。两边完全一致，(4.14) 成立。注意系数之和 \(2+3+1=6=3!\)，正是排列总数。
长度 \(n=3\) 的 6 个排列，按“圈的个数”分三堆 1 个圈：c(3,1)=2 2 个圈：c(3,2)=3 3 个圈：c(3,3)=1 (123) (132) (12)(3) (13)(2) (23)(1) (1)(2)(3)
用圈表示法写出 \(6\) 个排列。每个排列括号里的“括号组”个数就是它的圈数。这堆数据正是 (4.14) 左边各系数的来历。

现在让我们对 (4.14) 的两边关于 \(x\) 求导。我们得到恒等式 \[\sum_{k=1}^{n} k\cdot c(n,k)\,x^{k-1}=\sum_{i=0}^{n-1}\frac{x(x+1)\cdots(x+n-1)}{x+i}.\] 请注意，对 (4.14) 右边求导时，我们只是用了乘积法则（product rule）。这一步很容易，因为每个单独的因子 \((x+i)\) 的导数都是 \(1\)。

为什么右边长这样右边是 \(n\) 个因子 \(x,\,x+1,\,\dots,\,x+n-1\) 连乘。乘积法则说：连乘的导数 = 逐个把其中一个因子换成它的导数、其余不动、再相加。由于每个因子求导都得 \(1\)，所以“把第 \(i\) 个因子换成 \(1\)”就等于“把整个乘积去掉第 \(i\) 个因子”，也就是把整个乘积除以那个因子 \((x+i)\)。于是 \(n\) 项加起来，得到右边的求和形式。
把乘积法则的这一步做实（仍取 \(n=3\)） 右边是 \(f(x)=x(x+1)(x+2)\)。按乘积法则： \[f'(x)=\underbrace{1\cdot(x+1)(x+2)}_{\text{第 0 项去掉 }x}+\underbrace{x\cdot 1\cdot(x+2)}_{\text{去掉 }(x+1)}+\underbrace{x(x+1)\cdot 1}_{\text{去掉 }(x+2)}.\] 每一项恰好是“整个乘积除以一个因子”： \[f'(x)=\frac{f(x)}{x}+\frac{f(x)}{x+1}+\frac{f(x)}{x+2}=\sum_{i=0}^{2}\frac{x(x+1)(x+2)}{x+i}.\] 而左边 \(\dfrac{d}{dx}\bigl(2x+3x^{2}+x^{3}\bigr)=2+6x+3x^{2}\)，正好是 \(\sum_{k=1}^{3}k\,c(3,k)\,x^{k-1}\)。两边相等，求导这一步无误。

现在让我们在上面这个等式中代入 \(x=1\)，得到 \[\tag{4.15}\sum_{k=1}^{n} k\cdot c(n,k)=\sum_{j=1}^{n}\frac{n!}{j}.\]

  1. 左边代 \(x=1\)：每个 \(x^{k-1}\) 都变成 \(1\)，于是 \(\sum_{k=1}^{n}k\cdot c(n,k)\,x^{k-1}\) 变成 \(\sum_{k=1}^{n}k\cdot c(n,k)\)。
  2. 右边代 \(x=1\)：分子 \(x(x+1)\cdots(x+n-1)\) 在 \(x=1\) 处等于 \(1\cdot 2\cdots n=n!\)。
  3. 右边第 \(i\) 项的分母 \((x+i)\) 在 \(x=1\) 处等于 \(1+i\)。当 \(i\) 从 \(0\) 跑到 \(n-1\) 时，\(1+i\) 恰好取遍 \(1,2,\dots,n\)。
  4. 于是右边每一项是 \(\dfrac{n!}{1+i}\)，把它们改用 \(j=1+i\) 记号汇总，就是 \(\sum_{j=1}^{n}\dfrac{n!}{j}\)，即 (4.15)。
数字核对 (4.15)（\(n=3\)） 左边 \(\sum_{k=1}^{3}k\,c(3,k)=1\cdot 2+2\cdot 3+3\cdot 1=2+6+3=11\)。
右边 \(\sum_{j=1}^{3}\dfrac{3!}{j}=\dfrac{6}{1}+\dfrac{6}{2}+\dfrac{6}{3}=6+3+2=11\)。两边都等于 \(11\)。

关键的观察是：左边的表达式 \(\sum_{k=1}^{n} k\cdot c(n,k)\)，恰好就是长度为 \(n\) 的所有排列中圈的总数。的确，由 \(c(n,k)\) 计数的那些排列，每一个都向这个总数贡献了 \(k\) 个圈。所以公式 (4.15) 事实上是一个关于“长度为 \(n\) 的所有排列里圈的总数”的公式。

为什么 \(\sum_{k} k\,c(n,k)\) 就是“圈的总数”把所有排列按圈数分堆：恰有 \(k\) 个圈的排列共有 \(c(n,k)\) 个，其中每一个都各自含有 \(k\) 个圈，所以这一堆一共贡献 \(k\cdot c(n,k)\) 个圈。把所有堆（\(k=1,2,\dots,n\)）的贡献加起来，就是全体排列的圈数总和。这正是“按贡献分类再求和”的计数手法。
数出 n=3 时全部排列的圈数总和 k=1 k=2 k=3 1·c=1·2=2 2·c=2·3=6 3·c=3·1=3 总圈数 = 2 + 6 + 3 = 11
每个柱高 \(=k\cdot c(n,k)\) 表示该堆贡献的圈数。三堆相加 \(=11\)，与 (4.15) 两边的数值一致。

等价地，如果我们把 (4.15) 的两边都除以 \(n!\)，就得到：长度为 \(n\) 的排列中圈的平均个数是 \[\frac{1}{n!}\sum_{k=1}^{n} k\cdot c(n,k)=\sum_{j=1}^{n}\frac{1}{j}.\] 这个数常被称为第 \(n\) 个调和数（the \(n\)th harmonic number），记作 \(H_n=1+\tfrac12+\tfrac13+\dots+\tfrac1n\)。虽然这个结果不用生成函数也能证明（见习题 18），但“对一个生成函数求导、再在 \(x=1\) 处求值”这一想法，在类似的情形中往往很有用。

为什么除以 \(n!\) 就得到“平均”“平均圈数” = “所有排列的圈数总和” ÷ “排列的个数”。排列的总个数是 \(n!\)，圈数总和是 (4.15) 的左边，所以平均值就是左边除以 \(n!\)。把 (4.15) 右边的 \(\sum_{j=1}^{n}\frac{n!}{j}\) 也除以 \(n!\)，每一项的 \(n!\) 被约掉，只剩 \(\sum_{j=1}^{n}\frac1j\)。
平均圈数（\(n=3\)） 总圈数 \(=11\)，排列数 \(=3!=6\)，所以平均每个排列有 \(\dfrac{11}{6}\) 个圈。另一边 \(H_3=1+\dfrac12+\dfrac13=\dfrac{6+3+2}{6}=\dfrac{11}{6}\)。两种算法吻合。也就是说，随机取一个长度为 \(3\) 的排列，平均会有 \(11/6\approx 1.83\) 个圈。
即时自测
  1. 用本节方法验证 \(n=2\) 的情形：写出 (4.14) 左边各系数 \(c(2,1),c(2,2)\)，分别算出 (4.15) 两边的值，并求出长度为 \(2\) 的排列的平均圈数。
  2. 对长度为 \(4\) 的排列，已知 \(c(4,1)=6,\ c(4,2)=11,\ c(4,3)=6,\ c(4,4)=1\)。请用 (4.15) 算出所有圈的总数，再除以 \(4!\) 验证它等于 \(H_4=1+\tfrac12+\tfrac13+\tfrac14\)。
  3. 说明为什么“对 (4.14) 求导后代 \(x=1\)”能得到圈的总数，而“直接在 (4.14) 中代 \(x=1\)”得到的却是排列的总数 \(n!\)。

返回 全书目录