学习笔记：容斥原理和广义 Mobius 反演

参考文献

容斥原理和广义 Mobius 反演（一）容斥原理和集合上的莫比乌斯反演

容斥原理和广义 Mobius 反演（二）莫比乌斯反演的推广

容斥原理和广义 Mobius 反演（三）广义莫比乌斯反演

前置知识

狄利克雷卷积：Dirichlet 卷积和 Bell 级数

引入

本文介绍容斥原理和广义的莫比乌斯反演，注意和拓扑学中的莫比乌斯变换和圆反演进行区分（虽然在更抽象的角度上它们也有联系，不过不在本文的讨论范围内）。阅读完本文，您将清楚莫比乌斯反演和容斥的关系，莫比乌斯反演和数论中的莫比乌斯反演是否一样，并学会一点基础的使用。

莫比乌斯变换能用来解决一些容斥相关的计数问题。本文只涉及理论，没有相关的题目，没有配图（懒得画），偏理论。

容斥原理

定理（容斥）：$S$ 为一个集合，$P_i,i=1,2,\cdots,m$ 是某个性质，$A_i=\{x\in S:P_i(x)\}$ 为满足第 $i$ 个性质的元素构成的集合，则不满足全部性质的元素的个数为：

$$|\overline{A_1}\cap\overline{A_2}\cap\cdots\cap\overline{A_m}|=|S|-\sum|A_i|+\sum|A_i\cap A_j|-\sum|A_i\cap A_j\cap A_k|+\cdots+\sum(-1)^m|A_1\cap A_2\cap A_3\cap\cdots\cap A_m|$$

我们用韦恩图很好理解这一点。

证明：我们只需计算每个元素在右边式子中被计算的次数。

当 $x\notin \overline{A_1}\cap\overline{A_2}\cap\cdots\cap\overline{A_m}$ 时，假设 $x$ 满足其中的 $k$ 个性质，则 $x$ 被计算的次数为

$$\binom{k}{0}-\binom{k}{1}+\binom{k}{2}-\cdots+(-1)^k\binom{k}{k}=0$$

当 $x\in \overline{A_1}\cap\overline{A_2}\cap\cdots\cap\overline{A_m}$ 时，$x$ 只在 $S$ 中被计数一次。证毕

推论：

$$|A_1\cup A_2\cup\cdots\cup A_m|=\sum|A_i|-\sum|A_i\cap A_j|+\sum|A_i\cap A_j\cap A_k|-\cdots+(-1)^{m+1}|A_1\cap A_2\cap A_3\cap\cdots\cap A_m|$$

证明：

$$\begin{align} |A_1\cup A_2\cup\cdots\cup A_m| &=|S|-|\overline{A_1\cup A_2\cup\cdots\cup A_m}|\\ &=|S|-|\overline{A_1}\cap\overline{A_2}\cap\cdots\cap\overline{A_m}| \end{align}$$

将上述

$$|\overline{A_1}\cap\overline{A_2}\cap\cdots\cap\overline{A_m}|=|S|-\sum|A_i|+\sum|A_i\cap A_j|-\sum|A_i\cap A_j\cap A_k|+\cdots+\sum(-1)^m|A_1\cap A_2\cap A_3\cap\cdots\cap A_m|$$

代入即得。

例一：

计算 $x_1+x_2+x_3+x_4=18$ 的整数解，其中

$$1\leq x_1\leq 5,-2\leq x_2\leq 4,0\leq x_3\leq 5,3\leq x_4\leq 9$$

令 $y_1=x_1-1,y_2=x_2+2,y_3=x_3,y_4=x_4-3$，使限制条件变为非负。

令 $S$ 为满足方程的非负解（即不考虑约束），$A_i$ 表示违反第 $i$ 个约束的非负解，然后用容斥原理计算即可。

例二：

计算 $1\sim n$ 的排列中，$i$ 不在第 $i$ 个位置的排列数 $D_n$

解：令 $S$ 为全排列数目，$A_i$ 为 $i$ 在第 $i$ 个位置的排列。则任意 $k$ 个 $A_i$ 的交的元素个数为

$$|A_{i_1}\cap A_{i_2}\cap\cdots\cap A_{i_k}|=(n-k)!$$

由容斥原理

$$\begin{align} D_n=|A_1\cap A_2\cap\cdots\cap A_n| &=|S|-\sum|A_i|+\cdots+(-1)^m|A_1\cap A_2\cap A_3\cap\cdots\cap A_m|\\ &=n!-(n-1)!+(n-2)!+\cdots+(-1)^n\\ &=n!(1-\frac{1}{1!}+\frac{1}{2!}+\cdots+(-1)^n\frac{1}{n!}) \end{align}$$

由上面结果可得到

$$e^{-1}=\lim_{n\rightarrow\infty}\frac{D_n}{n!}\\ D_n=(n-1)(D_{n-1}+D_{n-1})\\ D_n=nD_{n-1}+(-1)^{n-2}\\ n!=\binom{n}{0}D_n+\binom{n}{1}D_{n-1}+\cdots+\binom{n}{n}D_0$$

莫比乌斯反演

集合上的莫比乌斯反演是容斥原理的泛化 ，即容斥原理可以看成它的特例。

令 $X_n={1,2,3,\cdots,n}$，$F:\mathcal{X}_n\rightarrow\R$ 是一个 $X_n$ 的幂集到实数的映射，定义 $G:\mathcal{P}(X_n)\rightarrow\R$ 为

$$G(K)=\sum_{L\subseteq K}F(L),\forall K\subseteq X_n$$

则其逆运算为

$$F(K)=\sum_{L\subseteq K}(-1)^{|K|-|L|}G(L),\forall K\subseteq X_n$$

正变换称为 $Z$ 变换，这个逆变换的过程为莫比乌斯反演。直接对所有子集计算这个式子，需要 $O(3^n)$，利用高维前缀和的技巧可以降为 $O(2^n)$。

证明：

$$\begin{align} \sum_{L\subseteq K}(-1)^{|K|-|L|}G(L) &=\sum_{L\subseteq K}(-1)^{|K|-|L|}\sum_{T\subseteq L}F(T)\\ &=\sum_{T\subseteq K}F(T)\sum_{T\subseteq L\subseteq K}(-1)^{|K|-|L|}\\ &=\sum_{T\subseteq K}F(T)\sum_{L\subseteq K-T}(-1)^{|L|}\\ &=F(K) \end{align}$$

最后一步是因为当 $K-T$ 非空时，偶数子集和奇数子集数目相同。$X_n$ 可以替换成任意有限集。

容斥原理可以看作它的特例，设 $A_1,A_2,\cdots,A_n$ 为某个有限集 $S$ 的子集 $A_{n+1}=S$，对于某个集合 $K\subseteq X_n$ 定义 $F(K)$ 为集合 $\cap_{k\notin K}A_k-\cup_{k/in K}A_k$ 中元素的个数，$s\in S$ 被 $F(L)$ 计数，当且仅当

$$\forall i\in L,s\notin A_i\\ \forall i\notin L,s\in A_i$$

再定义

$$G(K)=\sum_{L\in K}F(L)$$

则，由于

$$a\in\bigcap_{i\notin K}A_i\Longleftrightarrow\exists L\subseteq K,a\in\bigcap_{i\notin L}A_i-\bigcup_{i\in L}A_i$$

因此 $G(K)$ 为

$$G(K)=\left|\bigcap_{i\notin K}A_i\right|$$

由莫比乌斯反演可知

$$F(K)=\sum_{L\subseteq K}(-1)^{|K|-|L|}G(L)$$

特别的，代入 $K=X_n$ 得

$$F(X_n)=\sum_{L\subseteq X_n}(-1)^{n-|L|}G(L)$$

由定义知 $F(X_n)=|\bigcap_{i\notin X_n}A_i-\bigcup_{i\in X-n}A_i|=|S-\bigcup_{i\in X_n}A_i|=|\bigcap_{i\in X_n}\overline{A_i}|$，因此

$$\begin{align} |A_1\cup A_2\cup\cdots\cup A_n| &=\sum_{L\subseteq X_n}(-1)^{n-|L|}\left|\bigcap_{i\notin L}A_i\right|\\ &=\sum_{J\subseteq X_n}(-1)^{|J|}\left|\bigcap_{i\in J}A_i\right| \end{align}$$

上式子中当 $J=\varnothing$ 时，右边等于 $|S|$，因此我们得到了容斥原理。

广义迪利克雷卷积和广义莫比乌斯函数

可以看成 Dirichlet 卷积和 Mobius 函数在偏序集上的推广。

可以将上面集合中莫比乌斯反演的 $\subseteq$ 关系，替换成偏序关系。任给一个有限偏序集 $(X,\leq)$，令

$$\mathcal{F}(X)=\{函数f:X\times X\rightarrow\C|f(x,y)=0,\forall x\not\leq y\}$$

对任意 $f,g\in\mathcal{F}(X)$，定义卷积

$$(f*g)(x,y)= \begin{cases} \displaystyle\sum_{x\leq z\leq y}f(x,z)g(z,y),&\text{if }x\leq y\\ 0,&\text{otherwise} \end{cases}$$

下面，这个 $\mathcal{F}(X)$ 在二元运算 $*$ 下为一个幺半群，即它满足结合律，以及存在单位元。过程和 Dirichlet 卷积差不多，所以具体推导从略。

有限是要保证求和式有定义，我们可以放宽一点限制，只要求任意 $x\leq y$ 满足 $x\leq z\leq y$ 的 $z$ 的个数有限即可，在本文中称其为线段有限（我不知道叫啥，集合论里面貌似叫这个线段）。比如自然数集就不是有限的，但是它是线段有限的。

容易验证卷积具有结合律 $f*(g*h)=(f*g)*h,\forall f,g,h\in\mathcal{F}(x)$

定义 Kronecker delta 函数

$$\delta(x,y)= \begin{cases} \displaystyle\frac{1}{f(y,y)},&\text{if }x=y\\ \displaystyle-\frac{1}{f(y,y)}\sum_{x\leq z\leq y}g(x,z)f(z,y),&\text{if }x<y\\ 0,&\text{otherwise} \end{cases}$$

可以得到

$$(g*f)(x,y)=\sum_{x\leq z\leq y}g(x,z)f(x,y)=\delta(x,y)$$

因此它是半群 $(\mathcal{F}(x),*)$ 的左逆元，而半群的左逆元就是逆元，即 $g$ 是 $f$ 在卷积下的逆。

如果我们用整除关系定义为偏序关系，令 $x=\Z^+$，对于一个数论函数 $f$，我们定义

$$\overline{f}(x,y)= \begin{cases} f(y/x),&\text{if }x\leq y\\ 0,&\text{otherwise} \end{cases}$$

则狄利克雷卷积，可以看成它的特例。

定义

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

定义广义 Mobius 函数 $\mu$ 为它在卷积下的逆，$\mu*\zeta=\delta$，由此得

$$(\mu*\zeta)(x,y)=\sum_{x\leq z\leq y}\mu(x,z)\mu(z,y)=\delta(x,y),\forall(x\leq y)$$

将 $\zeta$ 定义代入，得

$$\sum_{x\leq z\leq y}\mu(x,z)=\zeta(x,y),\forall x\leq y$$

由这个等式，可以看到

$$\mu(x,x)=1,\forall x\in X$$ $$\mu(x,y)=-\sum_{x\leq z\leq y}\mu(x,y),\forall x\leq y$$

下面，我们举几个特例下 $\mu$ 的值

例一：

取偏序集为 $(\mathcal{P}(X_n),\subseteq)$，对 $A\subseteq B\subseteq X$，有

$$\mu(A,B)=(-1)^{|B|-|A|}$$

证明：因为 $\mu(A,A)=(-1)^0,\forall A\subseteq X$，并且 $\forall A\subsetneq B\subseteq X$，由归纳可知

$$\begin{align} \mu(A,B) &=-\sum_{A\subseteq C\subseteq B}\mu(A,C)\\ &=-\sum_{A\subseteq C\subseteq B}(-1)^{|C|-|A|}\\ &=-\sum_{k=0}^{p-1}(-1)^{k}\binom{p}{k}\\ &=(-1)^p\\ &=(-1)^{|B|-|A|} \end{align}$$

其中 $p=|B|-|A|$，最后两步是因为

$$0=(1-1)^p=\sum_{k=0}^p(-1)^k\binom{p}{k}\Longrightarrow\sum_{k=0}^{p-1}(-1)^k\binom{p}{k}=(-1)^{p+1}\binom{p}{p}$$

例二：

考虑 $X_n=\{1,2,\cdots,n\}$ 上的自然全序，则

$$\mu(k,l)= \begin{cases} 1,&\text{if }l=k\\ -1,&\text{if }l=k+1\\ 0,&\text{otherwise} \end{cases}$$

证明：由

$$\sum_{k\leq j\leq k+1}\mu(k,j)=0\Longrightarrow\mu(k,k+1)=-\mu(k,k)=-1$$

然后可以归纳得出，当 $l>k+1$ 时，

$$\sum_{k\leq j\leq l}\mu(k,j)=0\Longrightarrow\mu(k,l)=0$$

例三：

考虑 $\Z^+$ 或者 $X_n$ 以及上面的整除偏序关系，我们有

$$\mu(l,k)= \begin{cases} \mu(1,k/l)=\mu(k/l),&\text{if }l\,|\,k\\ 0,&\text{otherwise} \end{cases}$$

其中，一元函数 $\mu$ 是数论中的莫比乌斯函数。

证明：$\mu(1,1)=\mu(1)=1$ 再由

$$\sum_{l|k}\mu(1,l)=0\,\text{and}\,\sum_{l|k}\mu(l)=0$$

得 $\mu(1,k)=\mu(k),\forall k\in\Z^+$

由

$$\sum_{l|p|k}\mu(l,p)=0,\mu(l,l)=1=\mu(1)$$

归纳得

$$\begin{align} \mu(l,k) &=-\sum_{l|p|k,p\neq k}\mu(l,p)\\ &=-\sum_{l|p|k,p\neq k}\mu(1,p/l)\\ &=-\sum_{t|\frac{k}{l},t\neq\frac{k}{l}}\mu(1,t)\\ &=\mu(1,k/l)\\ &=\mu(k/l) \end{align}$$

关于两个偏序集的直积诱导的偏序集，

定理：

令为两个线段有限偏序集，定义 $X\times Y$ 上的偏序为

$$(x,y)\leq(x',y')\Longleftrightarrow x\leq x'\text{ and }y\leq y'$$

假设 $\mu_1,\mu_2$ 分别是 $(X,\leq_1),(Y,\leq_2)$ 上的莫比乌斯函数，$\mu$ 是 $(X\times Y,\leq)$ 上的莫比乌斯函数，则

$$\mu((x,y),(x',y'))=\mu_1(x,x')\mu2(y,y'),\forall(x,y),(x',y')\in X\times Y$$

证明：因为 $(x,y)\not\leq(x',y')\Longleftrightarrow x\not\leq x' \text{ or }y\not\leq y'$，以及 $(x,y)=(x',y')\Longleftrightarrow x=x'\text{ and }y=y'$，因此

$$\mu((x,y),(x,y))=1=\mu_1(x,x)\mu_2(y,y)\\ \mu((x,y),(x',y'))=0=\mu_1(x,x')\mu_2(y,y'),\forall(x,y),(x',y')\in X\times Y$$

然后归纳，当 $(x,y)<(x',y')$，

$$\begin{align} \mu((x,y),(x',y')) &=-\sum_{(x,y)\leq(u,v)\leq(x',y')}\mu((u,v),(x',y'))\\ &=-\sum_{(x,y)\leq(u,v)\leq(x',y')}\mu_1(u,x')\mu_2(v,y')\\ &=-\left(\sum_{x\leq_1u\leq_1x'}\mu_1(u,x')\right)\left(\sum_{y\leq_2v\leq_2y'}\mu_2(v,y')\right)+\mu_1(x,x')\mu_2(y,y')\\ &=0·0+\mu_1(x,x')\mu_2(y,y') \end{align}$$

得证。

广义莫比乌斯反演

定理（广义莫比乌斯反演）：

令 $(X,\leq)$ 是一个具有最小元（记为0）的线段有限偏序集。令 $\mu$ 是它的广义莫比乌斯函数，令 $F:X\rightarrow \C$ 是一个 $X$ 上的函数，定义 $G:X\rightarrow \C$ 为

$$G(X)=\sum_{z\leq x}F(z),\forall x\in X$$

则我们由反演公式

$$F(x)=\sum_{y\leq x}G(y)\mu(y,x),\forall x\in X$$

证明：直接证明

$\forall x\in X$

$$\begin{align} \sum_{y\leq x}G(y)\mu(y,x) &=\sum_{y\leq x}\sum_{z\leq y}F(z)\mu(y,x)\\ &=\sum_{y\leq x}\mu(y,x)\sum_{z\in X}\zeta(z,y)F(z)\\ &=\sum_{z\in X}\sum_{y\leq x}\zeta(z,y)\mu(y,x)F(z)\\ &=\sum_{z\in X}\left(\sum_{y\leq x}\zeta(z,y)\mu(y,x)\right)F(z)\\ &=\sum_{z\in X}\delta(z,x)F(z)\\ &=F(x) \end{align}$$

不过从卷积的角度来看更加清晰，可以说一目了然。

定义

$$f(x,y)= \begin{cases} F(y),&\text{if }x=0\\ 0,&\text{otherwise} \end{cases}\\ g(x,y)= \begin{cases} G(y),&\text{if }x=0\\ 0,&\text{otherwise} \end{cases}$$

则

$$g(x,y)=\sum_{z\leq y}f(z,y)=(f*\zeta)(x,y)$$

即 $g=f*\zeta$，两边再卷上 $\mu$ 得到（$\mu$ 和 $\zeta$ 互为逆）

$$f=g*\mu$$

故

$$F(x)=f(0,x)=(g*\mu)(0,x)=\sum_{y\leq x}g(0,y)\mu(y,x)=\sum_{y\leq x}G(y)\mu(y,x)$$

证毕

注意定理中的一个条件 $(X,\leq)$ 具有最小元（不是极小，而是最小）。这个最小元的限制，保证了求和式都是有限的，可以直接交换，而不必考虑收敛性问题。

我们同样可以将这个限制放宽，比如只需保证 $\sum_{z\leq x}F(z),\sum_{z\leq x}G(z)$ 是绝对收敛的。

推论（广义莫比乌斯变换反向形式）：令 $(X,\leq)$ 是一个线段有限偏序集. 令 $\mu$ 是它的广义莫比乌斯函数，令 $F:X\rightarrow\C$ 是一个上的函数，定义 $G:X\rightarrow\C$ 为

$$G(x)=\sum_{z\geq x}F(z),\forall x\in X$$

则我们由反演公式

$$F(x)=\sum_{y\geq x}G(y)\mu(y,x),\forall x\in X$$

其中满足 $\forall x\in X,\sum_{z\geq x}F(z),\sum_{z\geq x}G(z)$ 绝对收敛。

证明：我们将偏序关系反过来，定义 $x\leq_1 y\Longleftrightarrow\leq x$。 根据上面的讨论就得到了这个定理

推论

（数论中莫比乌斯变换的倍数形式）：设 $f$ 是一个数论函数，定义

$$F(n)=\sum_{n|N}f(N)$$

其中 $\sum_{n|N}f(N),\sum_{n|N}F(N),\forall n$ 绝对收敛。则

$$f(n)=\sum_{n|N}F(N)\mu(\frac{N}{n})$$

广义莫比乌斯变换的例子

1. 容斥原理可以看作是广义莫比乌斯变换的特例，只需让 $X+\mathcal{P}(X_n)$，以包含关系作为偏序关系。
2. 数论中的莫比乌斯反演也是它的特例，只需取 $X=X_n$ 以及整除关系作为偏序关系，设 $F$ 为某个 $X$ 上的实函数，

$$G(n)=\sum_{d|n}F(d)$$

则有

$$F(n)=\sum_{d|n}\mu(d,n)G(d)=\sum_{d|n}\mu(n/d)G(d)$$

1. 利用莫比乌斯反演，计算欧拉函数 $\varphi(n)$，即 $1\sim n$ 中和 $n$ 互素的元素个数

取偏序集同上，定义

$$G(n)=\sum_{d|n}\varphi(d)=\sum_{d|n}\varphi(n/d)$$

由于

$$\begin{align} \sum_{d|n}\varphi(n/d) &=\sum_{d|n}\#{x\in \Z^+\text{ and }x\leq n/d\text{ and }\gcd(x,n/d)=1}\\ &=\sum_{d|n}\#{x\in \Z^+\text{ and }dx\leq n\text{ and }\gcd(dx,n)=d}\\ &=\sum_{d|n}\#{y\in \Z^+\text{ and }y\leq n\text{ and }\gcd(y,n)=d}\\ &=n \end{align}$$

即 $G(n)=n$，利用 莫比乌斯反演，得到

$$\varphi(n)=\sum_{d|n}\mu(n/d)d=\sum_{d|n}\mu(d)n/d$$

令 $n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$，$\alpha_i\geq 1$，利用 $\mu$ 的积性性质，得

$$\begin{align} \varphi(n) &=\sum_{d|n}\mu(d)n/d\\ &=\sum_{d=p_1^{\beta_1}p_2^{\beta_2}\cdots p_k^{\beta_k},\beta_i\leq 1}\mu(d)n/d\\ &=\sum_{\beta_1\leq 1}\mu(p_1^{\beta_1})p_1^{\alpha_1-\beta_1}\sum_{\beta_2\leq 1}\mu(p_2^{\beta_2})p_2^{\alpha_2-\beta_2}\cdots\sum_{\beta_k\leq 1}\mu(p_k^{\beta_k})p_k^{\alpha_k-\beta_k}\\ &=\prod_{i=1}^k(p_i^{\alpha_i}-p_i^{\alpha_i-1})\\ &=n\prod_{i=1}^k(1-\frac{1}{p_i}) \end{align}$$

1. 利用莫比乌斯变换解决计数问题。问题是 $1\sim k$ 组成的长度为 $n$ 的可重复循环排列有多少种？可重复指的是 $1\sim k$ 可以重复使用，循环指的是它形成一个环，同一个环旋转得到的是同一个循环排列。或者这样描述，有 $k$ 种颜色的珠子，每种颜色的珠子数量无限。问用它们能串成多少种长度为 $n$ 的手链。

这个问题可以使用Polya计数解决，这里我们使用莫比乌斯反演。

我们将手链拆成串，按周期，对各种情况进行分类。那些周期不为本身的，由更小的周期串组成。令 $f(m)$ 为长度为 $m$ 且周期为 $m$ 的子串，$h(n)$ 为我们要计数的手链种类数，则

$$h(n)\sum_{d|n}\frac{f(d)}{d}$$

因为每个长度为的串，刚好重复计算 $d$ 次

令

$$g(m)=\sum_{e|m}f(e)$$

则 $g(m)$ 为所有长度为 $m$ 的串，因此 $g(m)=k^m$，利用莫比乌斯反演，我们得到

$$f(m)=\sum_{e|m}\mu(m/e)g(e)=\sum_{e|m}\mu(m/e)k^e$$

将 $f$ 代回，得

$$\begin{align} h(n) &=\sum_{d|n}\frac{f(d)}{d}\\ &=\sum_{d|n}\frac{1}{d}\sum_{e|d}\mu(d/e)k^e\\ &=\sum_{e|n}\left(\sum_{m|\frac{n}{e}}\frac{1}{me}\mu(m)\right)k^e\\ &=\sum_{e|n}\left(\sum_{r|\frac{n}{e}}\frac{r}{n}\mu((n/e)/r)\right)k^e\\ &=\sum_{d|n}\frac{\varphi(n/e)}{n}k^e\\ &=\frac{1}{n}\sum_{e|n}\varphi(n/e)k^e \end{align}$$