sss

<更新提示>

<第一次更新>

<正文>

容斥原理

容斥原理指的是一种排重，补漏的计算思想，形式化的来说，我们有如下公式：

[left | igcup_{i=1}^nS_i ight |=sum_{i}|S_i|-sum_{i,j}|S_icap S_j|+...+(-1)^{n-1}left | igcap_{i=1}^nS_i ight | ]

设(P={1,2,...,n})，则容斥原理还有如下表现形式：

[left | igcup_{i=1}^nS_i ight |=sum_{Tsubseteq P}(-1)^{|T|-1}left | igcap_{iin T} S_i ight | ]

容斥原理在很多计数题中都得到了很好的运用，最经典的就是欧拉函数计算式的推导。

定理：设(n=p_1^{a_1} imes p_2^{a_2} imes ... imes p_k^{a_k})，则有(phi(n)=n imes sum_{i=1}^k(1-frac{1}{p_i}))。

证明：
(phi(n))的定义为(1-n)的整数中与(n)互质的数的个数，于是所有(p_1,p_2,...,p_k)的倍数都不符合要求。设(S_i)代表(1-n)内(p_i)的倍数所组成的集合，那么可以得到：

[phi(n)=n-left | igcup _{i=1}^kS_i ight | ]

利用容斥原理，我们可以得到：

[phi(n)=n-sum_{Tsubseteq P}(-1)^{|T|-1}left | igcap_{iin T} S_i ight | ]

不难得到

[left | igcap_{iin T} S_i ight |=frac{n}{prod_{iin T}p_i} ]

于是

[phi(n)=n-sum_{Tsubseteq P}(-1)^{|T|-1}frac{n}{prod_{iin T}p_i}\phi(n)=n imes (1-sum_{Tsubseteq P}(-1)^{|T|-1}frac{1}{prod_{iin T}p_i}) ]

而由多项式乘法可以得到：$$1-sum_{Tsubseteq P}(-1)^{|T|-1}frac{1}{prod_{iin T}p_i}=sum_{i=1}^k(1-frac{1}{p_i})$$

所以证得结论：$$phi(n)=n imes sum_{i=1}^k(1-frac{1}{p_i})$$

类似与容斥原理，我们有一种作用于最大最小值函数的容斥计算方法，称为(min-max)容斥。

仍设(P={1,2,...,n})，则有

[max_{i=1}^n{x_i}=sum_{Tsubseteq P}(-1)^{|T|-1}min_{iin T}{x_i} ]

普通的(min-max)容斥还有另一种很常见的形式，即(min-max)具有对称性：

[min_{i=1}^n{x_i}=sum_{Tsubseteq P}(-1)^{|T|-1}max_{iin T}{x_i} ]

具体证明可以参考这篇博客。

(min-max)容斥最经典的运用就是结合数学期望的线性性，在求解(min-max)期望的题目中化繁为简，灵活转换。

形象的说，在期望中，两个不相关随机变量(A,B)不满足：$$E(max(A,B))=max(E(A),E(B)) E(min(A,B))=min(E(A),E(B))$$

但是我们可以利用(min-max)容斥在最大最小值间建立联系：

[E(max_{i=1}^n{x_i})=sum_{Tsubseteq P}(-1)^{|T|-1}E(min_{iin T}{x_i})\ \ E(min_{i=1}^n{x_i})=sum_{Tsubseteq P}(-1)^{|T|-1}E(max_{iin T}{x_i}) ]

<后记>