組合數學

組合數學

組合數學（Combinatorics）研究有限（或可數）對象的計數、構造與結構。它常見於算法、機率論、圖論與計算機科學的證明與分析中：很多看似「算數量」的題，其實是在搭建集合之間的一一對應（雙射）或把集合拆成互不重疊的幾塊。

本書以計數原理為主線：從加法/乘法原理出發，進入排列與組合、二項式定理、容斥原理、鴿巢原理，並進一步接觸遞推與（入門級）生成函數方法。生成函數部分可作為後續更深入學習的入口（例如整數劃分、遞推求解等）。

---

0. 預備：集合與計數語言

• 記 $|A|$ 為集合 $A$ 的元素個數（基數）。
• 若兩個集合間存在雙射，則它們元素個數相同。
• 常見策略：把難數的集合 $X$ 與好數的集合 $Y$ 建立雙射；或把 $X$ 分成互不相交的若干塊，再分別計數。

---

1. 基本計數原理

1.1 分類加法原理

若 $A_{1},A_{2},\dots ,A_{k}$ 兩兩互不相交，則 $|A_{1}\cup A_{2}\cup \cdots \cup A_{k}|=|A_{1}|+|A_{2}|+\cdots +|A_{k}|$。

直覺：把選擇分成互不重疊的幾類，總數等於各類之和。

例 1

一個班要選「數學課代表或英語課代表」各 1 名。若數學候選 5 人、英語候選 4 人，且兩職位不能同一人（互斥），則方法數為 $5+4=9$。

1.2 分步乘法原理

若一個過程分為 $k$ 步，每一步的選擇數分別為 $n_{1},n_{2},\dots ,n_{k}$（且每一步對前面選擇的依賴已被正確計入），則總方法數為 $n_{1}\cdot n_{2}\cdot \cdots \cdot n_{k}$。

例 2

用 0–9 組成 4 位數（首位不能為 0）。首位 9 種，其餘 3 位各 10 種，總數為 $9\cdot 10^{3}=9000$。

1.3 常見陷阱：互斥、分步與重複計數

• 互斥：適合加法原理。
• 分步：適合乘法原理。
• 若既不互斥又不是清晰分步，往往需要重構問題（例如用容斥原理糾正重複計數）。

---

2. 排列與組合

2.1 排列

從 $n$ 個不同元素中取出 $k$ 個並排成序列，稱為 $k$-排列，常記作 $P(n,k)=n(n-1)\cdots (n-k+1)={\frac {n!}{(n-k)!}}$。

例 3

6 位不同同學排成一列：$6!=720$ 種。

2.2 組合

從 $n$ 個不同元素中取出 $k$ 個不計順序，稱為 $k$-組合，記作 ${\binom {n}{k}}={\frac {n!}{k!(n-k)!}}$。

例 4

從 10 人中選 3 人當小組：${\binom {10}{3}}=120$。

2.3 先選再排

恆等式：${\binom {n}{k}}k!=P(n,k)$。 解釋：先從 $n$ 個元素中選出 $k$ 個（不計順序），再把它們排成序列（計順序）。

---

3. 二項式係數與二項式定理

二項式定理給出 $(x+y)^{n}$ 的展開： $(x+y)^{n}=\sum _{k=0}^{n}{\binom {n}{k}}x^{n-k}y^{k}$。

組合解釋：展開時從 $n$ 個括號中選出 $k$ 個取 $y$，其餘取 $x$；選擇方式數就是 ${\binom {n}{k}}$。這種「用計數解釋恆等式」的思路在組合數學裡非常常見。

推論（帕斯卡恆等式）： ${\binom {n}{k}}={\binom {n-1}{k}}+{\binom {n-1}{k-1}}$。

---

4. 容斥原理

當集合有重疊時，「直接相加會重複計數」。容斥原理提供系統糾正方式。

4.1 兩個集合

$|A\cup B|=|A|+|B|-|A\cap B|$。

4.2 三個集合

$|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|$。

例 5（整除計數）

求 1–100 中能被 2 或 5 整除的數的個數。 設 $A$ 為被 2 整除，$|A|=50$；$B$ 為被 5 整除，$|B|=20$； $A\cap B$ 為被 10 整除，$|A\cap B|=10$。因此 $|A\cup B|=50+20-10=60$。

---

5. 鴿巢原理

5.1 基本形式

若把 $n+1$ 個物品放入 $n$ 個盒子，則至少有一個盒子裡不少於 2 個物品。

5.2 強化形式

若把 $N$ 個物品放入 $n$ 個盒子，則至少有一個盒子裡不少於 $\left\lceil {\frac {N}{n}}\right\rceil$ 個物品。

例 6

任意 13 個人里，必有至少 2 人同月生日（把月份當 12 個盒子）。

例 7

任取 6 個整數，必存在兩個數差為 5 的倍數。按除以 5 的餘數分 5 類即可。

---

6. 遞推與計數（入門）

很多計數問題的關鍵是：把大問題拆成規模更小的同類問題。

6.1 鋪磚問題（斐波那契型遞推）

問題：用 1×2 的多米諾骨牌鋪滿 2×n 的長方形，有多少種鋪法？設 $f(n)$ 為鋪法數。

• 若第一列豎放一塊，則剩下 2×(n-1)：貢獻 $f(n-1)$。
• 若第一列用兩塊橫放跨兩列，則剩下 2×(n-2)：貢獻 $f(n-2)$。

因此 $f(n)=f(n-1)+f(n-2)\quad (n\geq 3)$， 且 $f(1)=1,\ f(2)=2$。

---

7. 生成函數（超入門）

生成函數思想：把數列 $a_{0},a_{1},a_{2},\dots$ 打包為形式冪級數 $A(x)=\sum _{n\geq 0}a_{n}x^{n}$。 一個關鍵性質是：乘法對應係數卷積。若 $A(x)B(x)=C(x)$，則 $c_{n}=\sum _{k=0}^{n}a_{k}b_{n-k}$。

作為補充的權威數學參考庫，NIST 的 DLMF 也提供了多處與「生成函數」相關的條目（尤其在特殊函數章節中）。

例 8（零錢問題）

用 1 元、2 元硬幣湊出 $n$ 元（不計順序）。考察 ${\frac {1}{(1-x)(1-x^{2})}}=(1+x+x^{2}+\cdots )(1+x^{2}+x^{4}+\cdots )$ 中 $x^{n}$ 的係數。選擇 $x^{2k}$（用 $k$ 枚 2 元）再配 $x^{n-2k}$（用 1 元），可得方案數 $\left\lfloor {\frac {n}{2}}\right\rfloor +1$。

---

8. 練習（含少量提示）

1. （乘法原理）從 A 城到 B 城有 3 條路，從 B 城到 C 城有 4 條路。問從 A 到 C 經 B 有多少種走法？
2. （排列）8 本不同的書排成一排，其中兩本特定的書必須相鄰，有多少種排法？
3. （組合）從 12 人中選 4 人組成委員會，其中必須包含某位同學，方法數是多少？
4. （二項式）求 $(1+x)^{6}$ 中 $x^{3}$ 的係數，並給出組合解釋。
5. （容斥）1–200 中，能被 3 或 8 整除的整數有多少個？
6. （鴿巢）任取 10 個整數，證明其中必有兩個數之差是 9 的倍數。
7. （遞推）設 $g(n)$ 為長度為 $n$ 的 0-1 串且不出現相鄰兩個 1 的個數，寫出遞推並給初值。

提示

• 1：$3\cdot 4$。
• 2：把相鄰兩本當作一個「塊」，與其餘 6 本共 7 個對象排列，再乘以塊內 2 種次序。
• 3：固定那位同學，再從剩餘 11 人中選 3 人：${\binom {11}{3}}$。
• 4：係數為 ${\binom {6}{3}}$。
• 5：$\left\lfloor {\frac {200}{3}}\right\rfloor +\left\lfloor {\frac {200}{8}}\right\rfloor -\left\lfloor {\frac {200}{24}}\right\rfloor$。
• 6：按模 9 的餘數分 9 類。
• 7：按末位分類得到斐波那契型遞推。

---

進一步閱讀

• 課程與講義：MIT OpenCourseWare 6.042J 相關材料。
• 生成函數：Wilf《generatingfunctionology》。
• 組合數學與算法分析基礎：Knuth 等人的《Concrete Mathematics》（作者頁面提供書目信息）。