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

1.2　何时相乘When we multiply

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

在本节里，我们将考虑这样一种情形下所有可能选择的数目：我们所选的对象带有不止一个相关的参数（parameter）。

本节目标说清楚“什么时候要把各部分的个数相乘”。当一个选择由几个互相独立的分项决定（先定第一项、再定第二项……）时，总的方案数等于各分项方案数的乘积。这是与上一节“加法 / 减法”并列的第三块计数地基。

1.2.1　乘法原理

一家汽车经销店出售五种不同的车型，而每一种车型都有七种不同的颜色可选。如果我们只关心一辆车的车型与颜色，那么这家经销店一共向我们提供了多少种不同的选择？

我们用五个大写字母 \(A,B,C,D,E\) 表示这五种车型，用数字 \(1,2,3,4,5,6,7\) 表示这七种颜色。于是每一种可能的选择，都能用“一个大写字母加一个数字”组成的有序对完整地刻画出来。所有选择的清单如下所示。

这里每一行对应某一种确定的车型。由于一共有五行，且每一行包含七种可能的选择，因此选择的总数为 \(5\times 7=35\)。

车型＼色 1 2 3 4 5 6 7 A A1A2A3A4A5A6A7 B B1B2B3B4B5B6B7 C C1C2C3C4C5C6C7 D D1D2D3D4D5D6D7 E E1E2E3E4E5E6E7 5 行 × 7 列 = 35 个格子，每个格子是一种选择
把所有选择排成 5 行 7 列的表格，格子总数 \(=5\times 7=35\)。这正是“相乘”的来由：每行 7 个，共 5 行。

这是下面这条一般性定理的一个例子。

定理 1.6（乘法原理）设 \(X\) 与 \(Y\) 是两个有限集合。那么，满足 \(x\in X\) 且 \(y\in Y\) 的有序对 \((x,y)\) 的个数为 \(|X|\times|Y|\)。
证明. 对于有序对 \((x,y)\) 的第一个元素 \(x\)，有 \(|X|\) 种选择；接着，无论 \(x\) 取了什么，第二个元素 \(y\) 都有 \(|Y|\) 种选择。\(x\) 的每一种选择都能与 \(y\) 的每一种选择配成对，因此命题得证。♦

把证明拆成最小的步子，看清它“为什么对”：

  1. 先定第一项 \(x\)：从 \(X\) 中挑，有 \(|X|\) 种挑法。
  2. 再定第二项 \(y\)：从 \(Y\) 中挑，有 \(|Y|\) 种挑法。关键是这一步的种数与第一步挑了谁无关，永远是 \(|Y|\)。
  3. 于是每一个 \(x\) 都对应一整组 \(|Y|\) 个有序对，互不重复；\(|X|\) 个 \(x\) 合起来就是 \(|X|\) 组，每组 \(|Y|\) 个，总数 \(=\underbrace{|Y|+|Y|+\cdots+|Y|}_{|X|\ \text{个}}=|X|\times|Y|\)。
小例子（先用数字验证） 设 \(X=\{A,B\}\)（\(|X|=2\)），\(Y=\{1,2,3\}\)（\(|Y|=3\)）。把全部有序对列出来：\(A1,A2,A3,\;B1,B2,B3\)，正好 \(6\) 个，而 \(|X|\times|Y|=2\times 3=6\)，吻合。

注意，满足 \(x\in X\) 且 \(y\in Y\) 的所有有序对 \((x,y)\) 构成的集合，称为 \(X\) 与 \(Y\) 的直积（direct product），也叫笛卡儿积（Cartesian product），通常记作 \(X\times Y\)。我们把这些 \((x,y)\) 称为有序对（ordered pairs），因为其中两个元素的顺序是要紧的。也就是说，除非 \(x=y\)，否则 \((x,y)\neq(y,x)\)。

X Y ABC 123 每个绿点 = 一个有序对 (x, y)，共 3×3 = 9 个
笛卡儿积 \(X\times Y\) 可以画成格点：横坐标取自 \(X\)，纵坐标取自 \(Y\)，每个交叉点恰好是一个有序对 \((x,y)\)。点的总数 \(=|X|\times|Y|\)。
为什么强调“有序”有序对 \((x,y)\) 把 \(x\)、\(y\) 放在固定的两个“位置”上：第一位、第二位。位置不同含义就不同，所以 \((A,1)\) 与 \((1,A)\) 是不同的对象（在汽车例子里，前者才表示“车型 A、颜色 1”）。正因为顺序要紧，先选第一项再选第二项的计数才不会重复、不会遗漏。
例 1.7 两位正整数的个数是 \(90\)。
解. 事实上，一个两位正整数无非就是一个有序对 \((x,y)\)，其中 \(x\) 是十位数字、\(y\) 是个位数字。注意 \(x\) 必须取自集合 \(X=\{1,2,\cdots,9\}\)（首位不能是 \(0\)），而 \(y\) 必须取自集合 \(Y=\{0,1,\cdots,9\}\)。因此 \(|X|=9\)，\(|Y|=10\)，由定理 1.6 命题得证。♦
  1. 把“两位数”翻译成“有序对”：十位 \(x\) 排第一位，个位 \(y\) 排第二位。
  2. 十位不能为 \(0\)（否则就不是两位数了），所以 \(x\) 只有 \(1\sim 9\) 这 \(9\) 种。
  3. 个位无限制，\(y\) 可取 \(0\sim 9\) 这 \(10\) 种，且与十位选了什么无关。
  4. 由乘法原理，总数 \(=9\times 10=90\)。可粗略验证：两位数是 \(10,11,\cdots,99\)，共 \(99-10+1=90\) 个，吻合。

乘法原理同样可以从“两个”推广到“多个”。当一个对象由 \(k\) 个分项依次决定时，结论自然地变成各分项种数的连乘积。

定理 1.8（广义乘法原理）设 \(X_1,X_2,\cdots,X_k\) 是有限集合。那么，满足 \(x_i\in X_i\) 的 \(k\)-元组 \((x_1,x_2,\cdots,x_k)\) 的个数为 \[|X_1|\times|X_2|\times\cdots\times|X_k|.\]

非正式地，我们可以这样论证。\(x_1\) 有 \(|X_1|\) 种选择；接着，无论之前如何选，\(x_2\) 有 \(|X_2|\) 种选择，于是由定理 1.6，序列 \((x_1,x_2)\) 有 \(|X_1|\times|X_2|\) 种选择。然后 \(x_3\) 有 \(|X_3|\) 种选择，再次由定理 1.6，序列 \((x_1,x_2,x_3)\) 有 \(|X_1|\times|X_2|\times|X_3|\) 种选择。如此继续，直到处理完 \(x_k\)，便证明了该定理。

这一论证的思路是正确的，但最后那句话不够严格。为了得到一个完全形式化的证明，我们将使用数学归纳法（mathematical induction）。读者很可能已经见过这一方法。关于该方法的简要回顾可在本书附录中找到。

为什么“如此继续……”不算严格“依此类推，直到 \(x_k\)”用省略号代替了无穷多步推理，并没有真正说明“对每一个 \(k\) 都成立”。数学归纳法把这件事变得严密：先验证起点成立，再证明“若第 \(k-1\) 步成立则第 \(k\) 步也成立”，这样就一劳永逸地覆盖了所有的 \(k\)。
证明（定理 1.8）. 我们对 \(k\) 作归纳。当 \(k=1\) 时无需证明；当 \(k=2\) 时，命题就退化为乘法原理（定理 1.6）。
现在假设我们已知命题对 \(k-1\) 成立，来证明它对 \(k\) 成立。一个满足 \(x_i\in X_i\) 的 \(k\)-元组 \((x_1,x_2,\cdots,x_k)\) 可以分解成一个有序对 \[\big((x_1,x_2,\cdots,x_{k-1}),\ x_k\big),\] 其中仍有 \(x_i\in X_i\)。根据归纳假设，这样的 \((k-1)\)-元组 \((x_1,x_2,\cdots,x_{k-1})\) 的个数为 \(|X_1|\times|X_2|\times\cdots\times|X_{k-1}|\)。而 \(x_k\in X_k\) 的取法有 \(|X_k|\) 种。因此，由乘法原理，满足条件的有序对 \(\big((x_1,\cdots,x_{k-1}),x_k\big)\) 的个数为 \[(|X_1|\times|X_2|\times\cdots\times|X_{k-1}|)\times|X_k|,\] 这也就是满足 \(x_i\in X_i\) 的 \(k\)-元组 \((x_1,x_2,\cdots,x_k)\) 的个数。♦

把这个归纳证明的骨架拆开，便于看清它“为什么严密”：

  1. 奠基：\(k=2\) 时就是已经证好的乘法原理，所以起点可靠。
  2. 分解：把一个 \(k\)-元组看成“前 \(k-1\) 项打包成一个整体”再配上“第 \(k\) 项”，即 \(\big((x_1,\cdots,x_{k-1}),x_k\big)\)。这一步把 \(k\) 个分项的问题，化归为“一个整体 + 一个分项”的两项问题。
  3. 用归纳假设：前 \(k-1\) 项的整体有 \(|X_1|\times\cdots\times|X_{k-1}|\) 种（这是“对 \(k-1\) 成立”给的）。
  4. 用乘法原理：整体（共 \(|X_1|\cdots|X_{k-1}|\) 种）与第 \(k\) 项（共 \(|X_k|\) 种）相乘，得 \(|X_1|\times\cdots\times|X_k|\)。第 \(k\) 步因此成立。
  5. 奠基成立、且“第 \(k-1\) 步成立 ⇒ 第 \(k\) 步成立”，由归纳法，命题对所有 \(k\) 成立。
小例子（三个分项相乘） 一份套餐要从 \(2\) 种主食、\(3\) 种小菜、\(4\) 种饮料中各选一样，共有多少种搭配？
取 \(k=3\)，\(|X_1|=2,\ |X_2|=3,\ |X_3|=4\)。由广义乘法原理，搭配数 \(=2\times 3\times 4=24\)。
起点 主食(2) 小菜(3) 饮料(4) → 末端共 2×3×4 = 24 条路径
选择树：每一层对应一个分项，分叉数依次是 \(2,3,4\)。从起点走到最末端的每一条完整路径恰好对应一种搭配，路径总数 \(=2\times 3\times 4=24\)。这就是“逐项相乘”的图形含义。
即时小结
  1. 用加法：当一个对象“要么属于这一类，要么属于那一类”，各类不相交时，把各类的个数相加（1.1 节）。
  2. 用乘法：当一个对象由几个分项依次共同决定，且每一分项的选法数与之前的选择无关时，把各分项的选法数相乘（本节）。
  3. 判断口诀：先问“这是分情况（加）还是分步骤（乘）”。分情况求和，分步骤求积。

返回 全书目录