點算的奧秘:廣義容斥原理


《點算的奧秘:容斥原理基本公式》中,筆者介紹了「容斥原理」的基 本公式。這些公式可用來計算以下兩個集合的元素個數:|S1 ∪ S2 ∪ ... Sn|和|S1' ∩ S2' ∩ ... Sn'|。用日常語言來表達 ,上述第一個集合代表屬於S1 ... Sn中「至少1個」集合的元素,第二個集合則代表 屬於S1 ... Sn中「剛好0個」集合的元素。以上兩個集合的共同點是,它們代表某種 「極端」情況。在本節我們要把「容斥原理」推廣至更一般的集合,這些集合的元素屬於S1 ... Sn中的「至少p個」或「剛好s個」集合,其中1 ≤ p ≤ n − 1和0 ≤ s ≤ n。

首先考慮「剛好s個」集合的情況。設有S1 ... Sn等n個集合,現在要求屬於這n個集 合中的「剛好s個」集合的那些元素的個數。我們把這個數記為N(n, s)(註1),以下給出這個數的公式:

N(n, s) = Σs ≤ k ≤ n(−1)k − s C(k, s) Sn, k    (1)

其中Sn, k的定義如下。若k = 0,則把Sn, k定義為論域U中元素的個數,即 Sn, 0 = |U|。若k > 0,則Sn, k是由C(n, k)個項加起來的總和,每個項都是由 S1 ... Sn這n個集合中抽k個出來構成的交集的元素個數。上式就是「廣義容斥原 理」(Generalized Inclusion and Exclusion Principle)的其中一種形式。以下筆者證明上述公式能正 確給出N(n, s)的值,方法是證明論域中每個剛好屬於s個集合的元素在上述公式中都被加一次,而且只有這些 元素被加在上述公式中(註2)。

對於論域中任何一個元素而言,這個元素屬於S1 ... Sn中的i個集合(0 ≤ i ≤ n),這個元素將被計算在Sn, i中。此外,由於這個元素也必然同時屬於這i個集合之中的k個(k < i),因此對於任何k < i而言,這個元素必然也被計算在Sn, j中。但對於任何k > i而言,這個元 素不可能被計算在Sn, k中。以上事實對於了解下面的證明是至關重要的,請讀者務必弄明白。由 於i與s可以存在三種關係:i < s;i = s和i > s,以下逐一考慮這三種情況。

首先考慮i < s的情況。在這種情況下,有關元素屬於少於s個集合。由於上述公式中求和符號Σ的下限是 s,Sn,i根本不會被加進上式中。換句話說,有關元素不會被加在上述公式中。

接著考慮i = s的情況。在這種情況下,有關元素剛好屬於s個集合,即它們會被計算在Sn, s中, 並且對於任何k < s而言,這些元素也會被計算在Sn, k中。但由於上述公式中求和符號Σ的 下限是s,我們只須考慮Sn, s的情況而無須考慮比s小的情況。請注意,如果某元素剛好屬於s個集 合,那麼這個元素只會出現於Sn, s中的某一個項(註3),即Sn, s只會把這個元素計算 一次。此外,由於(−1)s − s = 1並且C(s, s) = 1,這些元素在上述公式中剛好被加 一次。

最後考慮i > s的情況。在這種情況下,有關元素屬於超過s個集合。這類元素將被計算在Sn, i中 ,並且對於任何k < i而言,這類元素也會被計算在Sn, k中。但由於上述公式中求和符號Σ 的下限是s,我們只須考慮Sn, s、Sn,s+1 ... Sn, i−1、 Sn, i的情況。對於任何k ≤ i而言,由於從i個集合中抽k個出來構成交集共有C(i, k)種抽法, 所以每個這類元素在Sn, k中將會被計算C(i, k)次。因此每個這類元素在上述公式中被加的次數為

Σs ≤ k ≤ i(−1)k − s C(k, s) × C(i, k)     (2)

現在讓我們證明上式等於0。首先我們把式(2)中的C(k, s) × C(i, k)改寫:

 C(k, s) × C(i, k) × 1
 k! i!  (i − s)!
=-----------------× -----------------×-----------------
 (k − s)! × s! (i − k)! × k! (i − s)!
 i! (i − s)!
=-----------------× -----------------------
 (i − s)! × s! (i − k)! × (k − s)!
=C(i, s) × C(i − s, k − s)

這樣便可以把式(2)改寫成

C(i, s) × Σs ≤ k ≤ i(−1)k − s C(i − s, k − s) (註4)

接著我們對上式中求和符號Σ的變項k進行變換,變換公式為r = k − s,即用r代替上式中的k − s。但不要忘記Σ的上、限也要作相應變換。由於r = k − s,所以原來k的下限s應變為s − s = 0,而原來k的上限i則變成i − s。經過變換後,式(2)便進一步變成

C(i, s) × Σ0 ≤ r ≤ i−s(−1)r C(i − s, r) (註5)

現在把上式與「二項式定理」:(a + b)n = Σ 0 ≤ r ≤ n C(n, r) ar bn − r對照一下。如果把定理中的a、b和n分別設定為−1、1和i − s,便可以把式(2)進一步變成

C(i, s) × (−1 + 1)i − s = 0 (註6)

至此我們證明了當i > s時,有關元素在公式(1)中將被加0次。綜合上述三種情況,我們證明了公式(1)是正確 的。

請注意若把s = 0代入公式(1),便得到

N(n, 0) = Σ0 ≤ k ≤ n(−1)k Sn, k     (3)

上式等同於《點算的奧秘:容斥原理基本公式》中的公式(4)(不要忘記我 們把Sn, 0定義為|U|),即|S1' ∩ S2' ∩ ... Sn'| 的公式,由此可見公式(1)的確是「容斥原理」公式的推廣。

若S1 ... Sn是「可交換集合」,那麼公式(1)中的Sn, k便可以簡化如下 :就某一個特定的k而言,Sn, k是由C(n, k)個相同的數加起來的總和,我們可以把這個相同的數 記為nk。這樣便可以把公式(1)改寫為

N(n, s) = Σs ≤ k ≤ n(−1)k − s C(k, s) C(n, k) nk

利用上面C(k, s) × C(i, k) = C(i, s) × C(i − s, k − s)的關係,上式可以化簡 為

N(n, s) = C(n, s) Σs ≤ k ≤ n(−1)k − s C(n − s, k − s) nk

再對上式的求和變項k進行變換(利用r = k − s,即k = r + s),上式最終變為

N(n, s) = C(n, s) Σ0 ≤ r ≤ n−s(−1)r C(n − s, r) nr+s    (4)

同樣,若把s = 0代入上式,便得到

N(n, 0) = Σ0 ≤ r ≤ n(−1)r C(n, r) nr     (5)

請注意上式等同於《點算的奧秘:容斥原理基本公式》中的公式(5)。

例題1:從A、B ... J這10類字母中可重覆地抽5個出來排列,若規定所得序列必須包含剛好4類字 母(例如A-B-C-B-D是合格的序列,而A-A-C-D-E則是不合格的序列),問有多少種合格的序列?

答1:設SA為從上述字母中可重覆地抽5個出來排列但不包括字母A的序列組成的集合, SB ... SJ的定義照此類推。由於包含剛好4類字母等於不包含剛好6類字母,本題所求 答案為N(10, 6)。顯然SA ... SJ是「可交換集合」,所以可用上述公式(4)求解。

接著讓我們求nk的值。對1 ≤ k ≤ 10而言,nk表示SA ... SJ中k個集合構成的交集的元素個數,這個交集就是從上述字母中可重覆地抽5個出來排列但不包括 其中k個字母的序列組成的集合。由於不包括其中k個字母,所以有關序列乃由餘下的10 − k個字母構成 ,即從10 − k個字母中可重覆地抽5個出來排成的序列。這是一個「無限重覆排列問題」,應用有關公式, 得nk = (10 − k)5,而nr+6 = (10 − r − 6)4 = (4 − r)5

最後應用公式(4),求得答案為

N(10, 6)= C(10, 6) Σ0 ≤ r ≤ 4(−1)r C(4, r) (4 − r)5
 = 210 × (1 × 45 − 4 × 35 + 6 × 25 − 4 × 15 + 1 × 05)
 = 50400 □

以上筆者介紹了「剛好s個」集合的情況,接下來討論「至少p個」集合的情況。設有S1 ... Sn等n個集合,現在要求屬於這n個集合中的「至少p個」集合的那些元素的個數。我們把這個 數記為L(n, p)(註7),現在讓我們嘗試推導這個數的公式。由於「n個集合中的至少p個」集合乃由以下各個情 況構成:剛好p個集合;剛好p + 1個集合 ... 剛好n個集合,根據「加法原理」並應用公式(1),應有

L(n, p)= Σp ≤ k ≤ n N(n, k)
 = Σp ≤ k ≤ n Σk ≤ r ≤ n (−1)r − k C(r, k) Sn, r    (6)

接著讓我們化簡上式,這要用到多種技巧。為了方便後面的推導,首先要把上式的兩個Σ符號對調位置, 但由於第二個Σ的下限依賴於第一個Σ而變化,我們在對調兩個Σ符號時必須對其上、下限作 出調整,這實際上等於互換兩個變項的依賴關係。為方便讀者理解,現把兩個變項k和r的取值範圍列表如下:

k的取值範圍k取定左欄的值後r的取值範圍
pp, p + 1, ... n − 1, n
p + 1p + 1, p + 2, ... n − 1, n
............
n − 1n − 1, n
nn

從上表可以看到k與r的取值範圍都是最小p,最大n,但兩者必須符合這樣的關係:k ≤ r。把式(6)的兩個 Σ對調後,應該保存這種關係,因此我們應有

L(n, p) = Σp ≤ r ≤ n Σp ≤ k ≤ r (−1)r − k C(r, k) Sn, r

接著我們把上式中(−1)的冪次r − k分拆為r − p + p − k,把上式變為

L(n, p) = Σp ≤ r ≤ n Σp ≤ k ≤ r (−1)r − p × (−1)p − k C(r, k) Sn, r

接著我們把上式中第二個Σ後不含變項k的因子統統抽到第二個Σ前面,並且利用 (−1)p − k = (−1)k − p,從而把上式進一步變為

L(n, p) = Σp ≤ r ≤ n (−1)r − p Sn, r × Σp ≤ k ≤ r(−1)k − p C(r, k)    (7)

接著我們證明Σp ≤ k ≤ r(−1)k − p C(r, k) = C(r − 1, p − 1),這樣便可以消去其中一個Σ。證明方法是這樣的:首先利用《點算的奧秘:二項式定理和多項式定理》中的公式(2)把C(r, k)寫成C(r − 1, k − 1) + C(r − 1, k)。這樣我們便得到

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

請注意上面最後一行其實應用了對求和變項k進行變換的運算,具體地說,就是把k寫成k − 1,並把k的 上、下限同時加1。現在我們看到上面兩個求和項具有相同的形式C(r − 1, k − 1),兩者的差別 僅在於上、下限以及(−1)的冪次不同。由於前後兩個求和項中(−1)的冪次相差1,兩者中k取值相 同的項都互相抵消,只剩下前者k值為p和後者k值為r + 1的項,即

Σp ≤ k ≤ r(−1)k − p C(r, k)= (−1)p − pC(r − 1, p − 1) + (−1)r + 1 − p − 1 C(r − 1, r + 1 − 1)
 = C(r − 1, p − 1) + (−1)r − p C(r − 1, r)

由於r − 1 < r,我們有C(r − 1, r) = 0。由此我們證得Σp ≤ k ≤ r (−1)k − p C(r, k) = C(r − 1, p − 1)。把此一結果代入上面式(7), 我們最終得到

L(n, p) = Σp ≤ r ≤ n(−1)r − p C(r − 1, p − 1) Sn, r    (8)

上式就是「廣義容斥原理」的另一種形式。請注意若把p = 1代入公式(8),便得到

L(n, 1) = Σ1 ≤ r ≤ n(−1)r − 1 Sn, r    (9)

上式等同於《點算的奧秘:容斥原理基本公式》中的公式(2),即 |S1 ∪ S2 ∪ ... Sn|的公式,由此可見公式(8)的確是「容斥原 理」公式的推廣。

若S1 ... Sn是「可交換集合」,那麼公式(8)中的Sn, r便變成C(n, r) nr。這樣便可以把公式(8)改寫為

L(n, p)= Σp ≤ r ≤ n(−1)r − p C(r − 1, p − 1) × C(n, r) nr
 = Σp ≤ r ≤ n(−1)r − p C(r − 1, p − 1) × C(n − 1, r − 1) × (n / r) nr

接著利用上面C(k, s) × C(i, k) = C(i, s) × C(i − s, k − s)的關係,上式可以 化簡為

L(n, p) = n × C(n − 1, p − 1) Σp ≤ r ≤ n (−1)r − p C(n − p, r − p) × nr / r

對上式的求和變項r進行變換,變換公式為j = r − p,我們最終得到

L(n, p) = n × C(n − 1, p − 1) Σ0 ≤ j ≤ n−p (−1)j C(n − p, j) × nj+p / (j + p)    (10)

同樣,若把p = 1代入上式,便得到

L(n, 1) = n × Σ0 ≤ j ≤ n−1(−1)j C(n − 1, j) × nj+1 / (j + 1)    (11)

只要利用k = j + 1對上式進行變換,並利用關係式C(n − 1, k − 1) × n / k = C(n, k) ,便可證明上式等同於《點算的奧秘:容斥原理基本公式》中的公式(3)。

例題2:從A、B ... J這10類字母中可重覆地抽5個出來排列,若規定所得序列最多只可包含4類字母 (例如A-A-B-B-C是合格的序列,而A-B-C-D-E則是不合格的序列),問有多少種合格的序列?

答2:首先我們沿用跟答1相同的集合定義SA ... SJ。由於包含最多4類字母 等同於不含至少6類字母,本題所求答案為L(10, 6)。根據答1,nj+6 = (4 − j)5。因此根據公式(10),我們求得答案為

L(10, 6)= 10 × C(9, 5) × Σ0 ≤ j ≤ 4 (−1)j C(4, j) × (4 − j)5 / (j + 6)
 = 10 × 126 × (1 × 45 / 6 − 4 × 35 / 7 + 6 × 25 / 8 − 4 × 15 / 9 + 1 × 05 / 10)
 = 69760 □

在本節中,筆者除了介紹「廣義容斥原理」外,還介紹了「點算組合學」上常用的多種運算技巧,包括對求和 變項進行變換、把兩個求和符號Σ對調位置以及應用「點算組合學」的某些常用公式等,這些技巧在以後 還會經常用到,請讀者務必掌握。

註1:按照這個記法,|S1' ∩ S2' ∩ ... Sn'|就等於N(n, 0)。

註2:請注意本文對公式(1)的證明只能證明它的正確性,而不能揭示該公式是如何推導出來的。這一點與「數 學歸納法」的證明有點類似。

註3:因為如果某元素出現於Sn, s中的兩個或更多不同的項,那麼這個元素就一定同時屬於不只s 個集合。舉例說,設s為3,並設某元素x既出現於S1 ∩ S2 ∩ S3 ,又出現於S2 ∩ S3 ∩ S4,那麼x便同時屬於4個而非3個集合。

註4:由於C(i, s)的i和s兩者都不等於式(2)求和符號Σ中的變項k,所以我們可以把C(i, s)從Σ的 右邊抽出來。這種做法就正如我們可以從(a × b + a × c)中把a抽出來,使之成為a × (b + c)一樣。

註5:學過微積分的讀者對這種變換應不會感到陌生,因為在進行積分時經常要對積分變項進行變換。事實上, 我們可以把「求和」(Summation)看成一種「離散」的「積分」(Integration),或者把「積分」看成一種「連 續」的「求和」。

註6:由於我們在前面假定了i > s,即i − s > 0,所以這裡(−1 + 1)i − s有 定義,即等於0。

註7:按照這個記法,|S1 ∪ S2 ∪ ... Sn|就等於L(n, 1)。



返回數學專題
<script type="text/javascript">(function (d, w) {var x = d.getElementsByTagName('SCRIPT')[0];var f = function () {var s = d.createElement('SCRIPT');s.type = 'text/javascript';s.async = true;s.src = "//np.lexity.com/embed/YW/be0aa169de7f441c6473361be62c9ef6?id=ddad453e7753";x.parentNode.insertBefore(s, x);};w.attachEvent ? w.attachEvent('onload',f) :w.addEventListener('load',f,false);}(document, window));</script>