Bóna · 枚举与解析组合学导论 · 第 5 章 图的计数

5.5　图与生成函数Graphs and generating functions

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

说明：本节所提供的原文 PDF 仅含本节的开头一页（书第 287 页），正文在“……卡莱公式告诉我们，\([n]\) 上有根树的数目为……”处自然结束。下文先逐句译出该页内容，再围绕这一页所讲的真实数学对象——有根树、删根后的有根森林结构、卡莱公式、以及由此得到的生成函数函数方程——展开高中讲解。

本节目标把上一章学到的强大计数工具——生成函数（generating function）——用到“数树”这件具体的事情上。核心思路是：一棵有根树（rooted tree）删掉根之后，剩下的是一片有根森林（rooted forest）；这个“拆解”关系能写成一个关于生成函数的函数方程（functional equation），再从方程里把树的个数解出来。

是时候把我们在上一章中学到的强大计数技巧，应用到“枚举各式各样的树”这件事情上了。我们先从一族经典的树开始探索。

5.5.1　用卡莱公式计数的树Trees counted by Cayley’s formula

\([n]\) 上的有根树具有一种很好的递归结构（recursive structure）。如果我们把这样一棵树的根 \(R\) 剪掉，就得到一片有根森林——也就是若干棵树，每棵树都以“原来与 \(R\) 相邻的那个顶点”为根。换句话说，有根森林是由有根树搭建起来的。这一结构可以用一个简单的函数方程来表达。我们由卡莱公式（Cayley’s formula）知道，\([n]\) 上有根树的数目为……

（原文 PDF 在此处结束。下面把这句话补完，并把它背后的数学讲清楚。）

先把名词讲清楚

第一步：看清“删根”这个动作

把根 \(R\) 从有根树上拿掉，会发生什么？\(R\) 原来连着的每一条边都断开了。原来挂在 \(R\) 上的每个邻居，现在各自带着“自己下方的那一团”独立出来，成为一棵新的、以这个邻居为根的小树。于是“一棵有根树”被拆成了“一片有根森林”。

一棵有根树（根 R） R ⟶ 删去根 R 一片有根森林（3 棵小树）
删去根 \(R\) 后，\(R\) 的每个邻居都成了一棵小有根树的根（图中加圈标出）；它们合起来就是一片有根森林。反过来，给一片有根森林“接上一个新根、再把根连到每棵小树的根”，又恰好还原成一棵有根树。
结构对应 “\([n]\) 上的有根树” 与 “一个新根 \(+\) 一片有根森林” 之间是一一对应（双射）的。正是这个对应，让我们能用生成函数把树的个数“算出来”。

第二步：卡莱公式给出树的个数

卡莱公式（有根树版）\([n]\) 上有根树的数目为 \[\tag{5.5.1} r_n=n^{\,n-1}.\] （去掉“指定根”这一步，则 \([n]\) 上无根树的数目为 \(n^{\,n-2}\)；二者相差一个因子 \(n\)，因为一棵 \(n\) 顶点的树有 \(n\) 种选根方式。）

这正是上面那句被截断的话要说的结论：树的数目是 \(n^{n-1}\)。我们用最小的几个 \(n\) 把它“数出来”验证一下。

例（逐个数小情形）
  1. \(n=1\)：只有顶点 \(1\)，它本身就是根。有根树共 \(1\) 棵。公式：\(1^{0}=1\)。✓
  2. \(n=2\)：树只有一条边 \(1\!-\!2\)（无根树只有 \(1\) 棵，即 \(2^{0}=1\)）；选根有两种——根是 \(1\)，或根是 \(2\)。所以有根树共 \(2\) 棵。公式：\(2^{1}=2\)。✓
  3. \(n=3\)：\(3\) 个顶点的无根树有 \(3^{1}=3\) 棵（即三条“链”：以谁居中分类）；每棵树选根有 \(3\) 种。所以有根树共 \(3\times3=9\) 棵。公式：\(3^{2}=9\)。✓
\(n=2\)：恰有 2 棵有根树（同一条边，根不同） 1 2 根 = 1 2 1 根 = 2
\(n=2\)：底层的树只有一条边，但因为根可以是 \(1\) 也可以是 \(2\)，有根树就有 \(2=2^{1}\) 棵。

第三步：把递归结构翻成生成函数

因为带标号，数树最顺手的工具是指数生成函数（exponential generating function, EGF）。设 \[T(x)=\sum_{n\ge 1} r_n\,\frac{x^n}{n!}=\sum_{n\ge 1} n^{\,n-1}\,\frac{x^n}{n!}\] 为“\([n]\) 上有根树”的指数生成函数。把前几项写出来： \[T(x)=x+2\cdot\frac{x^2}{2!}+9\cdot\frac{x^3}{3!}+64\cdot\frac{x^4}{4!}+\cdots=x+x^2+\tfrac{3}{2}x^3+\tfrac{8}{3}x^4+\cdots.\]

现在用第一步的“删根 / 接根”双射，把 \(T(x)\) 自己和自己联系起来。回忆指数生成函数的两条规则：

EGF 的两条规则
  1. “一族同类对象的集合”对应 EGF 的指数：若每个“零件”由 \(A(x)\) 计数，则“由若干个互不重叠的零件拼成的集合”由 \(e^{A(x)}\) 计数（这就是指数公式，把零件个数 \(0,1,2,\dots\) 一并求和，并自动配上正确的标号分配权重）。
  2. “添一个带标号的特殊点”对应乘以 \(x\)。
  1. 一片有根森林 = 若干棵有根树组成的集合。由规则 1，有根森林的 EGF 是 \(e^{T(x)}\)。
  2. 一棵有根树 = 一个新根（带标号的特殊点，乘 \(x\)）连到一片有根森林（EGF 为 \(e^{T(x)}\)）。由规则 2，把二者相乘。
  3. 于是有根树的 EGF 满足函数方程 \[\tag{5.5.2} T(x)=x\,e^{\,T(x)}.\] 这正是正文所说的“可以用一个简单的函数方程来表达”的那个方程。
\(T\) = 新根（×x） 一片有根森林 （EGF \(=e^{T}\)） ⟹ \(T=x\,e^{T}\)
把“删根”的双射读成等式：一棵有根树 \(=\) 一个新根（贡献因子 \(x\)）接上一片有根森林（贡献因子 \(e^{T}\)）。两边的 EGF 相等，得到 \(T=x e^{T}\)。

第四步：从方程反解，验证 \(r_n=n^{n-1}\)

方程 \(T=x e^{T}\) 可以直接逐项把系数解出来，从而印证 \(r_n=n^{n-1}\)。设 \(T=\sum_{n\ge1} r_n x^n/n!\)，把它代入两边比较系数即可。我们演示最前面几步。

  1. 把 \(e^{T}=1+T+\tfrac{T^2}{2}+\tfrac{T^3}{6}+\cdots\) 展开，再乘上 \(x\)。
  2. \(x^1\) 的系数：右边只有 \(x\cdot 1\) 贡献，得 \(r_1/1!=1\)，即 \(r_1=1=1^{0}\)。✓
  3. \(x^2\) 的系数：右边 \(x\cdot T\) 贡献 \(r_1=1\)，得 \(r_2/2!=1\)，即 \(r_2=2=2^{1}\)。✓
  4. \(x^3\) 的系数：右边 \(x\big(T+\tfrac{T^2}{2}\big)\) 贡献 \(\tfrac{r_2}{2!}+\tfrac12 r_1^2=\tfrac{2}{2}+\tfrac12=\tfrac32\)，得 \(r_3/3!=\tfrac32\)，即 \(r_3=9=3^{2}\)。✓

一般地，对 \(T=x e^{T}\) 使用拉格朗日反演（Lagrange inversion）可一次性得到 \[\big[x^n\big]\,T(x)=\frac{1}{n}\big[t^{\,n-1}\big]\big(e^{t}\big)^{n}=\frac{1}{n}\cdot\frac{n^{\,n-1}}{(n-1)!}=\frac{n^{\,n-1}}{n!},\] 也就是 \(r_n=n!\cdot[x^n]T(x)=n^{\,n-1}\)。这与卡莱公式 (5.5.1) 完全吻合：生成函数不仅“验证”了公式，更给出了一条推导它的路径。

小结这一段“删根 → 有根森林”的递归结构 \(\;\Longrightarrow\;\) 函数方程 \(T=x e^{T}\) \(\;\Longrightarrow\;\) 系数 \(r_n=n^{n-1}\)。这就是“用生成函数数树”的完整链条，也是把第 4 章工具搬到第 5 章图论里的范例。
即时自测
  1. 用公式 \(r_n=n^{n-1}\) 算出 \([4]\) 上有根树的棵数，并用“无根树棵数 \(\times\) 选根方式”验证它。
  2. 写出 \(T(x)=x e^{T(x)}\) 中 \(x^4\) 的系数方程，解出 \(r_4\)，看是否等于 \(64\)。
  3. 解释为什么“有根森林”的指数生成函数恰好是 \(e^{T(x)}\)，而不是 \(\dfrac{1}{1-T(x)}\)。（提示：森林里的小树之间是否区分先后次序？）

返回 全书目录