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

5.3　顶点不可自由标号时When the vertices are not freely labeled

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

在某些情形里，我们会用一种很自然的方式去限制树的顶点所能取的标号。本节就来讨论由此产生的若干计数问题。

本节目标前几节里树的顶点可以“随便贴标号”——只要顶点集是 \(\{1,2,\dots,n\}\)（记作 \([n]\)），把哪个数字贴到哪个顶点上都行。本节要研究的是：当标号的贴法被某条规则卡住（例如要求“父亲的号码必须比儿子小”）时，树还有多少种。先把“自由标号”和“受限标号”这两件事讲清楚，再用具体的小例子把受限情形数出来。

5.3.1　先说清楚“自由标号”是什么

回忆一下前面用到的对象。一棵有根有标号树（rooted labeled tree）是这样得到的：取 \(n\) 个顶点，把数字 \(1,2,\dots,n\) 一一对应地贴在顶点上（这就是“标号”），再用 \(n-1\) 条边把它们连成一棵树，并指定其中一个顶点为根（root）。所谓自由标号（freely labeled），意思是：哪个数字贴到树的哪个位置上，没有任何额外限制。

定义（自由标号 vs. 受限标号）设一棵树的形状（即顶点之间谁连谁、谁是根）已经画好。
例（自由标号的计数）取一棵固定形状：根下面挂着两片叶子（一个“小三角”形状），共 \(3\) 个顶点。问：用 \(\{1,2,3\}\) 自由标号，有几种？
根的位置可以放 \(1,2,3\) 中任意一个，共 \(3\) 选;剩下两个数字放到两片叶子上。但两片叶子地位对称（左右互换得到的是同一棵树），所以放叶子的两种顺序算同一棵。于是答案是 \(3\times\dfrac{2!}{2}=3\) 种——即由根上的数字决定。
1 2 3 根 = 1 2 1 3 根 = 2 3 1 2 根 = 3
同一个“小三角”形状，自由标号下的 \(3\) 棵不同的树：根上分别是 \(1,2,3\)。两片叶子对称，所以叶子上数字的左右顺序不计。

5.3.2　一种典型的受限：递增树

当标号不再自由时，最自然、也最重要的一种限制是要求沿着从根往叶子的每条路径，号码严格递增。这样的树叫作递增树（increasing tree）。

定义（递增树）顶点集为 \([n]=\{1,2,\dots,n\}\) 的一棵有根有标号树称为递增树，如果对每一条边，靠近根的那一端（父亲）的号码都小于远离根的那一端（儿子）的号码。等价地说：从根出发沿任意一条向下的路径走，看到的号码一路严格增大。

注意一个直接的推论：在任何递增树里，根上必然是号码 \(1\)。因为根是所有路径的起点，它的号码必须比沿路所有顶点都小，而 \(1\) 是最小的。这与“自由标号”形成鲜明对比——自由时根上可以是任何数字。

例（\(n=3\) 的全部递增树）顶点 \(\{1,2,3\}\)，要求父亲号码 \(<\) 儿子号码。根必为 \(1\)。剩下 \(2,3\) 怎么挂？
  1. 把 \(2\) 挂到 \(1\) 下面，再把 \(3\) 挂到 \(1\) 下面：得到“根 \(1\) 带两个儿子 \(2,3\)”的树（路径 \(1\!\to\!2\)、\(1\!\to\!3\) 都递增，合法）。
  2. 把 \(2\) 挂到 \(1\) 下面，再把 \(3\) 挂到 \(2\) 下面：得到一条链 \(1\!\to\!2\!\to\!3\)（递增，合法）。
  3. 能不能把 \(3\) 挂到 \(1\) 下、\(2\) 挂到 \(3\) 下？路径 \(1\!\to\!3\!\to\!2\) 在最后一步 \(3\!\to\!2\) 递减，不合法。
所以 \(n=3\) 时恰有 \(2\) 棵递增树。
1 2 3 两个儿子 1 2 3
\(n=3\) 的两棵递增树：左为“根 \(1\) 带两个儿子”，右为链 \(1\!\to\!2\!\to\!3\)。根永远是 \(1\)。

5.3.3　递增树到底有多少棵

下面这条结果给出递增树个数的一个干净公式。它的妙处在于：受限标号反而让计数变得更简单。

定理（递增树计数）顶点集为 \([n]\) 的递增树恰有 \[\tag{5.6}(n-1)!\] 棵（其中规定 \(0!=1\)，故 \(n=1\) 时为 \(1\) 棵）。

证明的关键想法是逐个插入顶点：从只有顶点 \(1\) 的树出发，按 \(2,3,\dots,n\) 的顺序把顶点一个一个加进去。每加一个新顶点时，看看它有多少种合法的挂法。

证明.
  1. 设已经有了一棵顶点集为 \([k-1]\) 的递增树（\(k\ge 2\)）。现在要把新顶点 \(k\) 加进来。因为 \(k\) 是当前所有号码里最大的，把它挂到任何一个已有顶点的下面，那条新边“父亲 \(<\) 儿子”一定成立——递增性绝不会被破坏。
  2. 所以顶点 \(k\) 的合法挂法数，恰好等于“它能挂到哪个父亲下面”的选择数，也就是当前树里已有的顶点个数 \(k-1\)。即新顶点有 \(k-1\) 种挂法，且每一种都给出一棵不同的递增树。
  3. 从顶点 \(1\) 起步（\(1\) 棵），依次加入 \(2,3,\dots,n\)，由乘法原理（product principle），递增树总数为 \[(2-1)\times(3-1)\times\cdots\times(n-1)=1\cdot 2\cdots (n-1)=(n-1)!.\]
  4. 反过来，任何一棵 \([n]\) 上的递增树都能由这套插入过程唯一地重建（先去掉号码最大的顶点 \(n\)，它必是叶子，得到 \([n-1]\) 上的递增树，如此回溯），所以这种数法不重不漏。♦
例（用公式验算小数据）
  1. \(n=1\)：\((1-1)!=0!=1\)。只有孤零零一个顶点 \(1\)，确实 \(1\) 棵。
  2. \(n=2\)：\((2-1)!=1!=1\)。只能是 \(1\) 在上、\(2\) 在下的链，\(1\) 棵，对。
  3. \(n=3\)：\((3-1)!=2!=2\)。与上面手数的 \(2\) 棵一致。
  4. \(n=4\)：\((4-1)!=3!=6\)。按插入法看：加 \(2\) 有 \(1\) 种，加 \(3\) 有 \(2\) 种，加 \(4\) 有 \(3\) 种，\(1\cdot2\cdot3=6\)。
已有递增树 1→2→3，插入最大号 4：可挂到 1、2、3 任一个下面（共 3 种） 1 2 3 4 挂到 1 下 1 2 3 4 挂到 2 下 1 2 3 4 挂到 3 下
插入证明的核心一步：新顶点 \(4\) 是最大号，挂到任何已有顶点下都不破坏递增，故有“已有顶点个数 = 3”种挂法。

5.3.4　对照：自由标号要多得多

把上面的结果和自由标号情形并排放，能更直观地看出“限制标号”带来的差别。按 5.2 节，顶点集为 \([n]\) 的有根有标号树共有 \(n^{\,n-1}\) 棵（凯莱公式 Cayley's formula 的有根版本）。而递增树只有 \((n-1)!\) 棵。下表把两者列出来。

\(n\) 自由 \(n^{n-1}\) 递增 \((n-1)!\) 221 392 4646 562524
同样的顶点集 \([n]\)，加上“父亲 \(<\) 儿子”这条限制后，合法的树锐减：从 \(n^{n-1}\) 降到 \((n-1)!\)。这正是“顶点不可自由标号”带来的效果。
即时自测
  1. 顶点集为 \([5]\) 的递增树有几棵？请直接用公式 (5.6) 给出。
  2. 在 \([4]\) 的递增树里，号码 \(4\) 一定是叶子吗？请说明理由。
  3. 形状固定为一条“竖链”（每个顶点至多一个儿子）的 \([n]\) 上的树，有多少棵是递增树？（提示：竖链上的号码从根到底必须严格递增，这唯一地决定了一种排法。）

返回 全书目录