容斥原理
2026-05-10
Max-min 容斥
最大值形式
maxS=T⊆ST=∅∑(−1)∣T∣+1minT
证明
考虑使用排列和组合恒等式证明。
将 S 中的元素记为 b1≤b2≤⋯≤bn,则 maxS=bn,所以我们需要考察右侧每个 bi 的总系数是多少。
对于每个满足 minT=bj 的集合 T,显然它只能由 bj∼bn 构成,设从 bj+1∼bn 中选出 t 个元素,则 ∣T∣=t+1 即 (−1)∣T∣+1=(−1)t。
于是 bj 总系数为:
t=0∑m(tm)(−1)t=(1−1)m
其中 m=n−j,即从 bj∼bn 中选。
- 当 j<n 时,m=n−j>0,和为 0。
- 当 j=n 时,m=0,此时指数 m 不满足二项式定理,即 1×(−1)0=1。
因此,总和刚好为 bn=maxS,证毕。
K 大值形式
额外的,Max-min 容斥还有第 k 大形式,即:
kthmax(S)=T⊆S∣T∣≥k∑(−1)∣T∣−k(k−1∣T∣−1)minT
证明
设原集合 S 中元素为 b1≤b2≤⋯≤bn,第 k 大即为 bn−k+1,取元素 bj,考虑 minT=bj 的系数。
包含 bj 且要求从后 m=n−j 个元素中取出 T,设后方取 t 个元素,则 ∣T∣=t+1,要求 ∣T∣≥k,则其总系数和为:
t=k−1∑m(tm)(−1)t+1−k(k−1t)
令 r=k−1,上式化为:
(−1)1−kt=r∑m(−1)t(tm)(rt)
利用组合恒等式,上式右侧 ∑t=rm(−1)t(tm)(rt)=(−1)r(rm)0m−r。
- 若 m>r,系数为 0。
- 若 m=r,系数为 (−1)1−k⋅(−1)k−1=1。
综上,总和刚好为 bn−k+1=kthmax(S)。
期望形式
由于期望的线性性,如果 S 中全为随机变量 Xi,可以得到:
E(imaxXi)=∅=T⊆{1,⋯,n}∑(−1)∣T∣+1E(i∈TminXi)
同理,也可以得到 K 大值的期望形式。
