容斥原理
容斥原理
假设有全集$U$，以及全集的若干子集$A_1,A_2,\ldots, A_k$。
在实际应用中要统计多个子集的交集的大小是比较容易的，但是要统计多个子集的并集的大小则比较困难。对于这种情况，我们可以使用容斥原理将并运算简化为若干次交运算。
记$K$表示由$1,2,\ldots,k$组成的集合。容斥原理的公式如下：
\[|A_1\cup A_2 \cup \ldots \cup A_k|=-\sum_{I\subseteq K\land I\neq \emptyset} (-1)^{|I|}|\bigcap_{i\in I} A_i|\]以及
\[\begin{aligned} &|\overline{A_1\cup A_2 \cup \ldots \cup A_k}|\\ =&|S|-|A_1\cup A_2 \cup \ldots \cup A_k|\\ =&\sum_{I\subseteq K} (-1)^{|I|}|\bigcap_{i\in I} A_i| \end{aligned}\]广义容斥原理
给定全集$U$，以及全集的若干子集$A_1,A_2,\ldots, A_k$。
容斥原理求的是$U$中有多少元素被至少一个子集$A_i$所包含。而广义容斥求的是被正好$m$个子集所包含的元素数目。
记$\alpha(m)=\sum_{I\subseteq K\land |I|=m}|\bigcap_{i\in I}A_i|$。记$\beta(m)$表示被正好$m$个子集包含的元素数目，那么有：
\[\beta(m)=\sum_{i=m}^{|U|}(-1)^{i-m}{i\choose m}\alpha(i)\]证明如下：
考虑任意一个元素$e\in U$，设$e$在$t$个子集中出现。考虑三种情况：
- $t<m$，那么$t$在等式的左右贡献都是$0$。
- $t=m$，那么$t$在等式的左右贡献恰好都是$1$。
- $t>m$，那么$t$在等式的左右贡献都是$0$。
其中$t>m$的情况详细说明一下右边为什么是$0$。很显然$t$在$\alpha(i)$中贡献为${t\choose i}$。因此对右边的贡献为：
\[\begin{aligned} &\sum_{i=m}^{t}(-1)^{i-m}{i\choose m}{t\choose i}\\ =&\sum_{i=m}^{t}(-1)^{i-m}{t\choose m}{t-m\choose i-m}\\ =&{t\choose m}\sum_{i=0}^{t-m}(-1)^{i}{t-m\choose i}\\ =&{t\choose m}(1-1)^{t-m}\\ =&0 \end{aligned}\]提供一道题目：
min-max容斥
\[\max\{S\}=\sum_{T\subseteq S}(-1)^{|T|+1}\min\{T\}\\ \min\{S\}=\sum_{T\subseteq S}(-1)^{|T|+1}\max\{T\}\]证明：
考虑第一个公式。假设$x$为$S$中的第$i+1$大元素。那么$x$的展开项系数为：
\[\sum_{j=0}^i(-1)^j{i\choose j}=(1-1)^i=0^i\]因此只有当$i$为$0$时，系数为$1$，其它情况都为$0$。第二个公式同理可证。
提供一些题目：
k-th min-max容斥
定义$\min^k(S)$表示$S$中第$k$小的数，对应的记$\max^k(S)$表示$S$中第$k$大的数。
\[\max^k(S)=\sum_{T\subseteq S} (-1)^{|T|-k}{|T|-1\choose k-1}\min(T)\\ \min^k(S)=\sum_{T\subseteq S} (-1)^{|T|-k}{|T|-1\choose k-1}\max(T)\]证明如下：
仅证明$\max^k(S)$的展开公式，$\min^k(S)$的展开公式类似。
考虑第$x+1$大的数的系数：
\[\begin{aligned} &\sum_{i=0}^x (-1)^{i+1-k}{i\choose k-1}{x\choose i}\\ =&\sum_{i=k-1}^x (-1)^{i+1-k}{x\choose k-1}{x-(k-1)\choose i-(k-1)}\\ =&{x\choose k-1}\sum_{i=0}^{x-(k-1)} (-1)^{i}{x-(k-1)\choose i}\\ =&{x\choose k-1}(1-1)^{x-(k-1)}\\ =&[x=k-1] \end{aligned}\]因此只有第$k$大的数正好贡献一次。
提供一些题目：