乘法原理

為什麼計數是古典機率的核心

在上一個階段，你學到了古典機率定義：當樣本空間中每個結果都同樣可能時，一個事件的機率就是讓它發生的結果數，除以結果的總數。看起來很簡單，但它悄悄交給你一個棘手的工作。要算出 P(A)，你必須數兩樣東西——事件的大小，以及整個樣本空間的大小——而這些結果通常多到根本沒辦法用手一一寫出來。

所以古典機率其實是一個披著外衣的計數問題。你現在開始的這整個階段，就是一套聰明計數的工具，讓「拿到葫蘆的機率是多少？」或「一個房間裡有兩個人同一天生日的機會有多大？」這類問題，從靠猜變成靠算。而這套工具裡的每一件——排列、組合、抽樣模型，甚至著名的生日問題——都建立在我們在這裡奠定的同一個基礎之上。

這個基礎就是乘法原理，也叫做基本計數原理。它是組合學教的第一件事，而且說真的，後面幾乎所有東西都只是這個想法換了套裝扮。現在就把它徹底刻進骨子裡，這個階段剩下的部分就會像在記帳一樣輕鬆。

原理本身：階段相乘

陳述如下。假設你透過做出一連串的選擇來建構一個結果：先做選擇 1，再做選擇 2，依此類推到選擇 k。如果選擇 1 有 n_1 種做法，而不論它結果如何選擇 2 都有 n_2 種做法，依此類推，那麼完成整個序列的總方法數就是乘積 n_1 * n_2 * ... * n_k。你把各階段的數目一個接一個地相乘。

想像一個小例子。你要從 3 件襯衫和 2 條長褲中搭配一套衣服。先選襯衫——3 種選法。然後不論選了哪件襯衫，你都還有 2 種選褲子的方式。所以可搭配的套數是 3 * 2 = 6。你可以把它看成一棵樹：頂端有 3 條分枝，每條再分出 2 條，底部就有 6 片葉子。數一棵分枝樹的葉子數，這就是乘法原理本身，而這個心像會帶你走得很遠。

shirt A --- trousers 1   (A,1)
        \-- trousers 2   (A,2)
shirt B --- trousers 1   (B,1)
        \-- trousers 2   (B,2)
shirt C --- trousers 1   (C,1)
        \-- trousers 2   (C,2)

        3 shirts x 2 trousers = 6 outfits

細則：每個階段的選擇數不可以變

這個原理有一個容易被略過的條件，所以請仔細讀。較後面選擇的做法數可以取決於你現在處在哪一個階段，但不可以取決於你先前實際選了哪些選項。在搭配衣服的例子裡，不論選了哪件襯衫你都有 2 種褲子可選——這正是相乘乾淨俐落的原因。只要某個階段的選擇數對於通往它的每一條路徑都確實是同一個數，你就可以相乘。

看看當選擇數確實改變時會怎樣。假設你要把 3 個不同的人安排到 3 張椅子上。第一張椅子：有 3 個人可選。第二張椅子：只剩 2 個人，因為已經有一個人坐下了——但關鍵在於不論誰先坐，這個數永遠是 2。第三張椅子：永遠是 1。所以答案是 3 * 2 * 1 = 6。每個階段的數變小了，但在每一條路徑上都縮小了相同的幅度，所以相乘依然成立。這個乘積 3 * 2 * 1 正是階乘 3!，而這恰好就是通往下一篇排列指南的橋樑。

「而且」用乘，「或者」用加

乘法原理有一個搭檔，用來處理另一種形狀的問題：計數的加法法則。這兩者用一個簡單的語言測試來分工。當一個結果是由做完一個階段而且再做另一個階段所建構的（襯衫而且長褲、第一張椅子而且第二張椅子），你用乘。當一個結果落入某一類或者另一個不重疊的類別時，你把這些類別的大小相加。

一個混合的範例會讓它豁然開朗。如果你必須經過 Y 鎮，而 X 到 Y 有 3 條路、Y 到 Z 有 4 條路，那麼從 X 鎮到 Z 鎮有幾種走法？這是 X 到 Y 而且 Y 到 Z，所以是 3 * 4 = 12 條路線。再換一個問題：如果今天從 X 出發，有 3 班公車或者 4 班火車，那麼有幾種直達的出發方式？這些是互斥的類別，所以是 3 + 4 = 7。「而且」這個詞召喚的是乘法；「或者」這個詞召喚的是加法。

順序內建其中：為什麼抽樣就是乘法

這就是為什麼這篇指南要打頭陣的深層原因。你將學到的幾乎每一種計數模型，都是一連串選擇的化身，而乘法原理正是把這個序列化為一個數字的東西。想想看，從裝有 10 個相異籌碼的袋子裡，一次抽一個。如果你在下一次抽之前把每個籌碼放回去——也就是取後放回的抽樣——那麼比方說 3 次抽取，每一次都有 10 種選項，得到 10 * 10 * 10 = 10^3 = 1000 種有順序的結果。每個階段的選擇數都不變，所以乘積是一個乾淨的乘冪。

現在改成每次抽完不把籌碼放回去——也就是取後不放回的抽樣。第一次抽有 10 種選項，第二次有 9 種（一個已經沒了），第三次有 8 種，得到 10 * 9 * 8 = 720 種有順序的結果。這種每次減一的模式又是階乘的想法，而這兩種設定之間的區別，正是本階段稍後取後放回與取後不放回的抽樣的主題。請注意這兩個數算的都是有順序的序列；至於順序到底該不該重要，那是有序與無序的問題，它將在接下來兩篇指南裡把排列和組合分開來。

1. 判斷你在數的是「而且」的階段（相乘）還是「或者」的類別（相加）。大多數逐步建構的問題都是「而且」的階段。
2. 依序列出各個階段，並寫下每個階段有幾種選項。
3. 檢查細則：每個階段的選擇數對於先前的每一條路徑都相同嗎？如果不是，先拆成幾種情況。
4. 把各階段的選擇數相乘，得到有順序的方法數。
5. 問問順序到底該不該算。如果不該，你稍後會把重複的排序除掉——那就是邁向組合的一躍。

第一個誠實的機率計算

讓我們把這個圈圈收回到機率上，因為計數只是手段。擲一顆公正的骰子兩次。根據乘法原理，樣本空間有 6 * 6 = 36 個同樣可能、有順序的結果。P(兩次都擲出 6) 是多少？恰好只有 1 個有利的有順序結果，所以 P = 1/36。P(兩次點數不同) 又是多少？用乘法直接數出有利結果：第一次有 6 種選擇，接著第二次有 5 種能避開與它相同的選擇，得到 6 * 5 = 30，所以 P = 30/36 = 5/6。

最後那一步——把有利結果當成一次全新的乘法來數，再除以樣本空間的大小——正是本課程中幾乎每一個古典機率問題的節奏。整個樣本空間是一個乘積；事件是另一個乘積（或幾個乘積之和）；機率就是兩者的比值。誠實的提醒：這只有在你所數的結果確實同樣可能時才成立。如果你把 36 個有順序的骰子配對塌縮成 21 個無序配對，這 21 個並不同樣可能（配對 {3,5} 可以用兩種方式發生，而 {4,4} 只能用一種），這時除以 21 會給出錯誤答案。計數方式必須與「同樣可能」一致，否則古典公式就會撒謊。