當相加重複算到了重疊
在本階一路走來，你已經建立起一套計數工具：把獨立選擇串接起來的乘法原理、處理有序排法的排列，以及處理無序選取的二項式係數。這些工具都靠「把東西組裝起來」來回答「有幾種方法」。最後這一篇要處理組裝會失靈的情況——你所數的類別彼此重疊，而直接相加會把重疊處算了兩次。解藥有個名字：排容原理。
想像一班 30 個學生。假設有 18 人修中文、15 人修英文。修了兩科中至少一科的有幾人？很容易脫口說 18 + 15 = 33——但這比全班還多，所以哪裡出錯了。同時修兩種語言的學生，在 18 人裡被算過一次，又在 15 人裡再被算一次。若有 9 人兩科都修，那麼 18 + 15 就把這 9 人算了兩次，因此必須把他們減回去：18 + 15 - 9 = 24 人至少修一科語言。這一次減法，就是排容原理最迷你的樣子。
Two-set inclusion-exclusion (sizes of sets): |A or B| = |A| + |B| - |A and B| Class example: |Chinese or English| = 18 + 15 - 9 = 24 Contrast: if A and B never overlap (mutually exclusive), |A and B| = 0, so |A or B| = |A| + |B| (the plain addition rule)
為何加法規則需要修正
本階稍早的加法規則說：若一項任務能以幾種互不重疊的方式之一完成，就把各個計數相加。關鍵的附帶條件是互不重疊。當這些類別互斥——沒有任何元素同時屬於其中兩個——直接相加恰好正確，因為沒有東西被算兩次。一旦這個假設破裂、類別之間共用了成員，你要伸手去拿的就是排容原理。
這裡還有一個與邏輯的深層連結，可以解釋接下來會出現的正負交替號。說「屬於 A 或 B」，是「既不屬於 A 也不屬於 B」的補集，而由笛摩根定律，「非 A 且非 B」這一側是用交集構成的。所以每一個聯集問題都能重新讀成關於重疊的問題。排容原理不過是一套記帳法，確保每一塊重疊都恰好被算一次——不多也不少。
三個集合與正負交替的規律
有三個重疊的集合時，記帳就豐富多了，而走一遍這個過程會揭示出一般規律。先把三個單一集合的大小相加，|A| + |B| + |C|。此時任何落在兩個集合裡的元素都被算了兩次，所以把每個兩兩重疊減掉：減去 |A and B|、|A and C|、|B and C|。那麼同時落在三個集合裡的元素呢？它先被加了三次，又被減了三次（每一對各減一次）——結果被算了零次，這又太少。所以必須再把它加回來一次。號是交替的：單一集合用加、兩兩交集用減、三重交集用加。
Three-set inclusion-exclusion:
|A or B or C| = |A| + |B| + |C|
- |A&B| - |A&C| - |B&C|
+ |A&B&C|
General pattern (n sets):
add all single sizes, subtract all pairwise intersections,
add all triple intersections, subtract all quadruples, ...
(odd-sized intersections +, even-sized intersections -)這套正負交替之所以恰好正確、而不只是僥倖湊出來的修正，是因為它逼得每個元素淨被算正好一次。一個恰好落在 m 個集合裡的元素，會在許多項中被加被減，而這些加減貢獻會剛好抵消到對每個 m ≥ 1 都精確等於 1——這是一個小小的代數奇蹟，直接來自你在第 3 篇看過的二項式係數恆等式。你不需要證明就能用公式，但知道這些號是被逼出來、而非隨意選定，是件好事。
硬著頭皮數：補集法與一個實算
排容原理常與它沉默的搭檔補集計數一起出現：與其直接數你想要的，不如數它的相反，再從整體中減掉。這是補集規則 P(not A) = 1 - P(A) 在計數裡的回聲。當你想要的東西很糾結、但它的否定很乾淨時——「至少一個」很雜亂、「一個都沒有」很簡單——就把問題翻過來。經典例子是數 1 到 100 之間可被 2 或 3 或 5 整除的整數。
- 數出 100 以內各單一數的倍數：2 的倍數有 50 個、3 的倍數有 33 個、5 的倍數有 20 個。相加：50 + 33 + 20 = 103。
- 減去兩兩重疊（乘積的倍數）：6 的倍數有 16 個、10 的倍數有 10 個、15 的倍數有 6 個。減去 16 + 10 + 6 = 32，得到 103 - 32 = 71。
- 加回三重重疊（2*3*5 = 30 的倍數）：有 3 個。所以 71 + 3 = 74 個整數可被 2、3 或 5 整除。
- 若你反而想知道有幾個一個都不被整除，就取補集：100 - 74 = 26 個 1 到 100 的整數與 30 互質。
請留意這兩個想法如何交織。我們用排容原理數出聯集（可被 2、3 或 5 整除），再用補集計數一次減法把它翻成「一個都不被整除」的答案。純粹正面硬攻——把每個互質整數列出來——會又慢又容易出錯；而有結構的加減加把它變成機械化的步驟。這才是「硬著頭皮數」的真義：不是更難的算術，而是一套能挺過簡單乘法或組合招架不住的重疊的方法。
錯位排列：公式展現價值之處
這裡是排容原理不再只是個漂亮把戲、而真正贏得敬意的地方。錯位排列是一種沒有任何元素停在自己原本位置上的排列。想像 n 封信與 n 個寫好地址的信封，完全隨機塞入：錯位排列就是「沒有任何一封信送到正確信封」的那場災難。直接數這些非常折磨人，因為「禁止某個固定點」與「禁止另一個固定點」彼此牽連。排容原理乾淨地處理它：去數那些壞排列——至少有一封信落在正確位置的——再相減。
令 A_i 為「把第 i 個元素固定在原位」的排列所成的集合。我們要的是不落在任何 A_i 裡的排列，故取補集後需要 n! 減去聯集的大小，而那個聯集正是排容原理所計算的東西。兩兩、三重以及更高的重疊收攏成一個著名的交替級數，而錯位排列數 D(n) 落在一個出奇精簡的公式上。更令人驚訝的是：所有排列中錯位排列所佔的比例，隨著 n 增大幾乎立刻就穩定在 1/e 附近——約 0.3679。
D(n) = n! * ( 1 - 1/1! + 1/2! - 1/3! + ... + (-1)^n / n! ) Small values: D(1)=0 D(2)=1 D(3)=2 D(4)=9 D(5)=44 Limit: D(n) / n! -> 1/e ~ 0.3679 (already true to 3 digits by n=6)