與容斥原理相關的數學知識 如下圖所示：

其中，容斥原理可以分為：

初等容斥原理：二元，三元的情況下的第一公式（《中小學數學》所涉及的內容）；

經典容斥原理：將 第一公式 擴充套件到 任意有限多元，並且加入第二公式；

廣義容斥原理：對第二公式進行擴充套件；

下面，對以上分類進行簡要的介紹：

初等容斥原理

對於 任意集合 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 反變換，廣義容斥原理 就自然證明了。

與容斥原理相關的數學知識 如下圖所示：

其中，容斥原理可以分為：

初等容斥原理：二元，三元的情況下的第一公式（《中小學數學》所涉及的內容）；

經典容斥原理：將 第一公式 擴充套件到 任意有限多元，並且加入第二公式；

廣義容斥原理：對第二公式進行擴充套件；

下面，對以上分類進行簡要的介紹：

初等容斥原理

對於 任意集合 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 反變換，廣義容斥原理 就自然證明了。