排列和組合搜尋 最佳化！

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

http://chowkafat.net/Enumeration2.html

在本節中，筆者將介紹「排列」(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! / (n! × (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!的定義能與「排列」的公式相協調。這一點就正如定義n⁰ = 1 (當n為正實數)一樣，是為了使n ^a的定義也適用於當a = 0的情況，並且使n⁰的定義能與指數的運算法則(例如n^{a − b} = n^a / n^b)相協調。

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