容斥原理

一句话

∣ A \cup B \cup C ∣ = ∣ A ∣ + ∣ B ∣ + ∣ C ∣ - ∣ A \cap B ∣ - ∣ A \cap C ∣ - ∣ B \cap C ∣ + ∣ A \cap B \cap C ∣

为什么是这七项、这些符号？看任何一个元素：如果它恰好属于 $k$ 个集合（ $k \geq 1$ ），那么它在公式里被数了

(1 k) - (2 k) + (3 k) = 1 - (1 - 1)^{k} = 1

次——不多不少，恰好一次。上面的图把这件事摊开了：每打开一项，相关区域的“次数”就加一或减一。

例：1～100 中，2、3、5 的倍数共有多少个？

第 1 / 4 步

先加单个集合
$∣ A ∣ = 50$ ， $∣ B ∣ = 33$ ， $∣ C ∣ = 20$ 。两两重叠的块被数了 $2$ 次，正中间被数了 $3$ 次。

$50 + 33 + 20 = 103$
减去两两交集
加回三者交集
反面

先猜后证

加上三个单集合、再减去三个两两交集之后，三者公共的那一块（ $A \cap B \cap C$ ）一共被数了几次？

先选定答案，才能看到结论。

第 1 站 · 集合的运算（卷一）

“都不满足”是交集 $∁ A \cap ∁ B \cap ∁ C$ ，由德·摩根律，它等于 $∁ (A \cup B \cup C)$ ——先数并集，再用全集减。

例：1～1000 中，既不是 2 的倍数、也不是 3 的倍数、也不是 5 的倍数的数有多少个？

第 1 / 4 步

德·摩根
要数的是三个补集的交集，等于并集的补集。

$∁ A \cap ∁ B \cap ∁ C = ∁ (A \cup B \cup C)$
单集合
交集
取补集

第 2 站 · 有限集元素的数目（卷一）

数“满射”：每个像都至少被用到一次。反面是“某个像没被用到”，这正是容斥最擅长的。

例：从 5 元集合到 3 元集合 {a, b, c} 的满射有多少个？

第 1 / 4 步

全部映射
每个元素有 $3$ 种去处。

$3^{5} = 243$
设坏事件
容斥
结论

第 3 站 · 容斥原理与错排（卷一）

$n$ 封信装进 $n$ 个写好地址的信封，全都装错有多少种？这就是错排数 $D_{n}$ 。

例：求 D₄

第 1 / 4 步

坏事件
$A_{i}$ ：第 $i$ 封信装对了。错排 = 所有 $A_{i}$ 都不发生。

$∣ A_{i_{1}} \cap \dots \cap A_{i_{k}} ∣ = (4 - k)!$
按 k 求和
算出来
结论

练一练

练习 1基础

$1, 2, \dots, 100$ 中，是 $3$ 的倍数或 $5$ 的倍数的数有多少个？

练习 2提高

$1, 2, \dots, 200$ 中，不能被 $2, 3, 7$ 中任何一个整除的数有多少个？

练习 3提高

$5$ 个人各写一张贺卡，收齐后打乱再每人发一张。没有人拿到自己写的贺卡，有多少种发法？

练习 4挑战

把 $4$ 个不同的球放进 $3$ 个不同的盒子，每个盒子至少一个球，有多少种放法？

错误博物馆 · 本站展品

离站之前，看看别人在这里踩过的坑。去博物馆看全部展品 →

展品

减完两两交集就停了

1 \sim 100

中

2, 3, 5

的倍数共有

50 + 33 + 20 - 16 - 10 - 6 = 71

个。

错在哪里？先想一想，再打开

病因　加三个集合时，同时是 $2, 3, 5$ 的倍数的数（ $30, 60, 90$ ）被数了 $3$ 次；减三个两两交集时又被减了 $3$ 次，结果一次也没数到。

再加回三个集合的交集：

71 + 3 = 74

。三个集合的容斥公式有七项，符号是

+, -, +

交替。

「加三次、减三次，等于没数」

展品

交集的个数用错了除数

1 \sim 100

中既是

4

的倍数又是

6

的倍数的数有

[\frac{100}{24}] = 4

个。

错在哪里？先想一想，再打开

病因　同时是 $4$ 和 $6$ 的倍数，等价于是最小公倍数 $12$ 的倍数，不是乘积 $24$ 的倍数。 $12$ 就被漏掉了。

[\frac{100}{12}] = 8

个。只有两数互质时，最小公倍数才等于乘积。

「交集看最小公倍数」

一句话

第 1 站 · 集合的运算（卷一）

第 2 站 · 有限集元素的数目（卷一）

第 3 站 · 容斥原理与错排（卷一）

练一练

错误博物馆 · 本站展品

这条线路经过的站