容斥原理

容斥原理

定义

对于有限集合 $A_1,A_2,\cdots,A_n$，有：

$$|\bigcup\limits_{i=1}^nA_i|=\sum\limits_{\varnothing \ne S \subseteq \{1,2,\cdots,n\}}(-1)^{|S|-1}|\bigcap\limits_{i \in S}A_i|$$

证明

证明 1：验证每个元素 $x$ 的出现次数是否正确

不妨设 $x$ 在 $A_{y_1},A_{y_2},\cdots,A_{y_k}$ 这 $k$ 个集合中出现过，可以算出它被计算的次数为：

$$\begin{aligned} C_k^1-C_k^2+C_k^3-\cdots-(-1)^kC_k^k &= -\sum\limits_{i=1}^k(-1)^iC_k^i \\ &= -(\sum\limits_{i=0}^k(-1)^iC_k^i)+C_k^0 \\ &= -(1-1)^k+1 \\ &= 1 \end{aligned}$$

推论

对于有限全集 $U$ 的子集 $A_1,A_2,\cdots,A_n$，有：

$$|\bigcap\limits_{i=1}^n\overline{A_i}|=\sum\limits_{S \subseteq \{1,2,\cdots,n\}}(-1)^{|S|}|\bigcap\limits_{i \in S}A_i|$$

其中 $\bigcap\limits_{i \in \{1,2,\cdots,n\}}A_i=U$。

作用

作用：将“或”型或“都不”型条件转化为“全都”型。

二项式反演

正向

对于数列 $f_0,f_1,\cdots,f_n$，若 $g_0,g_1,\cdots,g_n$ 满足：

$$g_k=\sum\limits_{i=0}^kC_k^if_i$$

那么反过来有

$$f_k=\sum\limits_{i=0}^k(-1)^{k-i}C_k^ig_i$$

作用：将“恰好 $k$ 个”化为“除了 $k$ 个都不”。

反向

对于数列 $f_0,f_1,\cdots,f_n$，若 $g_0,g_1,\cdots,g_n$ 满足：

$$g_k=\sum\limits_{i=k}^nC_i^kf_i$$

那么反过来有

$$f_k=\sum\limits_{i=k}^n(-1)^{i-k}C_i^kg_i$$

作用：将“恰好 $k$ 个”化为“选取 $k$ 个”。

Min-max 容斥

Min-max 容斥

把数字 $t$ 看成集合 $T=(-\infty,t]$，那么 $A \cup B$ 就是 $\max\{a,b\}$，$A \cap B$ 就是 $\min\{a,b\}$。

因此形式上将容斥原理转写可得：

对于实数集 $S$，

$$\max\limits_{i \in S}i=\sum\limits_{\varnothing \ne T \subseteq \{S\}}(-1)^{|T|-1}\min\limits_{i \in T}i$$

作用：将“最大”型化为“最小”型。

$k$-th Min-max 容斥

推导过程

假设 $T$ 的容斥系数为 $f(|T|)$，使得：

$$k\mathrm{-th}\max\limits_{i \in S}i=\sum\limits_{\varnothing \ne T \subseteq S}f(|T|)\min\limits_{i \in T}i$$

我们考虑一个从小到大数排名为 $x$ 的元素对答案的贡献：

$$[n-x+1=k]=\sum\limits_{i=0}^{n-x}C_{n-x}^if(i+1)$$

$$[x=k-1]=\sum\limits_{i=0}^xC_x^if(i+1)$$

根据二项式反演，我们有：

$$f(x+1)=\sum\limits_{i=0}^x(-1)^{x-i}C_x^i[i=k-1]=(-1)^{x-k+1}C_x^{k-1}$$

$$f(x)=(-1)^{x-k}C_{x-1}^{k-1}$$

结论

$$k\mathrm{-th}\max\limits_{i \in S}i=\sum\limits_{\varnothing \ne T \subseteq S}(-1)^{|T|-k}C_{|T|-1}^{k-1}\min\limits_{i \in T}i$$

例题：简单容斥原理

例题：容斥原理

例题：二项式反演

例题：min-max 容斥

参考资料

• 容斥原理（翻译） - vici - C++博客