组合数学——Min-Max容斥

Min-Max 容斥，即 $$\max(S)=\sum_{T\in S,T\neq\emptyset}(-1)^{|T|-1}\min(T)$$

接下来证明上面那个式子是对的。定义 \(S\) 中共有 \(N\) 个元素，由大到小分别为 \(s_1,s_2,\dots,s_N\)，\(T_i\) 为所有 \(S\) 大小为 \(i\) 的子集。

所有元素都大于 \(s_i\) 且大小为 \(j\) 的子集有 \(\tbinom{i-1}{j}\) 个；则最小元素为 \(s_i\) 且大小为 \(j\) 的子集，即 \(s_i\) 并上任意一个所有元素都大于 \(s_i\) 且大小为 \(j-1\) 的子集，有 \(\tbinom{i-1}{j-1}\) 个。

那么，满足 \(\min(T)=s_i\) 的 \((-1)^{|T|-1}\) 之和为 \(\sum\limits_{j=1}^{i}(-1)^{j-1}\tbinom{i-1}{j-1}\)，根据二项式定理，这个东西等于 \((1+(-1))^{i-1}\) 即 \(0^{i-1}\)。除了 \(s_1\) 即最大值，其他元素的系数都为 \(0\)；而 \(0^0\) 无意义，根据组合数的定义， \(s_1\) 的系数为 \(1\)（这就相当于构造了一个“开关”，只有最大值才不会被抵消）。于是得证。

接下来从容斥原理的角度证明。

设 \(\max(S)=\sum_{T\in S,T\neq\emptyset}f_i\min(T)\)，则有 \(f_i\min(S)=\sum_{T\in S,T\neq\emptyset}(-1)^{|S|-|T|}\max(T)\)，\(f_i=\frac{\sum_{T\in S,T\neq\emptyset}(-1)^{|S|-|T|}\max(T)}{\min(S)}\)。

根据二项式定理，只有 \(\max(T)=\min(S)\) 的 \(T\) 不会被抵消，得到 \(f_i=(-1)^{|T|-1}\)。

同理，有更加普遍的式子 $$k\mathrm{th}\max(S)=\sum_{T\in S,T\neq\emptyset}(-1)^{|T|-k}\tbinom{|T|-1}{k-1}\min(T)$$

在组合计数中，Min-Max 容斥有时很有用。比如有 \(N\) 种球，每次会随机抽到 \(1\) 种，求每种球都至少抽到 \(A_i\) 个的期望次数，相当于求最晚满足要求的那种球满足要求的时间，这是没有上限的。但是如果使用 Min-Max 容斥，就可以转换为每个子集最早满足要求的那种球满足要求的时间，这个东西的上限是 \(\sum{(A_i-1)}+1\)，可以简单改写式子，然后合并类似状态进行 DP。