容斥原理
原理
引入 首先我们来看一个小学生的问题：
一个班中，学习日语的有 \(a\) 人，学习俄语的有 \(b\) 人，学习两科的有 \(c\) 人，求至少学了一门外语的人数有几人。
答案很明显，为 \(a+b-c\)。
容斥原理
\[|\bigcup _{i}A_i|=\sum_{i}\mid A_i\mid-\sum_{i<j}|A_i\cap A_j|+\sum_{i<j<k}|A_i\cap A_j\cap A_k|+\ldots+(-1)^{n-1}|\bigcap_{i}S_i| \]证明：
对于元素 \(a\)，假设 \(a\) 在上式子拆开后有 \(x\)，有且仅有 \(m\) 个 \(A_i\) 集合包含 \(a\)。
那么右式中的贡献为：
\[x={m\choose1}-{m\choose2}+\ldots+(-1)^{m}{m\choose m}=\sum_{i=1}^m((-1)^{i-1}{m\choose i}) \]我们可以构造一个式子：
\[(1-1)^m=0 \]对它使用二项式展开：
\[0=\sum_{i=0}^{m}((-1)^{i-1}{m\choose i}) \]于是：
\[\begin{matrix} x-{m\choose0}=0\\ x=1 \end{matrix} \]反之，亦然。证毕。
例题
例1.
若 \(\sum x_i=m,x_i\in \N\)，求 \(x_i\) 取值的方案数。
\((1)\) 对 \(x_i\) 无限制
则就是小球与挡板的问题。
共 \(\Large{m+n-1\choose m}\) 种方案。
\((2)\) 若 \(x_i\le b_i\)
例5. 欧拉函数
定义：\(\varphi(n)\) 表示 \(1\sim n\) 中与 \(n\) 互质的数的个数。这个函数叫做欧拉函数。求 \(\varphi(n)\) 的展开式。
例6. 广义容斥原理
容斥原理常用于集合的计数问题，而对于两个集合的函数 \(f(S),g(S)\)，
\[f(S)=\sum_{T\subseteq S}g(T) \Leftrightarrow g(S)=\sum_{T\subseteq S}(-1)^{|S|-|T|}f(T) \]证明
接下来我们简单证明一下。我们从等式的右边开始推：
\[\begin{aligned} &\sum_{T\subseteq S}(-1)^{|S|-|T|}f(T)\\ =&\sum_{T\subseteq S}(-1)^{|S|-|T|}\sum_{Q\subseteq T}g(Q)\\ =&\sum_{Q}g(Q)\sum_{Q\subseteq T\subseteq S}(-1)^{|S|-|T|}\\ \end{aligned} \]我们发现后半部分的求和与 \(Q\) 无关，因此把后半部分的 \(Q\) 剔除：
\[=\sum_{Q}g(Q)\sum_{T\subseteq (S\setminus Q)}(-1)^{|S\setminus Q|-|T|} \]记关于集合 \(P\) 的函数 \(F(P)=\sum_{T\subseteq P}(-1)^{|P|-|T|}\)，并化简这个函数：
\[\begin{aligned} F(P)&=\sum_{T\subseteq P}(-1)^{|P|-|T|}\\ &=\sum_{i=0}^{|P|}\dbinom{|P|}{i}(-1)^{|P|-i}=\sum_{i=0}^{|P|}\dbinom{|P|}{i}1^i(-1)^{|P|-i}\\ &=(1-1)^{|P|}=0^{|P|} \end{aligned} \]因此原来的式子的值是
\[\sum_{Q}g(Q)\sum_{T\subseteq (S\setminus Q)}(-1)^{|S\setminus Q|-|T|}=\sum_{Q}g(Q)F(S\setminus Q)=\sum_{Q}g(Q)\cdot 0^{|S\setminus Q|} \]分析发现，仅当 \(|S\setminus Q|=0\) 时有 \(0^0=1\)，这时 \(Q=S\)，对答案的贡献就是 \(g(S)\)，其他时侯 \(0^{|S\setminus Q|}=0\)，则对答案无贡献。于是得到
\[\sum_{Q}g(Q)\cdot 0^{|S\setminus Q|}=g(S) \]综上所述，得证。
推论
该形式还有这样一个推论。在全集 \(U\) 下，对于函数 \(f(S),g(S)\)，
\[f(S)=\sum_{T\supseteq S}g(T) \Leftrightarrow g(S)=\sum_{T\supseteq S}(-1)^{|S|-|T|}f(T) \]这个推论其实就是补集形式，证法类似。
标签：函数,sum,容斥,setminus,choose,原理,subseteq From： https://www.cnblogs.com/gutongxing/p/18220235