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

1.1　何时相加，何时相减When we add and when we subtract

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

我们以一个非常简单的任务来开始这门枚举组合学（enumerative combinatorics）的课程，即：求两个不相交集合的并集的大小。

本节目标把“合起来有多少个”这件事说清楚：什么时候能把各部分的个数直接相加，什么时候要用总数减去一部分。这是整本书所有计数的两块地基。

1.1.1　何时相加

一群朋友去划独木舟。其中五人在旅途中的某个时刻掉进了水里，另有七人全程没有沾湿地完成了旅程。这次划船一共去了多少位朋友？

在读者嘲笑我们用如此简单的问题开篇之前，请允许我们先给出答案。当然，\(5+7=12\) 人参加了这次旅行。然而，需要指出的是，能给出这样简单的答案，仅仅是因为旅途中的每个人要么掉进了水里，要么保持干燥：没有中间状态，没有人能同时属于两组，也没有人能两组都不属于。一旦掉进水里，你自己心里是有数的。换句话说，每个人都恰好属于这两组人中的一组。

作为对比，假设我们并不被告知有多少人掉没掉进水里，而是被告知：这次旅行有五人穿白衬衫，八人戴棕色帽子。那么我们就无法判断这次旅行去了多少人——因为可能有人同时属于两组（一个人完全可以既穿白衬衫又戴棕色帽子），也可能有人两组都不属于。

A：掉进水里（5 人） B：保持干燥（7 人）
两堆互不重叠（不相交），把点数全部数一遍，等于各自数完再相加：\(|A\cup B|=|A|+|B|=5+7=12\)。

现在我们可以给出本书的第一条、也是最容易的计数原理。用 \(|X|\) 表示有限集合 \(X\) 的元素个数。例如 \(|\{2,3,5,7\}|=4\)。回忆一下：若两个子集没有公共元素，则称它们是不相交的（disjoint），即 \(A\cap B=\varnothing\)。

定理 1.1（加法原理）若 \(A\) 与 \(B\) 是两个不相交的有限集合，则 \[\tag{1.1}|A\cup B|=|A|+|B|.\]

为如此极其简单的命题提供证明，或许显得有些奇怪，但我们希望由此立下标准。

证明. 等式 (1.1) 的两边都在计数同一个集合 \(A\cup B\) 的元素。左边直接计数，而右边分别计数 \(A\) 与 \(B\) 的元素。因为 \(A\) 与 \(B\) 不相交，每个元素都恰好被计数一次，所以两边相等。♦

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

  1. 左边 \(|A\cup B|\)：把并集里的元素一个一个数一遍。
  2. 右边 \(|A|+|B|\)：先数完 \(A\)，再数完 \(B\)。
  3. 因为不相交，没有元素同时落在两边，于是每个元素恰好被数到一次，两种数法结果必然相同。

上面的定理说的是两个集合，但这里的“二”并没有什么神奇之处。如果说划船的每位参与者恰好遭遇一桩不幸之事，比如五人掉水、三人被黄蜂蜇、四人中暑，那么仍可断定共有 \(5+3+4=12\) 人。这是广义加法原理。

定理 1.2（广义加法原理）设 \(A_1,A_2,\dots,A_n\) 是两两不相交的有限集合，则 \[|A_1\cup A_2\cup\dots\cup A_n|=|A_1|+|A_2|+\dots+|A_n|.\]
证明. 同样地，两边都在计数同一个集合 \(A_1\cup\dots\cup A_n\) 的元素，因此相等。♦

务必强调：集合 \(A_i\) 必须两两不相交。把这个条件去掉，原理立刻失效。看下面的对照图。

白衬衫（5） 棕帽（8） 既穿又戴 （被数两次） 两样都没有的人不在任何圈里（被漏掉）
有重叠时 \(5+8=13\) 把中间的人数了两次、又漏掉了圈外的人。有重叠的情形如何处理，是 2.4 节容斥原理的主题。

1.1.2　何时相减

同一个划船故事换个问法：十二位朋友去划船，其中五人掉进了水里，问有多少人没掉水就完成了旅程？答案当然是 \(12-5=7\)。这是减法原理。为便于讨论，先引入两个集合之差：若 \(A,B\) 是两个集合，则 \(A-B\) 是由 \(A\) 中那些不属于 \(B\) 的元素组成的集合。

例 1.3 设 \(A=\{2,3,5,7\}\)，\(B=\{4,5,7\}\)。把 \(A\) 中也在 \(B\) 里的 \(5,7\) 划掉，剩下 \(A-B=\{2,3\}\)。

注意，即使 \(B\) 不是 \(A\) 的子集，\(A-B\) 也有定义。然而减法原理只在 \(B\) 是 \(A\) 的子集时才成立。

定理 1.4（减法原理）设 \(A\) 为有限集合，\(B\subseteq A\)，则 \(|A-B|=|A|-|B|\)。

它的证明其实就是“反过来用一次加法原理”。看图：当 \(B\) 整个落在 \(A\) 里面时，\(A\) 被切成不相交的两块——“在 \(B\) 里的”和“不在 \(B\) 里的（即 \(A-B\)）”。

A（全部，\(|A|\) 个） A − B B（B⊆A）
\(B\subseteq A\) 时，\(A\) 恰好被分成不相交的两块 \(A-B\) 与 \(B\)。
证明. 先证 \(|A-B|+|B|=|A|\)（编号 (1.2)）。
  1. \(A-B\) 与 \(B\) 不相交，且并集恰为 \(A\)，对它们用加法原理 (1.1)： \[\tag{1.2}|A-B|+|B|=|A|.\]
  2. 两边同减 \(|B|\)，即得 \(|A-B|=|A|-|B|\)。♦
为什么必须 \(B\subseteq A\)若 \(B\) 里含有 \(A\) 之外的元素，上图就不成立——\(B\) 不再是 \(A\) 的一块，等式 (1.2) 会把 \(A\) 外的元素也算进来而失效。
反例（条件不满足就会错） 取 \(A=\{2,4,6,8\}\)（一位偶数），\(B=\{3,6,9\}\)（一位的 \(3\) 的倍数）。此时 \(B\not\subseteq A\)（\(3,9\notin A\)）。直接算 \(A-B=\{2,4,8\}\)，\(|A-B|=3\)；而 \(|A|-|B|=4-3=1\)。\(3\neq 1\)，减法原理不成立——正因条件 \(B\subseteq A\) 没满足。

当计数 \(B\)（“坏家伙”）比计数 \(A-B\)（“好家伙”）更容易时，使用减法原理是明智的。

例 1.5 求不超过 \(1000\) 且至少含两个不同数字的正整数个数。答案是 \(1000-27=973\)。
直接数“至少含两个不同数字”的数很费劲，但它的反面——“所有数字都相同”的数——很少、容易数。设 \(A\) 为 \(1\) 到 \(1000\) 的全部正整数（\(|A|=1000\)），\(B\) 为 \(A\) 中“只用一种数字”写成的数。所求即 \(|A-B|\)。
  1. 一位数中只用一种数字的：\(1,2,\dots,9\)，共 \(9\) 个。
  2. 两位数中两位相同的：\(11,22,\dots,99\)，共 \(9\) 个。
  3. 三位数中三位相同的：\(111,222,\dots,999\)，共 \(9\) 个。（\(1000\) 含不同数字，不在 \(B\) 内。）
  4. 三类互不相交，加起来 \(|B|=9+9+9=27\)。
  5. 由减法原理 \(|A-B|=|A|-|B|=1000-27=973\)。♦

这样做更快，是因为 \(|A|=1000\) 一眼可知、\(|B|=27\) 也几乎一眼可数，比直接硬数 \(973\) 个目标数省事得多。

即时自测
  1. 大于 \(20\)、小于 \(50\)，且是素数或素数的平方的两位正整数有几个？
  2. 称 \(x\) 为孤立素数，若 \(x\) 是素数但 \(x-2,x+2\) 都不是素数。\(10\) 到 \(35\) 之间有几个孤立素数？
  3. 有多少个正整数 \(x\le 50\)，使得不存在非负整数 \(k\) 与素数 \(p\) 满足 \(x=p^k\)？

返回 全书目录