容斥原理

**排容原理**（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_1，……，_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_1，……，_An_，上面的恆等式也成立，如果把概率測度 $\mathbb {P} $ 換為測度 _μ_。

## 特殊情況

如果在排容原理的概率形式中，交集 _AI_ 的概率只與 _I_ 中元素的個數有關，也就是說，對於 {1, ...,_n_} 中的每一個 _k_，都存在一個 _ak_，使得：

　
: $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_1，……，_An_ 的併集的元素個數感興趣，且對於 {1, ..., _n_} 中的每一個 _k_，交集

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

的元素個數都相同，例如 _ak_ = |_AI_|，與 {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_1，……，_An_ 的情況中，也可以進行類似的簡化。

## 排容原理的證明

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

　
: $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_1，……，_An_ 的併集中的每一個 _x_，等式都成立。假設 _x_ 正好屬於 _m_ 個集合（1 ≤_m_ ≤ _n_），不妨設它們為 _A_1，……，_Am_。則 _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_1，……，_An_ 的併集。於是：

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

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

### 歸納法證明

設：S1= n (A1)+n (A2)+n (A3) +…...+n (An)

S2= n(A1∩A2)+ n(A1∩A3) …...+ n(A1∩An)+ n(A2∩A3)+ …...+n(An-1∩An)

S3= n(A1∩A2∩A3)+ ……+ n(An-2∩An-1∩An)……

Sn =n(A1∩A2∩A3∩……∩An)

求證：A=n (A1∪A2∪A3∪A4……∪An)= S1-S2+ S3+……+(-1)n-1Sn

證明：當 n=2 時，A=n (A1∪A2)=n(A1)+n(A2) -n(A1∩ A2)= S1-S2

假設：當 n=k (k>=2) 時，A=n (A1∪A2∪A3∪A4……∪Ak)= S1-S2+ S3+……+(-1)k-1Sk 等式成立。

當 n=k+1 時，

A= n( (A1∪A2∪A3∪A4……∪Ak) ∪Ak+1)

= n (A1∪A2∪A3∪A4……∪Ak)+n(Ak+1)-n((A1∪A2∪A3∪A4……∪Ak) ∩Ak+1)

= n (A1∪A2∪A3∪A4……∪Ak) +n(Ak+1)-n((A1∩Ak+1) ∪(A2∩Ak+1) ∪(A3∩Ak+1) ∪ …∪(Ak∩Ak+1))

∵ 當 n=k 時，等式成立

∴A= n (A1∪A2∪A3∪A4……∪Ak) +n(Ak+1)-(n (A1∩Ak+1)+ n (A2∩Ak+1)+ ……+n(Ak∩Ak+1)-n(A1∩A2∩Ak+1)-n(A1A3∩Ak+1) -……- n(Ak-1∩Ak∩Ak+1)+ ……+(-1)k.n(A1∩A2∩A3∩∪……∩Ak+1)

   = S1-S2+ S3+……+(-1)k-1Sk+n(Ak+1)-(n (A1∩Ak+1)+ n (A2∩Ak+1)+ ……+n(Ak∩Ak+1)-n(A1∩A2∩Ak+1)-n(A1∩A3∩Ak+1) -……- n(Ak-1∩Ak∩Ak+1)+ ……+(-1)k.n(A1∩A2∩A3∩∪……∩Ak+1)

    = S1-S2+ S3+……+(-1)kSk+1

綜上所述，當 n>=2 時，n (A1∪A2∪A3∪A4……∪An)

= n (A1)+n (A2)+n (A3) ……+ n (An)-n(A1∩A2)- n(A1∩A3) ……- n(A1∩An)- n(A2∩A3)- ……-n(An-1∩An)+n(A1∩A2∩A3)+ n(A1∩A2∩A3)+ ……+ n(An-2∩An-1∩An)- ……+……+(-1)n-1.n(A1∩A2∩A3∩……∩An)

## 其它形式

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

　
: $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》的內容，版權遵守創用 CC 協議：署名 - 相同方式共享協議。