1.9　习题解答Solutions to exercises

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

习题 1

第一个柜台前的人排队有 \(n!\) 种方式，第二个柜台前的人排队有 \(m!\) 种方式。因此由乘法原理（product principle），总共有 \(n!\,m!\) 种可能。现在，若 \(m=0\)，则可能总数为 \(n!\)，因为第一个柜台前的人排队的方式数不变。所以，只有取 \(m!=0!=1\) 才能使公式 \(n!\,m!\) 仍然成立。

1. 把"两个柜台各自排队、再用乘法原理相乘"拆开看：第一柜台 \(n\) 人排成一列，第一个位置有 \(n\) 种选法、第二个位置剩 \(n-1\) 种……一直到最后一个位置 \(1\) 种，所以是 \(n\cdot(n-1)\cdots1=n!\)。第二柜台同理为 \(m!\)。
2. 两个柜台的排队互不影响，第一柜台的每一种排法都能配上第二柜台的每一种排法，于是相乘：总数 \(=n!\cdot m!\)。
3. 当 \(m=0\) 时，第二柜台没有人，只有"空队列"这一种情形，对总数没有任何影响，所以总数仍应等于 \(n!\)。
4. 要让公式 \(n!\,m!\) 在 \(m=0\) 时也给出 \(n!\)，必须 \(n!\cdot 0!=n!\)，即 \(0!=1\)。这就是"规定 \(0!=1\)"背后的道理：它不是随意约定，而是为了让乘法原理在边界情形不出例外。

习题 2

我们来数由 \(a+b\) 个字母组成的单词，其中前 \(a\) 个字母取自一个 \(n\) 字母的字母表，后 \(b\) 个字母取自一个 \(m\) 字母的字母表。由乘法原理，这种单词的个数为 \(n^a m^b\)。特别地，若 \(b=0\)，那么我们只是在数 \(n\) 元字母表上的 \(a\) 字母单词。我们知道这种单词的个数为 \(n^a\)。因此在这种情况下 \(n^a=n^a\cdot m^0\)，从而 \(m^0=1\)。

1. 前 \(a\) 个位置每个都有 \(n\) 种字母可选，互相独立，所以前半段共 \(\underbrace{n\cdot n\cdots n}_{a\text{ 个}}=n^a\) 种。
2. 后 \(b\) 个位置每个都有 \(m\) 种字母可选，共 \(m^b\) 种。
3. 前后两段独立，乘法原理给出总数 \(n^a\cdot m^b\)。
4. 当 \(b=0\) 时，后半段为"空"，单词其实只有前 \(a\) 个字母，所以个数应当就是 \(n^a\)。代入公式要求 \(n^a\cdot m^0=n^a\)，故 \(m^0=1\)。这正是规定"任何非零数的 \(0\) 次方为 \(1\)"的组合解释。

习题 3

每一列必须恰有一个车（rook）。第一个车可以放在它所在列的任意位置（\(n\) 种可能）。第二个车可以放在它所在列的任意位置，但不能与第一个车同行，这剩下 \(n-1\) 种可能。第三个车可以放在它所在列的任意位置，但不能落在第一、二个车占用的行上，剩下 \(n-2\) 种，依此类推，最终得到 \(n\cdot(n-1)\cdots 2\cdot 1=n!\) 种可能。

1. "互不同列"且共 \(n\) 个车、\(n\) 列 → 每列恰好一个车。于是只需逐列决定它在第几行。
2. 第 1 列的车：行随便选，\(n\) 种。
3. 第 2 列的车：行不能与第 1 列重复，剩 \(n-1\) 种。
4. 第 3 列：避开前两行，剩 \(n-2\) 种……第 \(k\) 列剩 \(n-k+1\) 种。
5. 各列独立相乘：\(n\cdot(n-1)\cdots1=n!\)。

习题 4

若我们放置 \(k\) 个车，则首先需要选出这 \(k\) 个车将被放入的 \(k\) 列。这可以用 \(\binom{n}{k}\) 种方式完成。沿用上一题解答的思路，我们接着可以用 \((n)_k\) 种方式把 \(k\) 个车放入选定的列。因此，总的可能数为 \[\sum_{k=1}^{n}\binom{n}{k}(n)_k.\]

1. "放 \(k\) 个互不攻击的车"分两步：先挑哪 \(k\) 列有车，再决定它们各占哪些行。
2. 挑 \(k\) 列：从 \(n\) 列中选 \(k\) 列，\(\binom{n}{k}\) 种。
3. 定行：这 \(k\) 个车要落在 \(k\) 个互不相同的行上。第 1 个有 \(n\) 行可选，第 2 个 \(n-1\) 行……第 \(k\) 个 \(n-k+1\) 行，相乘得 \((n)_k=n(n-1)\cdots(n-k+1)\)。
4. 固定 \(k\) 时，方法数为 \(\binom{n}{k}(n)_k\)。\(k\) 可取 \(1\) 到 \(n\)（题目要求至少放一个车），各情形互不相交，由加法原理求和。

习题 5

可能的结果数为 \(15!/2\)。事实上，设 \(S\) 为可能结果的集合，\(T\) 为不可能结果的集合，即那些 Bob 排在 Amy 前面的结果。那么存在一个双射（bijection）\(f:S\to T\)，即简单地把 Amy 和 Bob 互换的那个函数。

1. 若不加限制，15 人排名共 \(15!\) 种。
2. 把全部 \(15!\) 种分成两类：\(S=\)Amy 在 Bob 前；\(T=\)Bob 在 Amy 前。其它人位置不限。
3. 构造对应 \(f\)：把一种名次里 Amy 与 Bob 两人位置对调、其余不动。这把 \(S\) 中每个名次唯一地变成 \(T\) 中一个名次，且可逆，故 \(f\) 是双射 → \(|S|=|T|\)。
4. 两类不相交且合起来是全体 \(15!\)，于是 \(|S|+|T|=15!\) 且 \(|S|=|T|\)，得 \(|S|=15!/2\)。

习题 6

由于所玩号码的顺序无关紧要，本题实际上是在问 \([49]\) 的所有六元子集的个数。正如我们由定理 1.4 所知，这等于 \(\binom{49}{6}=13983816\)。

1. 买彩票选 6 个号码，号码不重复、先后顺序不计，正是"无序、不放回"地从 49 个中取 6 个，即子集。
2. 个数 \(\binom{49}{6}=\dfrac{49\cdot48\cdot47\cdot46\cdot45\cdot44}{6!}\)。
3. 分子 \(=10068347520\)，\(6!=720\)，相除得 \(13983816\)。

习题 7

能被 5 整除的四位整数共有 \(9\cdot10\cdot10\cdot2=1800\) 个，因为这样的整数末位必须是 0 或 5。其中 \(8\cdot9\cdot9\cdot2=1296\) 个不含数字 3，所以含有数字 3 的有 \(1800-1296=504\) 个。

1. 四位数 \(\overline{d_1d_2d_3d_4}\)。能被 5 整除 ⇔ \(d_4\in\{0,5\}\)，2 种。
2. \(d_1\) 不能为 0（否则不是四位数），\(d_1\in\{1,\dots,9\}\)，9 种；\(d_2,d_3\) 各 0–9，10 种。相乘 \(9\cdot10\cdot10\cdot2=1800\)。
3. 再数"不含数字 3"的：\(d_1\) 不能是 0 也不能是 3 → 8 种；\(d_2,d_3\) 不能是 3 → 各 9 种；\(d_4\in\{0,5\}\) 都不含 3 → 仍 2 种。共 \(8\cdot9\cdot9\cdot2=1296\)。
4. "含 3 的" = "全部" − "不含 3 的"（减法原理）：\(1800-1296=504\)。

习题 8

必然有一个数字被使用两次，其余两个数字各用一次。若我们把数字 3 用了两次，则需要尝试 \(\binom{4}{2,1,1}=12\) 次。由对称性，重复数字 5 或 9 时同样的论证成立。因此，在最坏情况下，我们需要尝试 \(3\cdot12=36\) 次。

1. 结构：长度 4，三种数字，一个出现 2 次、两个各 1 次。先固定"哪个数字重复"。
2. 若重复的是 3，则密码用了 \(\{3,3,5,9\}\) 这四个数字排列。不同排列数为多重组合 \(\binom{4}{2,1,1}=\dfrac{4!}{2!\,1!\,1!}=\dfrac{24}{2}=12\)。
3. "重复 5"或"重复 9"的情形与之结构相同，各 12 种。三类互不相交。
4. 总数 \(3\cdot12=36\)。最坏情况下要把所有 36 种都试一遍才保证命中。

习题 9

若不要求 3 和 4 不在相邻位置，则将给定数字排成一列有 \(\binom{7}{2,2,1,1,1}=1260\) 种方式。我们来数那些 3 和 4 处于相邻位置的排法。为此，把 3 和 4 粘成一个"超级数字" \(X\)。于是有 \(\binom{6}{2,2,1,1}=180\) 种可能的排列。然而，每一种都对应两种原排列，因为 \(X\) 可以还原成 34 或 43。因此由乘法原理，坏排列有 \(2\cdot180=360\) 种，于是由减法原理，好排列有 \(1260-360=900\) 种。

1. 先不管限制：7 个位置里有两组各 2 个相同、三组各 1 个，排法 \(\dfrac{7!}{2!\,2!\,1!\,1!\,1!}=\dfrac{5040}{4}=1260\)。
2. 数"坏排列"（3、4 相邻）：把 34 视作一个整体 \(X\)，对象变为 6 个，其中仍有两组各 2 个相同，排法 \(\dfrac{6!}{2!\,2!\,1!\,1!}=\dfrac{720}{4}=180\)。
3. \(X\) 内部可为 "34" 或 "43" 两种，故坏排列 \(=180\cdot2=360\)。
4. 好排列 = 全部 − 坏的 \(=1260-360=900\)（减法原理）。

习题 10

选取一周中四天或五天有 \(\binom{7}{4}+\binom{7}{5}=35+21=56\) 种方式。其中 \(\binom{5}{4}+\binom{5}{5}=5+1=6\) 种不包含任何周末日。因此可能的安排数为 \(56-6=50\)。

1. 一周 7 天，要选 4 天或 5 天：两类互斥，加法原理 \(\binom{7}{4}+\binom{7}{5}=35+21=56\)。
2. "完全避开周末"= 只能从 5 个工作日里选 4 或 5 天：\(\binom{5}{4}+\binom{5}{5}=5+1=6\)。
3. 题目要求至少含一个周末日，于是从 56 中减去那 6 个"全工作日"方案：\(56-6=50\)（减法原理）。

习题 11

没有任何限制时，教练有 \(\binom{20}{4}\) 种可能。唯一的坏选择是：所有奖学金都给了进攻球员，或者都给了防守球员。因此坏选择数为 \(2\cdot\binom{10}{4}\)，于是由减法原理，好选择数为 \(\binom{20}{4}-2\cdot\binom{10}{4}\)。

1. 无限制地选 4 人：\(\binom{20}{4}=4845\)。
2. 坏情形 A："4 人全是进攻" = 从 10 名进攻里选 4，\(\binom{10}{4}=210\)。
3. 坏情形 B："4 人全是防守" = \(\binom{10}{4}=210\)。两者不可能同时发生（不相交），坏的共 \(2\cdot210=420\)。
4. 好选择 \(=\binom{20}{4}-2\binom{10}{4}=4845-420=4425\)。

习题 12

正如例 1.26 那样，从 \(O\) 经 \(B\) 到 \(A\) 的开车路线数，等于从 \(O\) 到 \(B\) 的路线数乘以从 \(B\) 到 \(A\) 的路线数。换言之，它是 \(\binom{8}{4}\cdot\binom{4}{2}=70\cdot6=420\)。现在我们要从刚数出的路径中减去坏路径，即经过禁止点 \(C\) 的路径数。这些坏路径从 \(O\) 到 \(C\) 到 \(B\) 到 \(A\)；因此它们的数目是 \(\binom{4}{1}\cdot\binom{4}{3}\cdot\binom{4}{2}=96\)。从而，好路径数为 \(420-96=324\)。

1. 格点最短路计数：从一点到另一点，需走固定的"向右步数 \(r\)"和"向上步数 \(u\)"，路径数 = 在 \(r+u\) 步里选哪几步向右 \(=\binom{r+u}{r}\)。
2. \(O\to B\)：按图所需步数给出 \(\binom{8}{4}=70\)；\(B\to A\)：\(\binom{4}{2}=6\)。经 \(B\) 的总路径 \(=70\cdot6=420\)（乘法原理，因为前后两段独立拼接）。
3. 坏路径必经 \(C\)，分三段 \(O\to C\to B\to A\)：\(\binom{4}{1}=4\)，\(\binom{4}{3}=4\)，\(\binom{4}{2}=6\)，相乘 \(4\cdot4\cdot6=96\)。
4. 好路径 \(=420-96=324\)（减法原理）。

习题 13

左边是 \([n]\) 所有子集的个数。事实上，当我们选取 \([n]\) 的一个子集时，要做 \(n\) 个决定，每个决定有两种选择。也就是说，对 \([n]\) 中每个元素 \(i\)，我们决定是否把 \(i\) 放进子集。右边是同一个量，按子集大小分类计数。事实上，\(\binom{n}{k}\) 是 \([n]\) 的所有 \(k\) 元子集的个数。

另一种解释：\(2^n\) 是从 \((0,0)\) 出发、走 \(n\) 步、每步向东或向北的格点路径（终点落在直线 \(x+y=n\) 上）的总数。在右边，我们按这些路径的终点 \((k,n-k)\) 来计数同样的路径。

1. 左边 \(2^n\)：构造一个子集，对每个元素 \(i\) 二选一（放/不放），\(n\) 个独立的二选一相乘 \(=2^n\)。
2. 右边 \(\sum_k\binom{n}{k}\)：把全部子集按"含几个元素"分堆。恰含 \(k\) 个元素的子集有 \(\binom{n}{k}\) 个，\(k\) 从 0 到 \(n\) 求和即所有子集。
3. 同一批对象（所有子集）数两遍，结果必相等，得证。

习题 14

左边正是从 \((0,0)\) 经一条东北向格点路径走到 \((k,n-k)\) 的方式数。右边是同一个量，按"最后一步向东（east）发生在何时"来分类计数。由于一共有 \(k\) 个东步，最后一个东步之前必须有 \(k-1\) 个东步和 \(i\) 个北步，其中 \(0\le i\le n-k\)。换言之，\(i\) 描述了最后一个东步取得有多晚（它是第 \(i+k\) 步）。最后一个东步之前的那 \(i\) 个北步与 \(k-1\) 个东步的排列方式数为 \(\binom{i+k-1}{k-1}\)。对所有可能的 \(i\) 求和，便得到右边。

1. 每条这样的路径恰有 \(k\) 个东步。盯住"最后一个东步"的位置来分类，可做到不重不漏。
2. 设最后一个东步是整条路径的第 \(i+k\) 步。那么在它之前有 \(k-1\) 个东步与 \(i\) 个北步（共 \(i+k-1\) 步），它之后只剩北步。
3. 前 \(i+k-1\) 步中安排 \(k-1\) 个东步的方法数为 \(\binom{i+k-1}{k-1}\)。
4. \(i\) 取 0 到 \(n-k\)（之后的北步个数从 \(n-k\) 减到 0），各情形不相交，求和得右边，于是两边相等。

习题 15

左边是从 \([n]\) 中选取两个子集（一个大小为 \(p\)，另一个大小为 \(q\)）的方式数。右边是同一个量，按这两个子集交集的大小来计数。

1. 左边：独立地选 \(P\)（\(\binom{n}{p}\) 种）与 \(Q\)（\(\binom{n}{q}\) 种），相乘。
2. 右边：按 \(|P\cap Q|=t\) 分类。先选公共部分 \(P\cap Q\)：\(\binom{n}{t}\)；再从剩下 \(n-t\) 个里给 \(P\) 补足 \(p-t\) 个独有元素：\(\binom{n-t}{p-t}\)；最后从不在 \(P\) 中的 \(n-p\) 个里给 \(Q\) 补 \(q-t\) 个：\(\binom{n-p}{q-t}\)。
3. 对所有 \(t\) 求和，数到的正是全部 \((P,Q)\) 对，与左边相同。

习题 16

我们由补充习题 7 得知，\([n]\) 中所有偶数大小子集的总数为 \[A=\binom{n}{0}+\binom{n}{2}+\binom{n}{4}+\cdots+\binom{n}{n}=2^{n-1}.\] 由于 \(n=4k+2\)，可见对偶数 \(m\)，\(m\) 和 \(n-m\) 中恰有一个能被 4 整除，所以相等的两数 \(\binom{n}{m}\) 与 \(\binom{n}{n-m}\) 中恰有一个被纳入和 \[B=\binom{n}{0}+\binom{n}{4}+\binom{n}{8}+\cdots+\binom{n}{n}.\] 因此 \(A=2B\)，证明了 \(B=2^{n-2}\)。

1. 背景结论：偶数大小子集共 \(2^{n-1}\) 个，即 \(A=2^{n-1}\)。\(B\) 只取下标为 4 的倍数的那些项。
2. 关键对称：\(\binom{n}{m}=\binom{n}{n-m}\)。当 \(n=4k+2\) 时，\(n\equiv2\pmod4\)。对偶数 \(m\)：若 \(m\equiv0\pmod4\) 则 \(n-m\equiv2\pmod4\)；若 \(m\equiv2\pmod4\) 则 \(n-m\equiv0\pmod4\)。所以"\(m,n-m\) 中恰有一个是 4 的倍数"。
3. 于是 \(A\)（所有偶数下标）里，每一对相等的 \(\binom{n}{m}=\binom{n}{n-m}\) 恰好贡献一项给 \(B\)（4 的倍数下标），即 \(A\) 的项可两两配对、每对里恰一项进 \(B\)、两项相等 → \(A=2B\)。
4. 故 \(B=A/2=2^{n-1}/2=2^{n-2}\)。

习题 17

由二项式定理，令 \(x=4\)、\(y=-1\)，可见该表达式等于 \(3^n\)。

1. 二项式定理：\((x+y)^n=\displaystyle\sum_{k=0}^n\binom{n}{k}x^{n-k}y^{k}\)。
2. 题中表达式为 \(\displaystyle\sum_{k=0}^n\binom{n}{k}4^{\,n-k}(-1)^{k}\)，正是上式取 \(x=4,\;y=-1\)。
3. 于是它 \(=(4+(-1))^n=3^{n}\)。

习题 18

由于湖人队（Lakers）和超音速队（Sonics）的位置已知，我们只需考虑其余五支球队的位置。让我们把国王队（Kings）、开拓者队（Trailblazers）、快船队（Clippers）各替换为一个符号 \(X\)。这三个符号 \(X\) 和余下的两支球队可以用 \(\binom{5}{3,1,1}=5!/3!=20\) 种方式排列。每一种这样的排列对应一个有效的排名，因为第一个 \(X\) 可还原为国王队、第二个 \(X\) 还原为开拓者队、第三个 \(X\) 还原为快船队。

1. 7 支球队排名，但湖人、超音速两队位置已固定，剩 5 支待排。
2. 国王、开拓者、快船三队在本题中相对顺序被锁定（用同一符号 \(X\) 表示其"位置"），于是把它们看作三个相同的 \(X\)，连同另两支不同球队，共 5 个对象排列：\(\dfrac{5!}{3!\,1!\,1!}=\dfrac{120}{6}=20\)。
3. 排好后，三个 \(X\) 从左到右依次还原为国王、开拓者、快船，对应唯一一个真实排名，不再产生额外倍数。故答案 \(=20\)。

习题 19

共有 720 个解。把火箭队（Rockets）和灰熊队（Grizzlies）粘在一起。排列剩下六个符号有 \(6!=720\) 种方式。其中一半是错误的，因为掘金队（Nuggets）必须排在马刺队（Spurs）后面。另一方面，火箭队和灰熊队可以用两种不同方式解粘，这把好排列数乘以 2。

1. 要求火箭与灰熊相邻 → 捆成一块 \(Y\)。此时对象为 \(Y\) 加其余 5 支队 = 6 个，排列 \(6!=720\)。
2. 再加约束"掘金在马刺之后"：在任意排列里，掘金与马刺的相对前后各占一半，所以满足该约束的占 \(720/2=360\)。
3. 块 \(Y\) 内部火箭、灰熊可为两种顺序，乘 2：\(360\cdot2=720\)。

习题 20

先选出魔术队（Magic）将进行两次主场、一次客场比赛的那五支球队。完成此事的方式数为 \(\binom{9}{5}\)。一旦确定，我们可以类似例 1.43 那样进行，只是现在我们需要用不同的符号来表示对同一支球队的主场比赛与客场比赛。因此，没有任何符号出现超过两次，而出现两次的符号个数为 \(4\cdot2+9=17\)。所以可能的赛程总数为 \[\binom{9}{5}\cdot\frac{71!}{2^{17}}.\]

1. 第一步选哪 5 支球队享受"两主一客"的待遇：\(\binom{9}{5}\) 种。
2. 第二步把全部比赛排成赛程序列。重复出现的比赛要用相同符号，于是用多重排列处理：总比赛数记为它们的全排列 \(71!\) 再除以每种重复符号的"内部排列"。
3. 出现两次的符号共 17 个（对应 \(4\cdot2+9=17\) 的计数），每个贡献一个因子 \(2!=2\) 需要除去，合计除以 \(2^{17}\)。
4. 两步相乘（乘法原理）：\(\binom{9}{5}\cdot\dfrac{71!}{2^{17}}\)。

习题 21

\(S\) 有 \(2^n\) 种选择，\(T\) 有 \(2^n\) 种选择，所以 \((S,T)\) 有 \(2^n\cdot2^n=4^n\) 种选择。

1. \([n]\) 的子集共 \(2^n\) 个（习题 13），故 \(S\) 任取一子集有 \(2^n\) 种。
2. \(T\) 独立地也任取一子集，\(2^n\) 种。
3. 有序对 \((S,T)\)：乘法原理 \(2^n\cdot2^n=4^n\)。

习题 22

(a) 这个数是 \(3^n\)。事实上，\([n]\) 的每个元素可以：在 \(T\) 中，或在 \(S\) 中但不在 \(T\) 中，或不在 \(S\) 中。

(b) 这个数仍然是 \(3^n\)。事实上，\(R\) 与 \(U\) 不相交当且仅当 \(R\) 的补集 \(S\) 包含 \(U\)。结论由 (a) 得出。

1. (a) 题为：数满足 \(T\subseteq S\subseteq[n]\) 的有序对 \((S,T)\)。对每个元素 \(i\)，它的归属恰有三种互斥情形：① \(i\in T\)（自动 \(\in S\)）；② \(i\in S,\ i\notin T\)；③ \(i\notin S\)（自动 \(\notin T\)）。\(n\) 个元素各独立三选一，得 \(3^n\)。
2. (b) 题为：数不相交的有序对 \((R,U)\)（即 \(R\cap U=\varnothing\)）。令 \(S=[n]\setminus R\) 为 \(R\) 的补集。则 \(R\cap U=\varnothing\) ⇔ \(U\subseteq S\)。
3. 给定不相交对 \((R,U)\) 与满足 \(U\subseteq S\) 的对 \((S,U)\) 之间是一一对应（\(R\) 与 \(S\) 互为补集，可逆）。后者正是 (a) 中的对（把 \(S,U\) 当作 \(S,T\)），共 \(3^n\) 个，故答案仍为 \(3^n\)。

习题 23

让网球选手们排成一列。这一列可以用 \((2n)!\) 种方式排成；设所有这些可能的队列构成集合 \(T\)。然后，让队列中第一人与第二人配对、第三人与第四人配对，依此类推。设 \(S\) 为以此方式形成的配对方案集合。我们断言 \(S\) 的每个元素对应 \(T\) 中 \(n!\,2^n\) 个不同元素。事实上，若我们置换一个 \(T\) 中队列里的各对，对应的 \(S\) 中配对不变，这解释了断言中的 \(n!\) 因子。此外，若我们交换 \(T\) 中队列里第 \(2i-1\) 个人与第 \(2i\) 个人，对应的 \(S\) 中配对也不变，这解释了断言中的 \(2^n\) 因子。因此，由除法原理（division principle），匹配网球选手的方式数为 \[|S|=\frac{|T|}{d}=\frac{(2n)!}{n!\,2^n}.\]

1. 先把 \(2n\) 人排成一列：\((2n)!\) 种，记为集合 \(T\)。再规定第 1、2 人一对，第 3、4 人一对……得到一个配对方案，落在 \(S\) 中。
2. 一个配对方案会被多少种队列产生？两类"无关紧要的重排"：
3. ① 把 \(n\) 对整块地重新排序，配对结果不变 → 贡献 \(n!\) 倍。
4. ② 每一对内部交换两人顺序，配对结果不变 → 每对 2 种、\(n\) 对共 \(2^n\) 倍。
5. 故每个配对方案恰对应 \(d=n!\,2^n\) 个队列。由除法原理 \(|S|=\dfrac{(2n)!}{n!\,2^n}\)。

习题 24

设 \(x_n=\dfrac{n!}{(n/r)^n}\)。那么 \[R_n=\frac{x_{n+1}}{x_n}=r\cdot\left(\frac{n}{n+1}\right)^n=r\,a_n.\tag{1.14}\] 由习题所给提示可知，序列 \(a_n\) 的每一项都大于 \(1/e\)。由于我们知道 \(e1\)，也就是说，序列 \(n!\) 比序列 \((n/r)^n\) 增长得更快。由于 \(1!>1/r\)，结论成立。

1. 令 \(x_n=\dfrac{n!}{(n/r)^n}\)，它是"\(n!\) 与 \((n/r)^n\) 之比"。看相邻比 \(R_n=\dfrac{x_{n+1}}{x_n}\)。
2. 代入化简：\(\dfrac{x_{n+1}}{x_n}=\dfrac{(n+1)!}{((n+1)/r)^{n+1}}\cdot\dfrac{(n/r)^n}{n!}=(n+1)\cdot\dfrac{(n/r)^n}{((n+1)/r)^{n+1}}=r\left(\dfrac{n}{n+1}\right)^n\)。
3. 即 \(R_n=r\,a_n\)，其中 \(a_n=\left(\dfrac{n}{n+1}\right)^n=\left(1+\tfrac1n\right)^{-n}\)；要点是 \(a_n>1/e\)。
4. 由 \(\left(1+\tfrac1n\right)^n1/e\)。再结合 \(er/e>1\)。
5. \(R_n>1\) 表示 \(x_n\) 严格递增；又起点 \(x_1=\dfrac{1!}{(1/r)^1}=r>1\)（因 \(r>e>1\)，即 \(1!>1/r\)），故对一切 \(n\) 有 \(x_n>1\)，即 \(n!>(n/r)^n\)，\(n!\) 增长更快，结论成立。

习题 25

(a) 由于我们要走 \(2n\) 步，其中 \(n\) 步向东，故 \(a_n=\binom{2n}{n}\)。

(b) 设 \(p\) 是被 \(b_n\) 计数的一条路径。那么 \(p\) 必然触及直线 \(y=x+1\)；设 \(X\) 是它第一次触及该直线的点。我们的双射 \(f\) 会取 \(p\) 介于 \((0,0)\) 与 \(X\) 之间的起始部分，并将其关于直线 \(y=x+1\) 作反射。这会把 \(p\) 变成一条路径 \(f(p)\in T\)。容易看出 \(f\) 是双射，因为每条路径 \(t\in T\) 都必与 \(y=x+1\) 相交，因此点 \(X\) 总能被还原。参见图 1.12 的例子。

(c) 由于我们要走 \(2n\) 步、其中 \(n+1\) 步向东，故 \(|T|=\binom{2n}{n+1}=\binom{2n}{n-1}\)。因此 (b) 蕴含 \(|S|=b_n=\binom{2n}{n-1}\)，于是由 (a)， \[c_n=a_n-b_n=\binom{2n}{n}-\binom{2n}{n-1}.\tag{1.15}\]

1. (a) 从 \((0,0)\) 到 \((n,n)\)：共 \(2n\) 步，其中向东 \(n\) 步、向北 \(n\) 步。选哪 \(n\) 步向东即 \(\binom{2n}{n}=a_n\)。
2. (b) \(b_n\) 数"坏路径"——那些越过对角线、触及 \(y=x+1\) 的路径。把它从起点到首次触线点 \(X\) 的一段沿 \(y=x+1\) 反射。反射后起点 \((0,0)\) 变成 \((-1,1)\)，整条路径变成 \(T\)：从 \((-1,1)\) 到 \((n,n)\) 的路径。
3. 这个反射可逆（任何 \(T\) 中路径都必过 \(y=x+1\)，第一次过线处即 \(X\)，反射回去复原），所以是双射 → \(b_n=|T|\)。
4. (c) 从 \((-1,1)\) 到 \((n,n)\)：向东 \(n+1\) 步、向北 \(n-1\) 步，共 \(2n\) 步，\(|T|=\binom{2n}{n+1}=\binom{2n}{n-1}\)。
5. 故"好路径"数 \(c_n=a_n-b_n=\binom{2n}{n}-\binom{2n}{n-1}\)，这正是第 \(n\) 个卡塔兰数（Catalan number）\(\dfrac{1}{n+1}\binom{2n}{n}\)。

习题 26

这一结果最早由 Bertrand（他只给出了证明梗概）和 André 于 1887 年证明。该问题常被称为选票问题（ballot problem）。我们对 \(a+b\) 用归纳法证明命题，初始情形 \(a+b=0\) 易于验证。注意当 \(b=0\) 或 \(kb=a\)（即 \((a,b)\) 位于允许区域的某条边界线上）时命题也成立。

由加法原理，从 \((0,0)\) 到 \((a,b)\) 具有所述性质的格点路径数，必然等于从 \((0,0)\) 到 \((a-1,b)\) 与从 \((0,0)\) 到 \((a,b-1)\) 的此类路径数之和。因此，利用归纳假设，从 \((0,0)\) 到 \((a,b)\) 具有所述性质的路径数为 \[\frac{a-1+b}{a+b-1}\cdot\frac{a-k(b-1)}{a-1+b}\;+\;\frac{a+b-1}{a+b-1}\cdot\frac{a-1-kb}{a}\,(\cdots).\] 于是只要能证明恒等式 \[\binom{a+b-1}{a}\frac{a-k(b-1)}{a+b-1}+\binom{a-1+b}{a-1}\frac{a-1-kb}{a+b-1}=\binom{a+b}{a}\frac{a-kb}{a+b}\] 即可。两边都除以 \(\binom{a+b}{a}\)、再乘以 \((a+b)(a+b-1)\)，便得到一个只需常规代数即可证明的恒等式。

1. 命题断言：在某约束（路径始终满足 \(x>k\,y\) 之类的"领先"条件）下，到 \((a,b)\) 的合法路径数有一个闭式 \(\dfrac{a-kb}{a+b}\binom{a+b}{a}\)。
2. 归纳基底：\(a+b=0\) 即起点，1 条路径，公式取值为 1，成立；边界 \(b=0\) 或 \(a=kb\) 也直接验证。
3. 归纳步：任一到 \((a,b)\) 的路径，最后一步要么自 \((a-1,b)\) 向东、要么自 \((a,b-1)\) 向北。两类不相交，加法原理给出"到 \((a,b)\) = 到 \((a-1,b)\) + 到 \((a,b-1)\)"。
4. 把这两项各自代入归纳假设的闭式，通分整理。两边除以 \(\binom{a+b}{a}\) 并乘 \((a+b)(a+b-1)\) 后，化为一条仅靠移项、合并同类项即可验证的代数恒等式，归纳完成。

习题 27

用二项式定理展开 \((1+x)^n\)，然后求导，再两边同乘以 \(x\)，得到 \[x\,n(1+x)^{n-1}=\sum_{k=1}^{n}k\binom{n}{k}x^{k}.\] 令 \(x=1/n\)，得到公式 \[\left(1+\frac1n\right)^{n-1}=\sum_{k=1}^{n}\binom{n}{k}\frac{k}{n^{k}}.\tag{1.16}\]

1. 从 \((1+x)^n=\displaystyle\sum_{k=0}^n\binom{n}{k}x^k\) 出发。
2. 两边对 \(x\) 求导：左边 \(n(1+x)^{n-1}\)，右边 \(\displaystyle\sum_{k=1}^n k\binom{n}{k}x^{k-1}\)（\(k=0\) 项求导为 0，故从 \(k=1\) 起）。
3. 两边同乘 \(x\)：\(x\,n(1+x)^{n-1}=\displaystyle\sum_{k=1}^n k\binom{n}{k}x^{k}\)。
4. 代入 \(x=1/n\)：左边 \(\dfrac1n\cdot n\left(1+\tfrac1n\right)^{n-1}=\left(1+\tfrac1n\right)^{n-1}\)；右边 \(\displaystyle\sum_{k=1}^n k\binom{n}{k}\dfrac{1}{n^{k}}=\sum_{k=1}^n\binom{n}{k}\dfrac{k}{n^{k}}\)，即 (1.16)。

习题 28

首先，利用公式 \(\binom{n+1}{k+1}=\binom{n}{k}+\binom{n}{k+1}\)，把右边的表达式拆开： \[\sum_{k=1}^{n}\binom{n+1}{k+1}\frac{k}{n^{k}}=\sum_{k=1}^{n}\binom{n}{k}\frac{k}{n^{k}}+\sum_{k=1}^{n}\binom{n}{k+1}\frac{k}{n^{k}}.\tag{1.17}\] 上一题的结果为右边第一项提供了闭式。第二项可如下变形： \[\sum_{k=1}^{n}\binom{n}{k+1}\frac{k}{n^{k}}=n\sum_{k=1}^{n}\binom{n}{k+1}\frac{k}{n^{k+1}}=n\sum_{k=1}^{n}\binom{n}{k+1}\frac{k+1}{n^{k+1}}-n\sum_{k=1}^{n}\binom{n}{k+1}\frac{1}{n^{k+1}}.\] 现在注意，最后一行第一项中的和几乎与上一题的表达式相同，因此它等于 \(\left(1+\tfrac1n\right)^{n-1}-1\)。该行第二项中的和，由二项式定理等于 \(\left(1+\tfrac1n\right)^{n}-2\)（因为下标为 0 和 1 的项缺失）。这表明 (1.16) 右边的最后一项等于 \[n\left(\left(1+\frac1n\right)^{n-1}-1\right)-n\left(\left(1+\frac1n\right)^{n}-2\right)=n-\left(1+\frac1n\right)^{n}.\] 证明现在立即完成，因为我们在上一题已算出 (1.16) 左边第一项恰为 \(\left(1+\tfrac1n\right)^{n-1}\)。

1. 目标是化简一个含 \(\binom{n+1}{k+1}\) 的求和。先用帕斯卡公式 \(\binom{n+1}{k+1}=\binom{n}{k}+\binom{n}{k+1}\) 把它劈成两个求和，即 (1.17)。
2. 第一个求和 \(\sum\binom{n}{k}\dfrac{k}{n^k}\) 正是习题 27 的左边，已知 \(=\left(1+\tfrac1n\right)^{n-1}\)。
3. 第二个求和处理分母与下标错位：把 \(\dfrac{k}{n^k}\) 写成 \(n\cdot\dfrac{k}{n^{k+1}}=n\left(\dfrac{k+1}{n^{k+1}}-\dfrac{1}{n^{k+1}}\right)\)，拆成两项。
4. 第一拆项的和与习题 27 形式相同（指标平移后），等于 \(\left(1+\tfrac1n\right)^{n-1}-1\)；第二拆项由二项式定理 \(\sum_{j}\binom{n}{j}\dfrac{1}{n^{j}}=\left(1+\tfrac1n\right)^n\)，去掉缺失的 \(j=0,1\) 两项后为 \(\left(1+\tfrac1n\right)^{n}-2\)。
5. 合并：\(n\big[(1+\tfrac1n)^{n-1}-1\big]-n\big[(1+\tfrac1n)^{n}-2\big]=n-(1+\tfrac1n)^n\)。把各块代回，恒等式两边相等，证毕。

习题 29

无论组织者怎么安排，确定一名冠军总是需要 84 场比赛。事实上，需要淘汰 84 人，而淘汰 84 人需要 84 场比赛。

1. 单淘汰赛中，每场比赛恰好淘汰 1 人。
2. 85 名选手要决出 1 名冠军，意味着另外 84 人都必须被淘汰。
3. "淘汰 84 人"与"打 84 场"是一一对应（每场淘汰 1 人、每被淘汰 1 人对应 1 场），所以恰需 84 场，与赛制（轮空与否、对阵如何）无关。

习题 30

胜场数的可能值为 \(0,1,2,\dots,15\)。这是一个含 16 个数的列表，所以它们每一个都必然恰好作为某位选手的胜场数出现。因此，冠军赢了 15 场、亚军赢了 14 场、季军赢了 13 场，依此类推，第六名的人赢了 10 场。

1. 16 名选手两两各赛一场（循环赛 round-robin），每人对手 15 个，故每人胜场在 \(0\) 到 \(15\) 之间。
2. 题设这 16 人的胜场数互不相同。\(0\) 到 \(15\) 恰好是 16 个不同的可能值，16 人占满 16 个值 → 每个值恰被一人取到。
3. 于是名次与胜场一一排好：第 1 名 15 胜、第 2 名 14 胜……第 \(t\) 名 \(16-t\) 胜。
4. 第六名：\(16-6=10\) 胜。

习题 31

左边把 \(\bigcup_{i=1}^{k}A_i\) 的每个元素恰好计数一次。右边计数同样这些元素，但若 \(x\) 出现在 \(t\) 个不同的 \(A_i\) 中，则它被计数 \(t\) 次。由于对 \(\bigcup_{i=1}^{k}A_i\) 的所有元素都有 \(t\ge1\)，命题得证。

1. 左边按定义把并集中每个元素只数一次。
2. 右边 \(\sum|A_i|\) 把元素 \(x\) 数了"它所属集合的个数" \(t_x\) 次。
3. 并集中每个元素至少属于一个 \(A_i\)，即 \(t_x\ge1\)。所以右边对每个元素的计数 \(\ge\) 左边的 1，逐项相加得 \(\sum|A_i|\ge|\bigcup A_i|\)。

习题 32

证明与鸽笼原理（pigeonhole principle）的证明非常相似。只需把 (1.11) 替换为不等式链 \[|A_1\cup A_2\cup\cdots\cup A_k|\le|A_1|+|A_2|+\cdots+|A_k|\le kr.\] 上一题表明这个不等式链确实成立。证明的其余部分不变。

1. 设有 \(k\) 个盒子 \(A_1,\dots,A_k\)，每个容量至多 \(r\)（即 \(|A_i|\le r\)）。
2. 第一个不等号来自习题 31（并集大小不超过各部分之和）；第二个不等号来自 \(|A_i|\le r\)，\(k\) 项相加 \(\le kr\)。
3. 于是若总元素数 \(>kr\)，则不可能全装进这 \(k\) 个盒子，矛盾——这正是广义鸽笼原理的结论。其余推理与标准鸽笼证明相同。

习题 33

我们断言只需考虑那些第一坐标为 1、2、3 或 4，且第二坐标至少为 1、至多为 82 的点。换言之，我们考虑一个矩形网格中的点，它有 82 行、每行长 4。

由于每行有四个点，每行共有 \(3^4=81\) 种可能的染色。既然有 82 行，就会有两行的染色完全相同。最后，由于我们只能用三种颜色去染四个点，每行（因而另一行也）中至少有一种颜色会重复。因此，会出现四个同色点，它们构成一个矩形。

1. 只取一个 \(4\times82\) 的子网格：横坐标 \(\in\{1,2,3,4\}\)（4 列），纵坐标 \(\in\{1,\dots,82\}\)（82 行）。
2. 每行 4 个点，每点 3 选 1，故一行的染色样式共 \(3^4=81\) 种。
3. 82 行 > 81 种样式 → 鸽笼原理：必有两行染色样式完全相同。
4. 在每行的 4 个点里用 3 种颜色 → 鸽笼原理：必有两点同色。这两点所在的两列，在那两行同色样式相同 → 四个同色点恰好构成矩形的四个角。

习题 34

我们这些整数可能的素因子是 2、3、5、7。所以它们都形如 \(2^a3^b5^c7^d\)，其中指数为整数。就被 3 整除而言，每个指数可以形如 \(3k\)、\(3k+1\) 或 \(3k+2\)。所以 \((a,b,c,d)\) 可以有 \(3^4=81\) 种不同的"类型"。因此，由鸽笼原理，在我们的 175 个整数中存在三个整数，其 \((a,b,c,d)\) 的类型相同。这三个整数的乘积将是一个完全立方数，因为它将包含 2、3、5、7 中每一个、且其指数都被 3 整除。

1. 这些整数只含素因子 2、3、5、7，故都写成 \(2^a3^b5^c7^d\)。一个数是完全立方数 ⇔ 四个指数都是 3 的倍数。
2. 给每个数贴"类型"标签 \((a\bmod3,\,b\bmod3,\,c\bmod3,\,d\bmod3)\)，每个分量 3 选 1，共 \(3^4=81\) 种类型。
3. 175 个数、81 种类型，因 \(175>2\cdot81=162\)，由鸽笼原理至少有一种类型出现 \(\ge3\) 次，取其中三个数。
4. 这三个数同类型，把它们相乘，每个素因子的指数 = 三个同余 \(\bmod3\) 的指数之和 \(\equiv 3\cdot(\text{同一余数})\equiv0\pmod3\)，故乘积每个指数都被 3 整除，是完全立方数。

返回 全书目录