容斥原理（英文名：Principle of inclusion-exclusion）又稱排容原理，是組合數學中的核心計數方法，用于計算多個有限集合的并集大小。其核心思想是：一些元素會同時存在于多個集合中，如果僅將這些集合的元素數量相加來求并集中元素數量會導致重復計算，因此需要通過交替加減各集合的交集來消除重復計數，從而精確求得并集的元素數量。
容斥原理的最早運用可追溯至16世紀，當時瑞士數學家尼古拉·貝努利在解決錯位排列問題時首次采用了這一原理。然而，那時尚未有明確的數學表述。17世紀，數學家John Venn以集合的形式提出了容斥原理的初步數學表達。隨后，著名數學家康托爾在17世紀末引入集合論，將容斥原理建立在更為堅實的基礎上，使其成為處理復雜計數和概率問題的重要工具。到了19世紀，英國數學家詹姆斯·約瑟夫·西爾維斯特首次提出了該定理的現代表述。
容斥原理的證明可以采用數學歸納法或枚舉法，將定理進行推廣，可得到一些新的結論。容斥原理廣泛地應用于數學、概率論、計算機等領域，如，在圖論中，容斥原理可以用于計算滿足某些性質的圖的數量，或者計算不滿足某些性質的圖的數量。
簡史
16世紀至17世紀
容斥原理被發掘出來的起因是組合學的——錯位排問題，16世紀，瑞士數學家尼古拉·貝努利(Nicholas Bernoulli）在解決錯位排問題時，用到了容斥原理，但他那時并沒有明確的整理和提出容斥原理的數學形式。法國數學家棣莫弗在1718年的著作《機會的學說》中首次明確闡述了容斥原理的思想，并用這個思想解決了一些問題。
18世紀至20世紀
18世紀至20世紀，容斥定理在數學領域得到了進一步的發展和推廣。著名的數學家格奧爾格·康托爾引入了集合論，以此為基礎，容斥原理的表述形式得到確定，而隨著數學家萊昂哈德·歐拉等人對容斥定理進行了深入的研究和推廣，提出了更加廣泛和深刻的應用。他們在組合數學、概率論和數論等領域中廣泛應用容斥定理，推動了容斥定理的發展和應用。在19世紀中葉，柯西、西爾維斯特等數學家嚴格表述了容斥原理的一般形式，并將容斥原理的思想推廣到數論等其他領域的研究中去，推動了容斥原理的應用。隨著數學的發展，容斥定理逐漸成為組合數學和概率論等領域的重要工具，為解決復雜的計數和概率問題提供了重要的方法和思路。
21世紀
21世紀以來，容斥定理在計算機科學、統計學和機器學習等領域得到了廣泛的應用。隨著大數據和人工智能等技術的快速發展，容斥定理在處理復雜的計數和概率問題上發揮了重要作用。許多新的領域和學科開始將容斥定理引入到他們的研究和應用中，推動了容斥定理在現代科學和技術領域的發展和應用。
定義
集合形式
在計數時，為了使重疊部分不被重復計算，所以先不考慮重疊的情況，把具有某種特征的所有對象的數目，優先計算出來，然后再把計數時重復計算的數目排斥出去，使得計算的結果既無遺漏又無重復，簡化了計數方法，這種計數的方法稱為容斥原理。
容斥原理運用的最簡單的情況是：
問題：求有限集合A，B的并的元素數目
這樣就會形成兩個等式：
等式1：
等式2：
當在涉及到多個集合時，可用最簡單的容斥原理推出以下的一般情況：
設是有限集合則會形成以下等式
群形式
在組合計數中，有一類問題需要計算集合 S 中不符合某些性質（或限制條件）的元素數量。通常情況下，集合 S 中符合某些性質的元素數量很容易計算出來。容斥原理是解決這類計數問題的有力工具，它提供了一個公式，可以用符合某些性質的元素數量來表示不符合這些性質的元素數量。首先利用自由尼爾斯·阿貝爾群可以把容斥原理的計數公式表述為中的2個元素相等，然后設 S 是一個有限集，是 S 的子集（或 S 的分別具有第個性質的元素組成的子集，當，對于任意即 S 中恰好屬于下標在J中的那些子集的元素所成的子集。||通常就是所要求計算的對象，在自由尼爾斯·阿貝爾群中，直接利用到Z的同態θ可得到經典的容斥原理的計數公式：。
相關定理
德摩根定理
德·摩根定理也稱德摩根定律、反演法，是由19世紀英國著名數學家De Morgan（德·摩根）提出。德摩根定律是數學運算的基本定律之一，它在數學中的集合論、命題邏輯、代數等領域都有使用，其中在集合中運用時，容斥原理可以配合德摩根定律解答一些相應的難題。德摩根定理的數學形式為：
(1)
(2)
例題：設愛好體育的同學組成的集合為，愛好文藝的同學組成的集合為，整個班級的同學組成的集合是，則體育和文藝都愛好的同學組成的集合是，體育和文藝都不愛好的同學組成的集合是，從而利用容斥原理再結合德摩根定律可得：
證明方法
數學歸納法
容斥原理的一般情況，可以通過一種數學證明方法——數學歸納法（Mathematical Induction, MI）進行證明。這種方法通常被用于證明某個給定命題在整個（或者局部）自然數范圍內成立。
已知時，得到
假設時有：
所以
但。
所以可以得到：
。
由上述公式可得：
。
枚舉法
枚舉法又稱元素法，是通過將問題的所有可能的答案一一列舉，然后根據條件判斷此答案是否合適，合適就保留，不合適就丟棄。根據容斥原理的一般基本公式定義可以知道，的數值等于有限集合中所有元素的個數。因此我們可以逐個分析容斥定理等式左邊集合中所有元素個數與等式右邊集合中所有元素個數的關系，在討論出所有的情況后，再全部進行證明即可得到相應的證明，證明如下：
對于任意一個元素x，分別分析這個元素與等式左邊和右邊集合的關系。對于容斥原理式子左邊有限集，元素x要么包含于要么不包含，當元素不包含于這個元素x也不包含于右邊所有的集合，故可知當核算這個元素x的個數時，等式兩邊成立，都為零。
當這個元素包含于，可假設有限集合的等價集合。然后分析元素x與集合之間的關系。可知集合中的所有元素可分類為成如下的各個部分，對于任意給定的一個元素：元素x只包含于一個中，元素x只包含于兩個中，元素x只包含于三個中，元素x只包含于n個中。
下面進行逐個證明：
當元素只包含于一個中，可假設元素只包含于，由于元素與集合的選取具有任意性，其他的證明方法可以類似。因為元素只包含于中，故，根據集合交集的定義，可知當核算這個元素的個數時，左邊式子等于1，右邊式子也等于1。
當元素x只包含于兩個中，可假設元素包含于集合,,由于元素與集合,的選取具有任意性，其他的證明方法可以類似。因為元素只包含于,中，故,，根據集合交集的定義，可知當核算這個元素 的個數時，左邊式子等于1，右邊，，
,以此類推，即右邊式子的數值等于2 ? 1 = 1等于左邊，即可證明。
推廣
定理一
集合S中恰好具有性質中k種性質的元素個數為：
推論1：當k=0時，有
以表示集合S中同時具有性質的元素個數，則
定理二
設集合中的元素具有性質，且那么，S種恰好具有中個性質中個性質的所有元素的權和：
推論2：當集合中恰好具有中個性質中個性質的元素的個數為：
。
定理三
設集合中的元素具有性質且，那么中恰好具有中r個性質且至少具有性質中個性質的元素的個數，則
證明過程：
任取，設滿足中個性質且滿足中個性質。為證明等式成立，只需說明
在等式兩邊被計數的次數是相同的即可。
1）時，在左邊中未被計數 ，而在等式右邊因為，故在等式右邊各項的中，均為被計數。
2）時，若時在左邊未被計數 ，在右邊也未被計數；若，在左邊)中被計數一次，而在右邊僅被 的項計數一次。
3）時，在左邊中未被計數，若，在右邊也未被計數，若，僅在的項中被計數，由此可知，在中被計數次，故在等式右邊所計數的總次數是：
類似理論
組合學中還有很多與容斥原理類似的基本原理，如抽屜原理、二項式定理等，在解決計數問題中應用很廣泛。
抽屜原理
抽屜原理 (boxprinciple) , 也稱做“鴿籠原理”, 學名為狄利克雷 (Dirichlet1805~1859 年 ,德國數學家 ) 原理 ,是一個基本的、重要的組合學原理。抽屜原理的基礎形式：將個物品放入個抽屜，則至少有一個抽屜中的物品數不少于兩個。
抽屜原理的其他形式：把個元素分為個集合用表示這個集合里相應的元素，則可用反證法證明至少存在某個大于或等于。
二項式定理
二項式定理，又稱牛頓二項式定理，是由英國物理學家牛頓，在1664年提出后，經過多個世紀的發展，被應用于數學領域多方面，如方程、函數、圓錐曲線、空間幾何、導數等。
二項式定理公式：
其中等式的右邊的多項式叫做的二項式展開式，展開式有項，而叫做二項式的第項，也稱作通項，可以用來表示，即叫做二項展開式第項的二項式系數。
應用領域
數學方面
容斥原理是數學中計數方面的一個重要原理，在數學中，容斥原理被廣泛應用于組合計數問題。這包括排列組合、集合論、圖論等領域。容斥原理通常用于計算滿足某些條件的對象數量，以及計算不滿足某些條件的對象數量。
素數
素數是數論中常被討論的一種特殊數字，它的個數也是無窮的，但是當在給定的一個數以內分布著多少個素數，并且怎么找到范圍內所有的素數時，便可以通過容斥原理來解決在計數時，可能會重復或者漏缺個數的問題。
色多項式
色多項式是圖論中的一個重要概念，用于描述圖的染色問題。給定一個圖G，其色多項式P(G,λ)給出了在用λ種顏色對圖G進行染色時所得到的不同染色方案的數量。而在求這個不同染色方案的數量時，便可以引入容斥原理來解決重復和漏缺的問題。還可以通過容斥原理來推到出色多項式的公式。
概率論方面
概率論（probability theory）又稱機率論，是研究隨機性或不確定性等現象的數學之一，而概率計算問題也可以通過容斥原理來解決。
定理3：
在樣本空間的有限集合內產生一個結果的實驗，事件表示，假設樣本空間內的所有結果的幾率是均等的，則任何一個事件都不發生的概率為：，其中表示事件發生的概率。
例題：
假設一家快餐店在兒童套餐中放入三種不同的玩具，一份套餐放入一個玩具，而且每一種玩具在任意一份兒童套餐里的幾率是均等的，如果買六份兒童套餐，得到所有三種玩具的概率是多少？
解：
此問題等價于把個可區分的球放入個可區分的盒子且使得沒有為空得概率，所以：
計算機方面
容斥原理算法
在通信網絡設計和運行中可靠度是一個重要參數，而可靠度可通過找出網絡所有的道路、k-樹或割集，然后再使用容斥原理的一利用容斥原理中相消項的一個非常簡單的性質給出一個求網絡可靠度的簡單而有效的容斥原理算法，證明了算法恰好給出了容斥原理表達中的不相消項，通過容斥原理的一般公式： 計算出可靠度的參數。若記為事件的交，則公式可轉化為，然后再將計算出的道路、k-樹或割集帶入公式中即可算出可靠度的參數，這就是容斥原理算法。
恢復算法
在使用頻繁項集時，有時只需要考慮單個項集的情況，例如在購物籃分析中，超市經理可能只關心四件產品同時出現的銷售情況，而不需要考慮其他產品之間的關系。但有時需要恢復所有頻繁項集以進行整體分析，這時就可以根據容斥原理，可以得知項集之間的析取支持度和合取支持度能夠相互演算，然后算出單個項集恢復。
超寬帶
超寬帶是一種新型的無線通信設備，也被稱為脈沖無線電。這種通訊設備發射出來的脈沖有很多的形式和分類，其中這種脈沖的形式和分類就需要通過容斥原理的一般形式，將它們分成不同的集合，然后計算出精確值的問題轉化為求滿足某些條件的 4 元組的問題，在通過容斥原理的思想，再計算出精確值。
參考資料 >
知識脈絡.萬方.2023-12-13
概率論.知識脈絡.2023-12-21