组合数学之容斥原理

容斥原理

1 容斥原理

对于$n$个有限集合$A_1,A_2,\cdots, A_n$,

$$|\cup_{i=1}^nA_i|=\sum_{I\subseteq\{1,\cdots, n\}}(-1)^{|I|-1}|\cap_{i\in I}A_i|$$

补集形式: 全集$U$

$$|\bar A_1\cap \bar A_2\cap\cdots\cap\bar A_n|=|U-\cup_{i=1}^nA_i|=|U|+\sum_{I\subseteq\{1,\cdots, n\}}(-1)^{|I|}|\cap_{i\in I}A_i|$$

对于$I\subseteq \{1,2,\cdots,n\}$, 表示

$$A_I=\cap_{i\in I}A_i$$

而$A_\emptyset = U$. 则$U$中不在任何$A_i$中的元素数量为

$$\sum_{I\subseteq \{1,\cdots, n\}}(-1)^{|I|}|A_I|$$

令$S_k=\sum_{|I|=k}|A_I|$, $S_0=|A_\emptyset|=|U|$. 则容斥原理可以写成

$$|\bar A_1\cap \bar A_2\cap\cdots\cap\bar A_n|=S_0-S_1+S_2+\cdots+(-1)^nS_n$$

1.1 满射

考虑问题: N和M中元素都不同, 满射$f:N\to M$的数量为

$$\sum_{k=1}^m(-1)^{m-k}\binom{m}{k}k^n$$

证明如下:

​ 令$U=\{f:[n]\to[m]\}$. 则$|U|=m^n$.

​ 对于任意$i\in [m]$, $A_i$表示满足没有$j\in [n]$映射到$i$的映射$f$ 的集合, 即$A_i=\{f:[n]\to [m]\setminus\{i\}\}$, 则$|A_i|=(m-1)^n$.

​ 对于任意$I\subseteq[m]$, $A_I=\cap_{i\in I}A_i$, 包含满足$f:[n]\to [m]\setminus I$的映射, $|A_I|=(m-|I|)^n$.

​ 映射$f$是满射当且仅当$f$不在任何$A_i$中. 根据容斥原理, 为

$$\sum_{I\subseteq [m]}(-1)^{|I|}|A_I|=\sum_{I\subseteq [m]}(-1)^{|I|}(m-|I|)^n=\sum_{j=0}^m(-1)^{j}\binom{m}{j}(m-j)^n$$

下面计算第二型斯特林数:

​ 对于满射$f:[n]\to[m]$, $(f^{-1}(0), f^{-1}(1),\cdots,f^{-1}(m-1))$是$[n]$的有序分割

​ 易证[m]到[n]的满射和[n]的有序m分割是一一对应的, 数量也相同.

​ 而[n]的有序m分割数量为$ m!\left\{\begin{matrix}n\\m\end{matrix}\right\}$, 所以可以得到第二型斯特林数的计算公式的计算公式

$$\left\{\begin{matrix}n\\m\end{matrix}\right\}=\frac{1}{m!}\sum_{k=1}^m(-1)^{m-k}\binom{m}{k}k^n$$

1.2 重排

问题: 一个集合到自己的无固定点(没有点$i$满足$\pi(i)=i$)的双射数量为

$$n!\sum_{k=0}^n\frac{(-1)^k}{k!}\approx\frac{n!}{e}$$

证明如下:

​ 令$U$为$\{1,2,\cdots, n\}$的所有排列, 则$|U|=n!$.

​ 令$A_i$表示有固定点$i$的排列数, 则$|A_i|=(n-1)!$.

​ 令$A_I=\cap_{i\in I}A_i$表示集合$I$中的点都是固定点的排列数, 则$|A_I|=(n-|I|)!$.

​ 重排则不在任何$A_i$中, 数量为

$$\sum_{I\subseteq \{1,2,\cdots, n\}}(-1)^{|I|}(n-|I|)!=\sum_{k=0}^n(-1)^k\binom{n}{k}(n-k)!=n!\sum_{k=0}^n\frac{(-1)^k}{k!}\approx \frac{n!}{e}$$

1.3 限定位置的排列

$B\subseteq\{1,\cdots,n\}\times\{1,\cdots,n\}$称为board, 可以看做一个棋盘, 上面有一些格子打了×.

对于$\{1,\cdots, n\}$的排列$\pi$, 定义图$G_\pi(V,E)$如下:

$$G_\pi=\{(i,\pi(i))|i\in\{1,2,\cdots, n\}\}$$

定义$N_0=|\{\pi|B \cap G_\pi=\emptyset\}|$即放$n$个non-attacking的棋子在棋盘上且都不在B中

$r_k=|\{S\in\binom{B}{k}|\forall(i_1,j_1),(i_2,j_2)\in S, i_1\ne i_2, j_1\ne j_2\}|$为在B中放$k$个non-attacking的棋子的种数

则

$$N_0=\sum_{k=0}^n(-1)^kr_k(n-k)!$$

证明太简单, 略

例1: 重排问题: $B=\{(1,1),(2,2),\cdots, (n,n)\}$

例2: Problème des ménages

• $n$ couple坐在圆桌周围, 男女轮流坐
• 没人坐在couple左右

解法:

• 首先让n个女性入座, 有$2(n!)$种, 此后编号为0到n-1

• $B=\{(0,0), (1,1), \cdots, (n-1.n-1), (0,1), (1,2), \cdots, (n-2, n-1), (n-1, 0)\}$

• $r_k$即在一圈$2n$个点中选择$k$个不相邻的点的数量

  • 如果是一行的, 可以用$m-k$个球, $k$个隔板的插板法计算, 为$\binom{m-k+1}{k}$
  • 如果是一圈的
    • 记结果为$f(m,k)$
    • $g(m,k)$: 在$m$个点中选$k$个不相邻的点涂红, 剩下的中选一个涂蓝, 下面算两次
    • 算法1: $g(m,k)=(m-k)f(m,k)$
    • 算法2: 选1个点涂蓝($m$种), 在这点剪短圆圈. 在一行$m-1$个中选择$m-1$个不相邻的涂红($\binom{m-k}{k}$种), 因此$g(m,k)=m\binom{m-k}{k}$
    • 因此$f(m,k)=\frac{m}{m-k}\binom{m-k}{k}$
  • 所以$r_k=\frac{2n}{2n-k}\binom{2n-k}{k}$, 从而可以算出$N_0$

• 总种数为

  $$2n!\sum_{k=0}^n(-1)^k\frac{2n}{2n-k}\binom{2n-k}{k}(n-k)!$$

2 逆

2.1 Posets

Poset: 集合$P$和二元关系$\le_P$满足自反性, 反对称性, 传递性.

$x$和$y$可比当且仅当$x\le y$或者$y\ge x$

2.2 莫比乌斯函数

有限Poset $P$, 考虑函数$\alpha: P\times P\to \mathbb R$ (可以看做一个矩阵)

Incidence algebra of poset:

$I(P)=\{\alpha: P\times P\to \mathbb R|\alpha(x,y)=0 ~ for ~ all ~ x\not\le_P y\}$.

将$\alpha$看做矩阵, 显然$I(P)$关于加法和数乘是闭的.

定义$I(P)$中矩阵乘法: 对于$\alpha, \beta\in I(P)$,

$$(\alpha\beta)(x,y)=\sum_{z\in P}\alpha(x,z)\beta(z,y)=\sum_{x\le z\le y}\alpha(x,z)\beta(z,y)$$

对于$\alpha\in I (P)$, 对于所有$z$不满足$x\le z\le y$, $\alpha(x,z)\beta(z,y)=0$

$I(P)$也是闭的

Zeta function and Möbius function:

特殊的$I(P)$:

$$\zeta(x,y)=\begin{cases} 1 & if ~ x\le_P y\\ 0 & otherwise \end{cases}$$

作为矩阵, $\zeta$是可逆的, 其逆为$\mu$, 称为莫比乌斯函数, 也是$I(P)$.

另一种等价定义如下:

$$\mu(x,y)=\begin{cases} -\sum_{x\le z<y}\mu(x,z) & ~ if ~ x < y\\ 1 & ~ if ~x = y\\ 0 & ~ if ~ x\not\le y \end{cases}$$

2.3 计算莫比乌斯函数

考虑$P=[n]$, $\le$为全序. 则

$$\mu(i,j)=\begin{cases} -1 & ~ if ~ i + 1 = j\\ 1 & ~ if ~ i = j\\ 0 & ~ otherwise \end{cases}$$

对于一般的poset, 有以下引理:

令$P$和$Q$为两个有限poset, $P\times Q$为笛卡尔积, 对于任意$(x,y),(x’,y’)\in P\times Q$, $(x,y)\le (x’,y’)$当且仅当$x\le x’$且$y\le y’$. 则$\mu_{P\times Q}((x,y), (x’,y’))=\mu_P(x,x’)\mu_Q(y,y’)$.

用递归定义证明.

Poset of subsets

$P=2^U$, 对于$S,T\subseteq U$, $S\le_P T$当且仅当$S\subseteq T$, 则

$$\mu(S,T)=\begin{cases} (-1)^{|T|-|S|} & ~ if ~ S\subseteq T\\ 0 & ~ otherwise. \end{cases}$$

证明:

• 把每个$S\subset U$用一个布尔序列$S\in \{0,1\}^U$表示, $S(x)=1$当且仅当$x\in S$.

• 对于每个元素$x\in U$, 定义poset$P_x=\{0,1\}$, $0\le 1$. 根据定义, $\mu_x(0,0)=\mu_x(1,1)=1$, $\mu_x(0,1)=-1$, $\mu_x(1,0)=0$.

• 根据引理

  $$\begin{align} \mu(S,T)&=\prod_{x\in U}\mu_x(S(x), T(x))\\ &=\prod_{x\in S, x\in T}1\prod_{x\not\in S, x\not\in T}1\prod_{x\in S, x\not\in T}0\prod_{x\not\in S, x\in T}(-1)\\ &=\begin{cases} (-1)^{|T|-|S|} & ~ if ~ S\subseteq T\\ 0 & ~ otherwise. \end{cases} \end{align}$$

Posets of divisors

考虑n的所有因数, $P=\{a>0| ~ a|n\}$, $a, b\in P, a\le_P b$当且仅当$a|b$, 则

$$\mu(S,T)=\begin{cases} (-1)^{r} & ~ if ~ \frac{b}{a}\text{ is the prduct of } r \text{ distinct primes} \\ 0 & ~ otherwise. \end{cases}$$

证明:

• $n=p_1^{n_1}\cdots p_k^{n_k}$. 表示n为tuple $(n_1,\cdots, n_k)$

• 对于任意$a\in P$, $a$可以表示为$(a_1,\cdots, a_k)$, $a_i\le n_i$

• $P_i=\{1,\cdots, n_i\}$, $\le$为全序关系

• $$\begin{align} \mu(S,T) &= \prod_{1\le i\le k}\mu(a_i,b_i)\\ &=\prod_{1\le i\le k, a_i=b_i}1\prod_{1\le i\le k, a_i+1=b_i}(-1)\prod_{1\le i\le k, b_i-a_i\not\in\{0,1\}}0\\ &=\begin{cases} (-1)^{r} & ~ if ~ \frac{b}{a}\text{ is the prduct of } r \text{ distinct primes} \\ 0 & ~ otherwise. \end{cases} \end{align}$$

2.4 莫比乌斯逆原理

Möbius inversion formula:

​ $P$ 为有限poset, $\mu$为莫比乌斯函数. 令$f,g:P\to \mathbb R$. 则

​ $\forall x\in P, g(x)=\sum_{y\le x}f(y)$当且仅当$\forall x\in P, f(x)=\sum_{y\le x}g(y)\mu(y,x)$.

证明:

• 把$f, g$看做向量
• $(f\zeta)(x)=\sum_{y\in P}f(y)\zeta(y,x)=\sum_{y\le x}f(y)$

• $(g\mu)(x)=\sum_{y\in P}g(y)\mu(y,x)=\sum_{y\le x}g(y)\mu(y,x)$

• $f\zeta =g$当且仅当$f=g\mu$, 因为$\mu\zeta=I$

对偶形式:

​ $P$ 为有限poset, $\mu$为莫比乌斯函数. 令$f,g:P\to \mathbb R$. 则

​ $\forall x\in P, g(x)=\sum_{y\ge x}f(y)$当且仅当$\forall x\in P, f(x)=\sum_{y\ge x}g(y)\mu(y,x)$.

证明类似

Principle of Inclusion-Exclusion证明:

$A_1,\cdots,A_n\subseteq U$. 对于任意$J\subseteq \{1,2,cdots, n\}$,

对于所有的$J$, 有$g(J)=\sum_{I\supseteq J}f(I)$.

使用Möbius inversion formula的对偶形式, 对于任何$J\subseteq \{1,\cdots, n\}$, 有

$f(J)=\sum_{I\supseteq J}\mu(J,I)g(I)=\sum_{I\supseteq J}\mu(J,I)|\cap_{i\in I}A_i|$, 其中莫比乌斯函数的poset为所有$\{1,\cdots,n\}$的子集, 序为$\subseteq$, 即对于$J\subseteq I$有$\mu(J,I)=(-1)^{|I|-|J|}$

因此$f(J)=\sum_{I\supseteq J}(-1)^{|I|-|J|}|\cap_{i\in I}A_i|$

$f(\emptyset)=|U\setminus \cup_i A_i|=\sum_{I\supseteq \{1,\cdots, n\}}(-1)^{|I|}|\cap_{i\in I}A_i|$

Möbius inversion formula for number theory:

$g(n)=\sum_{d|n}f(d)$当且仅当$f(n)=\sum_{d|n}g(d)\mu(\frac{n}{d})$ for all $n|N$

$\mu$是数论莫比乌斯函数:

$$\mu(n)=\begin{cases} 1 & \text{ if n is product of an even number of distinct primes}\\ -1 & \text{ if n is product of an odd number of distinct primes}\\ 0 & otherwise. \end{cases}$$

3 数论中的筛法

3.1 欧拉$\phi$函数

$\phi(n)$为$\{1,2,\cdots,n\}$中和$n$互素的数的数量

假设$n$有$r$ 个素因子, 记为$p_1,p_2,\cdots, p_r$, 则

$$\phi(n)=n\prod_{i=1}^r (1-\frac{1}{p_i})$$

证明:

$U=\{1,2,\cdots, n\}$.

$U$中被$p_{i1},p_{i_2},\cdots,p_{i_s}\in \{p_1,\cdots, p_r\}$整除的数的数量为$\frac{n}{p_{i1}p_{i_2}\cdots p_{i_s}}$

根据容斥原理

$$\phi(n)=n+\sum_{k=1}^r(-1)^k\sum \limits_{1\le i_1\le \cdots\le i_k\le n}\frac{n}{p_{i1}p_{i_2}\cdots p_{i_s}}=\cdots=n\prod_{i=1}^r (1-\frac{1}{p_i})$$