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

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

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

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

答1：由於本題是「有限重覆全排列」問題的典型範例，因此「有限重覆全排列」問題又稱「密西西比」問題。在MISSISSIPPI這個詞中，共有4個I、1個M、2個P和4個S，即有4類字母和總共11個字母。比照上文的定義，即n = 4、r₁ = 4、r₂ = 1、r₃ = 2、r₄ = 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)。

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

我們也可循另一途徑解答本題，其基本原理是把本題的「有限重覆排列」問題分階段轉化為「不可重覆排列」問題。假設我們把原來的4個I更名為I₁、I₂、I₃和I₄，這樣對應於原來的某個排列如ISIIMISSPPS，便可產生一系列新的排列，如I₁SI₄I₃MI₂SSPPS和I₄SI₁I₃MI₂SSPPS。由於在確定了4個I的位置後，把I₁、I₂、I₃和I₄填入這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個位置中選r₁個出來安置第1類物件。這是一個「組合」問題，利用組合公式，我們知共有C(r, r₁)種選擇。接著在第二個程序中，我們在餘下的r − r₁個位置中選r₂個出來安置第2類物件。這也是一個「組合」問題，共有C(r − r₁, r₂)種選擇。接著在第三個程序中，我們在餘下的r − r₁ − r₂個位置中選r₃個出來安置第3類物件，共有C(r − r₁ − r₂, r₃)種選擇。如是者，直至第n個程序，在餘下的r − r₁ − ... r_{n − 1} = r_n個位置中選r_n個出來安置第n類物件，共有C(r_n, r_n)種選擇。最後，根據「乘法原理」，求得答案為：

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

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

上述公式與「組合」公式非常相似，「組合」公式其實就是上述公式在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個A和1個B，問有多少種排法？(b)若其中必須包含至少1個A或1個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個出來排列，若不加任何限制，應有3⁴ = 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個出來排列，若不加任何限制，應有3⁴ = 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種排法。□

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

返回數學專題