容斥原理是组合数学中用于计数的一种基本方法，核心思想是：先不考虑重叠，把各种情况计数后，再减去重复计算的部分，加上被多减的部分，以此类推．

两个集合的情况

设有两个集合 $A$ 和 $B$ ，我们想求它们的并集大小 $|A \cup B|$ ．

直接加 $|A| + |B|$ 会把中间重叠部分 $|A \cap B|$ 算两次，所以需要减去一次：

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

三个集合的情况

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

规律：奇加偶减．即：

加 1 个集合的交集
减 2 个集合的交集
加 3 个集合的交集
……

一般形式#

设 $A_1, A_2, \dots, 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 A_{i_2} \cap \dots \cap A_{i_k}|

使用补集：求“不满足任何性质”的元素个数#

正难则反，如果全集 $U$ 中有一些“坏性质” $P_1, P_2, \dots, P_n$ ，设 $A_i$ 为满足性质 $P_i$ 的元素集合，则不满足任何性质的元素个数为：

|\overline{A_1} \cap \overline{A_2} \cap \dots \cap \overline{A_n}| = |U| - \left| \bigcup_{i=1}^n A_i \right|

对于各个性质地位相等#

如果已知“各个性质彼此地位相等”，即对于选择一些性质后的交集大小只与性质的条数 $k$ 有关，与这些性质具体是什么无关．我们就说这个问题是对称的．换句话说，交集的大小和性质的条数呈函数关系，不妨记交集的大小为 $a(k)$ ，故 $a(k)$ 在 $k$ 确定时为一定值，即

a(k)=|A_{i_1}\cap A_{i_2}\cap\cdots\cap A_{i_k}| \quad (\forall i_1<\dots<i_k)

则至少满足一个性质的元素个数：

\Bigl|\bigcup_{i=1}^n A_i\Bigr| = \sum_{k=1}^n (-1)^{k-1} \sum_{1\le i_1<\dots<i_k\le n} a(k)

内层对每个 $k$ 都要枚举 $\binom{n}{k}$ 个交集，总共 $2^n$ 项．

由于内层的每个性质条数为 $k$ 的交集都等于 $a(k)$ ，而性质条数为 $k$ 的子集共有 $\binom{n}{k}$ 个（一共 $n$ 条性质），因此

\sum_{1\le i_1<\dots<i_k\le n} |A_{i_1}\cap\cdots\cap A_{i_k}| = \binom{n}{k} a(k)

代入上式得

\boxed{\Bigl|\bigcup_{i=1}^n A_i\Bigr| = \sum_{k=1}^n (-1)^{k-1} \binom{n}{k} a(k)}

项数立刻由 $2^n$ 降为 $n$ （实际对 $k$ 从 $1$ 到 $n$ 求和）．这就是容斥原理的多项式形式．

依此，有补集形式：不满足任何性质的元素个数：

|\overline{A_1}\cap\cdots\cap\overline{A_n}| = |U| - \Bigl|\bigcup_{i=1}^n A_i\Bigr| = \sum_{k=0}^n (-1)^k \binom{n}{k} a(k)

其中规定 $a(0)=|U|$ （选取 $0$ 个性质即全集）．

经典例子：错位排列#

求 $1,2,\cdots ,n$ 的排列 $a$ 中满足 $a_i \neq i$ 的排列数．

正难则反，可以定义性质 $P_i$ ：第 $i$ 位是 $i$ ．显然对称．

$a(k)$ ：固定某 $k$ 个位置不动，其余 $n-k$ 个位置任意排列，故 $a(k)=(n-k)!$
$|U|=n!$

错位排列数：

D_n = \sum_{k=0}^n (-1)^k \binom{n}{k} (n-k)!

化简即为 $D_n = n! \sum_{k=0}^n \frac{(-1)^k}{k!}$ ，复杂度 $O(n)$ ．

二项式反演#

定义#

设我们有一个包含 $n$ 个性质的集合．

$f_k$ ：恰好满足 $k$ 个性质的元素个数．
$g_k$ ：钦定必须满足某 $k$ 个特定性质的元素个数，但不关心其他性质是否满足．更准确地说，我们选定 $k$ 个性质，强制要求元素满足这 $k$ 个性质，而其余 $n-k$ 个性质可以满足也可以不满足．从 $n$ 个性质中选择 $k$ 个来钦定有 $\binom{n}{k}$ 种选择方案，因此我们定义 $g_k$ 为所有 $\binom{n}{k}$ 种选法的总和，即

g_k = \sum_{1\le i_1<\dots<i_k\le n} \bigl|\{x : x \text{ 满足性质 } P_{i_1},\dots,P_{i_k}\}\bigr|

如果问题是对称的， $g_k$ 就等于 $\binom{n}{k} \times a(k)$ ．

关系推导#

任何一个恰好满足 $i$ 个性质的元素，在计算 $g_k$ 时，会被重复计数．具体来说，若一个元素 $x$ 恰好满足 $i$ 个性质（ $i \ge k$ ），那么从这 $i$ 个性质中选出 $k$ 个来“钦定”的方式有 $\binom{i}{k}$ 种．即 $x$ 会出现在 $\binom{i}{k}$ 个钦定子集之中，它对每一个子集的贡献都为 1，因此它对 $g_k$ 的贡献是 $\binom{i}{k}$ ．

于是有：

g_k = \sum_{i=k}^n \binom{i}{k} f_i

反演公式#

已知 $g_k$ ，想要求出 $f_k$ ，就需要反演上面的关系．二项式反演告诉我们：

\boxed{f_k = \sum_{i=k}^n (-1)^{i-k} \binom{i}{k} g_i}

常见应用#

错位排列：
- $f_0$ = 没有不动点的排列数（错排数 $D_n$ ）
- $a(k)$ = 固定 $k$ 个位置不动，其余任意排列的方法数 = $(n-k)!$
- 由 $g_k = \binom{n}{k}(n-k)!$ ，用反演求出 $f_0$ ．
组合计数：求恰好有 $k$ 个指定特征的方案数．

音乐

音乐

一般形式#

使用补集：求“不满足任何性质”的元素个数#

对于各个性质地位相等#

经典例子：错位排列#

二项式反演#

定义#

关系推导#

反演公式#

常见应用#

文章分享

音乐

安吉D4：容斥原理

一般形式#

使用补集：求“不满足任何性质”的元素个数#

对于各个性质地位相等#

经典例子：错位排列#

二项式反演#

定义#

关系推导#

反演公式#

常见应用#

文章分享