第十五章：基數規則 — 動畫敘事
第十五集 · Ch.15 基數規則
衣櫃裡有
幾種穿法？
幾種穿法？
3 件上衣、4 件褲子——共幾種搭配？
12 種。這是乘法原理。
排列組合不是死背公式，而是從幾個基本原理出發。
12 種。這是乘法原理。
排列組合不是死背公式，而是從幾個基本原理出發。
三個基本計數原理
×
乘法原理
獨立的選擇：方案數相乘
例：上衣 3 種 × 褲子 4 種 = 12 種
例：上衣 3 種 × 褲子 4 種 = 12 種
+
加法原理
互斥的選擇：方案數相加
例：坐公車或捷運，3+5=8 種方式
例：坐公車或捷運，3+5=8 種方式
−
容斥原理
有重疊時：|A∪B|=|A|+|B|-|A∩B|
例：既會 Python 又會 Java 的人
例：既會 Python 又會 Java 的人
排列 vs 組合
排列（順序有關）vs 組合（順序無關）
從 n 個中選 k 個：
排列 P(n,k)：
例：5 人賽跑，第 1~3 名有幾種可能？P(5,3)=60
組合 C(n,k)：
例：10 人選 3 人委員，有幾種選法？C(10,3)=120
排列 P(n,k)：
n! / (n-k)! 順序有關例：5 人賽跑，第 1~3 名有幾種可能？P(5,3)=60
組合 C(n,k)：
n! / (k!(n-k)!) 順序無關例：10 人選 3 人委員，有幾種選法？C(10,3)=120
互動：排列組合計算機
輸入 n 和 k 後按計算
鴿巢原理
如果 n+1 隻鴿子飛進 n 個巢，至少有一個巢裡有至少 2 隻鴿子。
例1
台北市有超過 260 萬人，一年 365 天——至少有兩個人同一天生日。
例2
任意 5 張撲克牌中，至少有兩張花色相同（花色只有 4 種）。
例3
任意 27 個英文單字中，至少有兩個首字母相同（英文只有 26 個字母）。
觀念測驗
一個密碼由 4 位數字（0-9）組成，可以重複，共有幾種密碼？
小結
1 / 7
本頁為動畫敘事版。看完後可前往 完整第十五章 進行互動練習。
教材來源：Mathematics for Computer Science (Lehman, Leighton, Meyer)