第3章 容斥原理

3.1 把每個物件的淨次數算成一

對有限集合 A、B，|A∪B|=|A|+|B|−|A∩B|：兩邊都屬於的物件先被計兩次，再扣一次。三集合時先加單集合、減兩兩交集、再加三重交集，因同在三集合的元素先加 3、減 3，必再補 1。

對 m 個集合，對每個非空索引子集 J，把其交集大小乘 (−1)^(|J|−1) 加起來。若某元素恰在 r 個集合，淨次數為 C(r,1)−C(r,2)+⋯+(−1)^(r−1)C(r,r)=1，理由是二項式 (1−1)ʳ=0（r≥1）。r=0 時沒有任何項。若題目要「一個條件都不碰」，先在明定的全集計數，再扣聯集；若要「恰中一個」，三重交集的係數又不一樣。

3.2 四個例題

例題1 倍數聯集要扣最小公倍數

在 1 到 30，3 的倍數有 10 個，5 的倍數有 6 個；同時是兩者倍數等於是 15 的倍數，有 2 個。故至少符合一個有 10+6−2=14 個，兩者都不符合有 30−14=16 個。

例題2 三集合的共同部分加回

某班以 A、B、C 記三項活動，單集合人數 12、11、9，兩兩交集人數依 AB、AC、BC 為 5、4、3，三重交集 2。至少參加一項為 12+11+9−5−4−3+2=22。若全班 30 人，三項皆未參加有 8 人。

例題3 分辨恰好一項與至少一項

沿用例題2，恰好一項用單集合和減兩倍兩兩交集和，再加三倍三重交集。淨次數對參與 1、2、3 項分別是 1、0、0，所以為 32−2·12+3·2=14。

例題4 用補集計禁位排列

把三封不同的信放入三個不同信封，每個信封恰放一封。問沒有信放入對應信封的方式數。全部有 3!=6 種。用容斥，至少一封放對有 3·2!−3·1!+0!=4 種。固定一封後兩封任排；固定兩封後最後一封也被迫放對；固定三封只剩一種。故全錯有 6−4=2 種。

3.3 練習

1. B10-C03-Q01 40 人中 A 有 18 人，B 有 15 人，兩者都有 7 人，至少一者多少？
2. B10-C03-Q02 1 到 24，能被 4 或 6 整除的個數？
3. B10-C03-Q03 1 到 20，不是 2 也不是 5 的倍數有幾個？
4. B10-C03-Q04 三集合大小各 8，兩兩交集大小各 3，三重交集大小 1，聯集多少？
5. B10-C03-Q05 沿用上一題，恰好屬於兩集合的元素有幾個？
6. B10-C03-Q06 A⊆B 時，容斥公式為何只剩 |B|？
7. B10-C03-Q07 若兩集合沒有交集，可直接加嗎？
8. B10-C03-Q08 把四封不同的信放入四個不同信封，每個信封恰放一封。沒有信放入對應信封的方式有幾種？
9. B10-C03-Q09 三集合中，某元素恰在 A、C，三集合公式對它計幾次？
10. B10-C03-Q10 1 到 30 中 3 或 5 的倍數，恰好只中其中一條有幾個？

3.4 完整解答

Q01

聯集為 18+15−7=26 人。其餘 14 人兩者皆無。

Q02

各有 6、4；共同倍數是 12 的倍數，有 2。故 6+4−2=8。

Q03

聯集 10+4−2=12，從全集 20 扣除，剩 8。

Q04

依次加、減、加，得 3·8−3·3+1=16。

Q05

兩兩交集的總數為 9，其中每個三重交集元素計三次。要留下恰兩者的元素，扣 3·1 得 6。

Q06

交集就是 A，因此右側 |A|+|B|−|A|=|B|；左側聯集也就是 B。

Q07

可以；每個物件只在其所在集合被計一次。這是交集修正項為零的情形。

Q08

全部 4!=24。至少一封對用容斥：4·3!−6·2!+4·1!−0!=24−12+4−1=15；全錯 24−15=9。

Q09

單集合加兩次，兩兩交集只有 AC 扣一次，沒有三重交集項，所以淨計 1 次。

Q10

先算兩個集合人數和 16；共同的 2 個在和中各計兩次，要全部扣掉，共 16−4=12。