排列與組合：為什麼順序會改變個數

五個人自願參加一個專案。你需要一位隊長和一位副隊長。隊長有五種選法，接著副隊長有四種選法。總共有二十種分派方式。

現在改一句話：你需要一個兩人的委員會，沒有各自的職務。同樣的五個人，產生十個委員會。人並沒有任何變化。改變的是「一個結果」的定義。

排列與組合是兩種不必把每種可能都列出來，就能計算結果個數的方法。一旦你決定了結果要保留哪些資訊，公式就說得通了。本文先建立這個決定的方式，再推導符號。

從位置開始，而不是從公式開始

想像兩個空盒子，分別標示隊長和副隊長。第一個盒子有五個可能的人選。填好之後，第二個盒子還剩下四個人。每一種第一個選擇，都有四種接續的選法，得到：

$$5 \times 4 = 20$$

這就是乘法原理。如果某一階段的每個選項，都有相同數量的後續可能，就把各階段的個數相乘。你可以想像一棵樹，有五個分支，每個分支再分成四個。

標示很重要。Alex 當隊長、Bea 當副隊長，與 Bea 當隊長、Alex 當副隊長是不同的。它們是同樣的人處在不同的位置。這就是有順序的選取，稱為排列。

委員會沒有標示的位置。寫成 Alex、Bea，或 Bea、Alex，描述的是同一個團體。如果你用二十種分派的個數來算委員會，你就把每一個團體都算了兩次。

對調測試告訴你順序重不重要

問：如果我把兩個被選中的東西對調，結果會不同嗎？

對於賽跑的頒獎台，會。金牌與銀牌是不同的結果。對於披薩配料的組合，通常不會。蘑菇加橄欖，與橄欖加蘑菇是同一個選擇。

這個問題問的是模型，而不是名詞。一道課本題目可能要你選三本書來買，順序不計；也可能要你把三本書排在書架上，順序要記錄。「書」這個字不會告訴你該用哪個公式。

計算之前，先寫出一個範例結果。「隊長 Alex，副隊長 Bea」包含了職務。「包含 Alex 與 Bea 的團體」則沒有。這個小步驟，比背一張更長的公式表能防止更多的錯誤。

最後兩列還需要問重複的問題。不要只憑順序來決定。

階乘計算完整的排列

把四本不同的書排成一列。第一個位置有四種選擇，第二個三種，第三個兩種，最後一個一種：

$$4! = 4 \times 3 \times 2 \times 1 = 24$$

驚嘆號代表階乘。它是遞減連乘積的縮寫。對於非負整數 $n$，階乘計算的是 $n$ 個不同東西全部排列的方式數。

為什麼 $0! = 1$？因為有一種空的排列。你什麼都不做，而空的排列就是完整的。這也是讓 $1! = 1 \times 0!$ 保持一致的值。

不要把階乘讀成重複的加法，或是一個次方。4 的階乘是二十四；4 的 4 次方是二百五十六。階乘的選擇會縮小，是因為一個東西不能再被使用。次方的選擇則保持不變。

排列的連乘會提早停下來

假設有七位跑者，你只想要前三名，不並列。第一名有七種選擇，第二名六種，第三名五種：

$$P(7,3) = 7 \times 6 \times 5 = 210$$

你不在乎其餘四位跑者怎麼完賽。如果一路乘到一，回答的就是另一個問題了。

對於從 $n$ 個不同的東西中，不重複地填入 $r$ 個有順序的位置：

$$P(n,r) = \frac{n!}{(n-r)!}$$

分母會約掉階乘中用不到的尾巴。在跑者的例子中，7 的階乘除以 4 的階乘，剛好剩下七乘六乘五。

這個公式假設 $0 \le r \le n$，且可選的東西互不相同。如果題目改變了這些假設，就回到盒子的想法，不要硬把數字塞進這個式子。

組合去掉重複的排列

從七個人中選三人組成委員會。有順序的個數是 210，但它把同一組三人的不同排列，當成不同的答案。

取一組三人：Alex、Bea 與 Chen。它的成員可以用六種順序列出：ABC、ACB、BAC、BCA、CAB 與 CBA。每一組三人在有順序的計數中，恰好出現六次，因為 $3! = 6$。

除以重複排列的個數：

$$\binom{7}{3} = \frac{210}{6} = 35$$

一般而言：

$$\binom{n}{r} = \frac{n!}{r!(n-r)!}$$

讀作「n 取 r」。第一個除法去掉排列計數中用不到的東西；第二個除法則去掉你不再區分的順序。

這裡有一個好用的對稱性：$\binom{7}{3} = \binom{7}{4}$。選出加入的三個人，同時也就確定了沒加入的四個人。這兩種描述指向的是同一組決定。

重複又改變了問題

一組四位數的密碼，可以在每個位置使用 0 到 9 的任何數字，包括開頭。允許重複的數字。每個盒子有十種選擇：

$$10^4 = 10000$$

如果沒有任何數字可以重複，個數就變成：

$$10 \times 9 \times 8 \times 7 = 5040$$

如果題目說的是「四位數」而不是「密碼」，開頭的零通常要排除。在允許重複的情況下，這給出：

$$9 \times 10 \times 10 \times 10 = 9000$$

三個非常相似的句子，三個不同的個數。公式並沒有變得不可靠。改變的是限制條件。

可重複的無順序選取，例如挑選有重複口味的幾球冰淇淋，需要另一種計數方法。一般的組合假設每個可選的東西最多只能被選一次。認出一個熟悉的公式並不適用，是正確的第一步。

照這個順序來判斷

計算之前，先寫下一個完整的結果長什麼樣子。然後問：順序或職務是否區分了不同的結果、有沒有東西可以重複，以及是否有特殊限制套用在某個位置上。

試試這三個問題，不要馬上看答案：

1. 從六個人中，選出一位主席和一位秘書，沒有人同時擔任兩個職務。
2. 從同樣的六個人中，選出兩位地位相同的代表。
3. 用四個符號組成一組三個字元的密碼，允許重複。

第一題有 $6 \times 5 = 30$ 種分派。第二題把它除以 $2!$，得到十五組。第三題有 $4^3 = 64$ 組密碼，因為四個符號在每個位置上都仍然可以使用。

說明比數字更重要。如果你能說出為什麼一個答案要除以二，而另一個不用，你就理解了這個區別。

計數是機率的基礎

當等可能的結果被正確地計數，你就可以用有利的結果除以所有可能的結果，得到機率。我們的直觀機率指南會邁出下一步。生日悖論展示了一個精心選擇的計數，如何讓一個令人驚訝的結果變得容易處理。

目前，先讓這項技能保持小規模：定義一個結果，如果有位置就把位置畫出來，並解釋每一個因子。下一個應用請用 Math Zen 的機率練習，每當符號開始遮住推理時，就回到一個小例子。

排列保留了安排。組合保留了成員。除以階乘，只是在忘掉安排，又不把同一個團體重複計算的過程。