min-max容斥
min-max容斥
$$
max(S)=\sum_{T\subseteq S}(-1)^{|T|-1}min(T)
$$
$$
min(S)=\sum_{T\subseteq S}(-1)^{|T|-1}max(T)
$$
广义min-max容斥
$$
max(S, k)=\sum_{T\subseteq S}(-1)^{|T|-k}\binom{|T|-1}{k-1}min(T)
$$
证明
对于第$t$大的数，它的贡献为：
$$
\sum_{i=0}^t\binom{t-1}{i-1}(-1)^{i-t}\binom{i-1}{k-1}=\binom{t-1}{k-1}\sum_{i=0}^t\binom{t-k}{i-k}(-1)^{t-i}=[t==k]
$$