组合数学

组合数学

组合数学（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》（作者页面提供书目信息）。