排容原理

排容原理（inclusion-exclusion principle）又稱容斥原理、取捨原理，在組合數學裏，其說明若$A_1, \cdots, A_n$ 為有限集，則$$\begin{align} \left|\bigcup_{i=1}^n A_i\right| = {} & \sum_{i=1}^n |A_i| - \sum_{1 \le i < j \le n} |A_i\cap A_j| + \sum_{1 \le i < j < k \le n} |A_i \cap A_j\cap A_k| - \cdots + (-1)^{n-1} \left|A_1\cap\cdots\cap A_n\right|. \end{align}$$

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

## 描述

### 兩個集合的容斥原理

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

### 三個集合的容斥原理

$$\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 |$$

### $n$個集合的容斥原理

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

最終得到公式：

$$\begin{align} \left|\bigcup_{i=1}^n A_i\right| = {} & \sum_{i=1}^n |A_i| - \sum_{1 \le i < j \le n} |A_i\cap A_j| + \sum_{1 \le i < j < k \le n} |A_i \cap A_j\cap A_k| - \cdots + (-1)^{n-1} \left|A_1\cap\cdots\cap A_n\right|. \end{align}$$

又可寫成

$$\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, \cdots, 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,\Sigma,\mu)$ 和有限測度的可測子集 $A_1, \cdots, A_n$，上面的恆等式也成立，如果把機率測度 $\mathbb{P}$ 換為測度 $\mu$。

## 特殊情況

如果在容斥原理的機率形式中，交集 $A_I$ 的機率只與I中元素的個數有關，也就是說，對於$\{1,\cdots,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 nk a_k$$

這是由於二項式係數$\scriptstyle\binom nk$的組合解釋。

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

$$A_I:=\bigcap_{i\in I} A_i$$

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

$$\biggl|\bigcup_{i=1}^n A_i\biggr| =\sum_{k=1}^n (-1)^{k-1}\binom nk a_k\,.$$

在一般的測度空間 $(S,\Sigma,\mu)$ 和有限測度的可測子集 $A_1, \cdots, 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_1, \cdots, A_n$ 的併集中的每一個 $x$，等式都成立。假設 $x$ 正好屬於 $m$ 個集合（$1\leq m\leq n$），不妨設它們為$A_1, \cdots, 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 mk$ 的組合解釋。由於$\textstyle1=\binom m0$，我們有：

$$\binom m0 =\sum_{k=1}^m (-1)^{k-1}\binom mk.$$

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

第二種方法 設 $A$ 表示集合 $A_1, \cdots, 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_1 = n(A_1) + n(A_2) + n(A_3) + \cdots + n(A_n)$$

$$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)$$

$$S_3 = n(A_1 \cap A_2 \cap A_3) + \cdots + n(A_{n-2} \cap A_{n-1} \cap A_n)$$

⋮

$$S_n = n(A_1 \cap A_2 \cap A_3 \cap \cdots \cap A_n)$$

求證$$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.$$

證明：

當$n=2$時。

$$n(A_1 \cup A_2) = n(A_1) + n(A_2) - n(A_1 \cap A_2) = S_1 - S_2.$$

假設當$n=k\ (k\ge2)$時，有$$n(A_1 \cup A_2 \cup \cdots \cup A_k) = S_1 - S_2 + S_3 - \cdots + (-1)^{k-1} S_k.$$

當$n=k+1$時。

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

∵ 當 $n=k$ 時，上式成立。

∴$$n(A_1 \cup A_2 \cup \cdots \cup A_{k+1}) = S_1 - S_2 + S_3 - \cdots + (-1)^k S_{k+1}.$$

綜上所述，當$n\ge2$時。

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

## 其它形式

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

$$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+\frac{1}{2}]$，其中$[x]$表示最接近 $x$ 的整數。

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

## 交集的計算

容斥原理與德·摩根定理結合起來，也可以用於計算集合的交集中元素的數目。設 $\overline{A}_k$ 表示 $A_k$關於全集 $A$ 的補集，使得對於每一個 $k$，都有 $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