容斥原理 学习笔记

容斥原理是组合数学中一种非常重要的思想。

容斥通式：

设全集为 $U$ 共包含 $n$ 种不同的属性，第 $i$ 种属性为 $P_i$ ，拥有 $P_i$ 的元素组成的集合为 $S_i$ 。

集合的并集：

$$|\bigcup_{i = 1}^nS_i| = \sum_{m = 1}^n (-1)^{m - 1}\sum_{a_i < a_{i + 1}}|\bigcap_{i = 1}^mS_{a_i}|$$

集合的交集：

$$|\bigcap_{i = 1}^nS_i| = |U| - |\bigcup_{i = 1}^n \overline{S_i}| \\ = |U| - \sum_{m = 1}^n(-1)^{m - 1}\sum_{a_i < a_{i + 1}}|\bigcap_{i = 1}^n \overline{S_{a_{i}}}|$$

其中 $\overline{S_i}$ 表示 $S_i$ 的补集。

容斥的性质

简单来说，容斥一共有几个要素

1. 物品 $q(S)$ 表示至少满足属性集合 $S$ 的物品个数。
2. 贡献函数 $g(k)$ 表示对于一个有 $k$ 个属性的物品，对答案的贡献。
3. 容斥系数 $f(x)$ 表示大小为 $x$ 的集合对答案的贡献。

一般来讲，一个有 $n$ 个属性的物品对答案的贡献为：

$$g(n) = \sum_{i = 1}^n \binom{n}{i}f(i)$$

大多数情况下，$g(n) = 1$ ，即一个物品对答案的贡献一般为 1 。这个时候容斥系数 $f(i) = (-1)^{i + 1}$ 。

总的答案为

$$Ans = \sum_{S\subseteq U} = q(S)f(|S|)$$

求容斥系数

已知$g(n) = \sum_{i = 0}^n \dbinom{n}{i} f(i),$求 $f(x)$ 。

首先可以递推求，假设已知 $f(1)$ 到 $f(n)$ ，求 $f(n + 1)$ 。整个过程下来时间复杂度 $O(n^2)$ 。

$$g(n + 1=) = \sum_{i = 0}^{n + 1}{n + 1\choose i} f(i) \\ f(n + 1) = g(n + 1) - \sum_{i = 0}^n {n + 1\choose i} f(i)$$

---

也可以用多项式去求，时间复杂度 $O(nlogn)$ 。

$$g(n) = \sum_{i = 0}^n \frac{n!}{(n-i)!}\frac{f(i)}{i!} = n!\sum_{i = 0}^n\frac{1}{(n - i)!}\frac{f(i)}{i!} \\ \frac{g(n)}{n!} = \sum_{i = 0}^n\frac{1}{(n - i)!}\frac{f(i)}{i!}$$

接下来生成函数，

$\frac{g(n)}{n!}$ 的生成函数 $G(x) = \sum_{i = 0}^{\infty}x^i\frac{g(i)}{i!},$

$\frac{1}{(n - i)!}$ 即 $\frac{1}{i!}$ （因为 $\sum_{i = 1}^n \dfrac{1}{(n - i)!}$ 所以可以直接替换）的生成函数$H(x) = \sum_{i = 0}^{\infty} x^i\frac{1}{i!} = e^x$,

$\frac{f(i)}{i!}$ 的生成函数 $F(x) = \sum_{i = 0}^{\infty}x^i\frac{f(i)}{i!}$ 。

则 $G(x) = H(x)F(x)$ 。

所以 $F(x) = e^{-x}G(x)$ 。套个多项式求逆就行。

容斥原理常见问题模型

不定方程非负整数解计数

简单版：给定 $k$ 个未知数 $x_1, x_2, \cdots, x_k$ 和一个方程 $x_1 + x_2 + \cdots + x_k = r$ ，求方程非负整数解的个数。

对于这个问题可以直接转换成向 $k$ 个盒子里放 $r$ 个球，可空的方案数。然后在每个盒子里先补上一个球，变成 $k$ 个盒子里放 $r + k$ 个球，不可空的方案数。

然后插板法，在 $r + k - 1$ 个球之间的空隙里插入 $k - 1$ 个板。总的答案 $\dbinom{r + k - 1}{k - 1}$ 。

升级版：给定 $k$ 个未知数 $x_1, x_2, \cdots, x_k$ ，$k$ 个约束条件分别为 $x_k \le n_k$ 和一个方程 $x_1 + x_2 + \cdots + x_k = r$ ，求方程非负整数解的个数。

这是一个求交集的问题，容斥是用来求并集的，所以可以转化为先求所有不满足条件的情况，再用上面算出来的总情况做差。

对于每个未知数 $x_i$ ，保证 $x_i$ 不满足要求的办法就是用 $x_i' = x_i + n_i + 1$ 替换 $x_i$ 。所以对于任意一个集合 $S$ 表示集合中的元素全部不符合条件，则

$$q(S) = \dbinom{r + k - 1 - \sum_{i \in s}(n_i + 1)}{k - 1}$$

容斥系数 $f(|S|)$ 很简单，就是 $(-1)^{|S|}$ 。

所以答案为

$$ans = \sum_{S \subseteq U}f(|S|)q(S) = \sum_{s \subseteq U}(-1)^{|S|}{r + k - 1 - \sum_{i \in s}(n_i + 1) \choose k - 1}$$

注意这里虽然没有用全集相减，但由于 $\varnothing \subseteq U$ 即所有数都至少有零个不合法也算在内，所以计算出来的答案是正确的。

错排计数

求一个长度为 $n$ 的排列中，满足 $a_i \ne i$ 的方案数

可以通过枚举哪些位置冲突，即 $a_i = i$ 来进行容斥。对于每个大小为 $|S|$ 集合 $S_i$ 表示至少有 $|S|$ 个位置满足 $a_i = i$ ，即 $\forall i \in S,\ a_i = i$。对于每个集合 $S_i$ 可以发现统计答案时只关心它的大小，而不关心它的具体情况，所以可以设 $i = |S|$ ，将所有满足这个条件的集合合并。满足 $S$ 的方案数共有 $q(S) = \dbinom{n}{|S|}$ 个，这些位置选定后剩下位置的方案数为 $(n - |S|)!$ ，容斥系数为 $(-1)^{|S|}$ ,答案则为

$$F(n) = \sum_{S \subseteq U}(-1)^{|S|}(n - |S|) ! \\ = \sum_{i = 0}^n (-1)^i(n - i)! \dbinom{n}{i} = (-1)^n + n\cdot F(n - 1)$$

求一个长度为 $n$ 的排列中，满足恰好 $m$ 个 $a_i \ne i$ 的方案数

$$F(n, m) = \sum_{i = 0}^m (-1)^i(n - i)!\dbinom{m}{i} \\$$

To Be Continued

本文作者：CloudySky
写作时间： 2022-01-21
最后更新时间： 2022-01-21
遵循协议： BY-NC-SA