5.9　习题Exercises

本页为译文 + 高中讲解合一：黑色正文（有序列表中的题目）为忠实翻译；彩色框（解题思路 / 分步推演 / 例）与配图为面向高中生的方法提示。本节只给思路与方法，不必给出完整最终答案——完整解答见对应的“习题解答”一节。

1. 证明：任何至少含两个顶点的有限简单图（finite simple graph）中，必有两个顶点的度数（degree）相同。

   思路用抽屉原理（pigeonhole principle）。设图有 \(n\ge2\) 个顶点，每个顶点的度数取值范围是 \(0,1,\dots,n-1\)，看似有 \(n\) 个可能值、\(n\) 个顶点，刚好不够用抽屉原理。关键在于排除冲突：度数 \(n-1\)（与所有点相邻）与度数 \(0\)（孤立点）不可能同时出现。
   1. 简单图中每个顶点度数 \(\in\{0,1,\dots,n-1\}\)。
   2. 若某点度数 \(=n-1\)，则它与所有其他点相连，于是没有点度数为 \(0\)；反之若有度数 \(0\) 的点，则没有点度数为 \(n-1\)。
   3. 所以实际可用的度数值最多只有 \(n-1\) 种，而点有 \(n\) 个，必有两点同度。♦

2. 设 \(G\) 是任一有限图，\(x,y\) 是 \(G\) 的两个顶点。证明：若 \(G\) 中存在从 \(x\) 到 \(y\) 的通道（walk），则也存在从 \(x\) 到 \(y\) 的路径（path）。

   思路通道允许重复顶点，路径不允许。核心想法：取最短的那条 \(x\to y\) 通道，它一定不重复顶点。
   1. 在所有 \(x\to y\) 通道中取一条边数最少的，记为 \(W\)。
   2. 反证：若 \(W\) 重复经过某顶点 \(v\)（即 \(v\) 出现两次），把两次 \(v\) 之间的那段“绕圈”去掉，得到更短的 \(x\to y\) 通道，与“最短”矛盾。
   3. 故 \(W\) 不重复顶点，即为一条路径。♦

3. 证明：有限简单图 \(G\) 是树（tree）当且仅当：对任意两个不同的顶点 \(x,y\)，恰好存在一条连接 \(x\) 与 \(y\) 的路径。

   思路这是“当且仅当”，要证两个方向。树 = 连通且无圈。
   1. （⇒）若 \(G\) 是树：连通保证至少一条路径；无圈保证不可能有两条不同路径（若有两条不同路径，把它们拼起来就出现圈）。
   2. （⇐）若任意两点恰有一条路径：恰有一条 ⟹ 至少一条 ⟹ 连通；恰有一条 ⟹ 没有圈（圈会在圈上两点间制造两条路径）。连通且无圈即为树。♦

4. 设 \(T\) 是一棵树，\(P\) 是 \(T\) 中的一条路径，\(v\) 是 \(P\) 之外的一个顶点。证明：存在 \(P\) 上的一个顶点 \(w\)，它比 \(P\) 上任何其他顶点都更接近 \(v\)（这里“接近”指树中两点间路径的边数即距离（distance）更小）。

   思路利用第 3 题的唯一路径性。从 \(v\) 出发到 \(P\) 上各点的路径，第一次“碰到” \(P\) 的那个顶点就是 \(w\)。
   1. 取 \(P\) 上离 \(v\) 最近的顶点 \(w\)（树中距离唯一确定，故 \(w\) 存在）。
   2. 对 \(P\) 上任意另一点 \(u\)：从 \(v\) 到 \(u\) 的唯一路径必先到 \(w\) 再沿 \(P\) 走到 \(u\)，因此 \(\mathrm{dist}(v,u)=\mathrm{dist}(v,w)+\mathrm{dist}(w,u)>\mathrm{dist}(v,w)\)。
   3. 故 \(w\) 严格最近，唯一。♦

5. 证明：在 \(10\) 个顶点上至少存在 \(25\) 棵树，使得其中任何两棵都不同构（isomorphic）。

   思路这是要给出一个下界。可用 Cayley 公式：\(10\) 个有标号顶点上的树共有 \(10^{10-2}=10^{8}=10^8\) 棵。每个同构类里标号树的个数最多为 \(10!\)（顶点的全部排列）。所以不同构的类数至少为 \(10^8/10!\)。
   1. 有标号树总数 \(=10^{8}=100{,}000{,}000\)。
   2. \(10!=3{,}628{,}800\)。
   3. 不同构类数 \(\ge \dfrac{10^{8}}{10!}=\dfrac{100000000}{3628800}\approx 27.6\)，故至少 \(28>25\) 棵两两不同构。♦

6. (+) 称停车函数（parking function）\(f\) 没有相同的相邻元素，如果其定义域中不存在 \(i\) 使得 \(f(i)=f(i+1)\)。求 \([n]\) 上没有相同相邻元素的停车函数的个数公式。

   思路停车函数总数为 \((n+1)^{n-1}\)。本题加了“相邻不相等”的限制，宜结合停车函数与有标号树/森林的对应，或对“相邻相等”用容斥（inclusion-exclusion）。先在小 \(n\) 上手算验证猜想。
   小例热身（n=2） \([2]\) 上的停车函数有 \((2+1)^{1}=3\) 个：\((1,1),(1,2),(2,1)\)。去掉相邻相等的 \((1,1)\)，剩 \(2\) 个。用这个数据去校验你猜出的公式。

7. 设 \(f:[n]\to[n]\) 是停车函数。证明：\(f\) 中停车失败尝试（unsuccessful parking attempt）的次数等于 \[\binom{n+1}{2}-\sum_{j=1}^{n} f(j).\] 所谓一次失败尝试，是指某辆车试图停入某车位却发现该位已被占。

   思路第 \(j\) 辆车想停 \(f(j)\)，若被占就依次往后找，失败尝试次数等于它实际停的位置减去 \(f(j)\)。把所有车的“实际位置之和”与“偏好之和”相减即可。
   1. 所有车最终恰好占满 \(1,2,\dots,n\)，故“实际停车位置之和” \(=1+2+\dots+n=\binom{n+1}{2}\)。
   2. 每辆车的失败次数 \(=\)（实际位置 \(-\) 偏好位置 \(f(j)\)）。
   3. 对所有 \(j\) 求和：总失败次数 \(=\binom{n+1}{2}-\sum_{j} f(j)\)。♦

8. 把一个图的度数序列（degree sequence）按非增顺序排列，得到的序列称为该图的有序度数序列。问：\(n\) 个顶点的树共有多少种可能的有序度数序列？（答案可含表示整数拆分（partition）个数的函数 \(p\)。）

   思路关键事实：\(n\) 个顶点的树有 \(n-1\) 条边，故度数之和 \(=2(n-1)\)，且每个度数 \(\ge1\)。问题化为：求和为 \(2(n-1)\)、恰含 \(n\) 个正整数部分的拆分个数。
   1. 每点度 \(\ge1\)，先各减 \(1\)：令 \(d_i'=d_i-1\ge0\)，则 \(\sum d_i'=2(n-1)-n=n-2\)。
   2. 于是有序度数序列 ↔ 把 \(n-2\) 拆成至多 \(n\) 个非负部分，即 \(n-2\) 的拆分（部分数自动不超过 \(n-2
   3. 故答案为 \(p(n-2)\)。还需验证每个这样的序列确有树实现（树的度数序列判定）。♦

9. (+) 推广停车函数：设 \(1\le k\le n\)。现有 \(n+1-k\) 辆车到达停车场，停车场仍有标号为 \(1\) 到 \(n\) 的 \(n\) 个车位。每辆车有偏好车位，偏好由函数 \(f:[n+1-k]\to[n]\) 给出。某天标号小于 \(k\) 的车位因施工关闭。若全部 \(n+1-k\) 辆车都能用通常的停车流程停好，则称 \(f\) 为 \(k\)-缩短停车函数（\(k\)-shortened parking function）（此名由 Catherine Yan 提出）。注意 \(1\)-缩短停车函数就是普通停车函数。

   (a) 求 \(f\) 是 \(k\)-缩短停车函数的充分必要条件。

   (b) 求停车函数 \(f:[n+1-k]\to[n]\) 中 \(k\)-缩短停车函数的个数公式。

   思路普通停车函数的判定（排序后第 \(i\) 小的偏好 \(\le i\)）要修正：因为前 \(k-1\) 个车位关闭，所有车只能停 \(k,k+1,\dots,n\)，且每个偏好 \(\ge\) 某下界。(a) 把偏好升序排为 \(b_1\le\dots\le b_{n+1-k}\)，给出形如 \(b_i\le k-1+i\) 的条件。(b) 仿照对普通停车函数用的“循环 + 计数”论证（Pollak 的环上论证）。

10. 求 \([n]\) 上恰有 \(k\) 个值等于 \(1\) 的停车函数个数 \(P(n,k)\) 的公式。

    思路“恰有 \(k\) 个 \(1\)”意味着第 \(2,3,\dots\) 个车位被剩下的 \(n-k\) 辆车（偏好 \(\ge2\)）以“在 \(2,\dots,n\) 上的停车函数”方式填满。先选哪 \(k\) 辆车偏好 \(1\)（\(\binom{n}{k}\) 种），再处理其余。
    小例（n=2） 停车函数 \((1,1),(1,2),(2,1)\) 中含 \(1\) 的个数分别是 \(2,1,1\)。故 \(P(2,2)=1,\ P(2,1)=2,\ P(2,0)=0\)。用来检验公式。

11. (+) 称 \([n]\) 上的停车函数为素停车函数（prime parking function），如果从中删去一个 \(1\) 后，得到的是 \([n-1]\) 上的停车函数。例如 \(1,1,2\) 是素停车函数，而 \(1,1,3\) 不是。约定 \([1]\) 上唯一的停车函数也是素的。

    本题旨在解释“素停车函数”这一名称：证明存在一个自然的双射（bijection），把 \([n]\) 上全体停车函数构成的集合 \(\mathcal P(n)\) 映到字符串集合 \(SPP(n)\)，其元素形如 \[(p_1,p_2,\dots,p_k,\ s_1,s_2,\dots,s_k),\] 其中 \(k\) 取 \(1\) 到 \(n\)（即 \(k\) 不固定），每个 \(p_i\) 是 \([a_i]\) 上的素停车函数，且 \(\sum_{i=1}^{k} a_i=n\)；而 \((s_1,s_2,\dots,s_k)\) 是集合 \([n]\) 的一个拆分（分块），其中块 \(s_i\) 含 \(a_i\) 个元素。换言之，所求双射不仅指明停车函数被分解成哪些素停车函数，还指明它们在原停车函数中的位置。

    思路类比“整数可唯一分解为素数”的思想：每个停车函数可唯一拆成若干素停车函数的“拼接 + 标位”。构造双射时，把停车函数按其“满载断点”切成不可再分的素段，块 \(s_i\) 记录每段占据的原始下标位置。验证可逆即得双射。

12. 设 \(P(n,k)\) 为 \([n]\) 上恰有 \(k\) 个值等于 \(1\) 的停车函数个数，\(PP(n,k)\) 为恰有 \(k\) 个值等于 \(1\) 的素停车函数个数。用 \(P(n,k)\) 表示 \(PP(n+1,k+1)\)。

    思路由素停车函数的定义（删去一个 \(1\) 仍是停车函数），在 \([n+1]\) 上含 \(k+1\) 个 \(1\) 的素停车函数与 \([n]\) 上含 \(k\) 个 \(1\) 的某类停车函数直接对应。建立“删 \(1\)/添 \(1\)”的映射并数清重数。

13. (+) 证明：对所有 \(n\ge1\)，素停车函数总数 \(PP(n)=(n-1)^{n-1}\)。

    思路对比普通停车函数总数 \((n+1)^{n-1}\)。可用上题的递推 \(PP(n+1,k+1)\) 与 \(P(n,k)\) 的关系求和，或用第 14 题的生成函数恒等式反推。先验证小值。
    小例 \(n=1:(1-1)^{0}=1\)（即 \([1]\) 上那个停车函数，约定为素）。\(n=2:(2-1)^{1}=1\)，即只有 \((1,1)\)（\((1,2),(2,1)\) 删去 \(1\) 后不是 \([1]\) 的停车函数？逐一检验，建立直觉）。

14. 证明： \[\sum_{n\ge0}(n+1)^{n-1}\frac{x^n}{n!}=\frac{1}{\,1-\displaystyle\sum_{n\ge1}(n-1)^{n-1}\frac{x^n}{n!}\,}.\]

    思路这是指数生成函数（exponential generating function, EGF）恒等式。左端是停车函数（计数 \((n+1)^{n-1}\)）的 EGF；右端 \(\frac{1}{1-A(x)}\) 是“序列结构”的 EGF，其中 \(A(x)=\sum(n-1)^{n-1}x^n/n!\) 是素停车函数（计数 \(PP(n)=(n-1)^{n-1}\)，见第 13 题）的 EGF。第 11 题的双射（停车函数 = 素停车函数的序列）正翻译成这个恒等式。
    1. 把第 11 题的结构“停车函数 ↔ 素停车函数序列 + 集合拆分”用 EGF 的序列构造（SEQ）翻译。
    2. 序列构造对应 \(\frac{1}{1-A(x)}\)，其中 \(A\) 是“素结构”的 EGF。
    3. 代入 \(PP(n)=(n-1)^{n-1}\) 与 \(\#\mathcal P(n)=(n+1)^{n-1}\)（注意 \([0]\) 上约定为 \(1\)）即得等式。♦

15. 求所有 \(n\le6\) 时 \(n\) 个顶点上互不同构的（unlabeled，无标号）树的个数 \(u(n)\)。

    思路直接枚举画图。按“最长路径长度”或“度数序列”分类，逐一画出并去掉同构者。
    1. \(u(1)=1\)（单点）。
    2. \(u(2)=1\)（一条边）。
    3. \(u(3)=1\)（路径 \(P_3\)）。
    4. \(u(4)=2\)（路径 \(P_4\)、星 \(K_{1,3}\)）。
    5. \(u(5)=3\)；\(u(6)=6\)。把它们都画出来核对。

16. 对图 5.46 中的三个图 \(G,H,J\)，分别求该图全部自同构（automorphism）的个数。

    思路自同构 = 把图映到自身、保持相邻关系的顶点置换。它们构成一个群，个数即自同构群的阶。逐一考察“哪些顶点可以互换而不破坏边”。
    1. 找出对称轴/对称中心：度数不同的顶点不能互换，所以先按度数分组，自同构只能在同度顶点间作用。
    2. 对每组用对称性数清可行置换数，再相乘（受边约束）。
    3. 例如完全图 \(K_m\) 的自同构数为 \(m!\)；路径 \(P_m\)（\(m\ge2\)）为 \(2\)（恒等与翻转）。以此类比图中各部分。

17. 给出一个 \(6\) 个顶点的图的例子，使它恰有 \(720\) 种标号方式（labeling）。

    思路关键公式：一个无标号图的不同标号方式数 \(=\dfrac{n!}{|\mathrm{Aut}|}\)，其中 \(|\mathrm{Aut}|\) 是自同构群的阶。这里 \(n=6\)，\(6!=720\)，所以要让标号数 \(=720\) 就要让 \(|\mathrm{Aut}|=1\)，即找一个没有非平凡对称（仅有恒等自同构）的图。
    1. 需要 \(|\mathrm{Aut}|=720/720=1\)。
    2. 构造一个所有顶点度数互不相同、或结构完全不对称的 \(6\) 点图（这样的图称“非对称图”，\(6\) 点上存在）。
    3. 验证它只有恒等自同构即可。♦

18. 设 \(T\) 是 \(n+1\) 个无标号顶点上的一棵有根树（rooted tree）。现用 \([n+1]\) 的元素给 \(T\) 的顶点贴标号，使每个标号恰用一次，且每个顶点的标号都小于其父顶点的标号。称这样标号的树为递减树（decreasing tree）（见图 5.47）。证明：\(n+1\) 个顶点上的递减树个数为 \(n!\)。

    思路注意：因为每点标号小于父标号，根必为最大标号 \(n+1\)。可对 \(n\) 用归纳，或建立递减树与排列（permutation）的双射，从而得到 \(n!\)。
    1. 根固定为 \(n+1\)。逐个把标号 \(n,n-1,\dots,1\) 按降序加入：标号 \(j\) 只能挂到已放入的、标号更大的某个顶点下。
    2. 放第 \(t\) 大的标号时，已放入的顶点有 \(t-1\) 个（除根外），可作父亲的选择数恰为它们的个数，逐步相乘得 \(n!\)。
    3. 归纳基：\(n=0\) 时 \(1=0!\)；\(n=1\) 时 \(1=1!\)。♦

19. 求 \(n+1\) 个顶点上、根恰有 \(k\) 个孩子的递增树（increasing tree）个数的公式。

    思路递增树即根标号最小（沿着远离根方向标号递增）。第 18 题证明了递减树总数为 \(n!\)；递增树与递减树通过标号取补（\(i\mapsto n+2-i\)）对称对应，故递增树总数同样为 \(n!\)。本题再按“根的孩子数 \(=k\)”细分。可用生成函数或对“根的孩子”这一层做组合分解。
    提示 这类计数通常给出第一类无符号 Stirling 数（unsigned Stirling numbers of the first kind）形式的答案，因为递增树与排列的循环结构对应。先在 \(n=2,3\) 上枚举验证。

20. (a) 求一个双射 \(f\)，把第 4 章习题 32 中定义的避 132 排列（132-avoiding permutation）的集合映到 \(n+1\) 个无标号顶点上的有根平面树（rooted plane tree）的集合。

    (b) 给出一个作为 (a) 答案的双射 \(f\)，使排列 \(p\) 的从左到右极小值（left-to-right minima）个数变成树 \(f(p)\) 的叶子（leaves）个数。

    思路避 132 排列与有根平面树都被卡塔兰数（Catalan number）\(C_n\) 计数，故必有双射。常用构造：递归地把排列按最大元（或最小元）分块，对应树的子树。(b) 要求双射把一种统计量精确翻译成另一种，构造时要让“极小值”与“叶子”同步产生。

21. 避模式排列已在第 4 章习题 32 中定义。求一个双射，把 \(n\) 个顶点上全体无标号二叉平面树（binary plane tree）的集合映到全体避 132 的 \(n\)-排列的集合。

    思路同样由卡塔兰数 \(C_n\) 计数两边。经典做法：用排列的最大元位置把排列切成左右两段，分别递归对应二叉树的左右子树。

22. 利用上一题的结果证明：含 \(k\) 个下降（descent）的避 132 的 \(n\)-排列个数，与含 \(k\) 个上升（ascent）的避 132 的 \(n\)-排列个数相同。

    思路把第 21 题的双射与二叉树的某种对称（如左右子树互换、镜像反射）结合，让“下降”与“上升”互换。也可直接对避 132 排列找一个交换上升/下降的对合（involution）。

23. 比较习题 20 与 22 的结果，证明定理 5.29。

    思路把第 20 题（避 132 ↔ 有根平面树，且极小值 ↔ 叶子）与第 22 题（上升/下降对称）拼起来，得到关于树的统计量分布的对称性，即定理 5.29 的论断。先回到正文重读定理 5.29 的精确陈述，再核对两题输出的统计量是否正好匹配。

24. 问：\([n]\) 上有 \(k\) 个不动点（fixed point）的无环函数（acyclic function）个数 \(a_{n,k}\) 是多少？

    思路无环函数即其函数图（每个 \(i\) 连一条 \(i\to f(i)\)）除自环外无圈——本质上对应森林。不动点 \(f(i)=i\) 对应自环，可视为“根”。先选哪 \(k\) 个点为不动点（根），再数以它们为根的有根森林个数。
    1. 选定 \(k\) 个不动点：\(\binom{n}{k}\) 种。
    2. 其余结构是“\(n\) 个顶点、\(k\) 棵树、指定 \(k\) 个根”的有根森林，其计数有现成公式 \(k\,n^{\,n-k-1}\) 类（用 Cayley 型公式）。
    3. 合并即得 \(a_{n,k}\)。在 \(n=2,3\) 上枚举验证。

25. 设 \(a_{n,k}\) 如上题定义。求生成函数 \[A_n(x)=\sum_{k=1}^{n} a_{n,k}\,x^k\] 的一个简单闭形式。

    思路把上题的 \(a_{n,k}\) 公式代入求和。若 \(a_{n,k}=\binom{n}{k}\cdot k\,n^{\,n-k-1}\) 之类，可用二项式定理把 \(\sum_k\binom{n}{k}(\cdot)x^k\) 收成 \((\,\cdot+x\,)^{?}\) 形式的闭式。

26. 证明：对所有图 \(G\)，满足下列条件的对 \((g,A)\) 的个数等于 \(\chi_G(n)\)：

    (a) \(A\) 是 \(G\) 的一个无环定向（acyclic orientation）；并且

    (b) \(g\) 是用 \([n]\) 中颜色对 \(G\) 顶点的一种染色，使得：若 \(A\) 中有从 \(u\) 到 \(v\) 的边，则 \(g(u)>g(v)\)。

    这里 \(\chi_G(n)\) 是 \(G\) 的色多项式（chromatic polynomial）。

    思路建立“合法染色 ↔ (无环定向, 相容染色)”的对应。一个用 \(n\) 种颜色的正常染色（proper coloring）会诱导一个无环定向（每条边从大颜色指向小颜色），反之每个 \((g,A)\) 给出一个正常染色。双向计数即得等于 \(\chi_G(n)\)。注意 (b) 中 \(g(u)>g(v)\) 自动保证相邻异色（正常染色）。

27. 设 \(n,m\) 为两个整数且 \(n

    思路\(\chi_G(t)\) 是次数为顶点数的多项式，其在非负整数处的值有组合意义：\(\chi_G(t)=\)“用 \(t\) 种颜色正常染色的方法数” \(\ge0\)。利用 \(\chi_G\) 的根都是非负整数、且“色数（chromatic number）以下的整数全为根”这一结构。
    1. \(\chi_G(t)=0\) 表示用 \(t\) 种颜色无法正常染色。
    2. 若用 \(t\) 种颜色不能染（\(\chi_G(t)=0\)），则用更少颜色 \(t-1\) 更不能染，故 \(\chi_G(t-1)=0\)。即根关于“变小”封闭，最小可染色数 = 色数。
    3. 因此 \(n,m\) 都是根意味着 \(0,1,\dots,\) 直到色数减 1 全是根，区间 \([n,m]\) 自然全含其中。♦

28. (+) 证明：若两个图有相同的色多项式，则它们必有相同的边数。

    思路读出色多项式的系数的组合意义。把 \(\chi_G(t)\) 展开成 \(t\) 的多项式，其最高次为 \(t^{|V|}\)，次高次项的系数恰为 \(-|E|\)（边数的相反数）。系数由多项式唯一决定，故色多项式相同 ⟹ 次高次系数相同 ⟹ 边数相同。
    1. 由删边-缩边（deletion-contraction）递推可证 \(\chi_G(t)=t^{|V|}-|E|\,t^{|V|-1}+\cdots\)。
    2. 两图色多项式相同 ⟹ 顶点数相同（最高次）且 \(t^{|V|-1}\) 系数相同。
    3. 故 \(|E|\) 相同。♦

29. 设 \(\mathrm{Co}_n\) 为顶点集 \([n]\) 上连通图（connected graph）的个数。

    (a) 证明：顶点集 \([n]\) 上有根图（rooted graph）的个数为 \[\sum_{k=1}^{n}\binom{n}{k}\,k\,\mathrm{Co}_k\cdot 2^{\binom{n-k}{2}}.\] 有根图是指其中一个顶点被指定为根的图。

    思路用分类计数（按根所在连通分支的大小 \(k\)）。把 \([n]\) 上的有根图按“根所在那个连通分支含 \(k\) 个顶点”分类求和。
    1. 选根所在分支的 \(k\) 个顶点（含根）：\(\binom{n}{k}\) 种。
    2. 这 \(k\) 个点构成一个连通图：\(\mathrm{Co}_k\) 种；在其中选一个作根：\(k\) 种（合为 \(k\,\mathrm{Co}_k\)）。
    3. 剩下 \(n-k\) 个点之间任意连边、与根分支不相连：边数最多 \(\binom{n-k}{2}\)，每条边可有可无，共 \(2^{\binom{n-k}{2}}\) 种。
    4. 对 \(k=1,\dots,n\) 求和即得公式。♦

返回 全书目录