排容原理

排容原理（inclusion-exclusion principle）又稱容斥原理，在組合數學裏，其說明若${\displaystyle A_{1}}$, ..., ${\displaystyle A_{n}}$ 為有限集，則 ${\displaystyle {\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}}}$

三個集的情況

其中${\displaystyle |A|}$表示${\displaystyle A}$的基數。例如在兩個集的情況時，我們可以通過將${\displaystyle |A|}$和${\displaystyle |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個集合的容斥原理

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

最終得到公式：

${\displaystyle {\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}}}$

又可寫成

${\displaystyle \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)}$

或

${\displaystyle \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 |}.}$

概率論中的容斥原理

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

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

當n = 3時，公式為：

${\displaystyle \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})}$

一般地：

${\displaystyle \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 )},}$

也可以寫成：

${\displaystyle \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，上面的恆等式也成立，如果把概率測度${\displaystyle \mathbb {P} }$換為測度μ。

特殊情況

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

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

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

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

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

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

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

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

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

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

容斥原理的證明

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

${\displaystyle 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處的等式化為：

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

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

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

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

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

${\displaystyle 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)^[1]

其它形式

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

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

那麼：

${\displaystyle 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。

交集的計算

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

${\displaystyle \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 （頁面存檔備份，存於網際網路檔案館）

參考文獻

1. 容斥原理的猜测与证明_ty1108_新浪博客. blog.sina.com.cn. [2018-02-06]. （原始內容存檔於2019-08-22）.

• 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》的內容，版權遵守知識共享協議：署名-相同方式共享協議。