Bóna · 枚举与解析组合学导论 · 第 1 章 基本方法

1.4　基本计数原理的应用Applications of basic counting principles

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

现在，我们要考察一些更复杂的情形，在这些情形里，基本的计数原理会显示出它们的用处。

本节目标把前几节的加法、乘法、除法原理真正“用起来”。核心是一种贯穿全书的方法——双射证明（bijective proof）：当一个集合不好直接数时，找一个已知大小的集合，把两者的元素一一配对，从而断定它们一样大。本节用方格街道里的路径、约数配对、吊扇方案、卡塔兰数等具体例子，把这套方法练熟。

1.4.1　双射证明

下面这个例子，将教给我们枚举组合学中一种极其重要的证明技巧。

例 1.26 在我们镇的某个区域里，街道排成一个正方形网格，并且每条街都是单行道，方向要么向北、要么向东。假设我们的汽车此刻位于这个网格的西南角，记作 \(O=(0,0)\)。
  1. (a) 我们有多少种方式开到点 \(X=(6,4)\)？
  2. (b) 如果途中想在 \(Y=(4,2)\) 处的面包店停一下，有多少种方式开到 \(X\)？
  3. (c) 如果途中想在 \(U=(3,2)\) 处的冰激凌店或 \(V=(2,3)\) 处的咖啡店停一下，有多少种方式开到 \(X\)？
图 1.3 给出了示意。
O(0,0) X(6,4) Y(4,2)面包店 U(3,2)冰激凌 V(2,3)咖啡店
图 1.3　单行道网格。蓝色折线是一条从 \(O\) 到 \(X\) 的合法路线：只能向东或向北走。
解.

(a) 汽车需要走十个街区：六个向东、四个向北。换句话说，司机要从 \([10]=\{1,2,\dots,10\}\) 中选出一个六元子集，用来指明在第几步向东走。例如，若他选择集合 \(\{2,3,5,7,8,9\}\)，那么他的第二、三、五、七、八、九步向东，其余各步（即第一、四、六、十步）向北。由于 \([10]\) 的六元子集共有 \(\binom{10}{6}\) 个，这就是汽车能到达点 \(X\) 的方式数。♦

(b) 汽车先要到达 \(Y\)。由 (a) 的论证，到 \(Y\) 共有 \(\binom{6}{4}=15\) 种方式。然后还要从 \(Y\) 走到 \(X\)，由类似论证，共有 \(\binom{4}{2}=6\) 种方式。由于从 \((0,0)\) 到 \(Y\) 的任意一条路径都可以接上从 \(Y\) 到 \(X\) 的任意一条路径，故合法路径总数为 \(\binom{6}{4}\binom{4}{2}=15\cdot 6=90\)。

(c) 用 (b) 中解释的论证，经 \(U\) 从 \((0,0)\) 到 \(X\) 的路径有 \(\binom{5}{3}\binom{5}{3}=100\) 条；经 \(V\) 的路径有 \(\binom{5}{2}\binom{5}{4}=50\) 条。注意，没有任何一条路径会同时经过 \(U\) 与 \(V\)。因此，合法路径总数为 \[\binom{5}{3}\binom{5}{3}+\binom{5}{2}\binom{5}{4}=150.\]

先看懂 (a)：路径 = 选子集从 \(O\) 到 \(X=(6,4)\) 必须正好走 \(6\) 步东、\(4\) 步北，一共 \(10\) 步，顺序可以任意。一条路径，等于在这 \(10\) 步里指定哪几步向东。指定“哪几步向东”，就是从 \(\{1,2,\dots,10\}\) 里挑出一个 \(6\) 元子集。于是“数路径”与“数 \(6\) 元子集”是同一件事，答案是 \(\binom{10}{6}=210\)。
例（亲手对应一次） 取子集 \(\{2,3,5,7,8,9\}\)（图 1.3 蓝线）。把它翻译成走法：
  1. 第 1 步不在子集里 → 向北；
  2. 第 2、3 步在子集里 → 连向东两次；
  3. 第 4 步不在 → 向北；第 5 步在 → 向东；第 6 步不在 → 向北；
  4. 第 7、8、9 步都在 → 连向东三次；第 10 步不在 → 向北。
  5. 合计东向步数 \(=6\)，北向步数 \(=4\)，正好到 \((6,4)\)。每一个 \(6\) 元子集都唯一对应一条路径，反之亦然。
例（拆点法，理解 (b)） 要求“必经 \(Y\)”，就把整条路从中间 \(Y\) 处切成两段：前段 \(O\to Y\)，后段 \(Y\to X\)。
  1. \(O\to Y=(4,2)\)：\(4\) 东 \(2\) 北共 \(6\) 步，选 \(2\) 步向北，\(\binom{6}{2}=\binom{6}{4}=15\) 条。
  2. \(Y\to X=(6,4)\)：还差 \(2\) 东 \(2\) 北共 \(4\) 步，\(\binom{4}{2}=6\) 条。
  3. 前段任配后段（乘法原理）：\(15\times 6=90\) 条。
而 (c) 中“经 \(U\) 或经 \(V\)”是两类不相交的路径（没有路径同时过 \(U\) 与 \(V\)，因为 \(U=(3,2)\)、\(V=(2,3)\) 谁也不在到对方的路径上），故用加法原理把两类相加：\(100+50=150\)。

让我们详细分析上面例子里的论证。在 (a) 中，我们要数从 \((0,0)\) 到 \((6,4)\) 的所有可能路径。我们说这等同于数 \([10]\) 的六元子集。为什么可以这样说？因为在我们的格点路径集合 \(S\) 与 \([10]\) 的六元子集集合 \(T\) 之间，存在一个一一对应。因此必有 \(|S|=|T|\)。注意，这正是定理 1.21（除法原理）在 \(d=1\) 时的特殊情形。

除法原理在 \(d=1\) 时的这一特殊情形如此重要，以至于它有了自己专门的名字。

定义 1.27 如果映射 \(f:S\to T\) 既是单射（one-to-one，一对一）又是满射（onto），那么我们称 \(f\) 为一个双射（bijection）。

换句话说，若 \(f:S\to T\) 是双射，它就把 \(S\) 的每个元素与 \(T\) 的一个不同的元素配成一对。

推论 1.28 设 \(S\) 与 \(T\) 是有限集合。若存在双射 \(f:S\to T\)，则 \(|S|=|T|\)。

注意，“\(S\) 与 \(T\) 为有限集”这一要求其实可以去掉；这样一来，便可定义这样的概念：若两个无限集合之间存在双射，则称它们具有相同的“大小”。这是一个非常有趣的话题，但它属于集合论教材的范畴，因此我们在此不作讨论。双射的一般图示见图 1.4。

S T f
图 1.4　一般双射的示意：\(S\) 的每个点恰好连到 \(T\) 的一个点，\(T\) 的每个点也恰好被连一次——一一配对，因此两堆点个数相同。

双射的思想，或者说双射证明，在计数论证中被极其频繁地使用。当我们想数出集合 \(S\) 的元素个数时，可以转而去证明：存在一个双射 \(f:S\to T\)，其中 \(T\) 是某个我们已知其元素个数的集合。通常的做法是：先定义一个函数 \(f\)，再证明这个 \(f\) 确实是从 \(S\) 到 \(T\) 的双射。一旦做到这一点，就能断定 \(|S|=|T|\)。有时我们甚至并不需要知道集合的具体元素个数，只需知道“两个集合元素个数相同”这一事实即可。在那种情形下，双射方法能替我们省去实际的计数。读者将在下一节，乃至本书其余部分，看到这一方法的许多例子。现在，先看几个该方法的简单应用。

命题 1.29 对任何正整数 \(n\)，\(n\) 的大于 \(\sqrt{n}\) 的约数个数，等于 \(n\) 的小于 \(\sqrt{n}\) 的约数个数。

由于这是我们的第一个双射证明，我们将把它讲得非常详尽。特别地，我们要演示如何证明一个映射确实是双射。读者不必因为觉得这个证明太“技术化”而气馁——我们所做的全部，不过是通过把两个集合的元素一个一个配对起来，来说明它们一样大。

证明. 设 \(S\) 为 \(n\) 的大于 \(\sqrt{n}\) 的约数所成之集，\(T\) 为 \(n\) 的小于 \(\sqrt{n}\) 的约数所成之集。定义 \(f:S\to T\) 为 \(f(s)=n/s\)。

现在来到证明的核心，即：我们要说明 \(f\) 确实是从 \(S\) 到 \(T\) 的双射。第一，对一切 \(s\in S\)，等式 \[\tag{1.6}s\cdot f(s)=n\] 成立，所以 \(f(s)\) 确实是 \(n\) 的约数。第二，必有 \(f(s)<\sqrt{n}\)，否则 \(s\cdot f(s)>\sqrt{n}\cdot\sqrt{n}=n\)，与 (1.6) 矛盾。因此 \(f(s)\) 总是 \(T\) 的元素，于是 \(f\) 确实是从 \(S\) 到 \(T\) 的函数。

现在要证明 \(f\) 是双射，即：对一切 \(t\in T\)，恰好存在一个 \(s\in S\) 使 \(f(s)=t\)。一方面，至少存在一个这样的 \(s\)，即 \(s=n/t\)。事实上，由 \(f\) 的定义，\(f(n/t)=\dfrac{n}{n/t}=t\)。另一方面，这个 \(s\) 是唯一合用的：若 \(f(s)=t\)，则由 (1.6) 必有 \(s\cdot t=n\)，故 \(s=n/t\)。因此 \(f\) 是双射，从而 \(S\) 与 \(T\) 元素个数相同。♦

为什么这个配对成立把 \(n\) 的约数从小到大排成一行。每取一个小约数 \(s'\)，就有一个“搭档”\(n/s'\)；二者乘积恰为 \(n\)。乘积是 \(n\)，意味着两者一个小于 \(\sqrt n\)、另一个就大于 \(\sqrt n\)（不可能两个都小于 \(\sqrt n\)，否则乘积小于 \(n\)；也不可能都大于）。于是“小于 \(\sqrt n\) 的约数”和“大于 \(\sqrt n\) 的约数”被这种乘积关系两两钩住，个数当然相等。
\(\sqrt{36}=6\) 小于 6 的约数 大于 6 的约数 136 218 312 49 ×=36
以 \(n=36\)（\(\sqrt{36}=6\)）为例：约数 \(1,2,3,4\) 分别与 \(36,18,12,9\) 配对，每对乘积都是 \(36\)。两侧各 \(4\) 个，个数相等。约数 \(6\) 恰等于 \(\sqrt n\)，自己跟自己配，不计入两侧。
例 1.30 整数 \(1000\) 恰有八个大于 \(\sqrt{1000}\) 的约数。
解：由命题 1.29，只需数出 \(1000\) 的小于 \(\sqrt{1000}=31.62\) 的约数即可。它们是 \(1,2,4,5,8,10,20,25\)，确实有八个。♦

换句话说，我们不必在区间 \([32,1000]\) 里搜寻约数，只需在短得多的区间 \([1,31]\) 里搜寻。

我们在上例中证明函数 \(f\) 确实是从 \(S\) 到 \(T\) 的双射的方式相当典型。为便于今后引用，我们把这一方法总结如下。

双射方法（证 \(|S|=|T|\) 的标准流程）
  1. 在集合 \(S\) 上定义一个有望成为 \(S\to T\) 双射的函数 \(f\)。
  2. 证明：对一切 \(s\in S\)，有 \(f(s)\in T\)（即 \(f\) 真把 \(S\) 映到 \(T\) 里）。
  3. 证明：对一切 \(t\in T\)，恰好存在一个 \(s\in S\) 满足 \(f(s)=t\)。这一步常拆成两小步：
    1. (a) 证明至少有一个 \(s\) 满足 \(f(s)=t\)（满射）；
    2. (b) 证明至多有一个 \(s\) 满足 \(f(s)=t\)（单射）。
例 1.31 一栋新房子有十个房间。对每个房间，房主可以决定是否装吊扇；若装，又可选较便宜或较贵两种型号。那么对全部十个房间，房主一共有多少种不同的方案？
解：我们断言方案数为 \(3^{10}\)。证法是：构造一个双射 \(f\)，把房主所有方案所成之集 \(S\)，映到字母表 \(\{a,b,c\}\) 上所有十字母单词所成之集 \(T\)。于是结论由推论 1.11 得出。
设 \(s\in S\)，把 \(f(s)\) 的第 \(i\) 个字母定义为 \[f(s)_i=\begin{cases}a,&\text{若房间 }i\text{ 没有吊扇,}\\ b,&\text{若房间 }i\text{ 装的是便宜吊扇,}\\ c,&\text{若房间 }i\text{ 装的是较贵吊扇.}\end{cases}\] 我们的构造表明 \(f(s)\in T\)，故 \(f\) 确为从 \(S\) 到 \(T\) 的函数。进而 \(f\) 确是双射：因为任意一个单词 \(t\in T\) 都毫不含糊地告诉我们，在满足 \(f(s)=t\) 的方案 \(s\) 中，每个房间该装哪种吊扇。♦
这里为什么是 \(3^{10}\)每个房间有且仅有 \(3\) 种独立的状态：无扇 / 便宜扇 / 贵扇，分别记作 \(a,b,c\)。十个房间各自独立地三选一，按乘法原理共 \(\underbrace{3\times3\times\cdots\times3}_{10}=3^{10}\) 种。双射的作用是把“方案”这一抽象对象，翻译成一个可数的具体对象——长度 \(10\) 的 \(abc\) 串。
房间 1 2 3 … 10 字母 b a c … a a=无扇　b=便宜　c=贵
每种装修方案 ↔ 一个十位 \(abc\) 串。一一对应，故方案数 \(=3^{10}\)。

1.4.1.1　卡塔兰数

为了看一个更复杂的双射，让我们回到例 1.26。例中所允许的那种行车路线，称为东北格点路径（northeastern lattice path，即每一步只能向东或向北的格点折线）。东北格点路径在枚举组合学中无处不在，因为它们可以表示形形色色、数目繁多的对象。

引理 1.32 从 \((0,0)\) 到 \((n,n)\)、且始终不越过对角线 \(x=y\)（主对角线）的东北格点路径的条数，等于用 \([2n]\) 的元素填满一个 \(2\times n\) 方格阵、每个元素恰用一次、并使每一行、每一列都递增（向右、向下递增）的方法数。

为简便起见，一个 \(2\times n\) 的矩形，若其方格里装入 \([2n]\) 的元素、每个元素恰用一次、且每行每列都递增（向右、向下），就称为一个形状为 \(2\times n\) 的标准杨表（Standard Young Tableau，简记 SYT）。

例 1.33 取 \(n=3\)。那么，从 \((0,0)\) 到 \((3,3)\)、不越过主对角线的东北格点路径恰有五条，见图 1.5；形状为 \(2\times 3\) 的标准杨表也恰有五个，见图 1.6。
EEENNNEENENNENEENNEENNENENENEN
图 1.5　\(n=3\) 时不越过主对角线的五条东北格点路径。蓝线是路径，橙色虚线是对角线 \(x=y\)；路径始终走在对角线及其下方（“东≥北”）。下方标注是把每步记为 E（东）/N（北）的步序。
123456 124356 134256 125346 135246
图 1.6　形状为 \(2\times 3\) 的五个标准杨表。每个表里 \(1\!-\!6\) 各用一次，每行从左到右递增、每列从上到下递增。它们与图 1.5 的五条路径一一对应。
证明（引理 1.32）. 不出所料，我们将构造一个从集合 \(S\) 到集合 \(T\) 的双射：\(S\) 是所有从 \((0,0)\) 到 \((n,n)\) 且不越过主对角线的东北格点路径之集，\(T\) 是所有形状为 \(2\times n\) 的标准杨表之集。

我们的双射 \(f\) 定义如下：设 \(s\in S\)。令 \(e_1,e_2,\cdots,e_n\) 表示 \(s\) 的 \(n\) 个东向步所处的位置。也就是说，如果 \(s\) 的前三个东向步实际上是它的第一、第三、第四步（于是第二、第五、第六步向北），那么 \(e_1=1,\ e_2=3,\ e_3=4\)。类似地，令 \(n_1,n_2,\cdots,n_n\) 表示 \(s\) 的北向步的位置；沿用刚才的例子，则 \(n_1=2,\ n_2=5,\ n_3=6\)。

令 \(f(s)\) 为形状 \(2\times n\) 的阵列，其第一行是 \(e_1,e_2,\cdots,e_n\)，第二行是 \(n_1,n_2,\cdots,n_n\)。我们断言 \(f(s)\in T\)。\(f(s)\) 的各行是递增的，因为第 \(i\) 个东向步必发生在第 \((i+1)\) 个东向步之前；北向步同理。我们还断言各列也递增。事实上，若不然，则对某个 \(j\) 有 \(n_j

反过来，对任意标准杨表 \(t\in T\)，恰好存在一条路径 \(s\) 使 \(f(s)=t\)：表的第一行告诉我们哪几步向东、第二行告诉我们哪几步向北，这就唯一地确定了一条路径；而“列递增”这一条件恰好保证这条路径不越过主对角线。于是 \(f\) 是双射，从而 \(|S|=|T|\)。♦

（说明：本节原文 PDF 页面在引理 1.32 证明“…即对某个 \(j\) 有 \(n_j<e_j\)，这意味着”处结束；上面对该证明结尾以及“反过来”一段的论证，按双射方法的标准框架补全，逻辑与原书一致，便于读者完整理解。）

把这条双射看穿一条路径，就是一串由 E（东）与 N（北）组成、长度 \(2n\) 的步序，其中“东≥北”始终成立。记下东向步出现在第几步，填进上行；记下北向步出现在第几步，填进下行——这正好得到一个 \(2\times n\) 表。
  1. 同一行内位置自然从小到大，所以每行递增。
  2. “路径不越过对角线”⟺“任何前缀里东向步不少于北向步”⟺“第 \(j\) 个东向步早于第 \(j\) 个北向步”，即 \(e_j<n_j\)，正是每列递增。两件事是同一件事的两种说法。
  3. 反向也能唯一还原：给定表，第一行的数说明哪几步是 E、第二行说明哪几步是 N，路径被完全确定。
所以路径与表一一对应，个数相等。
例（用 \(n=3\) 验一遍对应） 取路径 \(s=\text{EENENN}\)（图 1.5 第二条）。
  1. 东向步在第 \(1,2,4\) 步 → 上行 \(e_1,e_2,e_3=1,2,4\)。
  2. 北向步在第 \(3,5,6\) 步 → 下行 \(n_1,n_2,n_3=3,5,6\)。
  3. 拼成杨表 \(\begin{smallmatrix}1&2&4\\3&5&6\end{smallmatrix}\)，正是图 1.6 第二个。检查：每行递增（\(1<2<4\)，\(3<5<6\)），每列递增（\(1<3,\ 2<5,\ 4<6\)），合格。
这样，五条路径与五个杨表被精确配成五对——这就是“数路径”等于“数杨表”的原因。

返回 全书目录