排容原理

排容原理（inclusion-exclusion principle）又稱容斥原理，在組合數學裏，其說明若${\displaystyle A_{1},\cdots ,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|}$相加，再減去其交集的基數，而得到其併集的基數。

描述

兩個集合的排容原理  

${\displaystyle \left|A\cup B\right|=\left|A\right|+\left|B\right|-\left|A\cap B\right|}$

三個集合的排容原理

${\displaystyle \left|A\cup B\cup C\right|=\left|A\right|+\left|B\right|+\left|C\right|-\left|A\cap B\right|-\left|A\cap C\right|-\left|B\cap C\right|+\left|A\cap B\cap C\right|}$

${\displaystyle 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} )}$中的事件 ${\displaystyle A_{1},\cdots ,A_{n}}$，當 ${\displaystyle 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}),}$

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

對於一般的測度空間 ${\displaystyle (S,\Sigma ,\mu )}$ 和有限測度的可測子集 ${\displaystyle A_{1},\cdots ,A_{n}}$，上面的恆等式也成立，如果把概率測度 ${\displaystyle \mathbb {P} }$ 換為測度 ${\displaystyle \mu }$。

特殊情況

如果在排容原理的概率形式中，交集 ${\displaystyle A_{I}}$ 的概率只與I中元素的個數有關，也就是說，對於${\displaystyle \{1,\cdots ,n\}}$ 中的每一個 ${\displaystyle k}$，都存在一個 ${\displaystyle 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}}}$的組合解釋。

類似地，如果對有限集合 ${\displaystyle A_{1},\cdots ,A_{n}}$ 的併集的元素個數感興趣，且對於 ${\displaystyle \{1,\cdots ,n\}}$ 中的每一個 ${\displaystyle k}$，交集

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

的元素個數都相同，例如 ${\displaystyle a_{k}=|A_{I}|}$，與 ${\displaystyle \{1,\cdots ,n\}}$ 的 ${\displaystyle k}$ 元素子集 ${\displaystyle I}$ 無關，則：

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

在一般的測度空間 ${\displaystyle (S,\Sigma ,\mu )}$ 和有限測度的可測子集 ${\displaystyle A_{1},\cdots ,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 (*)}$

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

第一種方法 我們只需證明對於 ${\displaystyle A_{1},\cdots ,A_{n}}$ 的併集中的每一個 ${\displaystyle x}$，等式都成立。假設 ${\displaystyle x}$ 正好屬於 ${\displaystyle m}$ 個集合（${\displaystyle 1\leq m\leq n}$），不妨設它們為${\displaystyle A_{1},\cdots ,A_{m}}$。則 ${\displaystyle x}$ 處的等式化為：

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

${\displaystyle m}$ 元素集合中的 ${\displaystyle 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}}.}$

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

第二種方法 設 ${\displaystyle A}$ 表示集合 ${\displaystyle A_{1},\cdots ,A_{n}}$ 的併集。於是：

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

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

歸納法證明

設 ${\displaystyle S_{1}=n(A_{1})+n(A_{2})+n(A_{3})+\cdots +n(A_{n})}$

${\displaystyle S_{2}=n(A_{1}\cap A_{2})+n(A_{1}\cap A_{3})+\cdots +n(A_{1}\cap A_{n})\;+\;n(A_{2}\cap A_{3})+\cdots +n(A_{n-1}\cap A_{n})}$

${\displaystyle S_{3}=n(A_{1}\cap A_{2}\cap A_{3})+\cdots +n(A_{n-2}\cap A_{n-1}\cap A_{n})}$

⋮

${\displaystyle S_{n}=n(A_{1}\cap A_{2}\cap A_{3}\cap \cdots \cap A_{n})}$

求證 ${\displaystyle n(A_{1}\cup A_{2}\cup A_{3}\cup \cdots \cup A_{n})=S_{1}-S_{2}+S_{3}-\cdots +(-1)^{n-1}S_{n}.}$

證明： 當${\displaystyle n=2}$時， ${\displaystyle n(A_{1}\cup A_{2})=n(A_{1})+n(A_{2})-n(A_{1}\cap A_{2})=S_{1}-S_{2}.}$

假設當${\displaystyle n=k\ (k\geq 2)}$時，有 ${\displaystyle n(A_{1}\cup A_{2}\cup \cdots \cup A_{k})=S_{1}-S_{2}+S_{3}-\cdots +(-1)^{k-1}S_{k}.}$

當${\displaystyle n=k+1}$時， ${\displaystyle {\begin{aligned}n(A_{1}\cup A_{2}\cup \cdots \cup A_{k}\cup A_{k+1})&=n{\Bigl (}(A_{1}\cup A_{2}\cup \cdots \cup A_{k})\cup A_{k+1}{\Bigr )}\\[1ex]&=n(A_{1}\cup A_{2}\cup \cdots \cup A_{k})+n(A_{k+1})\\[1ex]&\quad -n{\Bigl (}(A_{1}\cup A_{2}\cup \cdots \cup A_{k})\cap A_{k+1}{\Bigr )}\\[1ex]&=n(A_{1}\cup A_{2}\cup \cdots \cup A_{k})+n(A_{k+1})\\[1ex]&\quad -n{\Bigl (}(A_{1}\cap A_{k+1})\cup (A_{2}\cap A_{k+1})\cup \cdots \cup (A_{k}\cap A_{k+1}){\Bigr )}.\end{aligned}}}$

∵ 當 ${\displaystyle n=k}$ 時，上式成立， ∴ ${\displaystyle n(A_{1}\cup A_{2}\cup \cdots \cup A_{k+1})=S_{1}-S_{2}+S_{3}-\cdots +(-1)^{k}S_{k+1}.}$

綜上所述，當${\displaystyle n\geq 2}$時， ${\displaystyle {\begin{aligned}n(A_{1}\cup A_{2}\cup \cdots \cup A_{n})=&\;n(A_{1})+n(A_{2})+\cdots +n(A_{n})\\[1ex]&\;-{\Bigl [}n(A_{1}\cap A_{2})+n(A_{1}\cap A_{3})+\cdots +n(A_{n-1}\cap A_{n}){\Bigr ]}\\[1ex]&\;+{\Bigl [}n(A_{1}\cap A_{2}\cap A_{3})+\cdots {\Bigr ]}\\[1ex]&\;-\cdots +(-1)^{n-1}n(A_{1}\cap A_{2}\cap \cdots \cap A_{n}).\end{aligned}}}$

其它形式

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

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

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

應用

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

錯排

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

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

交集的計算

排容原理與德·摩根定理結合起來，也可以用於計算集合的交集中元素的數目。設 ${\displaystyle {\overline {A}}_{k}}$ 表示 ${\displaystyle A_{k}}$關於全集 ${\displaystyle A}$ 的補集，使得對於每一個 ${\displaystyle k}$，都有 ${\displaystyle 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 （頁面存檔備份，存於網際網路檔案館）

參考文獻

• 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協議：署名-相同方式共享協議。