组合数学

组合数学研究“有限对象有多少种构造方式”。关键能力是把复杂问题拆成可计数的结构。

1. 两大计数原理

1.1 加法原理

若任务由互斥的 $k$ 类方法完成，第 $i$ 类有 $m_i$ 种，则总数为

$$\sum_{i=1}^k m_i.$$

1.2 乘法原理

若任务分 $k$ 步完成，第 $i$ 步有 $m_i$ 种，则总数为

$$\prod_{i=1}^k m_i.$$

例题 1（加乘混合）

班级从 4 名男生与 3 名女生中选 1 名班长与 1 名学习委员（职位不同，可同组别）。有多少种选法？

解： 先选班长 $7$ 种，再选学习委员 $6$ 种，共 $7\times6=42$ 种。

2. 排列与组合

2.1 公式

• 排列：

$$P(n,k)=\frac{n!}{(n-k)!}$$

• 组合：

$$C(n,k)=\binom{n}{k}=\frac{n!}{k!(n-k)!}$$

例题 2（有条件排列）

5 本不同书排成一行，甲乙两本必须相邻，有多少种？

解： 将甲乙视为一个整体，与其余 3 本共 4 个对象排列：$4!$；甲乙内部还可交换 $2!$。总数 $4!\times2=48$。

例题 3（分步组合）

从 8 人中选 3 人参加算法赛、再选 2 人参加数学赛（不可重复），共有多少种？

解：

$$\binom83\binom52=56\times10=560.$$

3. 二项式定理与组合恒等式

3.1 二项式定理

$$(x+y)^n=\sum_{k=0}^n\binom{n}{k}x^{n-k}y^k.$$

3.2 常见恒等式

$$\sum_{k=0}^n\binom{n}{k}=2^n, \quad \sum_{k=0}^n k\binom{n}{k}=n2^{n-1}.$$

例题 4（系数法）

求 $(1+x)^6$ 中 $x^3$ 的系数。

解： 系数为 $\binom63=20$。

4. 容斥原理与错排问题

4.1 一般形式的容斥原理

设 $S$ 是有限集，$P_1, P_2, \dots, P_n$ 是 $n$ 个性质。令 $A_i$ 是 $S$ 中具有性质 $P_i$ 的元素子集。则不具备任何性质的元素个数为：

$$|\overline{A_1} \cap \overline{A_2} \cap \dots \cap \overline{A_n}| = |S| - \sum |A_i| + \sum |A_i \cap A_j| - \dots + (-1)^n |A_1 \cap \dots \cap A_n|.$$

也可以表示为具有至少一个性质的元素个数：

$$\left| \bigcup_{i=1}^n A_i \right| = \sum_{k=1}^n (-1)^{k-1} \sum_{1 \le i_1 < \dots < i_k \le n} |A_{i_1} \cap \dots \cap A_{i_k}|.$$

4.2 应用：错排问题 (Derangements)

定义：$n$ 个元素的排列 $\sigma$，若对所有 $i$，都有 $\sigma(i) \neq i$，则称其为错排。其个数记为 $D_n$。

公式推导：利用容斥原理，令 $A_i$ 为满足 $\sigma(i)=i$ 的排列集合。 $|S| = n!$，$|A_i| = (n-1)!$，$|A_i \cap A_j| = (n-2)!$。

$$D_n = n! \left( 1 - \frac{1}{1!} + \frac{1}{2!} - \dots + (-1)^n \frac{1}{n!} \right) = n! \sum_{k=0}^n \frac{(-1)^k}{k!}.$$

递推关系： $D_n = (n-1)(D_{n-1} + D_{n-2}), \quad D_1 = 0, D_2 = 1.$

例题 6（一般容斥应用）

求 $1$ 到 $100$ 中不能被 $2, 3, 5$ 整除的整数个数。

解：$|S|=100$。令 $A_1, A_2, A_3$ 分别为能被 $2, 3, 5$ 整除的数。 $|A_1| = \lfloor 100/2 \rfloor = 50, |A_2| = 33, |A_3| = 20$。 $|A_1 \cap A_2| = \lfloor 100/6 \rfloor = 16, |A_1 \cap A_3| = 10, |A_2 \cap A_3| = 6$。 $|A_1 \cap A_2 \cap A_3| = \lfloor 100/30 \rfloor = 3$。 结果 $= 100 - (50+33+20) + (16+10+6) - 3 = 100 - 103 + 32 - 3 = 26$。

5. 进阶计数：多重集的排列与组合

5.1 多重集的全排列

设 $n = n_1 + n_2 + \dots + n_k$，其中第 $i$ 类元素有 $n_i$ 个。其全排列数为：

$$\frac{n!}{n_1! n_2! \dots n_k!}.$$

5.2 多重集的组合（隔板法）

从 $n$ 种元素中取 $k$ 个（每种无限量），方案数为：

$$\binom{n+k-1}{k}.$$

6. 本章练习

练习 1：基础计数

从 $1$ 到 $1000$ 的整数中，有多少个数的各位数字之和等于 $9$？

Check Solution

设三位数为 $x_1x_2x_3$，则 $x_1+x_2+x_3=9$，其中 $0 \le x_i \le 9$。 利用隔板法，相当于将 9 个小球放入 3 个盒子（可空）：$\binom{9+3-1}{9} = \binom{11}{2} = 55$。 注：$1000$ 的各位数字之和为 $1$，不计入。

练习 2：错排应用

5 个人去参加聚会，结束后随机拿走一顶帽子。求没有一个人拿到自己帽子的概率。

Check Solution

总情况 $5! = 120$。 错排数 $D_5 = 5!(1 - 1 + 1/2 - 1/6 + 1/24 - 1/120) = 60 - 20 + 5 - 1 = 44$。 概率 $P = 44/120 = 11/30 \approx 0.367$。

练习 3：深度容斥

求 $x_1+x_2+x_3=15$ 的整数解个数，限制条件 $0 \le x_i \le 6$。

Check Solution

总解数（无上限限制）：$|S| = \binom{15+3-1}{15} = \binom{17}{2} = 136$。 令 $A_i$ 为 $x_i \ge 7$ 的解集。 $|A_1|: y_1+x_2+x_3=8 \implies \binom{8+3-1}{8} = \binom{10}{2} = 45$。 $|A_1 \cap A_2|: y_1+y_2+x_3=1 \implies \binom{1+3-1}{1} = \binom{3}{1} = 3$。 $|A_1 \cap A_2 \cap A_3| = 0$ (因为 $7+7+7=21>15$)。 由容斥原理：$136 - 3 \times 45 + 3 \times 3 - 0 = 136 - 135 + 9 = 10$。

练习 4：Lucas 定理（思考题）

简述计算 $\binom{n}{k} \pmod p$ 的方法（$p$ 为小质数）。

Check Solution

使用 Lucas 定理： $\binom{n}{k} \equiv \prod_{i=0}^k \binom{n_i}{k_i} \pmod p$，其中 $n_i, k_i$ 是 $n, k$ 的 $p$ 进制表示的各位系数。

7. 学习闭环

• 前置：集合论
• 并行：图论基础
• 配套题单：离散数学练习库