Min-Max容斥学习笔记

先给出定义，\(Min(S)\)代表集合\(S\)的最小元素，\(Max(S)\)代表集合\(S\)的最大元素

再给出结论：\(Max(S)=\sum_{\phi \not= T \subseteq S} (-1)^{|T|-1} Min(T)\)

证明如下：我们先证明一个容斥系数\(f(x)\)，使得

\[Max(S)=\sum_{\phi \not= T\subseteq S} f(|T|) Min(T) \]

考虑第\(x+1\)大的数的贡献，\(F(x+1)=[x=0]\)

第\(x+1\)大的数作为最小值，那么其他的数一定是前\(x\)个比他大的数，即

\[F(x+1)=\sum_{i=0}^x {x \choose i} f(i+1) \]

二项式反演一下：

\[f(x+1)=\sum_{i=0}^x (-1)^{x-i} {x \choose i}[i=0]\\ f(x+1)=(-1)^x\\ f(x)=(-1)^{x-1} \]

同理的得：\(Min(S)=\sum_{\phi \not= T \subseteq S} (-1)^{|T|-1} Max(T)\)

很妙的是，它在期望意义下也成立，所以就有很多应用了