容斥原理

一句话

几个集合两两不交时，并集的元素个数就是各集合元素个数之和（加法原理）。有重叠时，重叠部分被多数了，要减掉；减多了，再加回来：

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

这就是容斥原理。上面的操作台把每一块“被数了几次”都标了出来：公式对，就是每一块都恰好数了 $1$ 次。

为什么每一块恰好数一次

第 1 / 4 步

先全加
$∣ A ∣ + ∣ B ∣ + ∣ C ∣$ ：只在一个圈里的块数了 $1$ 次，在两个圈里的块数了 $2$ 次，正中间数了 $3$ 次。

$∣ A ∣ + ∣ B ∣ + ∣ C ∣$
减去两两的交
加回三个的交
任意多个集合

第 1 站 · 整数：数“都不是”

$1 \sim 60$ 中，与 $30$ 互质的数有多少个？ 与 $30$ 互质，就是既不是 $2$ 、也不是 $3$ 、也不是 $5$ 的倍数——圈外的那一块。上面算出圈内有 $44$ 个，所以圈外是 $60 - 44 = 16$ 个。

先猜后证

$1 \sim 100$ 中，既不是 $2$ 的倍数、也不是 $3$ 的倍数、也不是 $5$ 的倍数的数有多少个？

个

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

第 2 站 · 排列：错排

$4$ 封信装进 $4$ 个写好地址的信封，每封都装错，有几种装法？

用容斥数错排

第 1 / 4 步

设集合
全部装法有 $4! = 24$ 种。设 $A_{i}$ 是“第 $i$ 封信装对了”的装法。要数的是一个 $A_{i}$ 都不在的装法。

$24 - ∣ A_{1} \cup A_{2} \cup A_{3} \cup A_{4} ∣$
各项的大小
容斥
取补

第 3 站 · 映射：每个盒子都不空

$5$ 个不同的球放进 $3$ 个不同的盒子，每个盒子都不空，有几种放法？ 两种想法，答案必须一样：

一题多解

$5$ 个不同的球放进 $3$ 个不同的盒子，没有空盒。求放法数。

容斥：从“随便放”里去掉有空盒的

随便放有 $3^{5} = 243$ 种。设 $A_{i}$ 为“第 $i$ 个盒子空着”： $∣ A_{i} ∣ = 2^{5} = 32$ ， $∣ A_{i} \cap A_{j} ∣ = 1$ ，三个都空不可能。

有空盒的放法 $= 3 \times 32 - 3 \times 1 + 0 = 93$ ，所以没有空盒的有 $243 - 93 = 150$ 种。

代价机械，换成 $n$ 个球 $m$ 个盒也照样算。

分划：先分组，再分配

先把 $5$ 个球分成 $3$ 个非空的组： $S (5, 3) = 25$ 种（第 4 站的练习）。再把 $3$ 组分给 $3$ 个盒子： $3! = 6$ 种。

共 $25 \times 6 = 150$ 种。

代价要先会数分划（第 4 站），但更能看清结构。

练一练

练习 1基础

$1 \sim 120$ 中，是 $2$ 的倍数或是 $3$ 的倍数的数有多少个？

练习 2基础

某班 $40$ 人，参加数学兴趣小组的有 $25$ 人，参加物理兴趣小组的有 $20$ 人，两个都没参加的有 $8$ 人。两个都参加的有多少人？

练习 3提高

$5$ 个人各写一张贺卡，收上来后再随机发回，每人恰好拿一张。有多少种发法使得没有人拿到自己写的贺卡？

练习 4挑战

$6$ 个不同的球放进 $3$ 个不同的盒子，每个盒子都不空，有多少种放法？

一句话

为什么每一块恰好数一次

第 1 站 · 整数：数“都不是”

第 2 站 · 排列：错排

用容斥数错排

第 3 站 · 映射：每个盒子都不空

容斥：从“随便放”里去掉有空盒的

分划：先分组，再分配

练一练

错误博物馆 · 本站展品

减完两两的交就停了

求“都不是”，减完就收工