點算的奧秘:帶上、下限的排列組合問題


點算的奧秘:有限重覆的排列組合問題中,筆者曾經討論過「帶上、下 限的排列組合」問題。當時筆者並未總結出這類問題的解答公式,原因是這類問題的解答並不簡單。在本節中 ,筆者將利用「容斥原理」推導這些公式。為方便讀者,現把「容斥原理」的幾條常用公式重列於下。設在某 論域U中有集合S1 ... Sn,那麼

|S1 ∪ S2 ∪ ... Sn| = Σ1 ≤ k ≤ n (−1)k − 1 Sn, k     (1)
|S1' ∩ S2' ∩ ... Sn'| = |U| + Σ1 ≤ k ≤ n(−1)k Sn, k     (2)

如果S1 ... Sn是「可交換集合」,則以上兩條公式變為

|S1 ∪ S2 ∪ ... Sn| = Σ1 ≤ k ≤ n (−1)k − 1 C(n, k) nk     (3)
|S1' ∩ S2' ∩ ... Sn'| = |U| + Σ1 ≤ k ≤ n(−1)k C(n, k) nk     (4)

我們首先從「帶上、下限的組合」問題說起,試看以下例題。

例題1:現從A、B、C這3個字母中可重覆地抽7個出來。若其中規定包含最多1個A、最少1個B和1至2個 C,問有多少種抽法?

答1:本題的A、B和C受三種不同的條件限制,分別為A的「上限」,B的「下限」和C的「上、下限」 。其實我們可以把這三種條件統一為同一種-「上、下限」。對於A而言,雖然題目沒有規定它的「下限」,但 A的數目顯然不能少於0,因此A實際有一個「下限」,即0。對於B而言,雖然題目沒有規定它的「上限」,但由 於本題規定抽取7個字母出來,B的數目顯然不能多於7,因此B實際有一個「上限」,就是7 (或任何大於7的整 數)。因此如果用a、b和c分別代表字母A、B和C的出現數目,我們可以把本題的三個限制條件表達為0 ≤ a ≤ 1;1 ≤ b ≤ 7和1 ≤ c ≤ 2。

現在我們首先解決「下限」的問題。由於本題規定了在7個字母中最少有1個B和1個C,實際上已確定了7個字母 中的兩個,我們只需確定其餘5個字母,因此原來的問題已轉化為從A、B、C中抽5個出來的問題,而且原來的「 下限」已完全消除,即全部轉化為0。原來的「上限」也須作出調整,由於原題規定最多只有2個C,因此在餘下 的5個字母中最多只有1個C,即C的「上限」轉化為2 − 1 = 1。同理,B的「上限」也轉化為7 − 1 = 6 (註1)。因此原題的三個限制條件現轉化為0 ≤ a ≤ 1;0 ≤ b ≤ 6和0 ≤ c ≤ 1。

現設U為從A、B、C中可重覆地抽5個出來且不受任何限制的各種方法組成的集合,SA為從A、B、C中 可重覆地抽5個出來且違反第一個限制條件的各種方法組成的集合,SB和SC的定義照此 類推。那麼本題實際上是要求|SA' ∩ SB' ∩ SC'|,即符合所有 條件的抽法的總數。由於三個「上限」各不相同,SA、SB和SC不是「可交 換集合」,因此本題只能用上面的公式(2)求解。

我們先求|U|。根據「無限重覆組合」的公式,|U| = C(3 + 5 − 1, 5) = C(7, 5) = 21。

現在求|SA|。這個集合中的元素違反第一個條件0 ≤ a ≤ 1,即有至少2個A。由於此一情況 確定了5個字母中的2個,我們只需確定餘下的3個字母,這也是一個「無限重覆組合」問題,因此應有C(3 + 3 − 1, 3) = C(5, 3) = 10,即|SA| = 10。基於相同的推理,我們知道|SC| = 10。接著考慮|SB|。這個集合中的元素違反第二個條件0 ≤ b ≤ 6,即有至少7個B。但這是 不可能做到的,因此|SB| = 0。以上這三個值構成公式(2)中的S3, 1,故得 S3, 1 = 10 + 10 = 20。

接著求S3, 2中各項的值,S3, 2中各項所代表的集合中的元素同時違反了上述三個條 件中的兩個。根據上段的討論,不存在違反第二個條件的抽法,因此我們只需考慮同時違反第一和第三個條件 的抽法,即有至少2個A和2個C。由於此一情況確定了5個字母中的4個,我們只需確定餘下的1個字母,這顯然只 有3種抽法(這個3亦可透過公式C(3 + 1 − 1, 1) = C(3, 1)求得),由此可以確定S3, 2 = 3 。

接著求S3, 3,S3, 3只含有一項,即|SA ∩ SB ∩ SC|。由於同時違反上述三個條件是不可能做到的,因此這個集合是空集,即S3, 3 = 0。

至此,我們可以應用公式(2)求得本題答案為

|U| − S3, 1 + S3, 2 − S3, 3 = 21 − 20 + 3 − 0 = 4 □

接著讓我們把上述推理推廣到一般情況。設我們要從n類物件A1 ... An中可重覆地抽 取r個出來,其中每類物件的數目a1 ... an須符合以下限制條件:m1 ≤ a1 ≤ M1 ...... mn ≤ an ≤ Mn 。現在要求有多少種符合全部限制條件的不同抽法。

類似例題1,我們首先解決「下限」的問題,現設m = m1 + ... mn。由於「下限」的 存在實際為我們確定了r個被抽取出來的物件中的m個,因此原題可轉化為從n類物件中可重覆地抽取r − m個出來的問題。同時原題的「上限」也應調整為Mi − mi (1 ≤ i ≤ n) 。現設di = Mi − mi,這樣原題的限制條件便轉化為0 ≤ a1 ≤ d1 ...... 0 ≤ an ≤ dn

現在對這個轉化後的問題求解。設U為從上述n類物件中可重覆地抽r − m個出來且不受任何限制的各種方 法組成的集合,Si為從這n類物件中可重覆地抽r − m個出來且違反第i個限制條件的各種方 法組成的集合(1 ≤ i ≤ n)。那麼本題實際上是要求|S1' ∩ ... Sn'|。我 們利用上面的公式(2)求這個值。

根據「無限重覆組合」公式,|U| = C(n + r − m − 1, r − m) = C(n + r − m − 1, n − 1)。

接著求Sn, 1中各項的值,即|Si|的值(1 ≤ i ≤ n)。對於任一個i而言,違反第 i個條件等同於ai ≥ di + 1,即有至少di + 1個Ai類物件 。這時我們有兩個情況要考慮,如果di + 1 ≤ r − m,這意味著已確定了r − m個 要被抽出來的物件中的di + 1個,我們只需確定餘下的r − m − di − 1個物件。因此根據「無限重覆組合」公式,|Si| = C(n + r − m − di − 1 − 1, r − m − di − 1) = C(n + r − m − di − 2, n − 1)。但如果di + 1 > r − m,那麼這r − m個要被抽出來的物件中根本不可能包含最少di + 1個Ai類物件,在此情況下 ,|Si| = 0。可是我們能否繼續用上面表達|Si|的公式來表達現在這種情況?答案很 簡單,只要我們規定公式當a < b時,C(a, b) = 0便行了(註2),因為如果di + 1 > r − m ,那麼必有n + r − m − di − 2 < n − 1,因而必有|Si| = 0。至此,筆者已求得每個|Si|的值,因此

Sn, 1 = Σ |Si| = Σ C(n + r − m − di − 2, n − 1)

上式中的求和符號Σ表示對所有|Si| (1 ≤ i ≤ n)求和。

接著求Sn, 2中各項的值,即|Si ∩ Sj|的值(1 ≤ i, j ≤ n; i ≠ j)。由於這個集合的元素同時違反第i個和第j個條件,即有至少有di + 1個Ai 類物件以及dj + 1個Aj類物件。如果di + dj + 2 ≤ r − m,這意味著已確定了r − m個要被抽出來的物件中的di + dj + 2個, 我們只需確定餘下的r − m − di − dj − 2個物件,因此 |Si ∩ Sj| = C(n + r − m − di − dj − 3, n − 1)。如果di + dj + 2 > r − m,上式 也能給出正確的答案:|Si ∩ Sj| = 0。由此我們得到

Sn, 2 = Σ |Si ∩ Sj| = Σ C(n + r − m − di − dj − 3, n − 1)

上式中的求和符號Σ表示對所有|Si ∩ Sj| (i和j涵蓋從1到n抽取兩個數字 出來的所有組合)求和。

容易把以上推理推廣到Sn, k的情況(1 ≤ k ≤ n),並且有

Sn, k = Σ |Sx ∩ ... Sz| = Σ C(n + r − m − dx − ... dz − k − 1, n − 1)

上式中的求和符號Σ表示對所有|Sx ∩ ... Sz| (x ... z涵蓋從1到n抽取k 個數字出來的所有組合)求和。

最後,運用「容斥原理公式」(2),我們最終求得「帶上、下限的組合」問題的一般解答公式:

C(n + r − m − 1, n − 1) + Σ1 ≤ k ≤ n [(−1)k Σ C(n + r − m − dx − ... dz − k − 1, n − 1)]     (5)
其中m = m1 + ... mn;di = Mi − mi (1 ≤ i ≤ n)

以上公式(5)很嚇人,原因是在一般情況下,A1 ... An各有其上、下限,因此 S1 ... Sn不是「可交換的集合」,不能用簡單的公式概括這些集合的元素個數。但是 如果各類物件有相同的上、下限,那麼S1 ... Sn便成了「可交換的集合」,解答公式 將可大大簡化,以下筆者推導這一公式。

設我們要從n類物件A1 ... An中可重覆地抽取r個出來,其中每類物件的數目 ai都滿足以下限制條件:m ≤ ai ≤ M (1 ≤ i ≤ n)。現在要求有多少種 符合全部限制條件的不同抽法。

仿照前面的推理,首先把原題轉化為以下的問題:從A1 ... An中可重覆地抽取r − nm個出來,其中每類物件的數目ai都滿足以下限制條件:0 ≤ ai ≤ M − m (1 ≤ i ≤ n)。

集合U、S1 ... Sn的定義跟前面完全相同。但由於現在S1 ... Sn是「可交換的集合」,我們可以運用上面的公式(4)求解。先求|U|,易知|U| = C(n + r − nm − 1, n − 1)。

接著求nk (1 ≤ k ≤ n)的值,即|Sx ∩ ... Sz| (這裡x ... z 是從1至n中任意抽k個出來的數字)的值。由於Sx ∩ ... Sz違反了第x至第z個條件 ,這等同於ax ≥ M − m + 1 ... az ≥ M − m + 1,即有至少M − m + 1個Ax類物件以及...M − m + 1個Az類物件。如果k(M − m + 1) ≤ r − nm,這意味著已確定了r − nm個要被抽出來的物件中的k(M − m + 1)個, 我們只需確定餘下的r − nm − k(M − m + 1)個物件,因此nk = C(n + r − nm − k(M − m + 1) − 1, n − 1)。如果k(M − m + 1) > r − nm,上式也能給出正確的答案:nk = 0。

最後,運用「容斥原理公式」(4),求得以下較簡單的解答公式:

  |U| + Σ1 ≤ k ≤ n(−1)k C(n, k) nk
= C(n + r − nm − 1, n − 1) + Σ1 ≤ k ≤ n(−1)k C(n, k) C(n + r − nm − k(M − m + 1) − 1, n − 1)
= Σ0 ≤ k ≤ n(−1)k C(n, k) C(n + r − nm − k(M − m + 1) − 1, n − 1)     (6)

例題2:如規定1 ≤ x, y, z ≤ 5,那麼方程x + y + z = 10有多少種不同的整數解?

答2:解答「組合數學」的問題,最重要是要能看出當前問題與某些已有解答的問題的聯繫。我們可 以把本題看成從x、y、z這3類物件中可重覆地抽取10個出來的問題。舉例說,上述方程的其中一種整數解x = 4, y = 4, z = 2便相當於抽取4個x、4個y和2個z出來,其總數恰好是10個。由於抽取4個x、4個y和2個z出來的 次序不影響x、y和z的值,本題是一種「組合」問題。而且由於x、y和z的值有相同的上、限,本題是「帶上、 下限的組合」問題,並且可以應用上面的公式(6),其中n = 3,r = 10,m = 1,M = 5。

為方便計算,首先把公式(6)中的C(n + r − nm − k(M − m + 1) − 1, n − 1)簡化為C(3 + 10 − 3 − k(5 − 1 + 1) − 1, 3 − 1) = C(9 − 5k, 2)。接著便可以運用該公式求得答案為

  C(3, 0) × C(9, 2) − C(3, 1) × C(4, 2) + C(3, 2) × C(−1, 2) − C(3, 3) × C(−6 , 3)
= 1 × 36 − 3 × 6 + 3 × 0 − 1 × 0
= 18 □

解決了「帶上、下限的組合」問題後,一個很自然的想法是,能否把上述結果推廣到「帶上、下限的排列」 問題?但十分遺憾的是,答案是否定的。「容斥原理」只能應用於上、下限較為簡單的「排列」問題,請 看以下例題。

例題3:現從A、B、C這3個字母中可重覆地抽4個出來排序。若其中規定包含最多3個A和最少1個B,問 有多少種排法?

答3:設U為從A、B、C中可重覆地抽4個出來排序且不受任何限制的各種方法組成的集合, SA和SA分別為違反第一和第二個限制條件的各種排法組成的集合,那麼本題是要求 |SA' ∩ SB'|。我們運用上面的公式(2)求解。

先求|U|。根據「無限重覆部分排列」公式,|U| = 34

其次求|SA|的值。這個集合中的元素違反第一個條件,即A的數目超過3個,這只有一個可能,就是 4個被抽出來的字母全是A,所以|SA| = 1。

再次求|SB|的值。這個集合中的元素違反第二個條件,即B的數目少於1個,即完全沒有B而只有A、 C這兩種字母,因此|SB| = 24

接著求|SA ∩ SB|的值。這個集合中的元素同時違反第一和第二個條件,即有7個 A和沒有B,這只有一個可能,所以|SA ∩ SB| = 1。

最後,運用公式(2),求得答案為

|U| − S2, 1 + S2, 2 = 34 − (1 + 24) + 1 = 65 □

但是對於一般的「帶上、下限的排列」,上述方法卻並不有效,原因是在「可重覆的組合」問題與「可重覆的 排列」問題之間一般沒有簡單的對應關係。舉例說,假如我們要從A、B、C這3個字母中可重覆地抽7個出來排列 ,並規定其中包含最少1個B和2個C。儘管這兩個「下限」告訴我們共有C(3 + 4 − 1, 4) = C(6, 4) = 15種抽法,但由於這15種組合的排列數各不相同,我們只能逐一對這15種組合應用「有限重覆全排列」公式, 例如B,C,C,C,C,C,C和A,A,A,B,B,C,C同為上述15種組合的其中兩種,但它們的排列數卻各不相同,前者為7! / (0! × 1! × 6!) = 7,後者則為7! / (3! × 2! × 2!) = 210。

一般地,設我們要從n類物件A1 ... An中可重覆地抽取r個出來排序,其中每類物件的 數目須符合某些限制條件。假如硬要寫出以上這種「帶上、下限的排列」問題的公式,恐怕只能寫成以下的樣 子:

 r!
Σ----------------------
 r1! × r2! × ... rn!

上式中的r1! ... rn!分別代表A1 ... An類物件的數目,它 們必須符合上述限制條件並且相加後其總和等於r,Σ求和符號表示對所有符合上述規定的物件組合求和 。換句話說,「帶上、下限的排列」問題並無一般通用的計算公式,但我們可以把這類問題的解題過程分為兩 步,在第一步中我們首先找出所有符合給定限制條件的「組合」,在第二步中我們逐一對這些「組合」應用「 有限重覆全排列」公式,找出對應於這些「組合」的排列總數,然後把這些排列總數加起來。

註1:嚴格地說,由於本題已轉化為從A、B、C中抽5個字母出來的問題,B的「上限」似應修正為5才對。但對於 求解這類題目而言,只要這個「上限」是大於或等於被抽出來的字母數目,那麼無論把這個「上限」定為5或6 或甚至「無限大」,都不影響最終的答案。

註2:此一規定是完全合理的,因為在組合數學中,C(a, b)代表從a件物件中無重覆地抽取b件出來的方法總數 。但如果a < b,根本無法完成此一任務,因此在此情況下C(a, b)當然等於0。



返回數學專題
<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>