XGM0913
與容斥原理相關的數學知識 如下圖所示：
其中，容斥原理可以分為：
初等容斥原理：二元，三元的情況下的第一公式（《中小學數學》所涉及的內容）；
經典容斥原理：將 第一公式 擴展到 任意有限多元，並且加入第二公式；
廣義容斥原理：對第二公式進行擴展；
下面，對以上分類進行簡要的介紹：
初等容斥原理
對於 任意集合 A 和 B，
從上圖可以直觀的得到：
這就是 容斥原理 最本源的公式。
注：公式 (1) 中，|A| 表示 集合 A 所含元素的個數，例如 |{a, b, c}| = 3。
在實際應用中，公式 (1) 中 集合元素個數 也可以換成 圖形的面積，幾何體的體積 等。舉個例子：
長方形 和 正方形 如下圖放在桌上，求 兩個圖形覆蓋住桌面的面積？
解：根據容斥原理，有：
兩圖形覆蓋面積 = 長方形面積 + 正方形面積 - 三角形面積 = 4 × 7 + 5 × 5 - 4 × 3 / 2 = 28 + 25 - 6 = 47
公式 (1) 是 二元容斥原理，在此基礎上，利用 集合交對並的分配率：
可以 擴展到 三元：
即，
舉個三元容斥原理 例子：
小學三門主課：語文，數學，英語，小明班上，喜歡語文的 7 人，喜歡數學的 5 人，喜歡英語的 3 人，同時喜歡 語言和 數學的 3 人，同時喜歡 語文和英語的 2 人，同時喜歡 數學和英語的 2 人，三門主課都喜歡的 1 人，問至少喜歡一門主課的有多少人。①
解：設，A = {喜歡語文的}, B = {喜歡數學的 }, C = {喜歡英語的} ，則 已知：|A| = 7 , |B| = 5, |C| = 3, |A∩B| = 3, |A∩C| = 2, |B∩C| = 2, |A∩B∩C| = 1。顯然 A∪B∪C = {至少喜歡一門主課的}，根據三元容斥原理，有：
|A∪B∪C| = |A| + |B| + |C| - |A∩B| - |A∩C| - |B∩C| + |A∩B∩C| = 7 + 5 + 3 - 3 - 2 - 2 + 1 = 9
經典容斥原理
考慮 例子 ①，再已知 小明班共有 20 人，然後問不喜歡任何主課的有多少人？
解：設，X = {小明班全體}，因為 A，B，C 是 喜歡語文，數學，英語的人，所以 Aᶜ， Bᶜ， Cᶜ 就是 不喜歡語文，數學，英語的人，進而 Aᶜ ∩ Bᶜ ∩ Cᶜ 就是 不喜歡任何主課的人。利用 De Morgan 定理：
有：
再 結合 公式(2) ，有：
於是，答案是：
上面 例子中 公式 (3) 稱為 容斥原理的 第二公式，它是三元形式，而 二元形式為：
相應的，稱 公式 (1) (2) 為 容斥原理的 第一公式。
以上是二、三元的情況，接下來我們要進行質的飛躍，將容斥原理擴展到任意有限多元。
先從 第一公式 開始，為了找到規律，用下標來區分 集合 ，則公式(2) 改寫為：
將各方括號內的寫成和式：
於是猜想： 對於 任意一組集合 A₁, A₂, ... A_n，滿足：
歸納證明：
假設，當 個集合時上面的猜想成立，則 對於 個集合 有：
等式左邊有：
於是，有：
這樣就證明了：
進而就歸納證明了 公式 (5) 成立。這就是 第一公式 的通用形式。
接著，利用 De Morgan 定理，就可以從 第一公式 的通用形式 推導出 第二公式 的通用形式：
廣義容斥原理
還是，例子 ①，問：只喜歡語文的有多少人？
分析：只喜歡語文的 就是 喜歡語文但是不喜歡數學和英語的，即，A ∩ Bᶜ ∩ Cᶜ 。
令 B' = A ∩ Bᶜ, C' = A ∩ Cᶜ ，則 B' ⊆ A, C' ⊆ A ，於是 以 A 為全集，則 (B')ᶜ = A ∩ B, (C')ᶜ = A ∩ C，進而 以 A 為全集下，利用 經典容斥原理 的 二元第二公式 (4)，有：
即，
根據上面分析，得到答案：|A ∩ Bᶜ ∩ Cᶜ| = 7 - 3 - 2 + 1 = 3
再 將 例子 ① 的問題升級，問：恰好喜歡一門主課的有多少人？
分析：恰好喜歡一門主課的人數 = 只喜歡語文的人數 + 只喜歡數學的人數 + 只喜歡英語的人數，上面求出的 (7) 就是喜歡語文的人數，類似地可以得到，只喜歡數學的人數 和 只喜歡英語的人數 分別為：
於是，得到：
進而，答案為：
|A ∩ Bᶜ ∩ Cᶜ | + |Aᶜ ∩ B ∩ Cᶜ | + |Aᶜ ∩ Bᶜ ∩ C| = (7 + 5 + 3) - 2 × (3 + 2 + 2) +３× 1 = 15 - 14 + 3 = 4
若，定義 ①：
則，等式 (8) 可以改寫為：
再思考，例子 ① ，問：恰好喜歡二門主課的有多少人？
分析：根據上面的經驗，有，
進而得到：
於是，答案為：
|A ∩ B ∩ Cᶜ | + |A ∩ Bᶜ ∩ C | + |Aᶜ ∩ B ∩ C| = (3 + 2 + 2) -３× 1 = 7 - 3 = 4
用 定義 ①，對 (8‘) 進行改寫：
另外：
恰好喜歡三門主課的人數 = 喜歡三門主課都喜歡的人數，於是：
恰好喜歡零門主課的人數 = 三門主課都不喜歡的人數，這個就是 第二公式的三元形式 公式(3)，用 定義 ① 改寫為：
比較 等式 (9) 、(9')、(9'')、(9''') ，我們不難總結得到：
這就是 廣義容斥原理。
到這裡容斥原理的分類就介紹完了。最後，需要說明：
廣義容斥原理 其實 是 定義在 局部有限偏序集 上的 Mobius 反變換（也稱為 Mobius 反演） 在 冪集 上的 特例，因此 Mobius 反變換 也可看做 容斥原理的 一個分類，不過篇幅實在沒有地方介紹 Mobius 反變換，只能以後再說。
由於 Mobius 反變換 在 《初等數論》中的 重要性，因此 很多 初等數論 問題，都可以看做 是 容斥原理的 應用；
同樣由於篇幅有限，最後的廣義容斥原理我沒有證明，其實這個證明沒有價值，因為只要證明了 Mobius 反變換，廣義容斥原理 就自然證明了。
（因本人數學水平有限，出錯在所難免，歡迎各位老師批評指正。）
