容斥原理与应用

写了半天，原来这个写的很好了
http://chowkafat.net/Enumeration6.html
 

點算的奧秘：容斥原理基本公式

「容斥原理」(Principle of Inclusion and Exclusion)(亦作「排容原理」)是「點算組合學」中的一條重要 原理。但凡略為複雜、包含多種限制條件的點算問題，都要用到這條原理。現在首先從一個點算問題說起。

例題1：設某班每名學生都要選修至少一種外語，其中選修英語的學生人數為25，選修法語的學生人 數為18，選修德語的學生人數為20，同時選修英語和法語的學生人數為8，同時選修英語和德語的學生人數為13 ，同時選修法語和德語的學生人數為6，而同時選修上述三種外語的學生人數則為3，問該班共有多少名學生？

答1：我們可以把上述問題表達為下圖：
其中紅色、綠色和藍色圓圈分別代表選修英語、法語和德語的學生。根據三個圓圈之間的交叉關係，可把上圖 分為七個區域，分別標以A至G七個字母。如果我們用這七個字母分別代表各字母所在區域的學生人數，那麼根 據題意，我們有以下七條等式：(1) A+D+E+G = 25；(2) B+D+F+G = 18；(3) C+E+F+G = 20；(4) D+G = 8； (5) E+G = 13；(6) F+G = 6；(7) G = 3。現在我們要求的是A+B+C+D+E+F+G。如何利用以上資料求得答案？

把頭三條等式加起來，我們得到A+B+C+2D+2E+2F+3G = 63。可是這結果包含了多餘的D、E、F和G，必須設法把 多餘的部分減去。由於等式(4)－(6)各有一個D、E和F，若從上述結果減去這三條等式，便可以把多餘的D、E和 F減去，得A+B+C+D+E+F = 36。可是這麼一來，本來重覆重現的G卻變被完全減去了，所以最後還得把等式(7)加 上去，得最終結果為A+B+C+D+E+F+G = 39，即該班共有39名學生。□

在以上例題中，給定的資料是三個集合的元素個數以及這些集合之間的交集的元素個數。在該題的解答中，我 們交替加上及減去這些給定的資料。如果我們用S₁、S₂和S₃分別代表選修 英語、法語和德語學生的集合，那麼我們要求的答案就是|S₁ ∪ S₂ ∪ S₃|，而該題的解答則可以重新表達為
|S₁ ∪ S₂ ∪ S₃| = (|S₁| + |S₂| + |S₃|) − (|S₁ ∩ S₂| + |S₁ ∩ S₃| + |S₂ ∩ S₃|) + |S₁ ∩ S₂ ∩ S₃| 我們可以把上式推廣至集合個數為n的情況，便得到以下的「容斥原理」。設有n個集合 S₁、S₂ ... S_n，那麼

|S1 ∪ S2 ∪ ... Sn| =	(|S1| + |S2| + ... |Sn|)
	− (|S1 ∩ S2| + |S1 ∩ S3| + ... |Sn − 1 ∩ Sn|)
	+ (|S1 ∩ S2 ∩ S3| + |S1 ∩ S2 ∩ S4| + ... |Sn − 2 ∩ Sn − 1 ∩ Sn|)
	− (|S1 ∩ S2 ∩ S3 ∩ S4| + ... |Sn − 3 ∩ Sn − 2 ∩ Sn − 1 ∩ Sn|)
	......
	+ (−1)n − 1 |S1 ∩ S2 ∩ ... Sn − 1 ∩ Sn|     (1)

有必要對上式作一些解釋。為易於理解，上式分數行列出，每一行都是一些集合元素個數的總和，其中第1行包 含全部n個集合S₁、S₂ ... S_n；第2行包含所有由2個集合構成的交集，應 共有C(n, 2)個項；第3行包含所有由3個集合構成的交集，應共有C(n, 3)個項...第n行包含由全部n個集合構成 的交集，這樣的交集只有C(n, n) = 1個。每行的開首交替為一個「加」(相當於「容納」)和一個「減」(相當 於「排斥」)號，第1行開首為「加」號，第2行為「減」號，第3行為「加」號，第4行為「減」號...。由於當k 為奇數時，(−1)^k = −1；當k為偶數時，(−1)^k = 1，我們可以把 第1行開首的「加」號改寫為「+ (−1)⁰」，把第2行開首的「減」號改寫為 「+ (−1)¹」...如此類推，我們可知第k行開首應有一個「+ (−1)^{k − 1} 」。

我們還可以把上式化簡，方法是引入一個新的變項S_{n, k}來代表上式等號右邊的第k行。 S_{n, k}是由C(n, k)個項加起來的總和，每個項都是由S₁、S₂ ... S_n這n個集合中抽r個出來構成的交集的元素個數。舉例說，當n = 5，k = 3時，S_{5, 3} 是由C(5, 3) = 10個項加起來的總和，這10個項都是由S₁ ... S₅這5個集合中抽3個出 來構成的交集的元素個數，其中一個是|S₂ ∩ S₄ ∩ S₅|，其餘類 推。利用S_{n, k}以及Σ求和符號，我們便可以把上面的「容斥原理」公式大大簡化為：
|S₁ ∪ S₂ ∪ ... S_n| = Σ_{1 ≤ k ≤ n} (−1)^{k − 1} S_{n, k}     (2) 接著讓我們證明以上「容斥原理」公式(1)的正確性，為此我們必須證明，S₁ ... S_n 這n個集合中的每一個元素在公式中都只被加一次。我們逐一考慮各種集合元素的情況。首先考慮那些只包含於 一個集合中的元素，每個這類元素只出現於上述公式的第1行n個集合的其中一個，因此只會被加一次。其次考 慮那些包含於兩個集合的元素，每個這類元素都出現於上述公式的第1行n個集合的其中兩個，並且出現於第2行 C(n, 2)個交集的其中一個。由於每個這類元素在第1行中被加兩次並在第2行中被減一次，因此結果該元素在公 式中被加一次。

我們把上述推理推廣至一般情況，即考慮那些包含於k個集合的元素。每個這類元素都出現於第1行的其中 C(k, 1) = k個集合，並且出現於第2行的其中C(k, 2)個交集，並且出現於第3行的其中C(k, 3)個交集...並且 出現於第k行的其中C(k, k) = 1個交集(註1)。總括而言，每個這類元素在公式中被加的次數為
C(k, 1) − C(k, 2) + C(k, 3) − C(k, 4) ... (−)^{k − 1} C(k, k) = Σ_{1 ≤ r ≤ k}(−1)^{r − 1} C(k, r) 現在的問題是，如何證明上式等於1？答案是借助《點算的奧秘：二項式定理和 多項式定理》中介紹的「二項式定理」：(a + b)ⁿ = Σ _{0 ≤ r ≤ n} C(n, r) a^r b^{n − r}。為了應用「二項式定理」，我們首先把上式等號右邊重 寫：

Σ1 ≤ r ≤ k(−1)r − 1 C(k, r)	= − Σ1 ≤ r ≤ k(−1)r C(k, r)
	= − [Σ0 ≤ r ≤ k(−1)r C(k, r) − (−1)0 C(k, 0)]
	= − Σ0 ≤ r ≤ kC(k, r) (−1)r + 1

現在如果把「二項式定理」中的a、b和n分別設定為−1、1和k，便得到Σ_{0 ≤ r ≤ k} C(k, r) (−1)^r = (−1 + 1)^k = 0。把這個結果代入上面最後一行 ，我們便得到Σ_{1 ≤ r ≤ k}(−1)^{r − 1} C(k, r) = −0 + 1 = 1。至此我們證明了每一個元素在「容斥原理」公式中都被加一次，因此該公式是正確的。

在應用上述「容斥原理」公式(1)時，我們必須逐一找出所有集合以及各種交集的元素個數，有時這是頗為繁瑣 的工作，會令上述公式失去價值，因此「容斥原理」一般應用於「可交換集合」(Exchangeable Sets)。如果從 n個集合S₁、S₂ ... S_n中任意抽取k個出來(1 ≤ r ≤ n)，所得交集 的元素個數只跟k有關，而跟抽取結果無關，則我們說這n個集合是「可交換」的。換句話說，不論是由哪k個集 合構成的交集，所得交集的元素個數都是同一個數字。

上面「容斥原理」公式(1)的第k行的每一項都是由k個集合構成的交集的元素個數。如果S₁、 S₂ ... S_n是「可交換集合」，那麼該行的每一項都是同一個數字，可不妨用符號 n_k來代表。由於該行共有C(n, k)個項，所以該行可簡化為(−1)^{k − 1} C(n, k) n_k。因此，「可交換集合」的「容斥原理」公式便是
|S₁ ∪ S₂ ∪ ... S_n| = Σ_{1 ≤ k ≤ n} (−1)^{k − 1} C(n, k) n_k     (3) 在某些應用中，所求的答案是不屬任何指定集合的元素個數，因此我們需要找出以上「容斥原理」公式的變化 形式。設某論域U包含n個集合S₁、S₂ ... S_n，現在我們要求不屬這n個集 合的任何一個的元素個數，即|S₁' ∩ S₂' ∩ ... S_n'|(註2)。根 據集合論的「德.摩根律」(De Morgan's Law)，S₁' ∩ S₂' ∩ ... S_n'等於U − (S₁ ∪ S₂ ∪ ... S_n)，因此 |S₁' ∩ S₂' ∩ ... S_n'| = |U| − |S₁ ∪ S₂ ∪ ... S_n| = |U| + (−|S₁ ∪ S₂ ∪ ... S_n|)(註3)。應用上面的「容斥原理」公式(2)，我們便得到
|S₁' ∩ S₂' ∩ ... S_n'| = |U| + Σ_{1 ≤ k ≤ n}(−1)^k S_{n, k}     (4) 同理，如果S₁、S₂ ... S_n是「可交換集合」，那麼上式便變成
|S₁' ∩ S₂' ∩ ... S_n'| = |U| + Σ_{1 ≤ k ≤ n}(−1)^k C(n, k) n_k     (5) 現在讓我們來看看「容斥原理」的一些簡單應用例子。有關該原理的其他應用，以後還會談到。

例題2：從26個英文字母中(可重覆地)抽取10個出來排成字串(String)(無需考慮這個字串是否構成一 個英文單詞)，其中不可包含全部5個元音字母(即A、E、I、O、U)，問有多少種排法？

答2：利用「容斥原理」解題的關鍵在於，把原題表達為適當的集合。就本題而言，如果我們用 S_A來代表所有由10個字母組成但不含A的字串集合...用S_U來代表所有由10個字母組成 但不含U的字串集合，那麼本題所要求的答案就是|S_A ∪ S_E ∪ S_I ∪ S_O ∪ S_U|。由於5個元音字母具有平等的地位，從S_A、 S_E、S_I、S_O和S_U這5個集合中任意抽取k個出來所構成的交集 的元素個數都是一樣的，所以這5個集合是「可交換」的。因此我們可以用上面的公式(3)來解題，但須先求得 n_k (1 ≤ k ≤ 5)的值。

我們先求n₁的值，這個值相當於由10個字母組成但不含A、E、I、O、U中某一個字母的字串的數目 。由於撇除了一個字母，我們可以從餘下的25個字母中(可重覆地)抽取10個出來排成字串，這是一個「無限重 覆排列」問題，應共有25¹⁰個這樣的字串，即n₁ = 25¹⁰。

接著考慮n₂，這個值相當於由10個字母組成但不含A、E、I、O、U中某兩個字母的字串的數目。由 於撇除了兩個字母，我們可以從餘下的24個字母中(可重覆地)抽取10個出來排成字串，因此n₂ = 24¹⁰。讀到這裡，相信讀者應能看到n_k = (26 − k)¹⁰。

最後，運用上面公式(3)，本題的答案是
Σ_{1 ≤ k ≤ 5}(−1)^{k − 1} C(5, k) (26 − k) ¹⁰ = 5 × 25¹⁰ − 10 × 24¹⁰ + 10 × 23¹⁰ − 5 × 22¹⁰ + 21¹⁰ 由於具體數字太大，這裡只列出其算式。事實上，「點算組合學」經常要和這樣的「天文數字」打交道。若非 靠邏輯思維，實在難以想像人類有何方法求得這類問題的答案，由此可見邏輯思維的巨大力量！□

例題3：現要把一對可區別的火星人、一對可區別的木星人和一對可區別的土星人安排坐在一排共6個 座位上。如規定同一類外星人不得坐在相鄰的位置上，問有多少種不同坐法？

答3：如果我們用U代表由各種不加限制的坐法組成的集合，並用S_M(S_J、 S_S)代表由兩個火星人(木星人、土星人)坐在相鄰位置的各種坐法組成的集合，那麼本題要求的答 案就是|S_M' ∩ S_J' ∩ S_S'|。本題的S_M、 S_J和S_S顯然是「可交換」的集合，因此可以用上面的公式(5)解題。

首先求|U|的值。由於6個外星人是可區別的，我們不妨用M₁、M₂、J₁、 J₂、S₁、S₂代表他們(其中M、J和S分別代表火星人、木星人和土星人)。 因此|U|的值等於把上述6個符號進行「全排列」的問題，故|U| = 6!。

接著求n₁的值，這個值相當於兩個火星人(或木星人、土星人)坐在相鄰位置的各種坐法的總數。由 於M₁、M₂總是聚在一塊，我們可以先把M₁和M₂合併為一個符 號M，然後求這個M與其餘4個符號進行「全排列」的總數，這個數應為5!。接著考慮M的「內部構造」， M₁和M₂有兩種可能形式構成M，即M₁-M₂和 M₂-M₁。總上所述，得n₁ = 5! × 2。

接著求n₂的值，這個值相當於兩個火星人以及兩個木星人(或其他組合)坐在相鄰位置的各種坐法的 總數。類似上段的做法，我們可以先把M₁和M₂以及J₁和J₂合 併為兩個新的符號M和J，然後求M、J與其餘2個符號進行「全排列」的總數，這個數應為4!。接著考慮M和J的 「內部構造」，各有兩種可能形式。總上所述，得n₂ = 4! × 2²。

接著求n₃的值，這個值相當於兩個火星人、兩個木星人和兩個土星人坐在相鄰位置的各種坐法的總 數。同樣，我們可以先把M₁和M₂、J₁和J₂以及S₁ 和S₂合併為三個新的符號M、J和S，然後求M、J和S進行「全排列」的總數，這個數應為3!。接著考 慮M、J和S的「內部構造」，各有兩種可能形式。總上所述，得n₃ = 3! × 2³。

最後，運用上面的公式(5)，求得本題答案為

	|U| − C(3, 1) n1 + C(3, 2) n2 − C(3, 3) n3
=	6! − 3 × 5! × 2 + 3 × 4! × 22 − 1 × 3! × 23
=	720 − 720 + 288 − 48
=	240 □

註1：如果讀者不明白本段的推理，可以嘗試用一個具體的例子代入上述推理，這樣便能較易明白。設n = 5，k = 4，並且假設某元素x包含於S₁、S₃、S₄和S₅這4個集合中。 那麼x出現於第1行的其中C(4, 1) = 4個集合，並且出現於第2行的其中C(4, 2) = 6個交集，這6個交集分別是 S₁ ∩ S₃、S₁ ∩ S₄、S₁ ∩ S₅、S₃ ∩ S₄、S₃ ∩ S₅和 S₄ ∩ S₅。在第3行中，x出現於C(4, 3) = 4個交集，這4個交集分別是 S₁ ∩ S₃ ∩ S₄、S₁ ∩ S₃ ∩ S₅、S₁ ∩ S₄ ∩ S₅和S₃ ∩ S₄ ∩ S₅。在4行中，x只出現於C(4, 4) = 1個交集，此即S₁ ∩ S₃ ∩ S₄ ∩ S₅。請注意x不會出現於第5行。總括而言，x在公式 中被加的次數為4 − 6 + 4 − 1 = 1次。

註2：這裡用S'代表集合S的補集(Complement Set)，即S' = U − S。

註3：這裡其實應用了集合論中的一個原理，即若T是S的子集，那麼|S − T| = |S| − |T|。

---