點算的奧秘:排列和組合基本公式


在本節中,筆者將介紹「排列」(Permutation)和「組合」(Combination)的基本概念和兩個基本公式。請注意 「點算組合學」中的很多概念都可以從不同角度解釋為日常生活中的不同事例,因此筆者亦會引導讀者從不同 角度理解「排列」和「組合」的意義。

先從「排列」開始。「排列」的最直觀意義,就是給定n個「可區別」(Distinguishable,亦作「相 異」)的物件,現把這n個物件的全部或部分排次序,「排列」問題就是求不同排列方式的總數。為了區別這些 物件,我們可不妨給每個物件一個編號:1、2 ... n,因此「排列」問題實際等同於求把數字1、2 ... n的全 部或部分排次序的方式總數。「排列」問題可分為「全排列」和「部分排列」兩種,當我們把給定的n個數字1 、2 ... n全部排次序,求有多少種排法時,就是「全排列」問題。我們可以把排序過程分解為n個程 序:第一個程序決定排於第一位的數字,第二個程序決定排於第二位的數字...第n個程序決定排於第n位的數字 。在進行第一個程序時,有n個數字可供選擇,因此有n種選法。在進行第二個程序時,由於在前一程序已選定 了一個數字,現在可供選擇的數字只剩下n − 1個,因此有n − 1種選法。在進行第三個程序時, 由於在前一程序已選定了一個數字,現在可供選擇的數字只剩下n − 2個,因此有n − 2種選法。 如是者直至第n個程序,這時可供選擇的數字只剩下1個,因此只有1種選擇。由於以上各程序是「各自獨立」的 ,我們可以運用「乘法原理」求得答案為n × (n − 1) × (n − 2) × ... 2 × 1。在數學上把上式簡記為n!,讀作「n階乘」(n-factorial)。

例題1:把1至3這3個數字進行「全排列」,共有多少種排法?試列出所有排法。

答1:共有3! = 3 × 2 × 1 = 6種排法,這6種排法為1-2-3;1-3-2;2-1-3;2-3-1; 3-1-2;3-2-1。□

當然,給定n個數字,我們不一定非要把全部n個數字排序不可,我們也可只抽取部分數字(例如r個,r < n)來 排序,並求有多少種排法,這樣的問題就是「部分排列」問題。我們可以把「部分排列」問題理解成 抽東西的問題。設在某袋中有n個球,每個球都標了編號1、2 ... n。現從袋中抽r個球出來(抽出來之後不得再 放回袋中),並把球上的數字按被抽出來的順序記下,這r個數字的序列實際便等同於一個排序。「部分排列」 問題的解答跟「全排列」問題非常相似,只不過現在我們是把排序過程分解為r個而非n個步驟。進行第一個程 序時,有n個數字可供選擇,因此有n種選法。在進行第二個程序時,由於在前一程序已選定了一個數字,現在 可供選擇的數字只剩下n − 1個,因此有n − 1種選法。在進行第三個程序時,由於在前一程序已 選定了一個數字,現在可供選擇的數字只剩下n − 2個,因此有n − 2種選法。如是者直至第r個程 序,這時可供選擇的數字只剩下n − r + 1個,因此只有n − r + 1種選擇。最後,運用「乘法原 理」求得答案為n × (n − 1) × (n − 2) × ... (n − r + 1)。

我們可以把上式改寫為更簡的形式n! / (n − r)!,為甚麼可以這樣改寫?這要用到n!的定義和乘法的結 合律。舉一個簡單的例子,由於5! = 5 × 4 × 3 × 2 × 1 = 5 × (4 × 3 × 2 × 1) = 5 × 4!。同樣由於5 × 4 × 3 × 2 × 1 = 5 × 4 × (3 × 2 × 1),我們又可得5! = 5 × 4 × 3!。抽象地看,我們 可以把n!改寫為n × (n − 1)!,也可以改寫為n × (n − 1) × (n − 2)!照此類推,我們可以把n!改寫為n × (n − 1) × (n − 2) × ... (n − r + 1) × (n − r)!。由此得n! / (n − r)! = n × (n − 1) × (n − 2) × ... (n − r + 1)。在「點算組合學」上,一般把上述「部分排列」的 解記為P(n, r)。至此我們求得「排列」問題的一條基本公式:

P(n, r) = n! / (n − r)!

例題2:從1至4這4個數字中抽2個出來排序,共有多少種排法?試列出所有排法。

答2:共有P(4, 2) = 4! / 2! = (4 × 3 × 2!) / 2! = 4 × 3 = 12種排法。這 12種排法是1-2;1-3;1-4;2-1;2-3;2-4;3-1;3-2;3-4;4-1;4-2;4-3。□

請注意只要我們定義0! = 1 (註1),那麼上述公式便也適用於「全排列」的情況。「全排列」其實就是r = n的 情況,因此如果把r = n代入以上公式,便得P(n, n) = n! / (n − n)! = n! / 0! = n! / 1 = n!,正 與前面討論的結果吻合。

接下來筆者介紹「組合」問題。設在某袋中有n個球,每個球都標了編號1、2 ... n。現從袋中抽r個 球出來(抽出來之後不得再放回袋中),並把球上的數字記下,但無須理會球被抽出的先後次序。由此可見,「 組合」問題與「排列」問題的主要區別是,前者只關心被抽出來的包含哪些數字,而不管這些數字的順序;而 後者則既關心被抽出來的包含哪些數字,也關心這些數字的順序。

惟請注意,「排列」和「組合」雖然是兩種很不相同的問題,但兩者卻並非絕然對立,而是有著非常密切的聯 繫。日常生活中很多點算問題往往同時包含著「排列」和「組合」的因素,如能了解其中奧妙,很多點算問題 便容易解決。事實上,我們正可利用「排列」和「組合」的這種微妙關係找出「組合」問題的公式。我們把從n 個球中抽r個出來的組合數記為C(n, r)。以下我們利用「排列」和「組合」之間的關係以及「排列」的公式來 推導出C(n, r)的公式。

前面提過,「部分排列」問題可以理解成從n個標了編號的球中抽r個出來,並把球上的數字按被抽出來的順序 記下。其實我們可以把上述過程分解為兩個程序,第一個程序就是從n個球中抽r個出來,先不理會它們被抽出 來的順序,此即前面所定義的「組合」問題。第二個程序則是把這r個被抽出來的球全部排次序,並求有多少種 排法,此即前面介紹過的「全排列」問題。換句話說,我們可以把「部分排列」問題分解為一個「組合」問題 和一個「全排列」問題(由此可見「排列」和「組合」並非絕然對立)。由於上述兩個程序是「各自獨立」的, 根據「乘法原理」,「部分排列」問題的解應等於「組合」問題的解乘以「全排列」問題的解,即P(n, r) = C(n, r) × r!,由此得C(n, r) = P(n, r) / r!。代入前面P(n, r)的公式,應得

C(n, r) = n! / ((n − r)! × r!)

正如前面的「排列」公式適用於「全排列」的情況,上述「組合」公式也適用於「全組合」的情況,即求 C(n, n)的問題。根據上述公式,C(n, n) = n! / ((n − n)! × r!) = n! / (0! × r!) = 1。這一結果是完全合理的,因為從n個球中抽取所有n個出來,當然只有1種方法。

例題3:從1至4這4個數字中抽2個出來(不考慮次序),共有多少種組合?試列出所有組合。

答3:共有C(4, 2) = 4! / (2! × 2!) = (4 × 3 × 2!) / (2! × 2!) = (4 × 3) / 2 = 6種組合。這6種組合是1,2;1,3;1,4;2,3;2,4;3,4。請注意如果我們把上述6種組合 的每一種排序,由於每一組合均包含兩個數字,所以每一組合各有兩種排序方式(例如從1,2可得到1-2和2-1兩 種排序方式),這樣從4個數字中抽2個出來排序的排法便有6 × 2 = 12種,這正與例題2的解答完全一致 。□

請注意在上述C(n, r)的公式中,如果我們把r換成n − r,我們將得到

C(n, n − r) = n! / (r! × (n − r)!)

其結果與C(n, r)相同,由此我們得到C(n, r) = C(n, n − r)。這一點是容易理解的,可以用一個簡單 的例子來說明箇中原理。假設我們要求從5個人(假設為A、B、C、D、E)中選出4個人的組合數,此即C(5, 4)。 這個問題其實可以從另一個角度去理解。由於只要我們知道哪一個是「落選者」,便自然知道哪些人是「入選 者」,因此從5個人中選出4個人(入選者)的組合數其實就等同於從5個人中選出1個人(落選者)的組合數,即 C(5, 4) = C(5, 5 − 4) = C(5, 1) = 5。把上述結果推廣到一般情況,便得到上述的等式。

前面提過,「排列」和「組合」並非絕然對立,有時同一個問題可以從不同角度理解為「排列」或「組合」的 問題,而轉換角度往往可以令本來難解的問題變得容易。以下筆者將舉出兩個例題,說明如何利用這種轉換角 度的方法解答問題。

例題4:用1和2這兩個數字可以構造多少個包含3個1的八位整數?

答4:本題初看似應理解為一個「排列」問題,可不是嗎?11122222跟22222111是兩個不同的八位整 數,由此可見,本題必須考慮八位整數中1和2的次序,因此似乎應運用「排列公式」。可是想深一層,本題其 實已規定了所求的八位整數必須包括3個1和5個2,因此我們已無須考慮這些八位整數應包含哪些數字,而只須 考慮這些數字的位置。而且由於這些八位整數只包含兩種數字,我們只需確定其中一種數字(例如1)的位置便確 定了整個八位整數,例如如果我們確定那3個1位於第1、第3和第5位,我們便確定這個八位整數是12121222。因 此確定本題的八位整數便等同於從8個位置中選出3個位置來安放那3個1,而且由於把代表位置的數字列出來無 所謂誰先誰後(註2),因此本題其實應理解為一個「組合」問題,所求答案是C(8, 3) = 8! / (5! × 3!) = (8 × 7 × 6 × 5!) / (5! × 3!) = (8 × 7 × 6) / (3 × 2) = 56。□

本例題說明了一點,對於一個具體問題,我們不能一概而論地把它歸類為「排列」問題還是「組合」問題,因 為這要看我們是在點算甚麼。就本例題而言,由於我們點算的對象是那3個1的「位置」,而這些位置的先後次 序不影響點算結果,所以本題是「組合」問題而非「排列」問題。

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

答5:由於這8個外星人是可區別的,不妨把他們命名為A、B、C、D、E、F、G和H。本題其實相當於把 這8個字母排次序,並求有多少種排法,因此本題是一個「全排列」問題,答案是8! = 40320。

有些人可能覺得奇怪,為何本題的答案如此簡單?既然本題涉及兩類數目各不相同的外星人,似乎應對這兩類 人分別處理。現在就讓我們從另一個角度解本題,看看答案是否相同。首先,我們可以把排座位的過程分解為 三個程序:第一個程序是先從那8個座位選5個出來給木星人坐,這是一個「組合」問題,應有C(8, 5)種選法。 第二個程序則是安排那5個木星人(假設為A、B、C、D和E)坐這5個已選定的座位,這是一個「全排列」問題,共 有5!種排法。第三個程序則是安排那3個火星人(假設為F、G和H)坐餘下的座位,這也是一個「全排列」問題, 共有3!種排法。最後運用「乘法原理」求得本題答案為C(8, 5) × 5! × 3! = (8! × 5! × 3!) / (3! × 5!) = 8!,所得結果跟前面的完全相同。□

比較上述兩種解題方法,當然是第一種簡潔得多。而這種簡潔的解題法之所以能成立,是因為本題所給予的有 兩類外星人的信息是多餘的。由於本題對兩類外星人的坐法完全不加限制,因此不論這兩類外星人的比例如何 ,也不論有多少類外星人,只要外星人的總數是8,答案都是一樣的。當然,如果對外星人的坐法有所限制,例 如不容許兩個火星人坐在相鄰的位置,情況將大為不同。此一情況在以後還將討論到。

註1:有些人可能難以理解為何0!等於1而不是等於0,因為0乘以任何數都是0。請注意n! = n × (n − 1) × ... 2 × 1這個定義只適用於當n是正整數的情況,當n = 0時,便不能再運用上式 來定義0!。至於為何要定義0! = 1,這完全是為了使上述的「排列」公式也適用於「全排列」的情況,並且使 0!的定義能與「排列」的公式相協調。這一點就正如定義n0 = 1 (當n為正實數)一樣,是為了使n a的定義也適用於當a = 0的情況,並且使n0的定義能與指數的運算法則(例如na − b = na / nb)相協調。

註2:例如,當我們說「那3個1位於第1、第3和第5位」,跟說「那3個1位於第5、第1和第3位」是沒有分別的。



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