5.10　习题解答Solutions to exercises

本页为译文 + 高中讲解合一：黑色正文为对原书每道解答的忠实翻译；彩色框（目标 / 例 / 分步推演）与配图为面向高中生的详解，把原书省略的步骤补全、举具体数字例子、必要时画图，全程不用比喻。

题 1　度数相同的两个顶点（鸽笼原理）

设 \(G\) 有 \(n\) 个顶点。若 \(G\) 含有一个孤立顶点（isolated vertex，度数为 \(0\) 的顶点），那么 \(G\) 中的最大度数至多为 \(n-2\)，也就是说各顶点可能的度数只能取 \(0,1,\dots,n-2\)。这一共是 \(n-1\) 种可能，故由鸽笼原理（pigeonhole principle）即得结论。

若 \(G\) 没有孤立顶点，则各顶点可能的度数为 \(1,2,\dots,n-1\)，同样是 \(n-1\) 种可能，按上面同样的方式得出结论。

1. 简单图（无重边、无自环）里，一个顶点最多和其余 \(n-1\) 个顶点各连一条边，故度数范围本来是 \(0,1,\dots,n-1\)，共 \(n\) 种。光这样还不够——\(n\) 只鸽子放进 \(n\) 个笼子未必撞车。
2. 关键观察：\(0\) 与 \(n-1\) 不能同时出现。若某顶点度数为 \(n-1\)，它和所有别的点都相连，那就没有点是孤立的（度数 \(0\)）；反之若有孤立点，就没有点能达到度数 \(n-1\)。
3. 于是真正可用的度数取值只有 \(n-1\) 种：要么是 \(\{0,1,\dots,n-2\}\)（有孤立点时），要么是 \(\{1,2,\dots,n-1\}\)（无孤立点时）。
4. \(n\) 个顶点取 \(n-1\) 种度数值，鸽笼原理保证至少两个顶点取到相同度数。♦

题 2　任何途径都含一条路（删环法）

设 \(W\) 是从 \(x\) 到 \(y\) 的一条途径（walk）。若 \(W\) 本身已是一条路（path，即顶点互不重复），则证毕。否则，\(W\) 中至少有一个顶点出现了至少两次。设 \(z\) 是第一个这样的顶点。那么把 \(W\) 中介于 \(z\) 的第一次出现与第二次出现之间的那一段删去，得到新的途径 \(W'\)，它仍然连接 \(x\) 与 \(y\)。现在对 \(W'\) 重复同样的操作，并一直做下去。这个过程最终必然停止，因为每一步都使 \(W\) 中的边数减少。当过程停止时，不再有重复的顶点，于是我们得到了一条从 \(x\) 到 \(y\) 的路。

1. 把途径写成顶点序列，例如 \(W:\ x=v_0,v_1,\dots,v_m=y\)。
2. 若某个顶点 \(z\) 在第 \(i\) 位和第 \(j\) 位重复出现（\(i<j\)），那么 \(v_i=v_j=z\)，中间这段 \(v_i\to v_{i+1}\to\dots\to v_j\) 是绕回到 \(z\) 的一圈。
3. 把这一圈整段删掉，接口处直接由 \(v_i\) 跳到 \(v_{j+1}\)（它们本来就相邻，因为 \(v_j=z=v_i\)）。新途径仍从 \(x\) 到 \(y\)，但边数严格变少。
4. 边数是非负整数，不能无限减小，所以过程必停。停下来时没有重复顶点，即得一条路。♦

题 3　树 ⇔ 任意两点间恰有一条路

若 \(G\) 是树（tree），则它是连通的，故 \(x\) 与 \(y\) 之间至少有一条路。倘若有两条，记为 \(p\) 与 \(p'\)，那么这两条路的对称差（symmetric difference）将含有一个圈。（如果你忘了：两个集合的对称差，是恰好属于其中一个集合的元素构成的集合。）事实上，这个对称差的每个连通分支都是一个各顶点度数均为 \(2\) 的图，而这样的图就是一个圈。

反过来，若 \(G\) 具有所述性质（任意两点间恰有一条路），则 \(G\) 是连通且无圈的——因为若它含有一个圈，那么该圈上任意两点之间就会有两条路。因此 \(G\) 是树。

1. 正向，至少一条：树的定义里包含连通，连通就保证任意两点有路。
2. 正向，至多一条：假设有两条不同的路 \(p,p'\)。把它们的边集做对称差（即只留下"只在其中一条路里出现"的边）。在对称差里，每个点的度数要么 \(0\) 要么 \(2\)：因为在每条路里点的度数 \(\le 2\)，两条路在公共边上抵消。度数全为 \(2\) 的非空图必含圈。但树无圈，矛盾，所以至多一条。
3. 反向："恰一条"先给出"至少一条"，即连通。再证无圈：若有圈 \(C\)，取圈上两点，沿圈两个方向走是两条不同的路，与"恰一条"矛盾。连通+无圈=树。♦

题 4　树上"到 \(v\) 最近的点"唯一

用反证法证明：假设相反，即在 \(P\) 上存在两个离 \(v\) 最近的顶点 \(x\) 与 \(y\)，设它们到 \(v\) 的距离都是 \(d\)。那么从 \(v\) 到 \(x\) 就会有两条路：一条是长度为 \(d\) 的最短路；另一条是长度为 \(d+k\) 的路——它先从 \(v\) 走到 \(y\)，再沿 \(P\) 从 \(y\) 走到 \(x\)。（为什么这是一条路？请读者思考。）这与我们在上一题中证明的树的性质（任意两点间恰有一条路）相矛盾。

1. 反设有两个最近点 \(x,y\)，距离都为 \(d\)。设它们沿 \(P\) 相隔 \(k\) 步（\(k\ge 1\)）。
2. 路一：\(v\to x\) 的最短路，长 \(d\)。
3. 路二：\(v\to y\)（长 \(d\)）再沿 \(P\) 从 \(y\to x\)（长 \(k\)），合起来长 \(d+k\)。要确认这"真是一条路"（顶点不重复），需要用到 \(P\) 是路、且 \(v\) 到 \(P\) 的接法不制造重复——这就是原文留给读者的小思考。
4. 两条长度不同（\(d\ne d+k\)）故是两条不同的路，违反题 3。所以最近点只能有一个。♦

题 5　不同构的 10 顶点树有很多

\(10\) 个有标号顶点上共有 \(10^8\) 棵树。其中每一棵至多与另外 \(10!<3.7\cdot10^6\) 棵同构（把树本身固定，对标号做置换即可得到与它同构的所有树）。因此由鸽笼原理即得结论。

1. Cayley 公式：\(n\) 个有标号顶点上的树有 \(n^{n-2}\) 棵。取 \(n=10\) 得 \(10^8\)。
2. 给定一棵无标号树（一种形状），给它的 \(10\) 个顶点贴标号，最多 \(10!\) 种贴法，所以一个形状最多对应 \(10!\) 棵有标号树（若该形状有对称性，对应数还更少）。
3. 于是 (无标号树数) \(\times\,10!\ \ge\ 10^8\)，即无标号树数 \(\ \ge\ \dfrac{10^8}{10!}=\dfrac{10^8}{3628800}\approx 27.6\)。
4. 所以至少有 \(28\) 棵互不同构的 10 顶点树（实际数目是 \(106\)，鸽笼只给出一个下界）。♦

题 6　一个停车函数变体仍是 \(n^{n-1}\)

这与定理 5.24 的证明类似。我们仍可使用环形停车场（circular parking lot）。第一辆车的偏好车位可以是 \([n+1]\) 中的任意一个，但其后每一辆车的偏好车位都只有 \(n\) 种可能（除去前一辆车的偏好车位之外的所有车位）。因此，偏好集合共有 \((n+1)n^{n-1}\) 种，并且其中 \(1/(n+1)\) 会导致停车函数（parking function）。故答案为 \(n^{n-1}\)。

1. 统计本题这类偏好的总数：第一辆车自由选 \(n+1\) 选项；从第二辆起，每辆车避开"前一辆的偏好位"，各有 \(n\) 个选项。共 \((n+1)\cdot n\cdot n\cdots n=(n+1)n^{n-1}\)。
2. 用环形停车场论证：每种偏好在环上恰留一个空位，且由旋转对称，空位落在 \(n+1\) 个位置中每一个的概率相等，即占总数的 \(1/(n+1)\)。
3. 合法（线性可停）当且仅当空位是第 \(n+1\) 个虚拟位。于是答案 \(=(n+1)n^{n-1}\cdot\dfrac{1}{n+1}=n^{n-1}\)。♦

题 7　失败停车尝试总数（归纳）

对 \(n\) 作归纳。当 \(n=1\) 时命题显然成立。假设对 \(n-1\) 已知命题成立，并对 \(n\) 来证。设 \(f\) 是 \([n]\) 上的停车函数。设 \(i\) 是按 \(f\) 执行停车过程时最终停在第 \(n\) 号车位的那辆车。

那么，去掉车 \(i\)、它的偏好以及最后一个车位，我们得到 \([n-1]\) 上的一个停车函数 \(f'\)，对它归纳假设成立。也就是说，除 \(i\) 之外所有车的失败停车尝试次数之和为 \(\binom{n}{2}-\sum_{j\ne i}f(j)\)。若 \(f(i)=a\)，则车 \(i\) 恰好经历了 \(n-a\) 次失败的停车尝试。把它加到前面的表达式上，结论即证。

1. 找到最终停在最后一格（第 \(n\) 格）的车 \(i\)。把它、它的偏好、第 \(n\) 格一并删掉，其余 \(n-1\) 辆车在 \(1\dots n-1\) 格上的停法不受影响，构成 \([n-1]\) 上的停车函数 \(f'\)，其中 \(f'(j)=f(j)\)。
2. 归纳假设：这 \(n-1\) 辆车（除 \(i\)）失败次数之和 \(=\binom{n-1}{2}-\big(\sum_{j\ne i}f(j)-(n-1)\big)=\binom{n}{2}-\sum_{j\ne i}f(j)\)（用 \(\binom{n-1}{2}+(n-1)=\binom{n}{2}\)）。
3. 车 \(i\) 偏好 \(a=f(i)\)，最终停第 \(n\) 格，沿途被占了 \(n-a\) 个位置，故它失败 \(n-a\) 次。
4. 总和 \(=\big[\binom{n}{2}-\sum_{j\ne i}f(j)\big]+(n-a)=\binom{n}{2}+n-\sum_{i}f(i)=\binom{n+1}{2}-\sum_i f(i)\)，与对 \(n\) 的命题一致。♦

题 8　树的有序度数序列特征化

为解决这个枚举问题，我们首先刻画可能的有序度数序列。我们断言：当 \(n\ge2\) 时，序列 \(d_1\ge d_2\ge\dots\ge d_n\ge0\) 是某棵树的（有序）度数序列，当且仅当

(a) \(\displaystyle\sum_{i=1}^n d_i=2n-2\)，且
(b) \(d_{n-1}=d_n=1\)。

一方面，两个条件都是必要的。事实上，第一个条件等价于该图有 \(n-1\) 条边；而若第二个条件不成立，就会有 \(d_i\ge2\) 对所有 \(i\le n-1\) 成立，导致 \(\sum_{i=1}^n d_i\ge 2n-1\)，与树只有 \(n-1\) 条边矛盾。

为证明两个条件合在一起也是充分的，我们对 \(n\) 作归纳。若 \(n=1\)（原文按 \(n=2\) 起步），条件只允许 \(d_1=d_2=1\)，确实存在具有该有序度数序列的树。假设命题对 \(n-1\) 成立，对 \(n\) 来证。

设 \(S=d_1\ge d_2\ge\dots\ge d_n\) 是任意一个被允许的序列，\(n\ge3\)。则序列中存在某个 \(d_i>1\)。选取最后一个这样的 \(d_i\)。现在从序列中去掉 \(d_n\)，并把 \(d_i\) 减 \(1\)。则所得序列 \(S'\) 满足 \(n-1\) 情形的两个条件（元素之和为 \(2n-4\)，且全为正，故最后两个必为 \(1\)）；因此归纳假设适用。也就是说，存在 \(n-1\) 个顶点上的树，其有序度数序列为 \(S'\)。再添加一个新顶点，把它连到对应于 \(d_i\) 的那个顶点上，便得到有序度数序列为 \(S\) 的树。这就完成了对允许序列的刻画。

当 \(n\ge3\) 时，它们的个数等于把 \(2n-4\) 分拆为 \(n-2\) 个部分的分拆数（因为第 \((n-1)\) 个和第 \(n\) 个部分必为 \(1\)）。

1. 必要性 (a)：每条边贡献给两个端点各 \(1\) 度，故 \(\sum d_i=2|E|=2(n-1)\)。
2. 必要性 (b)：若最后两位不全是 \(1\)，则至少 \(d_1,\dots,d_{n-1}\) 都 \(\ge2\)，再加 \(d_n\ge1\)，和 \(\ge 2(n-1)+1=2n-1>2n-2\)，矛盾。
3. 充分性（构造）：取最后一个 \(>1\) 的位置 \(d_i\)，删去末尾的叶子 \(d_n=1\) 并把 \(d_i\) 减 \(1\)。新序列和为 \((2n-2)-1-1=2n-4\)，满足 \(n-1\) 情形。归纳得树后，挂一片新叶子到 \(d_i\) 对应顶点，度数恢复，得到序列 \(S\) 的树。
4. 计数：固定末两位为 \(1\) 后，前 \(n-2\) 位是把 \((2n-2)-2=2n-4\) 写成 \(n-2\) 个 \(\ge1\) 的不增整数之和——这恰是 \(2n-4\) 分拆成 \(n-2\) 个部分的分拆数。♦

题 9　\(k\)-缩短停车函数的特征与计数

(a) 这与停车函数的情形类似。粗略地说，麻烦出在太多车都偏好高编号车位时。若有不止一辆车想要最后一个车位，或更一般地，对某个 \(j\in[n-k+1]\)，有超过 \(j\) 辆车想要落在最后 \(j\) 个车位之中，过程就会失败。（只有 \(n-k+1\) 辆车，所以无需考虑更大的 \(j\)。）

我们断言：若对每个 \(j\in[n-k+1]\)，至多有 \(j\) 辆车想停在最后 \(j\) 个车位之一，则 \(f\) 是一个 \(k\)-缩短停车函数（\(k\)-shortened parking function）。请读者自行证明此断言（重温引理 5.23 的证明会有帮助）。注意差别在于对 \(j\) 的条件更弱：这里只需对所有 \(j\in[n-k+1]\) 成立，而非所有 \(j\in[n]\)。另一种等价表述是：把 \(f(1),\dots,f(n-k+1)\) 的值按不减重排得到向量 \((a_1,\dots,a_{n-k+1})\)，则其充要条件为该向量逐坐标 \(\le(k,k+1,\dots,n)\)。

(b) 再次考虑定理 5.24 证明中的环形停车场。我们有 \(n+k-1\) 辆车，它们的偏好取自 \([n+1]\)，故将有 \(k\) 个车位空着。若其中一个空位是车位 \(n+1\)，则 \(f\) 是 \(k\)-缩短停车函数。我们断言这种情况在所有情形中占 \(k/(n+1)\)。

事实上，设 \(v=(f(1),\dots,f(n-k+1))\) 是任意函数 \(f:[n-k+1]\to[n+1]\) 的取值向量。对 \(i\in[n]\)，定义 \(v_i=(f(1)+i,\dots,f(n-k+1)+i)\)，其中加法是模 \(n+1\) 的。即 \(v_i\) 是 \(v\) 的环形平移。则在 \(n+1\) 个向量 \(v_i\) 中，恰有 \(k\) 个不含坐标 \(n+1\)，因为恰有 \(k\) 个环形旋转把 \(n+1\) 移到 \(v\) 中未出现的那 \(k\) 个空位之一。这就证明了断言。

由于所有函数 \(f:[n-k+1]\to[n+1]\) 的个数显然是 \((n+1)^{n-k+1}\)，故 \(k\)-缩短停车函数 \(f:[n-k+1]\to[n]\) 的个数为 \(k(n+1)^{n-k}\)。

1. (a) 充要条件：停车成功 ⇔ 不出现"挤兑高位车位"。把偏好排序成不减向量 \((a_1,\dots,a_{n-k+1})\)，条件就是逐项 \(a_t\le k+t-1\)，即 \(\le(k,k+1,\dots,n)\)。
2. (b) 总数：把偏好放宽到 \([n+1]\)、车数补到 \(n+k-1\) 辆（环形版），总函数数 \((n+1)^{n-k+1}\)。
3. 旋转计数：把一个偏好向量 \(v\) 做 \(n+1\) 个环形平移 \(v_0,\dots,v_n\)。它们一起恰好"避开"\(n+1\) 这个坐标的有 \(k\) 个（因为 \(v\) 在 \([n+1]\) 中漏掉 \(k\) 个值，把 \(n+1\) 旋进这 \(k\) 个空位之一就成功）。故成功比例 \(=k/(n+1)\)。
4. 因此 \(k\)-缩短停车函数数 \(=(n+1)^{n-k+1}\cdot\dfrac{k}{n+1}=k(n+1)^{n-k}\)。♦

题 10　恰有 \(k\) 个值等于 \(1\) 的停车函数 \(P(n,k)\)

首先选出 \(k\) 个值等于 \(1\) 的位置，这可以用 \(\binom{n}{k}\) 种方式完成。对于剩下的 \(n-k\) 个位置，我们需要这样的取值：它们按不减重排得到的向量 \((b_1,b_2,\dots,b_{n-k})\) 各坐标都大于 \(1\)，并且逐坐标小于 \((k+1,k+2,\dots,n)\)。等价地，向量 \((b_1-1,\dots,b_{n-k}-1)\) 的各坐标必须是正整数且逐坐标小于 \((k,k+1,\dots,n-1)\)。换句话说，它必须是某个 \(k\)-缩短停车函数 \(f:[n-k]\to[n-1]\) 的不减重排。由上一题 (b) 我们知道这有 \(k\,n^{n-1-k}\) 种方式。因此

1. 选位置：\(\binom nk\)。
2. 其余值排序后逐项 \(>1\) 且 \(<(k+1,\dots,n)\)；整体减 \(1\) 后即逐项 \(\ge1\) 且 \(<(k,\dots,n-1)\)，这正是题 9 里 "\(f:[n-k]\to[n-1]\) 的 \(k\)-缩短停车函数"。
3. 题 9(b) 把 \(n\mapsto n-1,\,n-k+1\mapsto n-k\) 代入得 \(k\,(n-1+1)^{(n-1)-k}=k\,n^{n-1-k}\)。
4. 相乘并用恒等式 \(\binom nk k=\binom{n-1}{k-1}n\)：得 \(P(n,k)=\binom nk k\,n^{n-1-k}=\binom{n-1}{k-1}n^{n-k}\)。♦

题 11　停车函数分解为素停车函数

设 \(p\) 是 \([n]\) 上的停车函数。找出最小的 \(a_1\)，使得 \(p\) 中恰有 \(a_1\) 个值是 \([a_1]\) 的元素——也就是使停车函数条件"恰好绷紧"地被满足的最小 \(a_1\)。若不存在这样的 \(a_1\)，则 \(p\) 是素的（prime），命题成立（\(k=1\)）。否则，有 \(a_1\) 辆车的偏好落在 \([a_1]\) 之内，它们的偏好构成 \([a_1]\) 上的一个停车函数。设 \(s_1\) 为这些车的集合，\(p_1\) 为它们确定的停车函数。则 \(p_1\) 是素的，因为 \(a_1\) 是使停车条件绷紧成立的最小整数，故可从 \(p_1\) 中省去 \(a_1\)（不再有更小的绷紧点）。

然后迭代此过程：从 \(p\) 的所有剩余值中减去 \(a_1\)，得到 \([n-a_1]\) 上的停车函数 \(p'\)。再次寻找最小的 \(a_2\)，使 \(p'\) 中恰有 \(a_2\) 个值落在 \([a_2]\) 中，依此类推。当得到一个素停车函数时过程停止；那个函数就是 \(p_k\)。

例如，若 \(p=(1,7,1,6,2,1,4,7,7)\)，则 \(a_1=5\)。\(p\) 中取自 \([5]\) 的值位于第 \(1,3,5,6,7\) 位，故 \(s_1=\{1,3,5,6,7\}\)，\(p_1=(1,1,2,1,4)\)。这样剩下 \(p'=(2,1,2,2)\)，得 \(a_2=1\)。于是 \(p_2=(1)\)，\(s_2=\{4\}\)（因为 \(p'\) 的第二个值原本是 \(p\) 的第四个值）。这又剩下 \(p''=(1,1,1)\)，它是素停车函数。所以我们得到的分解为

为了从分解 \((p_1,p_2,\dots,p_k,s_1,s_2,\dots,s_k)\) 恢复原停车函数 \(p\)，只需把 \(p_i\) 的各值放回 \(s_i\) 指定的位置，然后给 \(p_i\) 的每个值加上 \(|s_1|+|s_2|+\dots+|s_{i-1}|\)。

1. 找首块：在 \(p=(1,7,1,6,2,1,4,7,7)\) 中数有多少个值 \(\le a\)。\(a=1\):有3个>1，绷紧需正好1个，不绷紧…逐个试到 \(a=5\)：值 \(\le5\) 的恰有 5 个（位置 1,3,5,6,7，值 1,1,2,1,4），第一次绷紧，故 \(a_1=5\)。
2. 取出 \(p_1\)：这 5 个值按原顺序为 \((1,1,2,1,4)\)，它是 \([5]\) 上的素停车函数；记录位置 \(s_1=\{1,3,5,6,7\}\)。
3. 剩余平移：其余值（位置 2,4,8,9 的 \(7,6,7,7\)）减去 \(a_1=5\) 得 \(p'=(2,1,2,2)\)。再找绷紧点：\(a=1\) 时恰 1 个值 \(\le1\)（那个 \(1\)），故 \(a_2=1\)，\(p_2=(1)\)，对应原位置 \(s_2=\{4\}\)。
4. 余下 \(p''=(1,1,1)\) 已是素停车函数 \(p_3\)，位置 \(s_3=\{2,8,9\}\)。分解完成。
5. 逆操作：把 \(p_i\) 填回 \(s_i\)，并给 \(p_i\) 各值加 \(|s_1|+\dots+|s_{i-1}|\)。例如 \(p_2=(1)\) 加 \(|s_1|=5\) 回到 \(6\)，放到位置 4——正是原来的 \(p(4)=6\)。♦

题 12　\(PP(n+1,k+1)=\frac{n+1}{k+1}P(n,k)\)

取一个被 \(P(n,k)\) 计数的函数，在它的 \(n\) 个值中任意一个之后、或在最前面，插入一个 \(1\)。所得是 \([n+1]\) 上的一个素停车函数，含有 \(k+1\) 个等于 \(1\) 的值，因而是被 \(PP(n+1,k+1)\) 计数的函数。每个这样的函数会被得到 \(k+1\) 次，因为它的每个等于 \(1\) 的项都可能是刚才插入的那个 \(1\)。这表明

1. 构造映射：给一个 \(P(n,k)\) 的函数（长度 \(n\)，\(k\) 个 1），在 \(n+1\) 个缝隙（含最前）之一插入一个新的 \(1\)，得长度 \(n+1\)、含 \(k+1\) 个 1 的函数。可证它一定是素的。
2. 数清重复：反过来，一个目标素停车函数有 \(k+1\) 个 1，删掉其中任意一个 1 都能还原成原函数，故每个目标被映到 \(k+1\) 次。
3. 计数等式：左边（带插入位置）总数 \(=(n+1)\cdot P(n,k)\)，每个目标重复 \(k+1\) 次，故 \(PP(n+1,k+1)=\dfrac{(n+1)P(n,k)}{k+1}\)。♦

题 13　素停车函数总数 \(PP(n+1)=n^n\)

\([n+1]\) 上的素停车函数必须有至少 \(2\) 个、至多 \(n+1\) 个值等于 \(1\)。利用上一题的结果以及题 10 的结果，得到

两边同除以 \(n^{n-1}\)，得到恒等式

第 1 章习题 28 表明右边等于 \(n\)，于是结论得证。

1. 求和上下限：素停车函数至少 2 个 1（否则只 1 个 1，去掉它剩的是更短停车函数，不素），至多 \(n+1\) 个 1（全 1）。对应 \(k+1\) 从 2 到 \(n+1\)，即 \(k=1,\dots,n\)。
2. 代入题 12、题 10：\(PP(n+1,k+1)=\dfrac{n+1}{k+1}P(n,k)\)，\(P(n,k)=\binom{n-1}{k-1}n^{n-k}\)。
3. 化简系数：\(\dfrac{n+1}{k+1}\binom{n-1}{k-1}=k\binom{n+1}{k+1}\cdot\dfrac1n\)（用 \(\binom{n+1}{k+1}=\frac{n+1}{k+1}\binom{n}{k}\) 与 \(\binom nk=\frac nk\binom{n-1}{k-1}\)），得每项 \(k\binom{n+1}{k+1}n^{n-k-1}\)。
4. 归一化：除以 \(n^{n-1}\) 得 \(\sum_{k=1}^n \frac{k}{n^k}\binom{n+1}{k+1}\)；第 1 章习题 28 给出此和 \(=n\)。故 \(PP(n+1)=n^n\)。♦

题 14　停车函数的生成函数（复合公式）

我们已经看到，每个停车函数都可以分解为若干素停车函数的有序分拆（ordered partition）。因此复合公式（compositional formula，定理 3.36）适用，其中

1. 题 11：每个停车函数唯一对应一串（有序的）素停车函数块。
2. "有序序列"这个外结构：长度为 \(k\) 的序列有 \(k!\) 种排法？不——这里外结构每种大小 \(k\) 的"序列骨架"权重为 \(k!\) 体现"块的次序"，其 EGF 为 \(B(x)=\sum_{k\ge0}k!\frac{x^k}{k!}=\sum_{k\ge0}x^k=\frac1{1-x}\)。
3. 把素停车函数的 EGF 代入 \(B\)，即用 \(H(x)=B(A(x))=\dfrac1{1-A(x)}\) 得到全体停车函数的指数生成函数。♦

题 15　小 \(n\) 的无标号树数 \(u(n)\)

对 \(n\le3\)，\(n\) 个顶点上只有一棵无标号树，即 \(n\) 个顶点上的路。对 \(n=4\)，要么有一个度数为 \(3\) 的顶点（得到星形 star），要么没有（得到路）。故 \(u(4)=2\)。当 \(n=5\) 时，最大度数可以是 \(4\)（得星形）、\(3\)（得在某片叶子上加一条边的星形）、或 \(2\)（得路）。故 \(u(5)=3\)。

当 \(n=6\) 时，最大度数为 \(5\)、\(4\) 或 \(2\) 的情形同上各只有一种。然而当最大度数为 \(3\) 时有若干可能：要么有两个度数为 \(3\) 的顶点（得到图 5.48 左侧的树），要么只有一个这样的顶点（得到图 5.48 右侧与底部的树——其一中，未与度数为 \(3\) 的顶点 \(A\) 相连的两个新顶点都与 \(A\) 距离为 \(2\)；另一中，其一与 \(A\) 距离为 \(2\)，另一与 \(A\) 距离为 \(3\)）。因此 \(u(6)=6\)。

题 16　三个图的自同构群大小

我们请读者验证：图 \(G\) 中心的那个顶点必须被每个自同构映到自身（它是唯一度数为 \(6\) 的顶点，而同构保持度数）。之后剩余顶点的任意置换都是自同构。因此 \(G\) 有 \(6!=720\) 个自同构。

在 \(H\) 中，两个度数为 \(3\) 的顶点可以互换，两个度数为 \(2\) 的顶点也可以互换，故 \(|\mathrm{Aut}(H)|=4\)。

最后，在 \(J\) 中，设 \(A\) 与 \(B\) 是两个相邻顶点。则对任意自同构 \(f\)，\(f(A)\) 与 \(f(B)\) 必相邻。我们有 \(5\) 种方式选 \(A\) 的像，之后有 \(2\) 种方式选 \(B\) 的像，此后便别无选择。因此 \(J\) 有 \(10\) 个自同构。

1. \(G\)（中心度 6 的星形 \(K_{1,6}\)）：唯一的 6 度中心必须固定不动，6 片叶子地位完全对称、可任意置换，故 \(|\mathrm{Aut}(G)|=6!=720\)。
2. \(H\)：两 3 度点可互换或不换（2 种），两 2 度点可互换或不换（2 种），其余被这两组的选择牵制，故 \(2\times2=4\)。
3. \(J\)（其自同构群为二面体型、阶为 10，例如 \(5\)-圈 \(C_5\)）："边映到边"。固定一条边 \(AB\)：\(A\) 的像有 5 种选法、与之相邻的 \(B\) 的像有 2 种选法，之后整个图被刚性确定。故 \(5\times2=10\)。♦

题 17　存在没有非平凡自同构的图

由定理 5.7，这等价于寻找一个 \(6\) 个顶点、只有一个自同构（平凡自同构）的图。图 5.49 给出了这样一个图。

1. 要让自同构只能是恒等：让每个顶点都能被"度数 + 邻居的度数"唯一辨认出来。
2. 图 5.49 中各点度数与局部结构互不相同，于是任何保持相邻关系的双射只能把每个点映到自己。
3. 故 \(|\mathrm{Aut}|=1\)，由定理 5.7 即得所需结论。♦

题 18　排列与递减树的双射

我们构造一个从 \(S_n\) 到 \(n+1\) 个顶点上的递减树（decreasing tree）集合 \(M_n\) 的双射 \(f\)。设 \(p\in S_n\)，\(p=p_1p_2\cdots p_n\)。每个项 \(p_i\) 对应 \(f(p)\) 的一个顶点。对应于 \(p_i\) 的顶点的唯一父亲，是对应于 \(p_j\) 的顶点，其中 \(p_j\) 是 \(p_i\) 左侧、满足 \(p_j>p_i\) 的最靠右的项。若不存在这样的项 \(p_j\)，则 \(p_i\) 的父亲是额外的顶点 \(n+1\)。例如图 5.47 左侧是 \(f(34251)\)，右侧是 \(f(23514)\)。

首先，\(f(p)\in M_n\)，因为我们的定义产生了所得树的一个递减标号。下面通过给出 \(f\) 的逆映射来证明它是双射。设 \(M\in M_n\)。则 \(f\) 的定义意味着根顶点 \(n+1\) 的孩子必为 \(p\) 的从左到右极大元（left-to-right maxima），因为它们正是那些大于其右边一切元素的项，因而对这些项找不到父亲 \(p_j\)。所以若 \(f(p)=M\)，我们就能从 \(M\) 读出 \(p\) 的从左到右极大元集合。由于排列的从左到右极大元构成一个递增序列，我们也知道它们的次序。设这些极大元为 \(m_1<m_2<\dots<m_k\)。则 \(M\) 中以 \(m_i\) 为根的子树，通过反复应用此论证，唯一地描述了 \(p\) 中从 \(m_i\) 开始、到 \(m_{i+1}\) 紧前结束的那段。

1. 由排列造树：把根标成 \(n+1\)。对每个 \(p_i\)，向左找第一个比它大的 \(p_j\) 当父亲；找不到就挂到根。父亲总比孩子大 ⇒ 树递减。
2. 例 \(p=34251\)：\(3\) 左无更大→父=6；\(4\) 左无更大→父=6；\(2\) 左最近更大者是 \(4\)→父=4；\(5\) 左无更大→父=6；\(1\) 左最近更大者是 \(5\)？不，\(5\) 在 \(2\) 之后、\(1\) 之前，\(1\) 左边最近的更大者是 \(5\)→父=5。逐一连边得上图同构结构。
3. 逆映射（造排列）：根的孩子恰是从左到右极大元，按值递增排好；每棵子树递归还原对应的子段，拼起来唯一恢复 \(p\)。
4. 有逆映射 ⇒ \(f\) 是双射。♦

题 19　按从左到右极大元个数计数

上一题我们已看到，"有 \(k\) 个从左到右极大元的 \(n\)-排列"集合与"我们这类树（指定根孩子数 \(=k\)）"集合之间存在双射。由于前者的个数依转移引理（transition lemma）为无符号第一类 Stirling 数 \(c(n,k)\)，故后者的个数也是 \(c(n,k)\)。

1. 题 18 的双射里，根 \(n+1\) 的孩子 = 排列的从左到右极大元，故"根有 \(k\) 个孩子的递减树"↔"有 \(k\) 个极大元的排列"。
2. 转移引理给出后者个数 \(=c(n,k)\)。
3. 双射保数 ⇒ 这类树也有 \(c(n,k)\) 个。♦

题 20　132-避免排列与有根平面树

(a) 一个 132-避免排列（132-avoiding permutation）\(p\) 可以切成若干块，使得每个给定块中的每个项都大于该块右侧的所有项。例如 \(78453612\) 可切成 \(78\,|\,4536\,|\,12\)。一般地，第一刀紧接在最大项的右侧落下，然后向右递归进行。若 \(p\) 以其最大项结尾，则 \(p\) 就是一整块。

沿着定理 5.28 的证明思路，一个归纳证明现在是直接的，其中以 \(n\) 结尾的排列对应于根只有一个孩子的树。

(b) (a) 部分的双射依然有效。这可由归纳看出：有根平面树的叶子数，恰是根的各子树叶子数之和；类似地，132-避免排列的从左到右极小元数，恰是各块的从左到右极小元数之和。

1. 切块：找到最大项 \(n\)，紧跟其后切第一刀。块内所有数都比右边大（否则会和右边的小数、中数凑出 132）。对右段递归切。
2. 例 \(78453612\)：最大项 \(8\) 在第 2 位，第一刀切出 \(78\)；右段 \(453612\) 最大项 \(6\) 在第 4 位（相对），切出 \(4536\)；再剩 \(12\)。得 \(78|4536|12\)。
3. 对树：把每块递归地变成根的一棵子树；"以 \(n\) 结尾"⇔"\(p\) 是单块"⇔"根只有一个孩子"。这给出与有根平面树的双射（Catalan）。
4. (b) 统计量匹配：叶子数 = 子树叶子数之和；左到右极小元数 = 各块极小元数之和。归纳即知两个统计量在双射下对应。♦

题 21　132-避免排列与二叉平面树

132-避免排列的定义说：\(p\) 是 132-避免的，当且仅当不能在 \(p\) 中找到三个项 \(a,b,c\)，使 \(a\) 最靠左、\(c\) 最靠右、\(b\) 最大，同时 \(a<c\)。

这意味着，在 \(p\) 的二叉平面树 \(T(p)\) 中，\(T(L)\)（左子树）的所有项都必须大于 \(T(R)\)（右子树）的所有项。（否则，若项 \(a\) 与 \(c\) 违反此约束，则 \(a\,n\,c\) 就是一个 132-模式。）递归地，\(T(p)\) 的每个结点都必须满足这一点。也就是说，对 \(T(p)\) 的每个结点，其左子树中任意顶点的标号都必须大于其右子树中任意顶点的标号。

换句话说，一旦给定无标号树 \(T(p)\)，并知道 \(p\) 是 132-避免的，我们就能通过选取满足上述条件的标号来恢复 \(p\)。

更明确地说，假设我们已对少于 \(n\) 个顶点的二叉平面树定义了双射 \(f\)。设 \(T\) 是 \(n\) 个顶点的二叉平面树，左子树为 \(T_L\)、右子树为 \(T_R\)。那么我们定义 \(f(T)=f(T_L)\,n\,f(T_R)\)，其中 \(f(T_L)\) 是把它的每个项都加上 \(|T_R|\) 后得到的。

1. 必要性：若某结点处左子树有个标号 \(a\) 比右子树某标号 \(c\) 小（\(a<c\)），加上根（左右子树之间的那个更大的值 \(n'\)），\(a\,n'\,c\) 正是 132 模式，矛盾。
2. 充分性 / 重建：给定无标号二叉树形状，按"左大右小"规则唯一地填标号——根填当前最大值，左子树占据较大的一批标号、右子树占较小的一批，递归下去。
3. 递归式：\(f(T)=f(T_L)\,n\,f(T_R)\)，且把 \(f(T_L)\) 的每个值加 \(|T_R|\)（让左子树的值整体抬高到右子树之上）。这就是双射的显式形式。♦

题 22　下降数 ↔ 右边数，且对称

我们断言：对任意 \(n\)-排列 \(p\)，\(p\) 的下降（descent）个数等于 \(T(p)\) 的右边（right edges，指向右孩子的边）个数。此断言用归纳易证（观察 \(T(p)\) 的两棵子树）。于是本题结论是直接的，因为 \(T(p)\) 可以关于竖直轴做镜面反射。

1. 归纳证 "下降数 = 右边数"：根把 \(p\) 分成左、右两段；跨过根处是否构成下降，恰对应根是否有右孩子，子树内部用归纳假设。
2. 把二叉树 \(T(p)\) 左右镜像：左边变右边、右边变左边。于是"右边数 \(=k\) 的树"一一对应"右边数 \(=n-1-k\)（即左边数 \(=k\)）的树"。
3. 翻回排列语言：下降数为 \(k\) 的 132-避免排列数 = 下降数为 \(n-1-k\) 的同类排列数，得到对称分布。♦

题 23　下降与从左到右极小元（Narayana 数）

只要能证明"有 \(k-1\) 个下降的 132-避免排列"与"有 \(k\) 个从左到右极小元的同类排列"一样多，命题即获证。

我们断言甚至更强的结论成立：这两个排列集合不仅等势，而且是同一个集合。事实上，我们断言：若 \(p=p_1p_2\cdots p_n\) 是 132-避免的，则 \(p_i\) 是 \(p\) 的从左到右极小元（left-to-right minimum），当且仅当 \(i=1\) 或 \(i-1\) 是 \(p\) 的一个下降。换句话说，从左到右极小元正是各个下降的"终点"（当然还有最左端那一项）。

"仅当"部分是平凡的。要看"当"部分，反设其不然，即存在 \(j<i\) 使 \(p_j<p_i\)。那么 \(p_j\,p_{i-1}\,p_i\) 是一个 132-模式，矛盾。

图 5.50 展示了最近几道题中证明的所有双射。我们再次指出，这些集合中每一个的元素个数都是 Narayana 数

关于这些数的参考文献，见定理 5.29 之后的评注。

1. "仅当"（极小元 ⇒ 下降终点）：若 \(p_i\) 是极小元且 \(i>1\)，则 \(p_i<p_{i-1}\)，即 \(i-1\) 是下降。平凡。
2. "当"（下降终点 ⇒ 极小元）：设 \(i=1\) 或 \(p_{i-1}>p_i\)。若 \(p_i\) 不是极小元，存在更左的 \(p_j<p_i\)（\(j<i-1\)）。则 \(p_j<p_i<p_{i-1}\)，三项 \(p_j,p_{i-1},p_i\) 形成 "小-大-中" = 132 模式，与 132-避免矛盾。
3. 于是两个统计量逐个排列地相等：极小元个数 = 下降个数 + 1。图 5.50 把这些结构（二叉平面树的左/右边、平面树的叶/内点）串成一组双射，公共计数即 Narayana 数 \(N(n,k)=\frac1n\binom nk\binom n{k+1}\)。♦

题 24　某类函数 ↔ 有根森林

这些函数与 \([n]\) 上有 \(k\) 个分支（components）的有根森林（rooted forests）一一对应。因此由定理 5.19，它们的个数为

1. 建立题中函数与有根森林的双射（每个连通分支对应一棵有根树，根 = 该分支的特殊元素）。
2. 套用定理 5.19：\([n]\) 上有 \(k\) 个分支的有根森林数 \(=\binom nk\,k\,n^{n-1-k}\)。
3. 故所求函数数 \(=a_{n,k}\)。♦

题 25　生成多项式 \(A_n(x)=x(x+n)^{n-1}\)

由上一题的结果，可得 \(a_{n,k}=\binom{n-1}{k-1}n^{n-k}\)。因此由二项式定理，

1. 恒等式换形：\(\binom nk k=\binom{n-1}{k-1}n\)，故 \(a_{n,k}=\binom nk k\,n^{n-1-k}=\binom{n-1}{k-1}n^{n-k}\)。
2. 令 \(i=k-1\)（\(i=0\dots n-1\)）：\(A_n(x)=\sum_{i}\binom{n-1}{i}n^{(n-1)-i}\,x^{i+1}=x\sum_i\binom{n-1}{i}n^{(n-1)-i}x^i\)。
3. 括号里正是 \((x+n)^{n-1}\) 的二项展开（把 \(x\) 看作第一项、\(n\) 看作第二项）。故 \(A_n(x)=x(x+n)^{n-1}\)。♦

题 26　真着色 ↔ (着色, 无环定向)

若 \(g\) 是一个真着色（proper coloring），则它定义了 \(G\) 的唯一一个满足第二条件的定向 \(A\)（每条边都指向颜色较小的端点），且该定向自动是无环的（acyclic）。

反过来，若 \((g,A)\) 满足这些条件，则 \(g\) 是真着色，因为没有边的两端同色。对每个 \(g\)，恰有一个 \(A\) 使 \((g,A)\) 满足条件。这就双射地证明了我们的断言。

1. 正向：有了真着色 \(g\)，把每条边定向为"由大色端指向小色端"（颜色都不同，方向唯一确定）。沿任何有向路颜色严格递减，故不可能回到起点 ⇒ 无环。
2. 反向：给定满足条件的 \((g,A)\)：每条边两端颜色不同（因为有"指向较小色"这件事可言），故 \(g\) 真着色。
3. 一一对应：每个真着色 \(g\) 唯一决定一个这样的 \(A\)，反之亦然，故是双射。♦

题 27　色多项式取值的非负性

首先，\(n\) 与 \(m\) 是非负的，因为定理 5.46 蕴含当 \(n<0\) 时 \(\chi_G(n)\ne0\)。事实上，当 \(n>0\) 时 \(\bar\chi_G(n)\ge1\)，因为在寻找被 \(\bar\chi_G(n)\) 计数的着色时，我们总能把所有顶点染成同一种颜色。

其次，若 \(\chi_G(m)=0\)，则不存在仅用 \([m]\) 中颜色的 \(G\) 的真着色；但那样的话，当然也就不存在仅用 \([i]\) 中颜色（\(i\le m\)）的真着色了。

1. \(n<0\) 不为零：由定理 5.46（色多项式的组合互反律一类结果），\(\chi_G(n)\) 在负整数处与 \(\bar\chi_G\) 相关，而 \(\bar\chi_G(n)\ge1\)（"全染同色"总是一种方案），故 \(\chi_G(n)\ne0\)。所以零点只能落在非负整数。
2. 单调消失：若 \(m\) 种颜色都没法真着色（\(\chi_G(m)=0\)），那么颜色更少（\(i\le m\)）当然更不行，\(\chi_G(i)=0\)。♦

题 28　色多项式次高项系数 = \(-(\)边数\()\)

我们断言：顶点集为 \([m]\) 的简单图 \(G\) 的边数，等于 \(\chi_G\) 中 \(n^{m-1}\)（紧跟最高次项之后的那一项）系数的 \(-1\) 倍。我们用对边数的归纳来证明，工具是命题 5.40。

若 \(G\) 是空图（无边），则 \(\chi_G(n)=n^m\)，断言成立（次高项系数为 \(0\)，边数也为 \(0\)）。现在假设断言对有 \(k-1\) 条边的图成立，并设 \(G\) 有 \(k\) 条边。则命题 5.40 给出 \(\chi_G(n)=\chi_{G-e}(n)-\chi_{G/e}(n)\)。\(m-1\) 次项是 \(\chi_{G-e}(n)\) 中的第二项（次高项），按归纳假设其系数为 \(-(k-1)\)，但同时 \(m-1\) 次项也是 \(\chi_{G/e}(n)\) 中的最高次项（领项），其系数为 \(1\)（补充习题 26）。综合 \(\chi_G=\chi_{G-e}-\chi_{G/e}\)，左边 \(n^{m-1}\) 的系数为 \(-(k-1)-1=-k\)，正如所断言。

1. 基例：空图色多项式 \(n^m\)，次高项 \(n^{m-1}\) 系数为 \(0=-(\)边数 \(0)\)。
2. 归纳：设 \(G\) 有 \(k\) 条边，写 \(\chi_G=\chi_{G-e}-\chi_{G/e}\)。
3. \(\chi_{G-e}\)（\(m\) 顶点，\(k-1\) 边）的 \(n^{m-1}\) 系数 = \(-(k-1)\)（归纳假设）；最高项 \(n^m\) 系数 1。
4. \(\chi_{G/e}\)（\(m-1\) 顶点）的最高项就是 \(n^{m-1}\)，系数为 \(1\)（补充习题 26：色多项式领项系数恒为 1）。
5. 相减：\(n^{m-1}\) 系数 \(=-(k-1)-(+1)=-k\)。即次高项系数 \(=-k=-(\)边数\()\)。♦

题 29　连通图计数（减法原理）

(a) 以 \(k\) 为指标的被加项，计数的是 \([n]\) 上根落在大小为 \(k\) 的分支中的有根图（rooted graphs）。

(b) 右边以 \(k\) 为指标的被加项，是 \([n]\) 上根落在大小为 \(k\) 的分支中的有根图的个数。若 \(k<n\)，则该图不连通。把求和除以 \(n\)，将计数不连通的无根图；于是由减法原理（subtraction principle），命题得证。

1. (a) 解释求和：固定根所在分支大小为 \(k\)：先选这 \(k\) 个点（含根）、在其上放一个连通图、其余 \(n-k\) 点上放任意图，乘起来就是该被加项。对 \(k=1\dots n\) 求和 = 全部有根图。
2. (b) 去根：每个无根图有 \(n\) 种选根方式，故"有根图数 ÷ \(n\)"= 无根图数。
3. 分离连通：\(k=n\) 项对应根所在分支就是整个图 = 连通图；\(k<n\) 各项之和 = 不连通图。用减法 连通数 = (全部) − (不连通) 解出连通图数。♦

题 30　邻接矩阵的幂数途径

对 \(k\) 作归纳，并利用矩阵乘法的定义。

1. 基例 \(k=1\)：\(A^1\) 的 \((i,j)\) 元就是 \(i,j\) 间边数 = 长度 1 的途径数。
2. 归纳：设 \(A^{k-1}\) 的 \((i,t)\) 元 = \(i\to t\) 长 \(k-1\) 的途径数。由矩阵乘法 \(A^{k}=A^{k-1}A\)，\((A^k)_{ij}=\sum_t (A^{k-1})_{it}(A)_{tj}\)。
3. 这恰是"先从 \(i\) 走 \(k-1\) 步到中转点 \(t\)，再从 \(t\) 走 1 步到 \(j\)"的所有方式数 = \(i\to j\) 长 \(k\) 的途径数。归纳完成。♦

题 31　每个非叶顶点至少两个孩子的有根平面树

正如我们在 5.5.2.1 节所做的，去掉这种树的根，注意到你要么得到空树，要么得到至少两棵树的序列。因此我们有

1. 拆根：一棵这种树 = 一个根（贡献因子 \(x\)）+ 它的孩子子树序列。规则要求：若根有孩子，则孩子数 \(\ge2\)；也允许根本身就是叶子（孩子序列为空）。
2. 列方程：空孩子序列贡献 \(1\)；\(n\ge2\) 棵子树的有序序列贡献 \(S(x)^n\)。故 \[S(x)=x\Big(1+\sum_{n\ge2}S(x)^n\Big)=x\Big(1+\frac{S(x)^2}{1-S(x)}\Big)=x+\frac{S(x)^2}{1-S(x)}.\] （用几何级数 \(\sum_{n\ge2}S^n=\dfrac{S^2}{1-S}\)。）
3. 解闭式：记 \(S=S(x)\)，两边乘 \((1-S)\)：\(S(1-S)=x(1-S)+S^2\)，即 \(S-S^2=x-xS+S^2\)，整理为 \[2S^2-(1+x)S+x=0.\] 解二次方程并取使 \(S(0)=0\) 的根（即取减号）： \[S(x)=\frac{1+x-\sqrt{1-6x+x^2}}{4}.\]
4. 验证：\(x=0\) 时 \(S=\frac{1-1}{4}=0\)，正确。展开前几项 \(S(x)=x+x^2+3x^3+11x^4+\cdots\)（即小 Schröder 数 / super-Catalan 数），与"每非叶点至少两孩子"的树数吻合。♦

返回 全书目录