排列組合 & 機率（Permutation, Combination & Probability）

計數（counting）

若要在下圖中從 A 點走到 B 點，共有幾種走法呢？

我們可以用「樹狀圖（tree diagram）」來表示所有可能的情況：

由上述樹狀圖可知，從 A 點到 B 點共有 8 種走法，但若我們將此情境應用在真正的地圖，假設 A 點是臺北車站、B 點是臺北 101 大樓，那麼從北車到 101 共有幾種路徑呢？

因為兩個點之間的岔路非常多，如果還是使用樹狀圖來列出所有可能，將顯得不切實際，不僅耗時且易出錯，可改用「乘法原理」與「加法原理」計算。

一、乘法原理（rule of multiplication）

探討完成目的不同「步驟間」的多種可能性時採用，這些步驟必須全部都要完成，才有辦法達到最終目的。

以上圖來說，在上半段中，左方橢圓可選擇 1~3 號路徑任一、右方橢圓可選擇 4~5 號路徑任一，左右兩個橢圓必須各挑一路徑才能從 A 走到 B，因此使用乘法原理，可求得走上半段共有 3×2=6 種可能。

二、加法原理（rule of addition）

完成目的多種可能性間「不可能同時發生」時採用。

在上圖中，共分為上半段與下半段，若選擇往上方路徑走，則不可能走到下方路徑；若選擇往下方路徑走，則不可能走上方路徑。

在「乘法原理」段落中，我們已經求得走上半段共有 6 種可能，而若挑選下半段的路徑，則有 2 種可能可達 B 點，因此，上半段與下半段合計一共有 6+2=8 種可能性可從 A 點走到 B 點，與樹狀圖列出所有可能的結果相同。

排列（permutation）

將相異物件「按照順序」排在特定容器，包含下列兩種情況：

物件數與容器數相同

假設有 n 個物件，要排列於 n 個容器中，則有 n 個容器可供第一個物件選擇、(n-1) 個容器供第二個物件選擇、...、最後剩下 1 個容器供第 n 個物件選擇，一共有 n·(n-1)·(n-2)·…·1=n! 種排列方法。

物件數多於容器數

若有 n 個物件，要排列於 k 個容器中，其中 n>k，則只剩下 k 個容器可供第一個物件選擇、第二個物件有 (k-1) 個、...、第 k 個物件會把最後一個容器用掉，最終剩下 (n-k) 個物件沒有機會被排列，這些沒機會被排列的可能性會減少總排列方法數，因此會有 n!/(n-k)! 種排列方式。

舉例來說，如果有 0~9 共十數字要挑五個排列，一個數字只能出現一次，則第一個數字可能為 0~9 共十種可能、第二個數字剩下九種、...、第五個數字仍有六種可能，一共只有 10·9·8·7·6 種排列方式，後面的 5·4·3·2·1 不計算，因此放一個 5·4·3·2·1 在分母，如此便可將分子 10! 的「5·4·3·2·1」約分，得「10·9·8·7·6」這個結果。

由以上概念可整理出排列「P(n,k)」公式如下：

物件數與容器數相等、即 n=k 時，分母變為 1!，總排列數即為分子「n!」。

重複排列（permutation with repetition）

若排列中有物件重複出現，將使排列的可能性減少，因此會將物件重複數量的階乘放在分母，將分子的階乘約分，不同重複物件間減少排列的次數以「乘法原理」呈現。

舉例來說，如果要排列「1788536583」這十個數字，8 重複出現三次、5 重複出現兩次、3 也重複出現兩次，一共有 10!/3!2!2! 種排列方式。

組合（combination）

組合跟排列最大的差異在於「不考慮順序」，因此要將排列的公式再除以總容器可排列數「k!」，得「C(n,k)」公式如下：

假設要從 ABC 取兩個字母「排列」，共有下列 3!/1!=6 種情況：

1. AB
2. BA
3. AC
4. CA
5. BC
6. CB

但在「組合」中，1.、2. 視為相等，3.、4. 視為相等，5.、6. 也視為相等，因此可能性只剩下 (3!/1!)/2!=3 種。

重複組合（combination with repetition）

相較於「重複排列」只要將重複的可能數放在分母、將分子的階乘約分，重複組合要考慮的情況較為複雜。

如果今天有 3 個物件要分成 2 組，總共有幾種可能？

1. 第一組 0 個、第二組 3 個
2. 第一組 1 個、第二組 2 個
3. 第一組 2 個、第二組 1 個
4. 第一組 3 個、第二組 0 個

看起來非常簡單，但若改為「4 個物件分 3 組」呢？

1. 第一組 0 個、第二組 0 個、第三組 4 個
2. 第一組 0 個、第二組 1 個、第三組 3 個
3. 第一組 0 個、第二組 2 個、第三組 2 個
4. 第一組 0 個、第二組 3 個、第三組 1 個
5. 第一組 0 個、第二組 4 個、第三組 0 個
6. 第一組 4 個、第二組 0 個、第三組 0 個
7. 第一組 3 個、第二組 0 個、第三組 1 個
8. 第一組 2 個、第二組 0 個、第三組 2 個
9. 第一組 1 個、第二組 0 個、第三組 3 個
10. 第一組 1 個、第二組 3 個、第三組 0 個
11. 第一組 2 個、第二組 2 個、第三組 0 個
12. 第一組 3 個、第二組 1 個、第三組 0 個
13. 第一組 1 個、第二組 1 個、第三組 2 個
14. 第一組 2 個、第二組 1 個、第三組 1 個
15. 第一組 1 個、第二組 2 個、第三組 1 個

物件數及組別數分別各只加 1，要列出所有可能性已經顯得略具挑戰，須依序考量每個組別各有 1 個物件、2 個物件、3 個物件的情況，將其中一組別的物件數固定時，另外兩組也有不同的物件數搭配，列表時容易有未考量到或重複計算的狀況。

若有 500 個物件要分為 100 組呢？

首先要考量 100 次單一組別有 500 個物件、其餘 99 組皆沒有物件的情況；接著考量其中一組有 1 個物件，剩下 99 組分配 499 個物件的情況，而考慮這 99 組如何分配 499 個物件時，還要一一思考其中一組有 1 個物件、2 個物件、...、一路到 499 個物件的情況；考慮其中一組有 1 個物件時，剩下的 98 組也依然要再考慮其中一組有 1 個物件、2 個物件...，這樣的狀況夠複雜了吧！那如果是 10000 個物件分為 235 組呢？

好在，我們可以用「重複排列」的公式計算重複組合數！

如果有 n 個物件要分為 k 組，可以想成要將這些物件跟分組的邊界一起進行重複排列，邊界共有 (k-1) 個，因此重複組合數「H(n,k)」為[n+(k–1)]!/n!(k–1)!。

以上述「四個物件分三組」為例，分三組會形成兩個分組邊界，可以想成「四個物件與兩個邊界做重複排列」，因此共有 [4+(3–1)]!/4!(3–1)!=6!/4!2!=15 種組合方式，與土法煉鋼得到的結果相同。

以「重複排列」形式表示四個物件分三組的重複組合所有情形

二項式定理（binomial theorem）

國中時，我們有學過乘法公式如下：
(x+y)²=x²+2xy+y²
如果再乘一次 (x+y)，則可得：
(x+y)³=(x+y)(x²+2xy+y²)=x³+3x²y+3xy²+y³
如果再乘一次 (x+y)，可再得：
(x+y)⁴=(x+y)
(x³+3x²y+3xy²+y³)=x⁴+4x³y+6x²y²+4xy³+y⁴
如果再繼續往上乘，可發現下列三個規律：

1. x 從左而右逐漸由最高次方降冪至 0 次方
2. y 從左而右逐漸由 0 次方升冪至最高次方
3. 每項的係數從左而右逐漸變大、再逐漸變小，左右邊對稱

如果將多個不同次方展開式放在一起比較，可發現這些係數剛好是上一次方展開式兩相鄰項次係數的和，形成「帕斯卡三角形／楊輝三角形（Pascal’s triangle）」。

帕斯卡三角形示意動畫（取自維基百科）

用「組合」觀念理解二項式定理係數

由上個段落可知，要找到二項式展開後的係數，可以用帕斯卡三角形慢慢往下加求得，但如果今天要求 (x+y)¹⁰、(x+y)¹⁰⁰、甚至 (x+y)¹⁰⁰⁰ 當中每個項次的係數呢？

如果還是從帕斯卡三角形的最上層慢慢往下加，會經過非常多的運算步驟，這時我們可以改用「組合」的觀念理解，係數分別代表從多個括弧內取幾個 x、幾個 y 組合相乘。

舉例來說，我們可以來看 (x+y)³ 的情況：
(x+y)³=(x+y)(x+y)(x+y)=1x³+3x²y+3xy²+1y³

1. x³ 的係數是 1：三個括號中各取一個 x 相乘，共一種可能
2. x²y 的係數是 3：三個括號選兩個取 x、另一個取 y，共三種可能
3. xy² 的係數是 3：三個括號選一個取 y、另兩個取 y，共三種可能
4. y³ 的係數是 1：三個括號中各取一個 y 相乘，共一種可能

如果我們以「取幾個 y」來表示展開式中每個項次的係數，可以表示如下：

1. x³：三個括號中不取任何 y 相乘，共「C(3,0)」種可能
2. x²y：三個括號選一個取 y，共「C(3,1)」種可能
3. xy²：三個括號選兩個取 y，共「C(3,2)」種可能
4. y³：三個括號全部取 y 相乘，共「C(3,3)」種可能

如果改成「取幾個 x」來表示每個項次的係數呢？

1. y³：三個括號不取任何 x 相乘，共「C(3,0)」種可能
2. xy²：三個括號選一個取 x，共「C(3,1)」種可能
3. x²y：三個括號選兩個取 x，共「C(3,2)」種可能
4. x³：三個括號全部取 x 相乘，共「C(3,3)」種可能

由上述討論可知，(x+y)³ 的這個二項式展開後可以寫成如下形式：

上式係數算的是「取幾個 y」、下式係數算的是「取幾個 x」；如果共有 n 個 (x+y) 相乘，可以寫成其展開式如下：

若用 Σ 表示等號右方展開式、k 表示 x 或 y 的次方數，可得：

一般來說，我們會讓前項 x 以降冪排列、後項 y 以升冪排列的方式，也就是取後項為組合數計算基準呈現。

如果今天要求 (x+y)¹⁰⁰ 中第 x³⁵y⁶⁵ 係數，可以用「C(100,35)」或「C(100,65)」得 100!/35!65!≈1.1 x 10²⁷。

用「二項式定理」求子集數量

若一超集為 {1,2,3}，請問共可以產生幾種子集呢？

1. 無任何元素（空集合）：{}
2. 有一個元素：{1}、{2}、{3}
3. 有兩個元素：{1,2}、{2,3}、{1,3}
4. 有三個元素：{1,2,3}

若不取任何元素，則有 C(3,0)=1 種、取一個元素有 C(3,1)=3 種、取兩個元素有 C(3,2)=3 種、取三個元素有 C(3,3)=1 種，根據加法原理，共有 1+3+3+1=8 種。

而這剛好就是帕斯卡三角形第四層的數字加總！

但如果超集有 100 個元素，那要如何找到 C(100,0)+C(100,1)+…+C(100,100) 呢？

我們可以想想該二項式展開前的模樣「(x+y)¹⁰⁰」，如果要讓展開後的每個係數都變成 1，那就取 x=1、y=1 如下：

C(100,0)+C(100,1)+…+C(100,100) 的值，相當於 (1+1)¹⁰⁰=2¹⁰⁰≈1.3 x 10³⁰。

若推廣至在有 n 個元素的超集中求可能的子集數量，則會有 C(n,0)+C(n,1)+…+C(n,n)=2ⁿ 種。

機率（probability）

在相同條件下，重複進行的試驗稱為「隨機試驗（experiment / trial）」，所有隨機試驗形成的集合稱為「樣本空間（sample space）」，即試驗所產生所有可能的結果。

在「樣本空間」中取一個子集為「事件（event）」，將事件中元素的數量除以樣本空間元素的數量即為「機率」。

若一事件的集合為 A、樣本空間的集合為 S，則在 S 中發生 A 的機率「P(A)」可用下式表示：

舉例來說，如果丟兩次銅板，以「+」代表擲到正面、以「–」代表擲到反面，則樣本空間為 {(+,+),(+,–),(–,+),(–,–)}，兩次都得到正面的事件為 {(+,+)}，因此丟兩次銅板，兩次都得到正面的機率為：

一、條件機率（conditional probability）

指在符合某條件下發生特定事件的機率，若要探討一事件 A 在 B 事件條件下發生的機率，記為「P(A|B)」，A 與 B 之間的關係可用下式表示，其中 P(B)≠0：

二、貝式定理（Bayes’ theorem）

根據上個段落「條件機率」的定義，亦可得「B 在 A 事件條件下發生的機率」如下，其中 P(A)≠0：

將此式等號兩邊同乘以 P(A)，可得下式：

此為兩起事件間的貝式定理，推廣至多起事件的貝式定理可參考中華科技大學教學影片。

貝式定理應用範例

貝式定理關係式看起來頗為複雜，其實只要能夠理解「條件機率」的意義，要回答貝式定理相關問題非常容易。

現在我們來看一題範例：某必修課大一學生佔 70%、大二學生佔 15%、大三學生佔 10%、大四學生佔 5%，在某次期末考中，大一學生有 60% 及格、大二有 80% 及格、大三有 90% 及格、大四 100% 及格，試問若遇到考及格的學生，且此生大二的機率為何？

我們一樣可以用「樹狀圖」來理解：

「遇到考及格的學生，且此生大二」的意思就是「在考試及格的條件下，遇到及格且大二學生」的機率，也就是「P(及格∧大二)/P(及格)」，而分母的「P(及格)」就是「P(及格∧大一)+P(及格∧大二)+P(及格∧大三)+P(及格∧大四)」，因此可得遇到「考及格且大二」學生的機率如下：

如果題目改為「在該班遇到大二的學生，且此生及格」的機率呢？

分子「P(大二∧及格)」，與「P(及格∧大二)」相同，但分母就變成「P(大二)」，這時只要套用條件機率定義，得「P(及格∧大二)/P(大二)=(15%·80%)/15%=80%。

不過其實也不用算得這麼麻煩，因為題目都已經說「大二的有80%及格」了，已知遇到的是大二生，則該生及格的機率理所當然就是 80%。

小結

1. 乘法原理：計數方法之一，適用計算須全部完成的不同步驟間所有可能性。
2. 加法原理：計數方法之一，適用計算無法同時發生的不同方案間所有可能性。
3. 排列：將數個物件「按照順序」排在不同容器中，記為「P(n,k)」，公式為「n!/(n-k)!」。
4. 重複排列：排列的物件部分重複，計算時應將重複處以約分方式排除。
5. 組合：將數個物件「不計順序」取至不同容器中，記為「C(n,k)」，公式為「n!/(n-k)!k!」。
6. 重複組合：即將物件分組，可視為所有物件與分組邊界的重複排列，記為「H(n,k)」，公式為「[n+(k–1)]!/n!(k-1)!」。
7. 二項式定理：二項式 (x+y)ⁿ 展開時，可寫成 axᵇyⁿ⁻ᵇ 之和的恆等式，不同項次的係數 a 依帕斯卡三角形在第 (n+1) 層的數字排列，也可用「組合」方式理解、求出各項係數。
8. 機率：「事件」子集基數佔「樣本空間」超集基數的比例。
9. 條件機率：符合特定條件時某一事件的機率，如「A 條件中 B 事件發生的機率」記為「P(B|A)」，根據定義，即為「P(B∧A)/P(A)」。
10. 貝式定理：條件機率中的定理，描述在一已知條件下，特定事件發生的機率。