容斥原理与Möbius函数

### 容斥原理 设$S_1,S_2,\cdots,S_n$为有限集合，$\left|S\right|$表示集合$S$的大小，则： $\ $ ### $\qquad \left|\bigcup\limits^n_{i=1}S_i\right|=\sum\limits^n_{i=1}\left|S_i\right|-\sum\limits_{1\le i<j\le n}\left|S_i\cap S_j\right|+\sum\limits_{1\le i<j<k\le n}\left|S_i\cap S_j\cap S_k\right|+\cdots+(-1)^{n+1}\left|S_1\cap\cdots\cap S_n\right|$ $\ $ ### 多重集的组合数(一般情况) 设$S=\{n_1\cdot a_1,n_2\cdot a_2,\cdots,n_k\cdot a_k\}$是由$n_1$个$a_1$，$n_2$个$a_2$，$\cdots$，$n_k$个$a_k$组成的多重集。设$n=\sum\limits^k_{i=1}n_i$，对于任意整数$r\le n$，从$S$中取出$r$个元素组成一个多重集$($不考虑顺序$)$，产生的不同多重集的数量为： $\ $ ### $\qquad C_{k+r-1}^{k-1}-\sum\limits^k_{i=1}C_{k+r-n_i-2}^{k-1}+\sum\limits_{1\le i<j\le k}C_{k+r-n_i-n_j-3}^{k-1}-\cdots+(-1)^kC_{k+r-\sum_{i=1}^kn_i-(k+1)}^{k-1}$ $\ $ ### $Möbius$函数 设正整数$N$按照算术基本定理分解质因数为$N=p_1^{c_1}p_2^{c_2}\cdots p_m^{c_m}$，定义函数： $\ $ ### $\qquad\mu(N)=\begin{cases}0&&&&\exists i\in[1,m],c_i>1\\1&&&&m\equiv0\ (mod\ 2),\forall i\in[1,m],c_i=1\\-1&&&&m\equiv1\ (mod\ 2),\forall i\in[1,m],c_i=1\end{cases}$ $\ $ 称$\mu(N)$为$Möbius$函数$($莫比乌斯函数$)$。 通俗地讲，当$N$包含相等的质因子时，$\mu(N)=0$。当$N$的所有质因子各不相等时，若$N$有偶数个质因子，$\mu(N)=1$，若$N$有奇数个质因子，$\mu(N)=-1$。