第十五章：基數規則
基數規則是解決「有多少種方法」這類問題的基石。本章介紹基本的計數技巧，包括乘法法則、排列組合以及鴿巢原理。
15.3 乘法法則
乘法法則：
若一個過程由 $k$ 個步驟組成，第 $i$ 個步驟有 $n_i$ 種選擇，則完成整個過程的方法數為：
$n_1 \times n_2 \times \dots \times n_k$
若一個過程由 $k$ 個步驟組成，第 $i$ 個步驟有 $n_i$ 種選擇，則完成整個過程的方法數為：
$n_1 \times n_2 \times \dots \times n_k$
🧪 衣櫃模擬器
假設你有不同數量的上衣和褲子。選擇一件上衣和一條褲子可以組成多少套搭配？
總搭配數 = 6
15.5 計算子集 (二項式係數)
從大小為 $n$ 的集合中選出大小為 $k$ 的子集，其方法數稱為二項式係數，記作 $\binom{n}{k}$。
$\binom{n}{k} = \frac{n!}{k!(n-k)!}$
🧪 帕斯卡三角形互動
帕斯卡三角形直觀地展示了二項式係數。點擊任意數字，查看其在三角形中的位置與值。
遞迴關係： $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$
5
15.8 鴿巢原理
這是一個簡單但強大的計數原理。
鴿巢原理：
若將 $n+1$ 或更多隻鴿子放入 $n$ 個巢中，則至少有一個巢中包含兩隻或更多鴿子。
若將 $n+1$ 或更多隻鴿子放入 $n$ 個巢中，則至少有一個巢中包含兩隻或更多鴿子。
🐦 動畫演示
我們有 4 個巢穴和 5 隻鴿子。點擊按鈕觀察分配結果。
教材來源：Mathematics for Computer Science (Lehman, Leighton, Meyer)