點算的奧秘:有限重覆的排列組合問題


在本節,筆者將介紹「有限重覆的排列組合問題」。請注意這裡的「有限」,不是英語的Finite,而是 Restricted,即被排列組合的物件的重覆次數受到某些條件的限制。根據限制條件的性質,我們可以對這類問 題作相應的分類。某些條件限制物件重覆的最小次數,這類問題可稱為「帶下限的排列組合問題」;某些條件 限制物件重覆的最大次數,這類問題可稱為「帶上限的排列組合問題」;當然我們還可以有「帶上、下限的排 列組合問題」。由於「有限重覆的排列組合問題」較前面各節的「排列組合問題」都複雜,並非每一種問題都 有簡單的公式。

現在首先讓我們考慮較簡單的「有限重覆全排列」問題。由於這類問題要求把所有有關物件進行「全 排列」,因此這類問題並非只提出重覆次數的上限或下限,而是嚴格規定了每種物件的重覆次數,所以這類問 題只有一種形式,即假設有n類物件,每類物件的個數都是有限的,並假設第1類物件共有r1個、第 2類物件共有r2個...第n類物件共有rn個,即總共有r = r1 + r2 + ... rn個物件。現要將全部r個物件排序,問有多少種排法?為了較容易理解這個問題, 現以一個具體的問題為例看看如何解這類問題。

例題1:如要把MISSISSIPPI (密西西比)這個詞的字母排成任意順序,問有多少種排法?

答1:由於本題是「有限重覆全排列」問題的典型範例,因此「有限重覆全排列」問題又稱「密西西 比」問題。在MISSISSIPPI這個詞中,共有4個I、1個M、2個P和4個S,即有4類字母和總共11個字母。比照上文 的定義,即n = 4、r1 = 4、r2 = 1、r3 = 2、r4 = 4、r = 11。我們可以把排序過程分解為4個程序,現逐一考慮每一個程序。在第一個程序中,我們決定那4個I的位置。 由於那4個I之間彼此沒有區別,所以我們只需從11個位置中抽取4個出來安置這4個I,而且由於位置無先後之分 ,所以這是一個「組合」問題,即第一個程序共有C(11, 4)種選擇。

接著讓我們考慮第二個程序,在這個程序中,我們要決定那1個M的位置,這顯然也是一個「組合」問題。不過 由於經第一程序後,只剩下11 − 4 = 7個位置可供安置M,所以現在的「組合」問題是從餘下的7個位置 中選1個出來,應有C(7, 1)種選擇。

在第三個程序中,我們要決定那2個P的位置,這也是一個「組合」問題。經第一、二個程序後,現在只剩下7 − 1 = 6個位置,所以應有C(6, 2)種選擇。在最後一個程序中,我們要決定那4個S的位置,由於現在只 剩下6 − 2 = 4個位置,所以顯然只有1種選擇。不過為完整起見,我們也寫出這個「組合」問題的式子 :C(4, 4)。

最後,我們運用「乘法原理」求得答案為:

 C(11, 4) × C(7, 1) × C(6, 2) × C(4, 4)
 11! 7!  6! 4!
=-----------× -----------×----------- ×-----------
 7! × 4! 6! × 1!  4! × 2! 0! × 4!
 11!
=----------------------
 4! × 1! × 2! × 4!
 11 × 10 × 9 × 8 × 7 × 6 × 5
=-------------------------------------
 2 × 4 × 3 × 2
=34650

我們也可循另一途徑解答本題,其基本原理是把本題的「有限重覆排列」問題分階段轉化為「不可重覆排列」 問題。假設我們把原來的4個I更名為I1、I2、I3和I4,這樣 對應於原來的某個排列如ISIIMISSPPS,便可產生一系列新的排列,如I1SI4I3 MI2SSPPS和I4SI1I3MI2SSPPS。由於在確 定了4個I的位置後,把I1、I2、I3和I4填入這4個位置應共有 4!種填法,因此新排列數目應為原來排列數目的4!倍。同理,當我們把1個M、2個P和4個S更名後,新排列數目 應為第一次更名後產生的新排列數目的1! × 2! × 4!倍。當把I、M、S、P全部更名後,我們便把原 來的問題轉化為11個字母「不可重覆全排列」問題,應有11!種排法。由於這11!種新排列是原來排列數目的4! × 1! × 2! × 4!倍,我們求得原來排列的數目應為11! / (4! × 1! × 2! × 4!) = 34650,答案跟前面完全一致。□

現在我們把上述推理推廣到一般情況。由於共有n類物件,我們可以把整個排序過程分為n個程序。在第一個程 序中,我們在總共r個位置中選r1個出來安置第1類物件。這是一個「組合」問題,利用組合公式, 我們知共有C(r, r1)種選擇。接著在第二個程序中,我們在餘下的r − r1個位 置中選r2個出來安置第2類物件。這也是一個「組合」問題,共有C(r − r1, r 2)種選擇。接著在第三個程序中,我們在餘下的r − r1 − r2 個位置中選r3個出來安置第3類物件,共有C(r − r1 − r2 , r3)種選擇。如是者,直至第n個程序,在餘下的r − r1 − ... rn − 1 = rn個位置中選rn個出來安置第n類物件,共有C(rn , rn)種選擇。最後,根據「乘法原理」,求得答案為:

 C(r, r1) × C(r − r1, r2) × C(r − r1 − r2, r3) × ... C(rn, rn)
 r! (r − r1)!  (r − r1 − r2)!   rn!
=-------------------× ------------------------× -----------------------------×... -----------
 (r − r1)! × (r1)!  (r − r1 − r2)! × (r2)!  (r − r1 − r2 − r 3)! × (r3)!  0! × r n!
 r!
=----------------------------------
 (r1)! × (r2)! × (r3)! × ... (rn)!

同樣,我們也可循另一途徑推導上式,也是把原來的「有限重覆全排列」問題轉化為「不可重覆全排列」問題 。假設我們首先把第一類物件更名,使這r1個物件各有不同的名稱,這樣對應於原來的排列便產生 了一系列新的排列,新排列數目應為原來排列數目的r1!倍。接著我們把第二類物件更名,使這 r2個物件各有不同的名稱,而且這些名稱也跟前述的r1個新名稱不同,這樣我們又將 產生一系列更新的排列,新排列數目應為上一次更名後產生的新排列數目的r2!倍。這樣繼續更名 下去,直至全部r件物件各有不同的名稱。至此產生的新排列應為原來排列的(r1)! × (r2)! × (r3)! × ... (rn)!倍。但r件不同物件的「全排列 」應有r!種排法,因此我們求得原來的排列數目應為r! / ((r1)! × (r2)! × (r3)! × ... (rn)!),跟前面的結果完全一致。

上式就是「有限重覆全排列」問題的公式。請注意,有些人用M(r1, r2 ... rn )來代表「有限重覆全排列」的結果。由此我們得到以下公式:

M(r1, r2 ... rn) = r! / ((r1)! × (r2)! × (r3)! × ... (rn)!)

上述公式與「組合」公式非常相似,「組合」公式其實就是上述公式在n = 2時的特例。筆者曾不只一次強調, 「排列」和「組合」並非絕然對立,而是有著千絲萬縷的聯繫,這裡我們再一次看到這種聯繫。事實上,筆者 在推導該公式的第一種方法中,是把它處理成「組合」問題的。

接著讓我們研究其他「有限重覆排列組合」問題。對於這類問題,我們必須運用推理,設法把問題化歸為已知 有解的問題,然後利用已有的解題方法求解。我們首先研究「帶下限的組合」問題。

例題2:貨架上有三類罐頭湯:忌廉湯、雜菜湯和羅宋湯,每類罐頭都有至少8個,現某甲從貨架上任 意抽取8罐罐頭湯,其中必須有至少1罐忌廉湯和2罐雜菜湯,問有多少種抽法?

答2:本題其實是對《點算的奧秘:無限重覆的排列組合問題》 例題1的變化,增加了兩個「下限」,即至少1罐忌廉湯和2罐雜菜湯。這兩個「下限」實際上為我們確定了8罐 湯的其中3罐,我們只需確定餘下5罐。因此本題實際上等同於從上述三類罐頭湯中任抽取5罐出來的問題,其結 果跟上一節例題1的答案相同,即C(3 + 5 − 1, 5) = 21。□

以上例題顯示,「帶下限的組合」問題非常簡單,只需變換問題的某些參數便能化歸為「無限重覆組合問題」 。相比之下,「帶下限的排列」問題便沒有那麼簡單。請看以一例題。

例題3:現從A、B、C這3個字母中抽4個出來排列。(a)若其中必須包含至少1個A1個B,問有 多少種排法?(b)若其中必須包含至少1個A1個B,那麼又有多少種排法?

答3
(a) 首先把排列過程分解為「組合」和「全排列」兩個程序,其中第一個程序相當於例題2的那種「帶下限的組 合」問題。由於已確定其中兩個字母,我們只需確定餘下的兩個字母,因此這個「組合」問題相當於從3類物件 中任意抽2個出來的「無限重覆組合」問題,應有C(3 + 2 − 1, 2) = 4! / (2! × 2!) = 6種組合 。這6種組合(連同給定的1個A和1個B)是:A,B,A,A;A,B,A,B;A,B,A,C;A,B,B,B;A,B,B,C;A,B,C,C。

接著考慮第二個程序,在這個程序中我們對以上6種組合進行「全排列」。由於6種組合的「全排列」數各不相 同,我們必須應用上面介紹的「有限重覆全排列」逐一計算如下。(1) 對於組合A,B,A,A,共有4! / (3! × 1!) = 4種排法;(2) 對於組合A,B,A,B,共有4! / (2! × 2!) = 6種排法;(3) 對於組合 A,B,A,C,共有4! / (2! × 1! × 1!) = 12種排法;(4) 對於組合A,B,B,B,共有4! / (1! × 3!) = 4種排法;(5) 對於組合A,B,B,C,共有4! / (1! × 2! × 1!) = 12種排法;(6) 對於組合A,B,C,C,共有4! / (1! × 1! × 2!) = 12種排法。由於上述6種情況互斥和窮盡一切可 能性,根據「加法原理」,可知共有4 + 6 + 12 + 4 + 12 + 12 = 50種排法。

(b) 本部分雖然與(a)部分只是一字之差,但解法可以完全不同。由於「包含至少1個A或1個B」的否定是「既沒 有A,也沒有B」,即「只有C」,因此從反面去求解會較為簡單,即從所有可能的排列減去只有C的排列,就是 本部分要求的答案。根據「無限重覆部分排列」公式,我們知道從A、B、C這3個字母中抽4個出來排列,若不加 任何限制,應有34 = 81種排法。而在這81種排法中,全部皆為C的排法只有一種(即C-C-C-C),因 此本部分的答案是81 − 1 = 80種排法。

請注意對本部分如沿用(a)部分的解題方法,情況會頗為複雜。首先我們須把「包含至少1個A或1個B」分為以下 三個互斥且窮盡一切可能性的情況,即(1)包含至少1個A但沒有B;(2)包含至少1個B但沒有A;(3)包含至少1個A 和1個B。然後對每種情況,我們要找出各種「組合」並對各種組合進行「全排列」。最後把所有「全排列」數 目加起來。相比之下,上段的解題方法就簡單明快得多。□

接著讓我們來看某些「帶上限的排列組合」問題。這類問題一般都要運用「加法原理」或如例題3(b)那樣從反 面求解,試看以下例題。

例題4:(a)現從A、B、C這3個字母中抽4個出來。若其中最多只能包含2個A,問有多少種抽法?試列 出所有不同抽法。(b)從A、B、C這3個字母中抽4個出來排列。若其中最多只能包含2個A,問有多少種排法?

答4
(a) 這是一個「帶上限的組合」問題。我們可以把「最多只包含2個A」分為以下三個互斥且窮盡一切 可能性的情況,即(1)沒有任何A;(2)包含剛好1個A;(3)包含剛好2個A。現在我們逐一考慮這三個情況。

(1) 這種情況相當於從B、C這2個字母中抽4個出來的「無限重覆組合」問題,因此應有C(2 + 4 − 1, 4) = 5! / (1! × 4!) = 5種組合。該5種組合為B,B,B,B;B,B,B,C;B,B,C,C;B,C,C,C;C,C,C,C。

(2) 這種情況相當於從B、C這2個字母中抽3個出來的「無限重覆組合」問題,因此應有C(2 + 3 − 1, 3) = 4! / (1! × 3!) = 4種組合。這4種組合與那個確定的A加在一起便構成以下4個組合:A,B,B,B; A,B,B,C;A,B,C,C;A,C,C,C。

(3) 這種情況相當於從B、C這2個字母中抽2個出來的「無限重覆組合」問題,因此應有C(2 + 2 − 1, 2) = 3! / (1! × 2!) = 3種組合。這3種組合與那兩個確定的A加在一起便構成以下3個組合:A,A,B,B; A,A,B,C;A,A,C,C。

最後,運用「加法原理」,得知共有5 + 4 + 3 = 12種組合。

(b) 由於本部分不要求列出所有不同排法,所以我們採取從反面求解的方法。首先,從A、B、C這3個字母中抽4 個出來排列,若不加任何限制,應有34 = 81種排法。由於「最多只包含2個A」的否定是「包含3或 4個A」,我們只需從81減去包含3或4個A的排列,便求得本部分的答案。這裡可分為兩個互斥且窮盡一切可能性 的情況,即(1)包含剛好3個A;(2)包含剛好4個A。現在我們逐一考慮這兩個情況。

(1) 由於已確定了4個字母中包含剛好3個A,餘下來的字母只有兩種選擇,因此符合這種情況的組合為A,A,A,B 和A,A,A,C。現在對這兩種組合進行「全排列」,由於這兩個組合都是3個A與1個非A的組合,所以它們的「全排 列」數目都是4! / (3! × 1!) = 4。因此在這種情況下,共有8種排法。

(2) 包含剛好4個A的字母組合只有1種排法(即A-A-A-A)。

綜合以上結果,得知本部分的答案為81 − 8 − 1 = 72。□

最後,筆者用一個例題說明如何運用上述技巧解答某些「帶上、下限的排列問題」。

例題5:現從A、B、C這3個字母中抽4個出來排列。若其中必須包含最多1個A、最少1個B和1至2個C, 問有多少種排法?

答5:跟前面一樣,我們把這個「排列」問題分解為「組合」和「全排列」這兩個程序,並首先考慮 第一個程序。由於本題的限制條件包括混合的上、下限條件,難以運用現有的公式求取符合所有限制條件的組 合數目(註3),所以我們索性直接根據所給的條件列出所有符合條件的組合。由於已規定有最少1個B,我們只須 考慮其餘3個字母。由於規定有1至2個C,我們可以分為兩個情況:(1)剛好有1個C;(2)剛好有2個C。符合(1)的 組合只有兩個:B,C,A,B和B,C,B,B。符合(2)的組合也只有兩個:B,C,C,A和B,C,C,B。

接著我們對以上4個組合進行「全排列」。(1) 對於組合B,C,A,B,共有4! / (2! × 1! × 1!) = 12種排法;(2) 對於組合B,C,B,B,共有4! / (3! × 1!) = 4種排法;(3) 對於組合B,C,C,A,共有4! / (1! × 2! × 1!) = 12種排法;(4) 對於組合B,C,C,B,共有4! / (2! × 2!) = 6種排法。 最後,運用「加法原理」,得知共有12 + 4 + 12 + 6 = 34種排法。□

以上幾個例題顯示,利用我們現有的方法,只能解答較簡單的「有限重覆排列組合」問題。對於較為複雜的問 題,我們須考慮很多複雜的情況,現有的方法有很大的局限性。以後讀者將會看到其他更有效的解題方法。

註1:由於容許重覆,所以現在我們不只有n件物件,而是n類物件,而且假定每類物件的個數無限。此外,我們 也假定同一類物件之間彼此沒有區別,因為如果可以區別,便不算是同一類了。

註2:在現實生活中,有時難以把某些事物的數目假定為無限,例如貨架上的罐頭數便不會是無限的。但只要該 類事物的數目足夠多,即至少等於被抽出物件的總數(即r),那麼我們仍可把這類問題視為「可無限重覆」的問 題。

註3:事實上,讀者從例題3和4應能發現,對於求解這類問題的第一個程序,最重要的不是要知道有多少種組合 ,而是要能列出這些組合。因此「無限重覆組合」公式的作用只是幫助我們「驗證」有否遺漏任何可能的組合 。



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