排容原理

三個集的情況

排容原理（inclusion-exclusion principle）又稱容斥原理，在組合數學裏，其說明若$A_{1}$, ..., $A_{n}$ 為有限集，則 ${\begin{aligned}\left|\bigcup _{i=1}^{n}A_{i}\right|={}&\sum _{i=1}^{n}|A_{i}|-\sum _{1\leq i<j\leq n}|A_{i}\cap A_{j}|+\sum _{1\leq i<j<k\leq n}|A_{i}\cap A_{j}\cap A_{k}|-\cdots +(-1)^{n-1}\left|A_{1}\cap \cdots \cap A_{n}\right|.\end{aligned}}$

其中$|A|$表示$A$的基數。例如在兩個集的情況時，我們可以通過將$|A|$和$|B|$相加，再減去其交集的基數，而得到其併集的基數。

描述

兩個集合的容斥原理  

n(A∪B)=n(A)+n(B) -n(A∩B)

三個集合的容斥原理

|A∪B∪C|=|A|+|B|+|C|-|A∩B|-|A∩C|-|B∩C|+|A∩B∩C|

n個集合的容斥原理

      要計算幾個集合併集的大小，我們要先將所有單個集合的大小計算出來，然後減去所有兩個集合相交的部分，再加回所有三個集合相交的部分，再減去所有四個集合相交的部分，依此類推，一直計算到所有集合相交的部分。

最終得到公式：

${\begin{aligned}\left|\bigcup _{i=1}^{n}A_{i}\right|={}&\sum _{i=1}^{n}|A_{i}|-\sum _{1\leq i<j\leq n}|A_{i}\cap A_{j}|+\sum _{1\leq i<j<k\leq n}|A_{i}\cap A_{j}\cap A_{k}|-\cdots +(-1)^{n-1}\left|A_{1}\cap \cdots \cap A_{n}\right|.\end{aligned}}$

又可寫成

$\left|\bigcup _{i=1}^{n}A_{i}\right|=\sum _{k=1}^{n}(-1)^{k+1}\left(\sum _{1\leq i_{1}<\cdots <i_{k}\leq n}|A_{i_{1}}\cap \cdots \cap A_{i_{k}}|\right)$

或

$\left|\bigcup _{i=1}^{n}A_{i}\right|=\sum _{\emptyset \neq J\subseteq \{1,2,\ldots ,n\}}(-1)^{|J|-1}{\Biggl |}\bigcap _{j\in J}A_{j}{\Biggr |}.$

概率論中的容斥原理

在概率論中，對於概率空間$(\Omega ,{\mathcal {F}},\mathbb {P} )$中的事件A₁，……，A_n，當n = 2時容斥原理的公式為：

$\mathbb {P} (A_{1}\cup A_{2})=\mathbb {P} (A_{1})+\mathbb {P} (A_{2})-\mathbb {P} (A_{1}\cap A_{2}),$

當n = 3時，公式為：

$\mathbb {P} (A_{1}\cup A_{2}\cup A_{3})=\mathbb {P} (A_{1})+\mathbb {P} (A_{2})+\mathbb {P} (A_{3})-\mathbb {P} (A_{1}\cap A_{2})-\mathbb {P} (A_{1}\cap A_{3})-\mathbb {P} (A_{2}\cap A_{3})+\mathbb {P} (A_{1}\cap A_{2}\cap A_{3})$

一般地：

$\mathbb {P} {\biggl (}\bigcup _{i=1}^{n}A_{i}{\biggr )}=\sum _{i=1}^{n}\mathbb {P} (A_{i})-\sum _{i,j\,:\,i<j}\mathbb {P} (A_{i}\cap A_{j})+\sum _{i,j,k\,:\,i<j<k}\mathbb {P} (A_{i}\cap A_{j}\cap A_{k})-\ \cdots \ +(-1)^{n-1}\,\mathbb {P} {\biggl (}\bigcap _{i=1}^{n}A_{i}{\biggr )},$

也可以寫成：

$\mathbb {P} {\biggl (}\bigcup _{i=1}^{n}A_{i}{\biggr )}=\sum _{k=1}^{n}(-1)^{k-1}\sum _{\scriptstyle I\subset \{1,\ldots ,n\} \atop \scriptstyle |I|=k}\mathbb {P} (A_{I}),$

對於一般的測度空間(S,Σ,μ)和有限測度的可測子集A₁，……，A_n，上面的恆等式也成立，如果把概率測度$\mathbb {P}$換為測度μ。

特殊情況

如果在容斥原理的概率形式中，交集A_I的概率只與I中元素的個數有關，也就是說，對於{1, ..., n}中的每一個k，都存在一個a_k，使得：

$a_{k}=\mathbb {P} (A_{I})$，對於每一個$I\subset \{1,\ldots ,n\}\,\,(|I|=k),$

則以上的公式可以簡化為：

$\mathbb {P} {\biggl (}\bigcup _{i=1}^{n}A_{i}{\biggr )}=\sum _{k=1}^{n}(-1)^{k-1}{\binom {n}{k}}a_{k}$

這是由於二項式係數$\scriptstyle {\binom {n}{k}}$的組合解釋。

類似地，如果對有限集合A₁，……，A_n的併集的元素個數感興趣，且對於{1, ..., n}中的每一個k，交集

$A_{I}:=\bigcap _{i\in I}A_{i}$

的元素個數都相同，例如a_k = |A_I|，與{1, ..., n}的k元素子集I無關，則：

${\biggl |}\bigcup _{i=1}^{n}A_{i}{\biggr |}=\sum _{k=1}^{n}(-1)^{k-1}{\binom {n}{k}}a_{k}\,.$

在一般的測度空間(S,Σ,μ)和有限測度的可測子集A₁，……，A_n的情況中，也可以進行類似的簡化。

容斥原理的證明

欲證明容斥原理，我們首先要驗證以下的關於指示函數的等式：

$1_{\cup _{i=1}^{n}A_{i}}=\sum _{k=1}^{n}(-1)^{k-1}\sum _{\scriptstyle I\subset \{1,\ldots ,n\} \atop \scriptstyle |I|=k}1_{A_{I}}\qquad (*)$

至少有兩種方法來證明這個等式：

第一種方法 我們只需證明對於A₁，……，A_n的併集中的每一個x，等式都成立。假設x正好屬於m個集合（1 ≤ m ≤ n），不妨設它們為A₁，……，A_m。則x處的等式化為：

$1=\sum _{k=1}^{m}(-1)^{k-1}\sum _{\scriptstyle I\subset \{1,\ldots ,m\} \atop \scriptstyle |I|=k}1.$

m元素集合中的k元素子集的個數，是二項式係數$\textstyle {\binom {m}{k}}$ 的組合解釋。由於$\textstyle 1={\binom {m}{0}}$ ，我們有：

${\binom {m}{0}}=\sum _{k=1}^{m}(-1)^{k-1}{\binom {m}{k}}.$

把所有的項移到等式的左端，我們便得到(1 – 1)^m的二項式展開式，因此可以看出，(*)對x成立。

第二種方法 設A表示集合A₁，……，A_n的併集。於是：

$0=(1_{A}-1_{A_{1}})(1_{A}-1_{A_{2}})\cdots (1_{A}-1_{A_{n}})\,,$

這是因為對於不在A內的x，兩邊都等於零，而如果x屬於其中一個集合，例如A_m，則對應的第m個因子為零。把右端的乘積展開來，便可得到等式(*)。

歸納法證明

設：S₁= n (A₁)+n (A₂)+n (A₃) +…...+n (A_n)

S₂= n(A₁∩A₂)+ n(A₁∩A₃) …...+ n(A₁∩A_n)+ n(A₂∩A₃)+ …...+n(A_n-1∩An)

S₃= n(A₁∩A₂∩A₃)+ ……+ n(A_n-2∩A_n-1∩An)_……

S_n =n(A₁∩A₂∩A₃∩……∩A_n)

求證：A=n(A₁∪A₂∪A₃∪A₄……∪A_n)= S₁-S₂+ S₃+……+(-1)^n-1S_n

證明：當n=2時，A=n(A₁∪A₂)=n(A₁)+n(A₂) -n(A₁∩ A₂)= S₁-S₂

假設：當n=k(k>=2)時，A=n (A₁∪A₂∪A₃∪A₄……∪A_k)= S₁-S₂+ S₃+……+(-1)^k-1S_k 等式成立。

當n=k+1時，

A= n( (A₁∪A₂∪A₃∪A₄……∪A_k) ∪A_k+1)

= n (A₁∪A₂∪A₃∪A₄……∪A_k)+n(A_k+1)-n((A₁∪A₂∪A₃∪A₄……∪A_k) ∩A_k+1)

= n (A₁∪A₂∪A₃∪A₄……∪A_k) +n(A_k+1)-n((A₁∩A_k+1) ∪(A₂∩A_k+1) ∪(A₃∩A_k+1) ∪ …∪(A_k∩A_k+1))

∵ 當n=k時，等式成立

∴A= n (A₁∪A₂∪A₃∪A₄……∪A_k) +n(A_k+1)-(n (A₁∩A_k+1)+ n (A₂∩A_k+1)+ ……+n(A_k∩A_k+1)-n(A₁∩A₂∩A_k+1)-n(A₁A₃∩A_k+1) -……- n(A_k-1∩A_k∩A_k+1)+ ……+(-1)^k.n(A₁∩A₂∩A₃∩∪……∩A_k+1)

   = S₁-S₂+ S₃+……+(-1)^k-1S_k+n(A_k+1)-(n (A₁∩A_k+1)+ n (A₂∩A_k+1)+ ……+n(A_k∩A_k+1)-n(A₁∩A₂∩A_k+1)-n(A₁∩A₃∩A_k+1) -……- n(A_k-1∩A_k∩A_k+1)+ ……+(-1)^k.n(A₁∩A₂∩A₃∩∪……∩A_k+1)

    = S₁-S₂+ S₃+……+(-1)^kS_k+1

綜上所述，當n>=2時,n (A₁∪A₂∪A₃∪A₄……∪A_n)

= n (A₁)+n (A₂)+n (A₃) ……+ n (A_n)-n(A₁∩A₂)- n(A₁∩A₃) ……- n(A₁∩A_n)- n(A₂∩A₃)- ……-n(A_n-1∩An)+n(A₁∩A₂∩A₃)+ n(A₁∩A₂∩A₃)+ ……+ n(A_n-2∩A_n-1∩An)- ……+……+(-1)^n-1.n(A₁∩A₂∩A₃∩……∩A_n)

其它形式

有時容斥原理用以下的形式來表述：如果

$g(A)=\sum _{S\,:\,S\subseteq A}f(S)$

那麼：

$f(A)=\sum _{S\,:\,S\subseteq A}(-1)^{\left|A\right|-\left|S\right|}g(S)$

在這種形式中可以看出，它是A的所有子集的偏序集合的指標代數的莫比烏斯反演公式。

應用

在許多情況下，容斥原理都可以給出精確的公式（特別是用埃拉托斯特尼篩法計算素數的個數時），但是用處不大，這是因為它裡面含有的項太多。即使每一個單獨的項都可以準確地估計，誤差累積起來仍然意味着容斥原理不能直接應用。在數論中，這個困難由維戈·布朗解決。開始時進展很慢，但他的想法逐漸被其他數學家所應用，於是便產生了許多各種各樣的篩法。這些方法是嘗試找出被「篩選」的集合的上界，而不是一個確切的公式。

錯排

容斥原理的一個著名的應用，是計算一個有限集合的所有亂序排列的數目。一個集合A的錯排，是從A到A的沒有不動點的雙射。通過容斥原理，我們可以證明，如果A含有n個元素，則亂序排列的數目為[n! / e]，其中[x]表示最接近x的整數。

這也稱為n的子階乘，記為!n。可以推出，如果所有的雙射都有相同的概率，則當n增大時，一個隨機雙射是錯排的概率迅速趨近於1/e。

交集的計算

容斥原理與德·摩根定理結合起來，也可以用於計算集合的交集中元素的數目。設$\scriptstyle {\overline {A}}_{k}$表示A_k關於全集A的補集，使得對於每一個k，都有$\scriptstyle A_{k}\,\subseteq \,A$。於是，我們有：

$\bigcap _{i=1}^{n}A_{i}={\overline {\bigcup _{i=1}^{n}{\overline {A}}_{i}}}$

這樣便把計算交集的問題化為計算併集的問題。

參見

• 其他組合原理，如：
  • 乘法原理
  • 抽屜原理
• 布爾不等式
• 項鍊問題
• 許特-內斯比特公式
• 最大-最小恆等式

拓展閱讀

• http://cs.tju.edu.cn/faculty/zhangkl/teaching/comb/lec09.pdf （頁面存檔備份，存於網際網路檔案館）

• http://blog.sina.com.cn/s/blog_6be9596c0100miag.html （頁面存檔備份，存於網際網路檔案館）

• http://e-maxx.ru/algo/inclusion_exclusion_principle （頁面存檔備份，存於網際網路檔案館） （頁面存檔備份，存於網際網路檔案館）（俄文） 中文翻譯：http://www.cppblog.com/vici/archive/2011/09/05/155103.html （頁面存檔備份，存於網際網路檔案館）

參考文獻

• Klaus Dohmen: Improved Bonferroni Inequalities via Abstract Tubes - Inequalities and Identities of Inclusion-Exclusion Type, Springer-Verlag, 2003, ISBN 3-540-20025-8.
• Stasys Jukna: Extremal Combinatorics, Springer, 2001, ISBN 3-540-66313-4.
• http://blog.csdn.net/xianglunxi/article/details/9310105 （頁面存檔備份，存於網際網路檔案館）

本條目含有來自PlanetMath《principle of inclusion-exclusion》的內容，版權遵守知識共享協議：署名-相同方式共享協議。