容斥原理

看了 $\sout{\rm{lsqs}}$ 的博客才知道自己容斥原理学的不够深
容斥大概是计数中非常重要的了。以前都是式子直接用，核心的层次大抵是没有接触到，证明的过程也很少看。所以总结一些比较基础的知识和证明过程。以后式子用起来希望能更有底气。🙏

原始公式

容斥原理最基础的两个公式：

$\begin{aligned} \left|\bigcap_{i=1}^{n}A_i\right|&=\sum_{S\subseteqq [n]\cap S\not=\emptyset}(-1)^{|S|+1}\left|\bigcup_{i\in S}A_i\right|=\sum_{S\subseteqq [n]}(-1)^{|S|}\left|\bigcap_{i\in S}\overline{A_i}\right|\\ \left|\bigcup_{i=1}^{n}A_i\right|&=\sum_{S\subseteqq [n]\cap S\not=\emptyset}(-1)^{|S|+1}\left|\bigcap_{i\in S}A_i\right| \end{aligned}$

设 $U=\bigcup\limits_{i=1}^{n}A_i$。

考虑证明。对于集合 $S\in [n]$，定义 $S'=(\bigcap_{i\in S}A_i)\bigcap (\bigcap_{j\in \overline{S}}\overline{A_j})$ （画个 $\rm{venn}$ 图可以发现就是 $S$ 中的集合共有的，其他集合没有的元素集合）。
显然，任意两个不同的 $S$ ， $S'$ 一定没有交。并且 $\bigcup_{S\in [n]} S'=U$。$S'$ 之间没有交是很好的性质，我们把元素给分开了，接下来只需要对于每个 $S'$ 考虑。

考虑每个 $S'$ 中的元素计算得到的系数和，显然系数和只与 $S$ 有关。设 $\left|S\right|=n$ ，易知系数和为

$\sum_{i=1}^{n}\binom{n}{i}(-1)^{i+1}=\sum_{i=0}^{n}\binom{n}{i}(-1)^{i+1}+1=1$

所以就证明了「交」到「并」的容斥。

再考虑证明「并」到「补集交」的容斥。首先有如下恒等式（$S\subseteq U$）：

$|U|=\left|\bigcap_{i\in S} \overline{A_i} \right|+\left|\bigcup_{i\in S}A_i\right|$

我们把 $\left|\bigcap_{i\in S} \overline{A_i} \right|$ 换成 $|U|-\left|\bigcup_{i\in S}A_i\right|$ ，带入原式展开，就比较明显了。

凑容斥系数的方法及扩展容斥原理

假设恰好被 $x$ 个集合覆盖的元素（令这些元素的集合为 $S$）的贡献是 $f(x)$，大小为 $n$ 的集合的容斥系数为 $g(n)$，则有

$\begin{aligned} f(|S|)&=\sum_{T\subseteq S\cap T\not=\emptyset}g(|T|)\\ f(x)&=\sum_{i=1}^{x}\binom{x}{i}g(i) \end{aligned}$

令 $g(0)=0$，那么有

$\begin{aligned} f(x)&=\sum_{i=0}^{x}\binom{x}{i}g(i)\\ g(x)&=\sum_{i=0}^{x}(-1)^{x-i}\binom{x}{i}f(i) \end{aligned}$

一般题目中 $f(x)$ 都比较容易（比如集合交的大小的话 $f(x)=[x\not=0]$，集合并的大小的话 $f(x)=[x=n]$），那么我们可以进而求出 $g(x)$ 。

本质上是二项式反演，重点是会用。
有一个小 $\rm{trick}$ ：$f(x)$ 通常是布尔表达式，而 $g(x)$ 的形式中有组合数有 $-1$ 次幂，也就意味着最后把式子写出来后， $g(x)$ 很大可能是可以继续化简的，直至消去 $\sum$ 。比如集合并的推导。

小练习：求下式的值

$\left|\bigoplus_{i=1}^{n}A_i\right|$

显然 $f(x)=[2\nmid x]$， $g(x)$ 也明显可以通过二项式定理化简。所以最后的式子为

$\left|\bigoplus_{i=1}^{n}A_i\right|=\sum_{S\subseteq [n]\cap S\not =\emptyset}(-1)^{|S|-1}2^{|S|-1}\left|\bigcap_{i\in S}A_i\right|$

有了上述知识，就不难理解扩展容斥原理了。

扩展容斥原理，用于求被恰好 $k$ 个集合包含的元素个数。
此时 $f(x)=[x=k]$，那么 $g(x)=(-1)^{x-k}\binom{x}{k}$ 。
假设答案为 $\rm{Ans}$，则

$\text{Ans}=\sum_{S\subseteq [n]\cap S\not= \emptyset}(-1)^{|S|-k}\binom{|S|}{k}\left|\bigcap_{i\in S}A_i\right|$

Min-Max 容斥及扩展 Min-Max 容斥

$\rm Min-Max$ 容斥指明了集合的最小/大值与其子集的最大/小值的关系。对于求某个最值不方便的题目，转化成相对的那个最值，问题或许会简单很多。

$\rm Min-Max$ 容斥的公式如下：

$\max\{S\}=\sum_{T\subseteq S\cap T\not=\emptyset}(-1)^{|T|+1}\min\{T\}$

证明可以从每个数在右边的贡献系数入手。假设一个数在集合中有 $x$ 个数比它大。枚举包含这个数作为最小值的集合大小，可得这个数在右边的贡献系数为

$\sum_{i=0}^{x}(-1)^{i}\binom{x}{i}=[x=0]$

当 $x=0$ 时，该数恰好是集合中的最大值。与左边是吻合的。

扩展 $\rm Min-Max$ 容斥的内容不是最值，而是集合的第 $k$ 小/大值。我们可以从二项式反演去推容斥系数。
根据之前证明 $\rm Min-Max$ 容斥的过程，我们设 $g(x)$ 表示大小为 $x$ 的集合的容斥系数，则有：

$\sum_{i=0}^{x}g(i+1)\binom{x}{i}=[x=k-1]$

右边设为 $f(x)$ ，那么反演可以得到

$g(x)=\sum_{i=0}^{x-1}(-1)^{x-i-1}\binom{x-1}{i}f(i)=(-1)^{x-k}\binom{x-1}{k-1}$

所以扩展 $\rm Min-Max$ 的式子为

$\max\{S,k\}=\sum_{T\subseteq S\cap T\not=\emptyset}(-1)^{|T|-k}\binom{|T|-1}{k-1}\min\{T\}$