Min-Max容斥公式

基本形式

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

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

$$$ E(\max(S))=\sum_{T\subseteq S} (-1)^{|T|+1} E(\min(T)) $$$

$$$ E(\min(S))=\sum_{T\subseteq S} (-1)^{|T|+1} E(\max(T)) $$$

$$$ kth\max(S)=\sum_{T\subseteq S} (-1)^{|T|-k} C_{|T|-1}^{k-1} \min(T) $$$

$$$ kth\min(S)=\sum_{T\subseteq S} (-1)^{|T|-k} C_{|T|-1}^{k-1} \max(T) $$$

$$$ E(kth\max(S))=\sum_{T\subseteq S} (-1)^{|T|-k} C_{|T|-1}^{k-1} E(\min(T)) $$$

$$$ E(kth\min(S))=\sum_{T\subseteq S} (-1)^{|T|-k} C_{|T|-1}^{k-1} E(\max(T)) $$$

推论

推论 1

$$$\operatorname{lcm}(a_1,a_2,…,a_n)=\prod_{S\subseteq A}\gcd(S)^{(-1)^{|S|+1}}$$$

证明：对每个质因子分别考虑，使用 min-max 容斥，易证。

推论 1-1

$$$\operatorname{lcm}(f_{a_1},f_{a_2},…,f_{a_n})=\prod_{S\subseteq A}f_{\gcd(S)}^{(-1)^{|S|+1}}$$$

其中 $f$ 为斐波那契数列。

证明：由 $\gcd(f_{a_1},f_{a_2},…,f_{a_n})=f_{\gcd(a_1,a_2,…,a_n)}$，易证。