在《點算的奧秘:容斥原理基本公式》中,筆者介紹了「容斥原理」的基本公式。這些公式可用來計算以下兩個集合的元素個數:|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),以下給出這個數的公式:
其中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)次。因此每個這類元素在上述公式中被加的次數為
現在讓我們證明上式等於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)改寫成
接著我們對上式中求和符號Σ的變項k進行變換,變換公式為r = k − s,即用r代替上式中的k − s。但不要忘記Σ的上、限也要作相應變換。由於r = k − s,所以原來k的下限s應變為s − s = 0,而原來k的上限i則變成i − s。經過變換後,式(2)便進一步變成
現在把上式與「二項式定理」:(a + b)n = Σ 0 ≤ r ≤ n C(n, r) ar bn − r對照一下。如果把定理中的a、b和n分別設定為−1、1和i − s,便可以把式(2)進一步變成
至此我們證明了當i > s時,有關元素在公式(1)中將被加0次。綜合上述三種情況,我們證明了公式(1)是正確的。
請注意若把s = 0代入公式(1),便得到
上式等同於《點算的奧秘:容斥原理基本公式》中的公式(4)(不要忘記我們把Sn, 0定義為|U|),即|S1' ∩ S2' ∩ ... Sn'|的公式,由此可見公式(1)的確是「容斥原理」公式的推廣。
若S1 ... Sn是「可交換集合」,那麼公式(1)中的Sn, k便可以簡化如下:就某一個特定的k而言,Sn, k是由C(n, k)個相同的數加起來的總和,我們可以把這個相同的數記為nk。這樣便可以把公式(1)改寫為
利用上面C(k, s) × C(i, k) = C(i, s) × C(i − s, k − s)的關係,上式可以化簡為
再對上式的求和變項k進行變換(利用r = k − s,即k = r + s),上式最終變為
同樣,若把s = 0代入上式,便得到
請注意上式等同於《點算的奧秘:容斥原理基本公式》中的公式(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的取值範圍 |
---|---|
p | p, p + 1, ... n − 1, n |
p + 1 | p + 1, p + 2, ... n − 1, n |
...... | ...... |
n − 1 | n − 1, n |
n | n |
從上表可以看到k與r的取值範圍都是最小p,最大n,但兩者必須符合這樣的關係:k ≤ r。把式(6)的兩個Σ對調後,應該保存這種關係,因此我們應有
接著我們把上式中(−1)的冪次r − k分拆為r − p + p − k,把上式變為
接著我們把上式中第二個Σ後不含變項k的因子統統抽到第二個Σ前面,並且利用(−1)p − k = (−1)k − p,從而把上式進一步變為
接著我們證明Σ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),我們最終得到
上式就是「廣義容斥原理」的另一種形式。請注意若把p = 1代入公式(8),便得到
上式等同於《點算的奧秘:容斥原理基本公式》中的公式(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)的關係,上式可以化簡為
對上式的求和變項r進行變換,變換公式為j = r − p,我們最終得到
同樣,若把p = 1代入上式,便得到
只要利用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)。