第1章 計數原理、排列與組合
1.1 先說清楚一個結果長什麼樣
計數的第一步是定義一個結果。選兩本書時，{甲,乙} 和 {乙,甲} 是同一組；選正副班長時，(甲,乙) 和 (乙,甲) 是兩個結果。把結果分成互不重疊且涵蓋全部的類別，就可相加。若每個結果恰對應一條兩步選擇路徑，且每個第一步都有相同數目的第二步，就可相乘。第二步數量若因第一步而變，要把各枝的數量相加。
對非負整數 n，n! 是 1 到 n 的乘積。空排列只有一種，所以 0!=1。從 n 個不同物件取 k 個不重複並排序，0≤k≤n，方法數為 P(n,k)=n(n−1)⋯(n−k+1)，其中 k=0 時取空乘積 1。若不計順序，每組恰被算 k! 次，故 C(n,k)=P(n,k)/k!=n!/(k!(n−k)!)。若每格可重用同一批 n 個物件，正長度 k 的序列有 nᵏ 種；長度零只有空序列，無須對 0⁰ 作約定。
1.2 四個例題
例題1 正副有順序，兩人小組沒有
甲、乙、丙三人中選正副班長。正班長有 3 種，副班長只能從剩下 2 人選，故 3×2=6。若只是選兩人小組，每組有 2 種正副安排，故 6÷2=3。
例題2 允許重複與不允許重複
用 0、1、2、3 組成長度 3 的字串，允許開頭是 0。若能重複，每格皆 4 種，得 4³=64；若不能重複，依序只有 4、3、2 種，得 24。
例題3 分枝數不同就逐類計
甲櫃有 2 種筆，乙櫃有 3 種筆，兩櫃筆款互不重複。若只在一櫃選一支，按櫃別分成互斥的兩類，總數 2+3=5。若每櫃各選一支，結果由兩個櫃各自的選擇決定，總數 2×3=6。
例題4 固定一塊再排列
甲、乙、丙、丁、戊五人排一列，甲乙必相鄰。把甲乙視為一塊，與另三人共四個單位，有 4! 種順序；塊內有甲乙、乙甲兩種。每個合法隊伍能唯一拆回塊順序與塊內順序，所以共 2·4!=48。
1.3 練習
- B10-C01-Q01 用五個不同字母排兩格，不重複，幾種？
- B10-C01-Q02 從五人選兩位不分職務，幾種？
- B10-C01-Q03 從 1、2、3 中組成長度 4 的序列，允許重複，幾種？
- B10-C01-Q04 1、2、3、4 四個數字組成四位數且不重複，末位須偶數，幾種？
- B10-C01-Q05 從七人選三位，指定的甲一定入選，幾種？
- B10-C01-Q06 六件不同禮物送給甲、乙各一件，不重複，幾種？
- B10-C01-Q07 在八本書中選零本或八本，各有幾種？
- B10-C01-Q08 五個不同物件排一列，指定甲不可在第一格，幾種？
- B10-C01-Q09 若從五人選兩人可重複，但不計次序，能用 5²÷2 嗎？
- B10-C01-Q10 證明 C(n,k)=C(n,n−k)，條件 0≤k≤n。
1.4 完整解答
Q01
第一格 5 種，第二格剩 4 種。每個有序對只由一條選擇路徑生成，所以 5×4=20。
Q02
先算有序 5×4，再除以同一雙的 2 種順序，得 10。
Q03
每個位置有 3 種且不影響其他位置，故 3⁴=81。
Q04
末位先取 2 或 4，共 2 種。餘下 3 個位置放其餘 3 個數，各用一次，共 3!；得 2·3!=12。
Q05
甲已固定，還須從其餘六人選兩位，不分順序，所以 C(6,2)=15。
Q06
甲先選 6 種，乙剩 5 種，故 30。即使禮物不排序，收件人不同，所以不除以 2。
Q07
選零本只有空集合，選八本只有全體，所以 C(8,0)=C(8,8)=1。
Q08
第一格由另外 4 個選，剩四個物件任排，有 4!。總數 4·24=96；也等於 5!−4!。
Q09
不能：同一人取兩次只有一種順序，兩人不同才有兩種。分開算 5 種重複與 C(5,2)=10 種不同，共 15。
Q10
把每個 k 元子集對應到它的補集，補集恰有 n−k 個元素。取兩次補集回到原集合，故是一一且滿的對應，兩數相等。