容斥原理与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$。


发表于 2018-05-16 12:37:57 in 笔记