容斥原理与错排数初学习笔记
xhui2ao
·
·
算法·理论
简述
容斥原理是一种计数技巧，用来解决多个条件同时满足/不满足时的计数问题。
公式
两个元素的容斥
|A \cup B| = |A| + |B| - |A \cap B|
三个元素的容斥
|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|
容斥原理的一般公式
= \sum_{k=1}^{n} (-1)^{k+1} \sum_{1 \le i_1 < i_2 < \dots < i_k \le n} \left| A_{i_1} \cap A_{i_2} \cap \dots \cap A_{i_k} \right|
这里的 (-1)^{k+1}，当 k=1 时为正、当 k=2 时为负、当 k=3 时为正，等等。形成正负正负的交替，是容斥原理的核心。
公式 \sum_{1 \le i_1 < i_2 < \dots < i_k \le n} \left| A_{i_1} \cap A_{i_2} \cap \dots \cap A_{i_k} \right| 表示，取 k 个集合交的大小。
运用
若有 n 个性质，我们通常会求：
全集 U 中，不满足任何性质的元素有多少个。
设 A_i 为满足性质 i 的集合。
则不满足任何性质的集合就是 U / (A_1 \cup A_2 \cup A_3 \cap \dots \cap A_n)。
考虑如何计算 A_1 \cup A_2 \cup A_3 \cap \dots \cap A_n，可以发现这就是容斥原理公式的结果。
即，可以写成：
|U| - \sum_{k=1}^{n} (-1)^{k+1} \sum_{i_1 < \dots < i_k} |A_{i_1} \cap \dots \cap A_{i_k}|
等价于：
|U| - \left( \sum |A_i| - \sum |A_i \cap A_j| + \sum |A_i \cap A_j \cap A_k| - \dots \right)
可以发现这里的全集 U 其实就是所有元素的并，考虑把全集放进去，就是当 k=0 时，0 个集合的交，所有元素都属于 0 个集合的交，因此最终形式为：
\boxed{
\sum_{k=0}^{n} (-1)^k \sum_{1 \le i_1 < \dots < i_k \le n} |A_{i_1} \cap A_{i_2} \cap \dots \cap A_{i_k}|
}
其中 k=0 时，定义为 |U|。
其中公式里的 |A_{i_1} \cap A_{i_2} \cap \dots \cap A_{i_k}| 的意思，不是 至少 k 个性质成立，而是 指定这 k 个性质成立，其他性质是否成立不管，是可能有重复的！
错排问题I
有 n 封信，编号为 1,2,3,\cdots,n；装到 n 个信箱里，编号为 1,2,3,\cdots,n。每封信都不在自己编号的信封里，求方案数。
设全集 U 为 n!（所有排列）。
设 A_i 表示“第 i 封信装进了第 i 个信封”。
要求的是“不满足任何 A_i”的排列数。
推导
指定 k 封信装对，其他随便装，共有 C_n^k \cdot (n-k)! 种方案。
其中 C^k_n 表示指定 k 封信装对；(n-k)! 表示剩下 n-k 个信封随便装。
根据我们刚刚的最终形式公式，可得错排公式基本形式：
D_n = \sum_{k=0}^{n} (-1)^k C_n^k (n-k)!
进一步化简，C_n^k=\frac{n!}{k!(n-k)!}，因此原式等于：
D_n = \sum_{k=0}^{n} (-1)^k \frac{n!}{k!(n-k)!} (n-k)!
即最终化简为：
\boxed{D_n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!}}
这就是错排公式。
错排公式递推公式
添加于 2026 年 8 月 28 日。
首先是初始值，易得 D_0=1，D_1=0。因为 0 个元素的排列只有一个空排列，没有固定点，所以 D_0=1。
接下来推导 D_n(n\ge2) 的递推公式。
推导
首先考虑元素 1，它一定不能放在位置 1，假设放在了位置 k。k 的选择有 n-1 种。
接下来考虑元素 k 放在哪里。
情况 1
元素 k 放在位置 1。也就是说元素 1 与 k 互换了位置。此时剩下 n-2 个元素进行错排，即 D_{n-2}。
情况 2
元素 k 不放在位置 1。
接下来是一个很神的转化！
我们令位置 k 改名为位置 1、位置 1 改名为位置 k。
此时即为“元素 k 不放进位置 k”，而原先的元素 1 已经在位置 1 了，不再参与剩余排列。
此时，剩下 n-1 个元素，就是元素 2\sim n。
剩下 n-1 个位置，就是位置 2\sim n。
我们要把这 n-1 个元素放在剩下 n-1 个位置上，并满足错排限制。
即为 D_{n-1}。
最终公式
这里 k 有 n-1 种情况。
因此，错排数的递推公式为：
\boxed{D_n=(n-1)\times(D_{n-2}+D_{n-1})}
错排问题II
有 m 封信，编号为 1,2,3,\cdots,m；选择其中 n 封信，装到 n 个信箱里，编号为 1,2,3,\cdots,n。每封信都不在自己编号的信封里，求方案数。
设全集 U 为 A^n_m（所有排列）。
设 A_i 表示“第 i 封信装进了第 i 个信封”。
同理，要求的是“不满足任何 A_i”的排列数。
推导
指定 k 封信装对，其他随便装，共有 C_n^k \cdot A^{n-k}_{m-k} 种方案。
其中 C^k_n 表示指定 k 封信装对；A^{n-k}_{m-k} 表示其他的 m-k 封信选 n-k 封的排列数。
根据我们刚刚的最终形式公式，可得错排公式II：
\boxed{P(m,n) = \sum_{k=0}^{n} (-1)^k C_n^k \cdot A^{n-k}_{m-k}}