在《點算的奧秘：容斥原理基本公式》中，筆者介紹了「容斥原理」的基本公式。這些公式可用來計算以下兩個集合的元素個數：|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)。