min_max 容斥

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

证明:

设计一个容斥系数 $f(x)$ ,使得

$$\max(S)=\sum\limits_{T\subseteq S}f(|T|)\min(T)$$

求 $x+1$ 大的数的贡献,显然有

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

二项式反演得:

$$\begin{aligned}f(x+1)&=\sum_{i=0}^x[x-i=0]\dbinom{x}{i}f(i+1)\\&=\sum_{i=0}^x\sum_{j=0}^{x-i}(-1)^j\dbinom{x-i}{j}\dbinom{x}{i}f(i+1)\\&=\sum\limits_{j=0}^x(-1)^j\dbinom{x}{j}\sum_{i=0}^{x-j}\dbinom{x-j}{i}f(i+1)\\&=\sum_{j=0}^x(-1)^{x-j}\dbinom{x}{j}[j=0]\\&=(-1)^x\end{aligned}$$

于是可得

$$f(|T|)=(-1)^{|T|-1}$$