JOVANA
Library Glossary Getting Started Three Levels Fields How it works Mission
Join the mission
All guides

排列：當順序很重要

當把同樣的東西重新排列就算成全新的結果時，你算的就是排列。本篇說明階乘與遞降乘積公式 P(n,k) 如何直接從乘法原理長出來。

順序就是重點所在

上一篇我們學了乘法原理：當一件事分步驟進行、且每一步的選項數穩定時，就把各步的選項數相乘。排列就是把那部引擎對準一個特定問題時得到的東西——把東西排成一個確定的「順序」有幾種方式？三名跑者 A、B、C 跑完一場比賽，可以是 ABC、ACB、BAC、BCA、CAB、CBA：共六種排序。順序在這裡不是小細節，而是問題的全部。ABC 與 ACB 用的是同樣三人，卻算成兩個不同的結果。

為什麼順序這麼常重要？因為在現實世界裡，重排往往會改變意義。頒獎台上的第一、第二、第三名，和第二、第一、第三名並不一樣。密碼「cat」不是密碼「act」。把奶奶安排在餐桌主位的座位表，和把她安排在末位的座位表，是兩張不同的表。只要對調兩個東西就會產生真正不同的結果，你就身處排列的領域——而那正是我們即將建立的排列計數。

全部排列：階乘

從最簡單的版本開始：把全部 n 個不同的東西排成一列。第一個位置有 n 個候選。它一旦填好，第二個位置可以是剩下的 n-1 個之一。第三個剩 n-2 個，依此類推，直到最後一個位置別無選擇——只剩 1 個候選。乘法原理說：相乘。所以全排列的數目是 n 乘 (n-1) 乘 (n-2) 乘……乘 2 乘 1。這個乘積太常見了，於是有了自己的符號 n!，唸作「n 階乘」。

要注意的關鍵是，5、4、3、2、1 這些「計數」從不依賴你實際先放了哪一個東西。不論你把誰安排到第一張椅子，第二張椅子永遠剩下恰好四人。這份穩定性正是乘法原理裡那個隱藏條件，也正是讓我們能相乘的原因。五個人排隊拍照有 5! = 5 乘 4 乘 3 乘 2 乘 1 = 120 種方式。成長極為猛烈：10! 已是 3,628,800，而一副洗過的 52 張牌有 52! 種排序——一個 68 位數，遠遠超過構成我們這顆行星的原子數。

只排一部分：P(n, k)

你常常不會把全部 n 個東西都排，只把其中 k 個排成順序——比如在 8 名短跑選手中頒發金、銀、銅牌。這就是所謂的 k-排列，寫作 P(n, k)。推理和階乘一模一樣，只是提早停下。第一面獎牌有 8 個候選、第二面 7 個、第三面 6 個——然後就停，因為只有三個位置。所以 P(8, 3) = 8 乘 7 乘 6 = 336。你乘的是從 n 開始、恰好 k 個因子的一段遞降乘積。

它有一個漂亮的封閉形式。遞降乘積 8 乘 7 乘 6，其實就是 8! 把尾巴 5 乘 4 乘……乘 1 = 5! 除掉。一般而言 P(n, k) = n! / (n - k)!。分母的 (n - k)! 恰好約掉你「沒用到」的那些因子。做個檢驗：把全部 n 個都排意味著 k = n，而 P(n, n) = n! / 0! = n! / 1 = n!——正是我們已經找到的階乘，也正是 0! = 1 這個慣例派上用場的地方。

P(n, k) = n times (n-1) times ... times (n-k+1)   [k falling factors]
       = n! / (n-k)!

P(8, 3) = 8 x 7 x 6 = 336          (medals among 8 runners)
P(26, 4) = 26 x 25 x 24 x 23 = 358800   (4-letter codes, no repeats)
P(n, n) = n! / 0! = n!            (arrange everything)
k-排列：k 個因子的遞降乘積，等於 n!/(n-k)!。

兩個誠實的陷阱

第一個陷阱是相同的東西。乾淨的計數 n! 假設每個東西都「可區分」。HELLO 這個字有五個字母，但其中兩個是 L，所以 5! = 120 多算了：把兩個 L 對調得到的字串看起來完全一樣。解法在更上一層的觀念——多重集的排列——你要把 n! 除以各重複次數的階乘。對 HELLO 就是 5! / 2! = 60。目前要記住的教訓是：單純的 P(n, k) 與 n! 只有在沒有任何重複時才有效。

第二個陷阱幾乎絆倒每一個人：把排列和組合搞混。決定性的問題只有一句話——「順序」重要嗎？如果重排會產生「新」結果（名次、密碼、座位、跑步順序），算排列。如果重排得回「同一個」結果（一手牌、一個委員會、一組樂透號碼），就改算組合，那不過是把排列的各種排序除掉。永遠先問這個問題；它正是下一篇要完整探討的岔路，也是四種抽樣模型的基礎。

從排列到機率

計數本身不是目的，它是機率的燃料。在古典定義下，當每一種排法等可能時，P(事件) 就是（有利的排法數）/（全部排法數）——而分子和分母都是排列計數。假設四個人抽籤決定排成一列的座位，我們問：安排在第一、博排在第二的機率是多少？四人的全部排序：4! = 24。有利的排序：安和博固定在第 1、2 個位置，其餘兩人以 2! = 2 種方式填滿剩下的。所以 P = 2 / 24 = 1/12。

  1. 判斷順序是否重要。這裡重要——排第一和排第二不同——所以算排列。
  2. 計算全部等可能的排法：四人排成一列，即 4! = 24。
  3. 計算有利的排法：把安釘在第 1 位、博釘在第 2 位，再排剩下的 2 人，得 2! = 2。
  4. 相除：P = 有利 / 全部 = 2 / 24 = 1/12。分子分母的排列計數完成了工作。

同一套機制也驅動了著名的生日問題，其中「k 個人中沒有人同一天生日」被算成相異日子的有序選取，365 乘 364 乘……——一個遞降乘積，正是喬裝過的 P(365, k)。一旦我們開始把東西分成有標籤的群組，排列也支撐起多項式係數。所以這個小小的觀念——有序排法就是一段選項的遞降乘積——在我們往上爬時會不斷重現。把「順序重要嗎？」這個問題練到熟，公式自己就會寫出來。