组合数学

组合数学

组合数学（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$-组合，记作 $(\genfrac{}{}{0ex}{}{n}{k})=\frac{n!}{k!(n-k)!}$。

例 4

从 10 人中选 3 人当小组：$(\genfrac{}{}{0ex}{}{10}{3})=120$。

2.3 先选再排

恒等式：$(\genfrac{}{}{0ex}{}{n}{k})k!=P(n,k)$。 解释：先从 $n$ 个元素中选出 $k$ 个（不计顺序），再把它们排成序列（计顺序）。

---

3. 二项式系数与二项式定理

二项式定理给出 $(x+y{)}^n$ 的展开： $(x+y{)}^n=\sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{k})x^{n-k}{y}^k$。

组合解释：展开时从 $n$ 个括号中选出 $k$ 个取 $y$，其余取 $x$；选择方式数就是 $(\genfrac{}{}{0ex}{}{n}{k})$。这种“用计数解释恒等式”的思路在组合数学里非常常见。

推论（帕斯卡恒等式）： $(\genfrac{}{}{0ex}{}{n}{k})=(\genfrac{}{}{0ex}{}{n-1}{k})+(\genfrac{}{}{0ex}{}{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$ 个盒子，则至少有一个盒子里不少于 $\lceil \frac{N}{n}\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)(n\ge 3)$， 且 $f(1)=1,f(2)=2$。

---

7. 生成函数（超入门）

生成函数思想：把数列 $a_0,a_1,a_2,\dots$ 打包为形式幂级数 $A(x)=\sum _{n\ge 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 元），可得方案数 $\lfloor \frac{n}{2}\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 人：$(\genfrac{}{}{0ex}{}{11}{3})$。
• 4：系数为 $(\genfrac{}{}{0ex}{}{6}{3})$。
• 5：$\lfloor \frac{200}{3}\rfloor +\lfloor \frac{200}{8}\rfloor -\lfloor \frac{200}{24}\rfloor$。
• 6：按模 9 的余数分 9 类。
• 7：按末位分类得到斐波那契型递推。

---

进一步阅读

• 课程与讲义：MIT OpenCourseWare 6.042J 相关材料。
• 生成函数：Wilf《generatingfunctionology》。
• 组合数学与算法分析基础：Knuth 等人的《Concrete Mathematics》（作者页面提供书目信息）。