渭南师范学院招生网-汽车销售工作总结

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

「容斥原理」(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。可是這結果包含了< br>多餘的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
1
、S
2
和S< br>3
分別代表選修英語、法語和德語學生的集合，那麼我們要求的答案就
是|S
1
∪ S
2
∪ S
3
|，而該題的解答則可以重新表達為

|S
1
∪ S
2
∪ S
3
| = (|S
1
| + |S
2
| + |S
3
|) − (|S
1
∩ S
2
| + |S
1
∩ S
3
| + |S
2
∩
S
3
|) + |S
1
∩ S
2
∩ S
3
|
我們可以把上式推廣至集合個數為n的情況，便得到以下的「容斥原理」。設有
n個集合 S
1
、S
2
... S
n
，那麼
|S
1
∪ S
2
∪ ... S
n
|
(|S
1
| + |S
2
| + ... |S
n
|)
=





− (|S
1
∩ S
2
| + |S
1
∩ S
3
| + ... |S
n
−
1
∩ S
n
|)
+ (|S
1
∩ S
2
∩ S
3
| + |S
1
∩ S
2
∩ S
4
| + ... |S
n
−
2
∩ S
n
−
1
∩ S
n
|)
− (|S
1
∩ S
2
∩ S
3
∩ S
4
| + ... |S
n
−
3
∩ S
n
−
2
∩ S
n
−
1
∩
S
n
|)
......
+ (−1)
n
−
1
|S
1
∩ S
2
∩ ... S
n
−
1
∩ S
n
| (1)
有必要對上式作一些解釋。為易於理解， 上式分數行列出，每一行都是一些集合
元素個數的總和，其中第1行包含全部n個集合S
1、S
2
... 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)
0
」，
把第2行開首的「減」號改寫為「+ (−1)
1
」...如此類推，我們可知第k行開首
應有一個「+ (−1)
k
−
1
」。

我們還可以把上式化簡，方法是引入一個新的變項S
n, k
來代表上式等號右邊的第
k行。 S
n, k
是由C(n, k)個項加起來的總和，每個項都是由S
1
、S
2
... S
n
這n個
集合中抽r個出來構成的交集的元素個數。舉例說，當n = 5，k = 3時，S
5, 3
是
由C(5, 3) = 10個項加起來的總和，這10個項都是由S
1
... S
5
這5個集合中
抽3個出來構成的交集的元素個數，其中一個是|S
2
∩ S
4
∩ S
5
|，其餘類推。
利用S
n, k
以及Σ求和符號，我們便可以把上面的「容斥原理」公式大大簡化為：
|S
1
∪ S
2
∪ ... S
n
| = Σ
1 ≤ k ≤ n
(−1)
k
−
1
S
n, k
(2)
接著讓我們證明以上「容斥原理」公式(1)的正確性，為此我們必須證明，S
1
...
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
C(k, r)
1 ≤ r ≤ k
(−1)
r
現在的問題是，如何證明上式等於1？答案是借助《點算的奧秘： 二項式定理和
多項式定理》中介紹的「二項式定理」：(a + b)
n
= Σ
0 ≤ r ≤ n
C(n, r) a
r
b
n
−

r
。為了應用「二項式定理」，我們首先把上式等號右邊重寫：
Σ


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

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

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

∪ ... S
n
| = |U| + (−|S
1
∪ S
2
∪ ... S
n
|)(註3)。應用上面的「容斥原理」
公式(2)，我們便得到
|S
1
' ∩ S
2
' ∩ ... S
n
'| = |U| + Σ
1 ≤ k ≤ n
(−1)
k
S
n, k
(4)

同理，如果S
1
、S
2
... S
n
是「可交換集合」，那麼上式便變成
|S
1
' ∩ S
2
' ∩ ... 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)的值。
< br>我們先求n
1
的值，這個值相當於由10個字母組成但不含A、E、I、O、U中某一< br>個字母的字串的數目。由於撇除了一個字母，我們可以從餘下的25個字母中(可
重覆地)抽取1 0個出來排成字串，這是一個「無限重覆排列」問題，應共有25
10
個這樣的字串，即n1
= 25
10
。

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

最後，運用上面公式(3)，本題的答案是
Σ
1 ≤ k ≤ 5
(−1)
k
−
1
C(5, k) (26 − k)
10
= 5 × 25
10
− 10 × 24
10
+ 10 × 23
10
−
5 × 22
10
+ 21
10

由於具體數字太大，這裡只列出其算式。 事實上，「點算組合學」經常要和這樣
的「天文數字」打交道。若非靠邏輯思維，實在難以想像人類有何 方法求得這類
問題的答案，由此可見邏輯思維的巨大力量！□

例題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
1
、M
2
、J< br>1
、 J
2
、S
1
、
S
2
代表他們 (其中M、J和S分別代表火星人、木星人和土星人)。因此|U|的值等
於把上述6個符號進行「全排 列」的問題，故|U| = 6!。

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

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

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

最後，運用上面的公式(5)，求得本題答案為
|U| − C(3, 1) n
1
+ C(3, 2) n
2
− C(3, 3) n
3

= 6! − 3 × 5! × 2 + 3 × 4! × 2
2
− 1 × 3! × 2
3

= 720 − 720 + 288 − 48
= 240 □


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

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

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