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

2.4　容斥原理The inclusion–exclusion principle

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

在这一节里，我们将研究这样一类情形：直接的方法会导致重复计数（overcount），也就是说，某些对象会被数到不止一次，从而得到错误的最终答案。

本节目标第 1.1 节里我们说过：只有当各部分两两不相交时，才能把它们的个数直接相加。可一旦两组之间有重叠，简单相加就会把重叠的元素数两次。本节给出修正办法——把多数的那部分减回去，这就是容斥原理（inclusion–exclusion principle）。本节先把最基本的“两个相交集合”的情形彻底讲清。

2.4.1　两个相交的集合

让我们再回到第 1 章里那群划独木舟的朋友身上。去年夏天的种种麻烦并没有吓倒他们，今年他们又出发去旅行了。我们听说，这趟出游同样是状况百出。说得更具体些：我们听说他们当中有五人在途中某个时刻掉进了水里，而有九人的早餐被浣熊偷走了。旅途中没有一位朋友能够幸免于这两种遭遇中的至少一种。今年一共有多少位朋友去划船了？

在读者断定我们又要拿加法原理来烦她之前，请让我们指出：这个问题与第 1.1 节里的问题不同。差别在于：这一次我们并不知道这两组倒霉的朋友是不相交的。事实上，除非另有说明，我们不能假定“掉进水里”就能保护一个人的早餐不被浣熊偷走。

顺着这个思路想下去，我们很容易看出：不补充更多信息，这道题根本无法求解。确实，设 \(A\) 为掉进水里的人组成的集合，\(B\) 为早餐被浣熊扣押的人组成的集合。可能发生 \(A\subset B\)，这将意味着今年有九位朋友去了；也可能 \(A\) 与 \(B\) 不相交，由加法原理这将意味着有 \(14\) 人去了；还可能同时遭遇两类麻烦的人数不为零、但少于五，这会得出一个大于九、小于 \(14\) 的最终答案。

正如上一段所暗示的，缺失的那一条信息，恰恰是同时属于 \(A\) 与 \(B\) 的人数，也就是属于 \(A\cap B\) 的那些朋友的数目。设这个数目为 \(k\)。那么我们就可以这样回答问题：有五个人掉进了水里；另有 \(9-k\) 个人早餐被偷、但没有掉进水里；于是由加法原理，旅途中所有人的数目为 \(5+(9-k)=14-k\)。

把上面的推理用数字走一遍 这里的关键是把“至少有一种遭遇”的人，切成三块互不相交的人来数。
  1. “掉进水里”的人：共 \(5\) 人（这是 \(|A|\)）。
  2. “早餐被偷但没掉进水里”的人：这部分是 \(B\) 去掉与 \(A\) 重叠的 \(k\) 人，剩 \(9-k\) 人。
  3. 这两块不相交，且因为人人至少遭遇一种，两块合起来就是全部的人，于是总人数 \(=5+(9-k)=14-k\)。
  4. 比如若有 \(k=3\) 人两样都摊上，则共 \(14-3=11\) 人；若 \(k=0\)（无人重叠）则 \(14\) 人；若 \(k=5\)（掉水的人早餐全被偷）则 \(9\) 人。答案随 \(k\) 变，这正说明没有 \(k\) 就无法定下答案。

把上述论证中的想法推广，我们得到下面这条有用的引理。

引理 2.32设 \(A\) 与 \(B\) 是有限集合。则 \[|A\cup B|=|A|+|B|-|A\cap B|.\tag{2.2}\]
证明. 我们给出一个与上面草拟的略有不同的证明，因为之后我们会想把这个证明推广。等式 (2.2) 的左边在计数 \(A\cup B\) 的元素。右边的前两项做的是同一件事，只不过那些同时属于 \(A\) 与 \(B\) 的元素被数了两次：一次在 \(|A|\) 中，一次在 \(|B|\) 中。然而第三项纠正了这一反常之处——它恰好减去了同时属于 \(A\) 与 \(B\) 的元素个数。因此，右边也在计数 \(A\cup B\) 的元素，并且每个只数一次；于是 (2.2) 两边数的是同一批对象，从而相等。♦

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

  1. 先把 \(A\) 里的元素全部数一遍，得 \(|A|\)；再把 \(B\) 里的元素全部数一遍，得 \(|B|\)。两者相加为 \(|A|+|B|\)。
  2. 这样数时，只属于 \(A\)（不在 \(B\) 里）的元素被数 \(1\) 次；只属于 \(B\) 的也被数 \(1\) 次；而两边都属于的元素被数了 \(2\) 次。
  3. 多数的那一次，正好是每个 \(A\cap B\) 中的元素各多数了一次，总共多数了 \(|A\cap B|\) 次。
  4. 把这多出来的 \(|A\cap B|\) 减掉，于是每个元素都恰好被计入一次，得到 \(|A\cup B|=|A|+|B|-|A\cap B|\)。
A B 只在 A 只在 B A∩B （数了两次） |A|+|B| 把中间这块算了 2 次，故要减去一份 |A∩B|
文氏图（Venn diagram）把并集切成三块互不相交的区域：只在 A、只在 B、A∩B。把 \(|A|\) 与 \(|B|\) 相加时，中间一块被加了两遍，所以要减去 \(|A\cap B|\)。
例 2.33 不超过 \(300\) 且能被 \(2\) 与 \(3\) 中至少一个整除的正整数共有 \(200\) 个。
解. 设 \(A\) 为这些合格整数中能被 \(2\) 整除者组成的集合，\(B\) 为能被 \(3\) 整除者组成的集合。则 \(|A|=150\)，\(|B|=100\)。要计算 \(|A\cap B|\)，注意到：\(n\) 同时被 \(2\) 与 \(3\) 整除，当且仅当 \(n\) 被 \(6\) 整除。这表明 \(|A\cap B|=50\)。于是由引理 2.32， \[|A\cup B|=150+100-50=200.\]♦
  1. \(|A|\)：\(1\) 到 \(300\) 中 \(2\) 的倍数有 \(300/2=150\) 个。
  2. \(|B|\)：\(3\) 的倍数有 \(300/3=100\) 个。
  3. \(|A\cap B|\)：既是 \(2\) 的倍数又是 \(3\) 的倍数，就是 \(6\) 的倍数，有 \(300/6=50\) 个。
  4. 若错误地直接相加 \(150+100=250\)，会把 \(6,12,18,\dots\) 这 \(50\) 个数各算两次；减去一份 \(50\) 得 \(200\)，每个数恰好算一次。

两个相交的集合及其大小，可以借助文氏图（Venn diagram）来直观表示，如图 2.13 所示。

A B 100 50 50
图 2.13　例 2.33 中两个相交的集合。只被 \(2\) 整除的有 \(150-50=100\) 个，重叠（被 \(6\) 整除）\(50\) 个，只被 \(3\) 整除的有 \(100-50=50\) 个；三块相加 \(100+50+50=200\)。

前一个例子展示了如何用引理 2.32 来计算属于两个集合中至少一个的元素个数。把它与减法原理结合起来，我们就能求出哪一个都不属于的元素个数。我们建议读者在继续往下读之前，先做练习 13。

“至少属于其一” 与 “一个都不属于” 的桥梁设全集（这里指被考虑的全部对象）共 \(N\) 个。属于 \(A\cup B\) 的有 \(|A\cup B|\) 个，那么既不在 \(A\) 也不在 \(B\) 的个数，由减法原理就是 \(N-|A\cup B|=N-\big(|A|+|B|-|A\cap B|\big)\)。先用容斥求“至少其一”，再用减法翻到“一个都不属于”。
例 2.34 我们邀请了 \(30\) 位宾客来参加婚礼。为安排座位，我们想把他们分成三组，每组 \(10\) 人。然而，某些宾客彼此不和：\(U\) 不喜欢 \(V\)，\(X\) 不喜欢 \(Y\)。因此这些人不能被分到同一组里。我们有多少种分法？
解. 让我们先来数坏的分法，也就是 \([30]\) 的那些分拆（partition）：每一块（block）的大小都是 \(10\)，但要么 \(1\) 和 \(2\) 在同一块里，要么 \(3\) 和 \(4\) 在同一块里，或者这两桩不幸之事同时发生。（这里把不和的两对宾客分别记成 \(1,2\) 与 \(3,4\)。）
设 \(A\) 为第一桩坏事发生的那些合格分拆组成的集合，即 \(1\) 与 \(2\) 在同一块里。把这样一个分拆中的 \(1\) 和 \(2\) 移走，我们就得到 \([28]\) 的一个分拆——分成两块大小为 \(10\) 的块，以及一块……
说明：原文 PDF 摘录到此中断本节所提供的原文 PDF 在例 2.34 的解答中途（“……以及一块大小为 \(8\) 的块”）被截断。下面这一框是按容斥原理把该例题补全的完整推演，数学上自洽，供读者把思路走通；它不属于已截断的原文译文。
例 2.34（按容斥原理补全的解答）
先约定：这里“分成三组、每组 \(10\) 人”指把 \([30]\) 分成三块大小均为 \(10\) 的无标号分拆（三组之间不分先后）。
  1. 总数 \(T\)（不加任何限制）。 把 \(30\) 个人排成一行再每 \(10\) 个切一刀，会把同一种分组重复数若干次：每块内部 \(10!\) 种排列、三块之间 \(3!\) 种次序都不该区分，故 \[T=\frac{30!}{(10!)^3\,3!}.\]
  2. \(|A|\)：\(1,2\) 同块。 含 \(\{1,2\}\) 的那一块还需从其余 \(28\) 人中选 \(8\) 人，剩下的 \(20\) 人分成两块大小为 \(10\)（这两块无标号，故除以 \(2!\)）。把 \(1,2\) 移走即得“\([28]\) 分成两块大小 \(10\) 与一块大小 \(8\)”： \[|A|=\frac{28!}{(10!)^2\,8!\,2!}.\]
  3. \(|B|\)：\(3,4\) 同块。 与 \(A\) 完全对称，\(\;|B|=\dfrac{28!}{(10!)^2\,8!\,2!}.\)
  4. \(|A\cap B|\)：\(1,2\) 同块且 \(3,4\) 同块。 分两种互不相交的情形相加：
    情形一，四人 \(1,2,3,4\) 在同一块：该块再从其余 \(26\) 人取 \(6\) 人，余下 \(20\) 人分两块大小 \(10\)： \[\frac{26!}{6!\,(10!)^2\,2!}.\]
    情形二，\(1,2\) 在一块、\(3,4\) 在另一块：含 \(\{1,2\}\) 的块从 \(26\) 人取 \(8\) 人，含 \(\{3,4\}\) 的块从余下 \(18\) 人取 \(8\) 人，最后 \(10\) 人成第三块；三块因内容不同而彼此可分，不再除以对称数： \[\binom{26}{8}\binom{18}{8}=\frac{26!}{(8!)^2\,10!}.\]
    于是 \(\displaystyle |A\cap B|=\frac{26!}{6!\,(10!)^2\,2!}+\frac{26!}{(8!)^2\,10!}.\)
  5. 坏分法总数（容斥）。 由引理 2.32， \[|A\cup B|=|A|+|B|-|A\cap B|=\frac{2\cdot 28!}{(10!)^2\,8!\,2!}-\left(\frac{26!}{6!\,(10!)^2\,2!}+\frac{26!}{(8!)^2\,10!}\right).\]
  6. 好分法（减法原理）。 把坏的从全体里减去： \[\text{答案}=T-|A\cup B|=\frac{30!}{(10!)^3\,3!}-|A\cup B|.\]♦
要点在于：直接去数“合法分法”很难下手，而“坏分法”由两类清楚的事件 \(A,B\) 描述，可用容斥求 \(|A\cup B|\)，再用减法翻成合法分法。
即时自测
  1. \(1\) 到 \(100\) 的正整数中，能被 \(4\) 与 \(6\) 中至少一个整除的有多少个？（提示：先求 \(4\) 的倍数、\(6\) 的倍数，重叠的是 \(\operatorname{lcm}(4,6)=12\) 的倍数。）
  2. 承上题，\(1\) 到 \(100\) 中既不被 \(4\) 整除、也不被 \(6\) 整除的有多少个？
  3. 把例 2.33 改为“不超过 \(300\) 且能被 \(2\)、\(3\)、\(5\) 中至少一个整除”的正整数个数，你会发现两个集合的容斥不够用了——想一想需要补充哪些“两两交”和“三者交”的项？

返回 全书目录