有捨即有得：取捨原理

本文簡介取捨原理（in­clu­sion–ex­clu­sion prin­ci­ple），也稱為排容原理、容斥原理。

1　取捨原理

1.1　定理

對於任意非負整數 $n \comma$我們定義 $[n] = \{0, 1, \ldots, n{\.-\.}1\} \period$

當我們從一特定集合中去除一些子集後，我們可以由這些子集交集的大小求得差集的大小，例如： \[\begin{split} \lvert X \setminus (A_0 \cup A_1) \rvert &= \lvert X \rvert - \lvert A_0 \rvert - \lvert A_1 \rvert + \lvert A_0 \cap A_1 \rvert \comma \\ \lvert X \setminus (A_0 \cup A_1 \cup A_2) \rvert &= \lvert X \rvert - \lvert A_0 \rvert - \lvert A_1 \rvert - \lvert A_2 \rvert \\ &\hspace{1.75em} + \lvert A_0 \cap A_1 \rvert + \lvert A_0 \cap A_2 \rvert + \lvert A_1 \cap A_2 \rvert \\ &\hspace{1.75em} - \lvert A_0 \cap A_1 \cap A_2 \rvert \period \end{split}\]

定理 1（取捨原理）即為上述等式一般化的狀況。

定理 1（取捨原理） 設 $X$ 為一有限集合，且 $A_0, A_1, \ldots, A_{n-1}$ 均為 $X$ 的子集，其中 $n$ 為一正整數。則我們有 \[\begin{split} \Biggl| X \setminus \bigcup_{i=0}^{n-1} A_i\Biggr| = \lvert X \rvert + \mkern-5mu \sum_{\varnothing \neq I \subseteq [n]} (-1)^{\lvert I \rvert} \Biggl|\.\bigcap_{i\.\in\.I}{A_i}\Biggr| \period \end{split}\]

證明　我們對 $n$ 使用數學歸納法。當 $n = 1$ 時，有 \[\begin{split}\lvert X \setminus A_0 \rvert = \lvert X \rvert - \lvert A_0 \rvert \period\end{split}\] 接著假設定理在 $n = m$ 時成立，其中 $m \geq 1 \period$我們說明定理在 $n = m+1$ 時成立：首先注意到我們有 \[\begin{split} X \setminus \bigcup_{i=0}^m A_i &= \Biggl(X \setminus \bigcup_{i=0}^{m-1} A_i\Biggr) \setminus \Biggl(A_m \setminus \bigcup_{i=0}^{m-1} (A_i \cap A_m)\Biggr) \period \end{split}\] 因而 \[\begin{split} \Biggl|X \setminus \bigcup_{i=0}^m A_i\Biggr| &= \Biggl|X \setminus \bigcup_{i=0}^{m-1} A_i\Biggr| - \Biggl|A_m \setminus \bigcup_{i=0}^{m-1} (A_i \cap A_m)\Biggr| \\ &= \Biggl(\lvert X \rvert + \mkern-5mu \sum_{\varnothing \neq I \subseteq [m]} (-1)^{\lvert I \rvert} \Biggl|\.\bigcap_{i\.\in\.I}{A_i}\Biggr|\,\Biggr) \\ &\hspace{1.75em} - \Biggl(\lvert A_m \rvert + \mkern-5mu \sum_{\varnothing \neq J \subseteq [m]} (-1)^{\lvert J \rvert} \Biggl|\.\bigcap_{i\.\in\.J}{(A_i \cap A_m)}\Biggr|\,\Biggr) \\ &= \lvert X \rvert + \mkern-5mu \sum_{\varnothing \neq I \subseteq [m+1]} (-1)^{\lvert I \rvert} \Biggl|\.\bigcap_{i\.\in\.I}{A_i}\Biggr| \period \end{split}\] 由此可知定理對所有正整數 $n$ 均成立，故定理得$\textrm{證。}\mkern6mu\blacksquare$

1.2　例子

範例 1　我們將一對一且映成的函數稱為對射（bi­jec­tion）。

給定一集合 $S$，若一對射 $f \colon S \to S$ 對所有 $x \in S$ 皆滿足 $f(x) \neq x$，則我們稱 $f$ 為 $S$ 的一個錯排（de­range­ment）。

對於任意非負整數 $n$，我們嘗試計算集合 $[n] = \{0 \cm 1 \cm \ldots \cm {n{\.-\.}1}\}$ 上的錯排的個數 $d_n$，並找出 $d_n / n!$ 在 $n$ 趨近無窮大時的極限。

設 $X$ 為 $[n]$ 的所有對射 $f \colon [n] \to [n]$ 所構成的集合；對任意 $i \in [n]$，設 $A_i$ 為滿足 $f(i) = i$ 的對射 $f \colon [n] \to [n]$ 所構成的集合。

注意到對任意 $\varnothing \neq I \subseteq [n] \comma$有 \[\begin{split}\Biggl|\.\bigcap_{i \.\in\. I} A_i\Biggr| = (n - \mkern-2mu \lvert I \mkern-1mu \rvert)!\period\end{split}\] 因而由定理 1（取捨原理）可得 \[\begin{split} d_n &= \Biggl|X \setminus \bigcup_{i=0}^{n-1} A_i\Biggr| \\ &= \lvert X \rvert + \mkern-5mu \sum_{\varnothing \neq I \subseteq [n]} (-1)^{\lvert I \rvert} \Biggl|\.\bigcap_{i\.\in\.I}{A_i}\Biggr| \\ &= n! + \sum_{\varnothing \neq I \subseteq [n]} (-1)^{\lvert I \rvert} (n-\lvert I \rvert)! \\ &= n! + \sum_{r=1}^n \binom{n}{r}(-1)^r (n-r)! \\ &= n! + \sum_{r=1}^n \frac{n!}{r!} (-1)^r \\ &= n! \sum_{r=0}^n \frac{(-1)^r}{r!} \period \end{split}\] 換句話說，若我們由 $X$ 中隨機抽出一個排列，則其為一錯排的機率為 \[\begin{split}p_n = \frac{d_n}{n!} = \sum_{r=0}^n \frac{(-1)^r}{r!} \period\end{split}\] 因而 \[\begin{split}\lim_{n \to \infty} p_n = \sum_{r \geq 0} \frac{(-1)^r}{r!} = \frac{1}{e}\comma\end{split}\] 即在 $n$ 趨近無窮大時，由 $X$ 中抽出錯排的機率會趨近於 $1/e \period$（事實上，$n \geq 1$ 時，$d_n$ 即為最接近 $n!/e$ 的整數。）