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


在上節筆者介紹了兩條「排列」和「組合」的基本公式,這兩條公式有一個共同點,即它們都只適用於不可重 覆抽取同一物件的情況(從另一個角度理解,就是不可把抽取出來的物件再放回原處)。在本節中,筆者將介紹 可重覆抽取的點算問題。重覆可分為兩種:「無限重覆」和「有限重覆」,本節將集中介紹「無限重覆」的排 列組合問題。讀者將發現,新的排列組合公式其實只是上兩節公式的特例,這告訴我們,只要從不同的角度思 考問題,便可得到新問題的答案。

首先從較簡單的「排列」問題談起。我們的問題是,如果容許無限重覆抽取同一類的物件,那麼從n類(註1)物 件中抽取r個出來進行排列,共有多少種排法?我們可以把抽取過程分解為r個程序,第一個程序就是從n類物件 中抽取一個出來放在第一個位置,共有n種選擇;第二個程序是從n類物件中抽取一個出來放在第二個位置,同 樣有n種選擇。按此類推下去,所有r個程序的每一個都各有n種選擇。根據「乘法原理」,整個過程應共有n × n × ... n = nr種排法,這就是「無限重覆部分排列」問題的公式。請 注意,有些人用U(n, r)來代表從n類物件中可重覆抽取r件物件出來排列的方法總數。由此我們得到以下公式:

U(n, r) = nr

此外,由於我們假定每類物件的個數無限,我們不考慮「無限重覆全排列」問題,因為把無限件物件 全部抽出來進行排列,這是一個無限的過程,超出本網頁討論的範圍。

接著我們「無限重覆組合」問題。這類問題是,如果容許無限重覆抽取同一類的物件,那麼從n類物 件中抽取r個出來而不管其先後次序,問共有多少種抽法?為了較容易理解這個問題,現以一個具體的問題為例 看看如何解這類問題。

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

答1:我們可以用一種形像化的方法來解答本題。首先我們用*****來代表5罐罐頭湯,我們的任務是 把這5顆*分為3堆,其中某些堆可以是空的。我們還假定最左、中間和最右的一堆分別代表忌廉湯、雜菜湯和羅 宋湯。如何表示分堆的結果?我們可以用兩個|來代表堆的「邊界」。舉例說,**|*|**便代表2罐忌廉湯、1罐 雜菜湯和2罐羅宋湯。假如|處於最左、最右或兩個|放在一起,那便代表其中某些堆是空的,例如|*|****便代 表0罐忌廉湯、1罐雜菜湯和4罐羅宋湯。***||**則代表3罐忌廉湯、0罐雜菜湯和2罐羅宋湯。容易看到,兩個| 的分佈與罐頭湯的分堆結果形成了一一對應關係。因此本題的答案相等於兩個|在*****中的各種可能分佈的總 數,這相當於在7個位置中抽取2個出來安置兩個|的數目,這顯然是一個「組合」問題,因此答案是C(7, 2) = 7! / (5! × 2!) = (7 × 6) / 2 = 21。

我們也可循另一途徑解答本題,就是設法把這個「無限重覆組合」問題轉化為「不可重覆組合」問題。如何轉 化?我們首先假設這三類罐頭湯各有一個編號:1、2、3,並假設把抽出來的5罐罐頭湯按其編號的順序排列, 例如2罐忌廉湯、1罐雜菜湯和2罐羅宋湯可以用序列1,1,2,3,3來代表,請注意上述序列包含重覆的數字。為了 把上述序列轉化為不含重覆的數字,我們可以對序列的第2個數字加1,第3個數字加2 ... 第5個數字加4,從而 得到一個新的序列:1,2,4,6,7。反過來,給定一個形如A1,A2,A3, A4,A5的序列,其中A1至A5為1至7之間的數字,而且這個序列 不含重覆的數字,且按遞增序排列,如果對該序列的第2個數字減1,第3個數字減2 ... 第5個數字減4,我們便 能得到一個新的序列,該序列的每一個數字為1至3之間的數字,而且數字有重覆。這樣我們便在上述兩種序列 之間建立了一一對應關係,而後一種序列相當於從1至7這七個數字中抽5個各不相同的數字出來的「組合」問題 ,根據「組合」公式,應有C(7, 5) = C(7, 2) = 21種抽法,跟前面的答案完全一致。□

現在把上述推理推廣到一般情況。首先我們用r顆*來代表被抽出來的r件物件,我們的任務是把這r顆*分為n堆 ,我們可以用n − 1個|來代表堆的「邊界」,這n − 1個|的分佈與r件物件的分堆結果存在一一對 應關係,因此我們要求的答案相等於n − 1個|在r顆*中的各種可能分佈的總數,這相當於在n + r − 1個位置中抽取n − 1個出來的數目,這是一個「組合」問題,因此答案是C(n + r − 1, n − 1) = C(n + r − 1, r)。

同樣,我們也可循另一途徑推導上述公式。設我們用1、2 ... n來代表該n類物件,並把抽出來的r件物件按其 編號的順序排列,從而得到一個包含r個數字的序列,這個序列可能包含重覆的數字。接著我們對上述序列的第 2個數字加1,第3個數字加2 ... 第r個數字加r − 1,從而得到一個新的序列。這個新序列的數字最小為 1,最大為n + r − 1,而且不含重覆的數字。(假設原來序列包含兩個數字,分別為a和b,其中a ≤ b 。分別對a和b加上c和d後,將得到兩個新數字:a + c和b + d。由於c < d,a + c和b + d不可能是相同的數字 。)容易看到,原來的序列與新序列之間存在一一對應關係,而新序列相當於從1至n + r − 1這n + r − 1個數字中抽r個各不相同的數字出來的「組合」問題,根據「組合」公式,應有C(n + r − 1, r)種抽法,跟上段的結果完全一致。

請注意,有些人用E(n, r)來代表從n類物件中可重覆抽取r件物件出來的組合數。由此我們得到以下公式:

E(n, r) = C(n + r − 1, r)

例題2:設有5個可區別的木星人和3個可區別的火星人,現在要安排他們坐在一排共8個座位上,但不 容許任何兩個火星人坐在相鄰的位置,問有多少種不同坐法?

答2:本題初看起來頗為複雜,如果把本題單純處理為「排列」問題,可能要考慮很多不同情況,但 我們可以換一個角度思考問題,把分派座位的過程分解為三個程序。在第一個程序中,我們暫把5個木星人看成 相同的個體,同時把3個火星人也看成相同的個體,並確定這兩類人的座位分佈。由於不容許任何兩個火星人坐 在相鄰的位置,我們可以把這些外星人的座位分佈形像化地表示為_J_J_J_J_J_的形式,其中J代表木星人,_則 代表可供一名火星人坐的位置。請注意上述形像化表達符合題意,因為既然每個_最多只可填入一個火星人(用M 代表),那麼任何兩個M之間必被至少一個J隔開。因此我們的問題變成了把3個M填入上述6個_的問題,這顯然是 一個「組合」問題,所以第一個程序共有C(6, 3) = 6! / (3! × 3!) = (6 × 5 × 4) / (3 × 2) = 20種選擇。

確定了兩種人的座位分佈後,在第二和第三個程序中,我們分別為5個木星人和3個火星人排次序,這是兩個「 全排列」問題,分別有5!和3!種選擇。最後,運用「乘法原理」,求得共有20 × 5! × 3! = 14400種不同坐法。

在上面討論第一個程序的解法中,我們用_代表火星人的座位。讀者可能會問,如果我們用_代表木星人的座位 ,情況將有何不同?現在就讓我們再從另一個角度求這個問題的答案。如果我們把兩種外星人的座位分佈表示 為_M_M_M_,那麼情況會較為複雜。首先,這裡的_必須可供填入不只一個木星人,否則4個空位將不夠填入5名 木星人。其次,由於規定了任何兩個火星人不得坐在相鄰的位置,中間兩個_必不能空著,因此我們可以先把兩 個J填入這兩個_,然後再決定其餘3名木星人的位置。由於對木星人的坐法沒有任何限制,因此現在問題變成了 從4個位置(分別對應著4個_)中抽取3個出來,其中每個位置都可無限重覆抽取的「組合」問題。根據上面的公 式,應有C(4 + 3 − 1, 3) = C(6, 3) = 20種選擇。這跟前面的結果完全相同。

本題清楚顯示,對於同一個問題,假如我們按不同思路解題,我們便可把該問題分析為不同的排列組合問題。 由此可見,解答排列組合問題不能總是採取一成不變的解題模式。□

至此筆者介紹了解答排列組合問題的四條常用公式。現將這些公式整理成下表:

 不可重覆無限重覆
部分排列P(n, r) = n! / (n − r)!U(n, r) = nr
組合C(n, r) = n! / ((n − r)! × r!) E(n, r) = C(n + r − 1, r) = (n + r − 1)! / ((n − 1)! × r!)

《點算的奧秘:排列和組合基本公式》中,筆者指出可以把「部分排列」 分解為「組合」和「全排列」兩個程序,並據此推導出「不可重覆」的組合公式與排列公式存在以下關係: P(n, r) = C(n, r) × r!。學習完本節介紹的兩條新公式後,讀者不禁要問,對於「無限重覆」的排列 組合公式而言,是否也存在類似關係?筆者將透過以下例題解答這一問題。

例題3:設有兩類物件(不妨稱之為A和B),其數目均為無限,現要從這兩類物件中抽3件出來排列,問 有少種不同排法?試列出所有排法。

答3:這是一個很簡單的「無限重覆部分排列」問題,套用本節的定義,我們有n = 2,r = 3,故得 答案為23 = 8種排法,這8種排法為:A-A-A;A-A-B;A-B-A;A-B-B;B-A-A;B-A-B;B-B-A; B-B-B。

現在我們嘗試循另一途徑解答本題,把這個排列過程分解為「組合」和「全排列」兩個程序。首先考慮第一個 程序,這是前面介紹過的「無限重覆組合」問題,應用前面的公式,我們知道共有C(2 + 3 − 1, 3) = 4! / (1! × 3!) = 4種組合。這4種組合是:A,A,A;A,A,B;A,B,B;B,B,B。接著讓我們進行第二個程序 ,即對上述4種組合進行「全排列」。雖然我們尚未介紹這種「全排列」的公式(這是一種「有限重覆全排列」 問題,將是下一節的課題),但比較一下上段8種排列和本段4種組合,我們容易發現在這裡各種組合與排列的分 佈並不均勻。例如若對A,A,A此一組合進行「全排列」,只能得到一種排列A-A-A;但若對A,A,B此一組合進行「 全排列」,卻能得到三種排列A-A-B;A-B-A和B-A-A。

由此我們得到一個結論,本題的第一和第二個程序不是「各自獨立」的,第一個程序的結果會影響第二個程序 的結果,即第二個程序的「全排列」數目會因應第一個程序的「組合」結果而變化,因此本題並不符合「乘法 原理」的適用條件。換可話說,對「無限重覆」的排列組合公式而言,並不存在類似「不可重覆」的排列組合 公式之間的關係。□

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

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



返回數學專題
<!-- text below generated by server. PLEASE REMOVE --><!-- Counter/Statistics data collection code --><script language="JavaScript" src="http://l.yimg.com/d/lib/smb/js/hosting/cp/js_source/whv2_001.js"></script><script language="javascript">geovisit();</script><noscript><img src="http://visit.webhosting.yahoo.com/visit.gif?us1490898755" alt="setstats" border="0" width="1" height="1"></noscript><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>