05 莫比乌斯反演

反演

在容斥原理一文中，根据定义我们有

$$N_\geq(S)=\sum\limits_{S \subseteq J}N_=(J)$$

由于$N_\geq(S)$通常是容易计算的，而$N_=(J)$是不容易计算的。容斥原理告诉我们可以这样从$N_\geq$“反解”出$N_=$：

$$N_=(S)=\sum\limits_{J:S \subseteq J \subseteq \mathscr{A}}(-1)^{|J|-|S|}N_\geq(J)$$

如果我们把$N_=$和$N_\geq$都看作$\mathcal{P}(\mathscr{A})\to\N$的函数，那么上面两个式子恰好像我们解释出了从一个函数变换到另一个函数的变换公式。一般而言，把上面那个公式看作正向变换，那么下面那个公式就是反向变换，简称为“反演(inversion)”。

注意到，上面两个式子都是线性的。因此，可以用$2^n\times 2^n$的矩阵来表示这两个变换。定义正向变换的矩阵为$Z$，也即

$$N_\geq = ZN_=$$

$Z$的元素应当是$0$或$1$，$Z(i,j)=1$当且仅当$i$对应的集合包含于$j$对应的集合。例如，当坏性质个数为$3$时（分别记为$A,B,C$），正向变换写作：

$$\begin{bmatrix}N_\geq(\{\varnothing\})\\N_\geq(\{A\})\\N_\geq(\{B\})\\N_\geq(\{C\})\\N_\geq(\{A,B\})\\N_\geq(\{A,C\})\\N_\geq(\{B,C\})\\N_\geq(\{A,B,C\})\\\end{bmatrix} = \begin{bmatrix} 1&1&1&1&1&1&1&1\\ 0&1&0&0&1&1&0&1\\ 0&0&1&0&1&0&1&1\\ 0&0&0&1&0&1&1&1\\ 0&0&0&0&1&0&0&1\\ 0&0&0&0&0&1&0&1\\ 0&0&0&0&0&0&1&1\\ 0&0&0&0&0&0&0&1\\ \end{bmatrix} \begin{bmatrix}N_=(\{\varnothing\})\\N_=(\{A\})\\N_=(\{B\})\\N_=(\{C\})\\N_=(\{A,B\})\\N_=(\{A,C\})\\N_=(\{B,C\})\\N_=(\{A,B,C\})\\\end{bmatrix}$$

“子集”的性质使得$Z$呈现为上三角矩阵，所以$Z$可逆。因此反演写作：

$$N_==Z^{-1}N_\geq$$

容斥原理已经帮我们求出了$Z^{-1}$：$Z^{-1}(i,j)=(-1)^{k}$，其中$k$为$j$对应的集合大小与$i$对应的集合大小的差值。$Z^{-1}$只会在$-1,0,1$间取值。

人们把$Z$称为Zeta矩阵，$Z^{-1}$称为Mobius矩阵。

关联代数

我们知道，容斥原理中所涉及的“子集的包含关系”实际上是一种特殊的偏序关系。可以看到，Zeta矩阵与Mobius矩阵实际上都是关于该偏序关系定义的。因此我们可以做推广，在一般的偏序集上定义Zeta矩阵和Mobius矩阵。

严格来看，讨论“矩阵”要求偏序集的大小是有限的。但从数学上，当偏序集满足一些特定的性质时，人们可以定义一种类比于矩阵的代数，称为关联代数(incidence algebra)。

对于偏序集$(P,\leq)$，一个关联代数$\mathscr{I}(P)$是一族$P \times P \to \R$的映射，满足：对于任意$\alpha\in \mathscr{I}(P)$，$\forall x,y \in P,\alpha(x,y) \neq 0 \implies x \leq y$。可见，关联代数中的元素可以看作一个“无穷矩阵”。可以定义其运算法则：

• $(\alpha_1+\alpha_2) (x,y) :=\alpha_1(x,y)+\alpha_2(x,y)$；
• $(c\alpha)(x,y):=c\cdot \alpha(x,y)$；
• $(\alpha \beta)(x,y)=\sum\limits_{z\in P}\alpha(x,z)\beta(z,y)$；

乘法法则可以改写为$(\alpha \beta)(x,y)=\sum\limits_{x \leq z \leq y}\alpha(x,z)\beta(z,y)$。证明：如果$x\not\leq y$，则$(\alpha \beta)(x,y)=0$。同时，对于任意$z\in P$，不可能同时成立$x\leq z\land z\leq y$，所以等式右边也为$0$；如果$x \leq y$，那么对于任意$z$，如果$z<x$或$y<z$，那么$\alpha(x,z)\beta(z,y)=0$；如果$z$与$x$不可比较大小或$z$与$y$不可比较大小，也有$\alpha(x,z)\beta(z,y)=0$。证毕。

定义“单位矩阵”$\delta(x,y):=\mathbb{1}[x=y]$，于是就可以定义“逆矩阵”$\alpha^{-1}$满足$\alpha \alpha^{-1}=\delta$。我们希望关联代数中元素的逆满足：左逆等于右逆；“逆”有唯一性。这对于偏序集有要求。人们通常要求偏序集满足“局部有限性”：$\forall x,y\in P$，满足$x \leq z \leq y$的$z$的个数是有限的。下面证明，局部有限的偏序集上：

• 左逆等于右逆：即证对于任意$\alpha,\beta\in \mathscr{I}(P)$，若$\alpha\beta=\delta$，则$\beta\alpha=\delta$。由$\alpha\beta=\delta$可知，$\forall x,y\in P$，$\mathbb{1}[x=y]=\sum\limits_{x\leq z\leq y}\alpha(x,z)\beta(z,y)$。当$x=y$时，$\delta(x,x)=\sum\limits_{x\leq z\leq x}\beta(x,z)\alpha(x,z)$，可见$(\beta\alpha)(x,x)=\delta(x,x)$。当$x,y$不可比较时，$\delta(x,y)=0$，不存在$z$满足$x\leq z\leq y$，因此$(\beta\alpha)(x,y)=\delta(x,y)$ $=0$。当$x<y$时，因为偏序集满足局部有限性，所以集合$W=\{z\mid x \leq z\leq y\}$是有限集，可以令$W=\{z_1,\cdots,z_m\}$，它们按偏序关系从小到大排列。因为$\alpha\beta=\delta$，所以$\delta(x,y)=(\alpha\beta)(x,y)=$ $\sum\limits_{k=1}^{m}\alpha(z_1,z_k)\beta(z_k,z_m)$。定义矩阵$A(i,j)=\alpha(z_i,z_j),B(i,j)=\beta(z_i,z_j)$，我们知道$\forall 1\leq i<j\leq m$，$\delta(z_i,z_j)=\sum\limits_{k=i}^{j}\alpha(z_i,z_k)\beta(z_k,z_j)=0$，也等于$\sum\limits_{k=1}^{m}\alpha(z_i,z_k)\beta(z_k,z_j)$。所以矩阵$A,B$满足$AB=I$。根据线性代数中矩阵的左逆等于右逆，得到$BA=I$。因此$\forall 1\leq i<j\leq m$，$\delta(z_i,z_j)=\sum\limits_{k=1}^{m}\beta(z_i,z_k)\alpha(z_k,z_j)=0$。所以$\delta(x,y)=\sum\limits_{x\leq z\leq y}\beta(x,z)\alpha(x,y)$。综上，$\beta\alpha=\delta$，证毕。
• 逆的唯一性：即证对于任意$\alpha,\beta,\gamma\in \mathscr{I}(P)$，若$\alpha\beta=\delta$且$\alpha\gamma=\delta$，则$\beta=\gamma$。由$\alpha\beta=\delta$可知，$\forall x,y\in P$，$\mathbb{1}[x=y]=\sum\limits_{x\leq z\leq y}\alpha(x,z)\beta(z,y)$；同理$\mathbb{1}[x=y]=\sum\limits_{x\leq z\leq y}\alpha(x,z)\gamma(z,y)$。当$x=y$时，$\delta(x,x)=\alpha(x,x)\beta(x,x)$ $=\alpha(x,x)\gamma(x,x)$，由于$\alpha(x,x)\neq 0$，故$\beta(x,x)=\gamma(x,x)$。当$x,y$不可比较时，$\beta(x,y)=\gamma(x,y)=0$。当$x<y$时，因为偏序集满足局部有限性，集合$W=\{z\mid x\leq z\leq y\}$是有限集，令$W=\{z_1,\cdots,z_m\}$按偏序关系排列。定义矩阵$A(i,j)=\alpha(z_i,z_j)$，$B(i,j)=\beta(z_i,z_j)$，$C(i,j)=\gamma(z_i,z_j)$。由$\alpha\beta=\delta$和$\alpha\gamma=\delta$可知$AB=I$且$AC=I$。根据线性代数中矩阵逆的唯一性，可知$B=C$，因此$\beta(x,y)=\gamma(x,y)$。综上，$\beta=\gamma$，证毕。

我们看到，“局部有限性”的条件让我们把关联代数上的证明转化为了普通的矩阵上的证明。在关于“逆”的性质上，关联代数和矩阵在本质上是相同的。

莫比乌斯反演

我们用关联代数仿照容斥原理定义zeta函数$\zeta$：$\zeta(x,y)=\mathbb{1}[x \leq y]$。定义莫比乌斯函数$\mu=\zeta^{-1}$。那么偏序集上的“容斥原理”表述为：给定局部有限的偏序集$(P,\leq)$，对于任意两个函数$f,g:P \to\R$，如果$f=\zeta g$，那么$g=\mu \zeta$。换言之，如果$\forall x\in P,f(x)=\sum\limits_{x \leq y}g(y)$，那么$\forall x\in P,g(x)=\sum\limits_{y\in P}\mu(x,y)f(y)$。注意到，因为$\mu$是关联代数中的元素，只有$x \leq y$时$\mu(x,y)$才不为0，因此$\sum\limits_{y\in P}\mu(x,y)f(y)=\sum\limits_{x \leq y}\mu(x,y)f(y)$。综上所述，我们有：

$$\forall x\in P,f(x)=\sum\limits_{x \leq y}g(y)\iff\forall x\in P,g(x)=\sum\limits_{x\leq y}\mu(x,y)f(y)$$

这称为莫比乌斯反演(Mobius inversion)。

在容斥原理中，莫比乌斯函数$\mu$有一个简单的表达式。那么，一般偏序集上的莫比乌斯函数是否也有简单的表达式？我们来做计算：因为$\mu\zeta=\delta$，因此$(\mu\zeta)(x,x)=1=\sum\limits_{x \leq z\leq x}\mu(x,z)\zeta(x,z)$ $=\mu(x,x)\zeta(x,x)=\mu(x,x)$，所以$\mu(x,x)=1$。对于$x<y$，$(\mu\zeta)(x,y)=0=\sum\limits_{x \leq z \leq y}\mu(x,z)\zeta(z,y)=\sum\limits_{x \leq z \leq y}\mu(x,z)$。所以得到$\sum\limits_{x \leq z < y}\mu(x,z)+\mu(x,y)=0$，因此$\mu(x,y)=-\sum\limits_{x \leq z < y}\mu(x,z)$。尽管这不是通项，但我们也足够满意了。因为$\mu$是关联代数中的元素，$x\not\leq y$时$\mu(x,y)=0$。这样我们就给出了莫比乌斯函数的递推表达式：

$$\mu(x,y) = \begin{cases} 0 & \mbox{ if }x\not\le y;\\ 1 & \mbox{ if }x=y;\\ -\sum\limits_{x\le z<y}\mu(x,z) &\mbox{ if }x<y . \end{cases}$$

有的时候，函数$f,g$满足的关系不是$f(x)=\sum\limits_{x \leq y}g(y)$而是$f(x)=\sum\limits_{x \geq y}g(y)$，那么用$\zeta$函数表示就必须写为$f=\zeta^{\top}g$，于是$g=(\zeta^{\top})^{-1}f$。可以证明$(\zeta^\top)^{-1}=(\zeta^{-1})^\top=\mu^\top$，因此$g=\mu^{\top} f$，即：

$g(x)=\sum\limits_{y}\mu^\top(x,y)f(y)=\sum\limits_{y}\mu(y,x)f(y)=\sum\limits_{y \leq x}\mu(y,x)f(y)$。

偏序集的乘积

设$(P_1,\leq_1),(P_2,\leq_2)$，那么定义偏序集的乘积$P_1 \times P_2 = (P_1 \times P_2, \leq)$（括号内的$\times$指的是笛卡尔积）。其中定义乘积偏序集中的元素$(x_1,y_1)\leq(x_2,y_2)$当且仅当$(x_1 \leq_1 x_2) \land (y_1 \leq_2 y_2)$。

下面证明：$\mu((x_1,y_1),(x_2,y_2))=\mu_1(x_1,x_2) \cdot \mu_2(y_2,y_2)$。如果$(x_1,y_1) \not\leq (x_2,y_2)$，那么$\mu=0$，此时要么$x_1 \not\leq_1 x_2$要么$y_1 \not\leq_2 y_2$，因此要么$\mu_1=0$要么$\mu_2 = 0$，成立。其余情况直接依据定义代入，使用归纳法：$\mu_1(x_1,x_2)$ $=-\sum\limits_{x_1 \leq x<x_2}\mu_1(x_1,x)$，$\mu_2(y_1,y_2)$ $=-\sum\limits_{y_1 \leq y<y_2}\mu_2(y_1,y)$，而$\mu((x_1,y_1),(x_2,y_2)) =$ $-\sum\limits_{(x_1,y_1)\leq (x,y)<(x_2,y_2)}\mu((x_1,y_1),(x,y))$。对$(x_1,y_1)$到$(x_2,y_2)$的链长归纳（定义为对应偏序集上$x_1$到$x_2$的链长与$y_1$到$y_2$的链长之和），那么运用归纳假设就得到上式中$\mu((x_1,y_1),(x,y))=\mu_1(x_1,x)\cdot\mu_2(y_1,y)$，因此$\mu((x_1,y_1),(x_2,y_2)) =-\sum\limits_{(x_1,y_1)\leq (x,y)<(x_2,y_2)}\mu_1(x_1,x)\cdot\mu_2(y_1,y)$ $=-\left[\left(\sum\limits_{x_1\leq x < x_2}\mu_1(x_1,x)\right)\left(\sum\limits_{y_1\leq y < y_2}\mu_2(y_1,y)\right)+\mu_1(x_1,x_2)\sum\limits_{y_1\leq y<y_2}\mu_2(y_1,y)+\mu_2(y_1,y_2)\sum\limits_{x_1\leq x<x_2}\mu_1(x_1,x)\right]$ $=-\left[(-\mu_1(x_1,x_2)(-\mu_2(y_1,y_2))-\mu_1(x_1,x_2)\mu_2(y_1,y_2)-\mu_2(y_1,y_2)\mu_1(x_1,x_2)\right]$ $=\mu_1(x_1,x_2)\cdot\mu_2(y_1,y_2)$。

由此我们变得非常容易证明最开始的容斥原理：我们定义一个只有两个元素的偏序集$P(\{0,1\},\leq)$，其中$0<1$。我们对这个偏序集连着乘$n$次（这是有定义的，我们每次只乘2个偏序集），得到的偏序集记为$P^n$。于是在$P^n$中元素可以理解为一个01串，一个串小于等于另一个当且仅当后者为0的地方前者必须是0，后者为1的地方前者可以是0或1——它对应着一个$2^{[n]}$中集合的包含关系！那么根据莫比乌斯函数在偏序集乘法中的运算法则，对于两个二进制串（集合）$x,y$，就有$\mu(x,y)=\mu_1(x_1,y_1)\cdots\mu_n(x_n,y_n)$，而$\mu_i(0,0)=1$，$\mu_i(0,1)=-\mu_i(0,0)=-1$，因此$\mu(x,y)=(-1)^k$，其中$k$是$x,y$中不同的位数的个数，这恰好对应着我们曾经用二项式定理贡献证明的容斥原理$N_=(S)=\sum\limits_{J:S \subseteq J \subseteq \mathscr{A}}(-1)^{|J|-|S|}N_\geq(J)$中的系数$(-1)^{|J|-|S|}$。

数论莫比乌斯函数

我们曾经看到过自然数上的“整除关系”也是一种偏序。所以我们对于特定的$n$可以定义一个偏序集$(D_n, \leq)$，其中就是所有$n$的约数构成的集合，其中$x \leq y$当且仅当$x|y$。

假如$n=p^\alpha$，其中$p$是一个素数，那么$D_n$中的元素只有$\{1,p,p^2,\cdots,p^\alpha\}$。其中的任意两个都可以比较大小，因此这其实是一个全序集，它可以看作指数的序列$\{0,1,2,\cdots,\alpha\}$。在这个集合上的莫比乌斯函数$\mu(x,y)$满足$\mu(x,x)=1$，当$x>y$时$\mu(x,y)=0$，当$x < y$时$\mu(x,y)=-\sum\limits_{x\leq z<y}\mu(x,z)$。由于$\mu(x,y+1)=-\sum\limits_{x \leq z < y+1}\mu(x,z)=-\sum\limits_{x \leq z < y}\mu(x,z)-\mu(x,y)=\mu(x,y)-\mu(x,y)=0$，而$\mu(x,x+1)=-\mu(x,x)=-1$，因此有

$$\mu(x,y) = \begin{cases} 1 & \mbox{ if }x=y \\ -1 & \mbox{ if }x+1=y\\ 0 &\mbox{ otherwise} \end{cases}$$

于是对于任意的正整数$n$，它可以写成唯一的质因数分解的形式$n=p_1^{\alpha_1}\cdots p_k^{\alpha_k}$。它的所有可能的$D_n$就是每个$p_i^{\alpha_i}$中指数任意取值。这相当于每个$p_i^{\alpha_i}$对应的偏序集的笛卡尔积。所以整个偏序集就是这些小偏序集的乘积，要计算它的莫比乌斯函数也就只需要用小的莫比乌斯函数相乘。对于$x<y$，有$\mu(x,y)=\mu_1(x_1,y_1)\cdots\mu_k(x_k,y_k)$。根据$p^\alpha$中莫比乌斯函数的结果，我们需要考察$y/x$的质因数分解：$y/x=p_1^{\beta_1}\cdots p_k^{\beta_k}$。如果$\beta_i>1$，那么$\mu_i(x_i,y_i)=0$，直接得到$\mu(x,y)=0$。因此对于$\mu(x,y) \neq 0$的情况必然要求$y/x$只是某一些质数的乘积（指数都为1），当$\beta_i=0$时莫比乌斯函数贡献1（相当于没贡献），$\beta=1$贡献$-1$。综上，$\mu(x,y)=(-1)^k$，其中$k$为$y/x$质因数分解后不同质数的个数。即：

$$\mu(x,y) = \begin{cases} 1 & \mbox{ if } x=y;\\ (-1)^k & \mbox{ if } y/x \mbox{ is the product of } k \mbox{ distinct primes};\\ 0 & \mbox{otherwise.} \end{cases}$$

结果表明，$\mu(x,y)$只与$y/x$有关，它实际上是一个一元函数。所以，我们也常常用$\mu(x)$来简记$\mu(1,x)$，它们的值是相同的。

由此，我们就可以在研究整除性的领域尝试莫比乌斯反演（容斥原理）。

例如，数论中的欧拉函数$\varphi(n)$定义为$1$到$n-1$中与$n$互质的数的个数（规定$\varphi(0)=1$）。我们有一个重要的关系$\sum\limits_{d|n}\varphi(d)=n$。这个结论可以通过真分数的约分来直观地理解：当$n$取12时，所有的真分数$\dfrac{1}{12},\cdots,\dfrac{11}{12}$约分后写作：

$\dfrac{1}{12},\dfrac{1}{6},\dfrac{1}{4},\dfrac{1}{3},\dfrac{5}{12},\dfrac{1}{2},\dfrac{7}{12},\dfrac{2}{3},\dfrac{3}{4},\dfrac{5}{6},\dfrac{11}{12}$

按分母归类：

$\dfrac{1}{2};\dfrac{1}{3},\dfrac{2}{3};\dfrac{1}{4},\dfrac{3}{4};\dfrac{1}{6},\dfrac{5}{6};\dfrac{1}{12},\dfrac{5}{12},\dfrac{7}{12},\dfrac{11}{12}$

由于真分数一定包括了所有与它互质的分子，而真分数的分母又取遍了所有$n$的约数（分子至少可以取1），所以这就是$\sum\limits_{d|n}\varphi(d)=n$这个关系的直接表达（还要加上$\varphi(0)=1$）。

那么，$\sum\limits_{d|n}\varphi(d)=n$用整除偏序集的语言来表达就写成$I(y)=\sum\limits_{x \leq y}\varphi(x)$，其中函数$I$表示自身到自身的映射，$I(x)=x$。注意此时是我们刚才提到的不等号方向相反的情况，所以我们要写$\varphi(x)=\sum\limits_{y \leq x}\mu(y,x)I(y)$。化简：$\varphi(n)=\sum\limits_{d|n}\mu(d,n)d$ $=\sum\limits_{d|n}\mu(\dfrac{n}{d})d$

于是得到了欧拉函数的一个计算方法：

$$\varphi(n)=\sum\limits_{d|n}\mu(\dfrac{n}{d})\cdot d$$

格（Lattice）

在树上我们有最近公共祖先的概念，在Hasse图上两个节点也有“公共祖先”，用偏序集来表示，$x,y$的公共祖先$u$满足$x \leq u,y \leq u$。只不过在偏序集里我们不称它为“祖先”而成为“上界”，这是序结构的看法。如果在所有$u$里满足$u_0 \leq u$恒成立的$u_0$就是最小上界，记为$x \or y$。同样的可以定义最大下界$x \land y$。

如果偏序集里的任意两个元素$x,y$存在唯一的最小上界和唯一的最小下界，就称这个偏序集为“格”（Lattice）。格是一种特殊的偏序集。我们来研究它的莫比乌斯函数有什么特殊的性质。

Weisner定理

对于一个格$P$，设$\hat{0}$是其中的最小元素，$\hat{1}$是它的最大元素。那么对于任意的元素$a$，我们找到所有满足$x \or a = \hat{1}$的元素$x$。Weisner定理指出，$\sum\limits_{x \or a = \hat{1}}\mu(\hat{0},x)=0$。我们这样来证明：枚举所有的$x$，而在后面乘上一个因子，使得这个因子只在$x\or a=\hat{1}$时取1，否则取0。这个因子就是$\sum\limits_{y\geq(x \or a)}\mu(y,\hat{1})$——如果$x \or a=\hat{1}$，那么$y$只能取$\hat{1}$，因此它就写成$\mu(\hat{1},\hat{1})=1$；如果$x \or a \neq \hat{1}$，即$x \or a < \hat{1}$，我们要说明这条链上的所有$\mu(y,\hat{1})$之和为0。这个事实其实和莫比乌斯函数定义中的$\sum\limits_{x \leq z \leq y}\mu(x,z)=0$是对称的，我们在定义莫比乌斯函数的时候是用“左逆”来求得，因此得到了所有与起点关联的函数值之和为0，如果我们用“右逆”再尝试一次就会发现所有与终点关联的函数值之和也是0了。于是这样就证明了恒等式$\sum\limits_{x \or a = \hat{1}}\mu(\hat{0},x)=\sum\limits_{x}\left(\mu(\hat{0},x)\cdot \sum\limits_{y \geq (x \or a)}\mu(y,\hat{1})\right)$，交换求和顺序可得$\sum\limits_{y \geq a}\left(\mu(y,\hat{1})\sum\limits_{x \leq y}\mu(\hat{0},x)\right)$。而$\sum\limits_{x \leq y}\mu(\hat{0},x)=\sum\limits_{\hat{0} \leq x \leq y}\mu(\hat{0},x)$，根据莫比乌斯函数的定义它就等于0。这样我们就证明了Weisner定理。

Weisner定理为我们提供一个方便地归纳求解莫比乌斯函数的方法。对这个定理移项可以得到$\mu(\hat{0},\hat{1})=-\sum\limits_{x \or a=\hat{1},x \neq \hat{1}}\mu(\hat{0},x)$，因此我们只要计算出底下的莫比乌斯函数就可以由此推出顶部的莫比乌斯函数。比如，整数的整除关系的偏序集是格，最小上界就是最小公倍数，最大下界就是最小公倍数，那么我们就可以用归纳法重新求解数论莫比乌斯函数的表达式：首先对于素数$p$，$\mu(p)=-\mu(1)=-1$。对于一般的$n$，质因数分解为$n=p_1^{\alpha_1}\cdots p_k^{\alpha_k}$。我们将Weisner定理中的$a$取为$p_1$，那么$\sum\limits_{x \or a=\hat{1}}\mu(\hat{0},x)=0=\sum\limits_{lcm(x,p_1)=n}\mu(x)=0$，即$\mu(n)=-\sum\limits_{lcm(x,p_1) =n,x \neq n}\mu(x)$。如果$\alpha_1>1$，那么$x$必须取$n$才能使$lcm(x,p_1)=n$，少了任何一个因子都不行，而$x$又不能等于$n$，所以直接得到$\mu(n)=0$；否则$\alpha_1=1$，此时$x$只能取$n/p_1$，少了别的任何一个因子都不行，因此$\mu(n)=-\mu(n/p_1)$。这样归纳下去，得到的结论和我们之前根据定义计算得到的数论莫比乌斯函数是一致的。

划分的莫比乌斯函数

考虑“划分”的偏序集：一种划分方案对应着偏序集里的一个元素，而如果划分$\pi_1$是$\pi_2$的加细（在原来的基础上分得更细），就定义$\pi_1 \leq \pi_2$。简单起见，我们以整数集合$[n]$的划分为例。我们可以验证这个划分是一个格，合并就是上界，拆散就是下届。每个元素单独划分就是$\hat{0}$，所有元素打包就是$\hat{1}$。

求解$\mu(\hat{0},\hat{1})$

莫比乌斯函数是被偏序关系决定的（Hasse图），我们发现，对于划分我们其实只关心待划分的元素个数，而不在意元素是什么。要计算任意两个划分的莫比乌斯函数$\mu(\pi_1,\pi_2)$，其实都可以还原到最简单的情形$\mu(\hat{0},\hat{1})$——假如$\pi_2$中有多个集合，那么我们可以考虑每个集合内部的划分，这些划分都是$\mu(x,\hat{1})$的形式的，我们把这些莫比乌斯函数计算出来然后按照之前定义的“偏序集的乘法”把他们乘在一起就好了；而对于每个$\mu(x,\hat{1})$，我们的划分$x$其实是若干个集合，在我们的考虑内没有必要更细了，因此每个集合其实就是一个元素，所以其实它就等于$\mu(\hat{0},[k])$。（我们所说的“就是”，其实是通过构建一个同构的新偏序集，并且证明这两个偏序集上的莫比乌斯函数相等）

所以关键只要求出$\mu(\hat{0},\hat{1})$。下面我们证明，$\mu(\hat{0},\hat{1})=(-1)^{n-1}(n-1)!$。

归纳法。当$n=1$时等于1，满足；当$n \geq 2$时，运用Weisner定理，取$a=\{\{1,2\},\{3\},\{4,\},\cdots,\{n\}\}$，即在$\hat{0}$的基础上将$1,2$合并。那么$\mu(\hat{0},\hat{1})=-\sum\limits_{\pi \or a =\hat{1},\pi \neq \hat{1}}\mu(\hat{0},\pi)$。如果$\pi$将$1,2$分在了同一个集合，那么为了使它和$a$合并后形成$[n]$，如果$\pi \neq [n]$就一定不可能，因此$1,2$不能属于同一个集合；除了含1和含2的集合以外，不能有第三个集合，不然也无法合并成一个集合。综上我们发现，$\pi$只能把元素分成两个集合$S_1,S_2$，其中$1 \in S_1,2 \in S_2$。那么$\mu(\hat{0},\pi) = \mu(\hat{0},\{S_1\}) \cdot \mu(\hat{0},\{S_2\})$，而由于我们是归纳法，这两个函数都已经得到了：$\mu(\hat{0},\{S_1\}) = (-1)^{|S_1|-1}(|S_1|-1)!$，$\mu(\hat{0},\{S_2\}) = (-1)^{|S_2|-1}(|S_2|-1)!$。枚举所有可能的$\pi$，这相当于对$\{3,\cdots,n\}$枚举子集$T$，得到$\mu(\hat{0},\hat{1})$ $=-\sum\limits_{T}\mu(\hat{0},\{1,T\})\mu(\hat{0},\{2,T^C\})=-\sum\limits_{k=0}^{n-2} \dbinom{n-2}{k}(-1)^{k}k!(-1)^{n-k-2}(n-k-2)!$ $=\sum\limits_{k=0}^{n-2}\dfrac{(n-2)!}{k!(n-2-k)!}(-1)^{n-1}k!(n-k-2)!=(n-1)(n-2)!(-1)^{n-2}=(-1)^{n-1}(n-1)!$

完全图的连通生成子图计数

来看用到划分的莫比乌斯函数的一个例子。我们很熟悉图的生成树，相应的也有“生成图”的概念。一个连通生成子图是指在原图里挑出一些边，使得这些边使得所有点连通。生成树当然是一个连通生成子图。现在我们保证原图是完全图（任意两个点之间都有边），想统计所有可能的连通生成子图的个数。

要应用划分的莫比乌斯函数的话，我们可以把图的连通性看作一种“划分”，每个连通块在划分中都被划在了同一个集合，不同的连通块就是不同的集合。于是对于划分$\pi$，我们定义函数$g(\pi)$表示在划分$\pi$下（连通块情况）的生成子图的个数，再定义$f(\pi) = \sum\limits_{\pi'\leq \pi}g(\pi')$，表示所有在$\pi$的基础上加细的所有连通情况下生成子图的个数之和——这是容易计算的，只要不取连通块之间的边，每个内部的边都可以乱选，所以假如$\pi$写作$\{S_1,\cdots,S_t\}$，第$i$个集合内有$|S_i|$个点，因此完全图里有$\dbinom{|S_i|}{2}=\dfrac{|S_i|(|S_i|-1)}{2}$条边，因此$f(\pi) = \prod\limits_{i=1}^{t}2^{\frac{|S_i|(|S_i|-1)}{2}}$。

那么根据$f(\pi) = \sum\limits_{\pi'\leq \pi}g(\pi')$莫比乌斯反演（注意又是不等号反过来的那种情况），得到$g(\pi)=\sum\limits_{\pi' \leq \pi}\mu(\pi',\pi)f(\pi')$。而莫比乌斯函数的求法我们已经通过“划分”的“格”得到了。

快速Zeta变换

我们回到最初定义莫比乌斯函数的矩阵，我们把这个矩阵写作了zeta函数$\zeta(x,y)=\mathbb{1}[x \leq y]$。对于给定的$f$，计算$\zeta f$的复杂度就是暴力做矩阵乘法（矩阵乘向量）的复杂度，为$O((2^n)^2)=O(4^n)$。

而我们知道$\zeta$函数其实是在枚举子集，而我们所做的计算其实是在考虑每个子集的子集。子集可以用二进制来表示，那子集的子集就可以用三进制来表示，因此应当存在一个$O(3^n)$的做法。这也并不困难，这个问题的优化就在于利用$\zeta$的性质——上三角矩阵。因此对于大小为$k$的子集（某一行），我们只需要遍历$2^k$个元素。由此可得总的复杂度为$O(\sum\limits_{k=0}^{n}\dbinom{n}{k}2^k)=O((1+2)^n)=O(3^n)$。

还有更快的方法。我们对于矩阵$\zeta$的某一行（记作01向量$(x_1,\cdots,x_n)$），我们是要寻找所有满足$y_i \geq x_i$的向量$y$的$f(y)$并求和。我们可以动态规划来尝试解决这个问题：定义$dp(k,x_1,\cdots,x_k,x_{k+1},\cdots,x_n)$表示对所有前$k$维$\geq x_i$而后$n-k$维$=x_i$的向量$y$对应的$f(y)$求和。那么对于每个$k$，如果$x_k=1$则$dp(k,x_1,\cdots,x_n)=dp(k-1,x_1,\cdots,x_{n})$；如果$x_k=0$，则在这基础上还要加上$dp(k-1,x_1,\cdots,x_{k-1},1,x_{k+1},\cdots,x_n)$这一项。初始时对于所有$x$，$k=0$时就是$f(x)$本身；而我们要的答案就是各个$x$在$k=n$时的dp值。我们看到状态转移的复杂度是$O(1)$的，状态数为$O(n \cdot 2^n)$，这就是时间复杂度了。这个方法就被成为“快速Zeta变换”。

快速莫比乌斯变换

快速Zeta变换完成的工作就是对所有二进制串$x$求出了$\sum\limits_{x \leq y}f(y)$，这里$\zeta$函数被隐含在了对遍历的限制条件$x \leq y$中。对应的，快速莫比乌斯变换就是要对所有$x$求出$\sum\limits_{x \leq y}\mu(x,y)f(y)$。

我们采用完全相同的动态规划方法：定义$dp(k,x_1,\cdots,x_k,x_{k+1},\cdots,x_n)$表示对所有前$k$维$\geq x_i$而后$n-k$维$=x_i$的向量$y$对应的$\mu(x,y)f(y)$求和。那么对于每个$k$，如果$x_k=1$则$dp(k,x_1,\cdots,x_n)=dp(k-1,x_1,\cdots,x_{n})$；如果$x_k=0$，则还要加上一项，但不能像Zeta变换一样加$dp(k-1,x_1,\cdots,x_{k-1},1,x_{k+1},\cdots,x_n)$这一项，因为在这里$x$变化了，而我们想要的$\mu(x,y)$中的$x$是原来的$x$。所以想要用这个状态，对于每个$y$都要必须除掉$\mu((x_1,\cdots,x_{k-1},1,x_{k+1},\cdots,x_n),y)$，乘上$\mu((x_1,\cdots,x_n),y)$。对于子集的偏序集，我们导出过$\mu(x,y)=(-1)^k$，其中$k$是$x,y$中不同位的个数。于是我们直接得到这两个莫比乌斯函数的比值为$-1$——也就是说此时的状态转移与Zeta变换相比，把“加上多出来的一项”改为“减去”就好了，其他与快速Zeta变换完全一致。初始化时对于所有$x$，$k=0$时也还是$\mu(x,x)f(x)=f(x)$本身。这称为“快速莫比乌斯变换”。

快速集合卷积

为了更好地看到“集合卷积”的意义，我们来看一个“q-着色”问题：用$q$种颜色给图着色，要求同一条边两端颜色必须不同，求方案数。

着色问题其实是要求我们把图分成$q$个独立集，每个独立集内的点染相同颜色，就得到了一个可行的方法。也就是我们要统计不同的独立集的选法的总数。如果定义一个“集合上的卷积”，就可以更清晰地描述“$q$个独立集”这件事——

集合卷积$(f * g)(Z)$定义为$\sum\limits_{X \subseteq Z} f(X)\cdot g(Z \setminus X)$。于是对于图上的点集$S$，我们定义一个函数$f(S)$当且仅当$S$是独立集时返回1，否则返回0。所以一个“2-着色”的解就是$(f*f)(V)$，即对于所有把点分成两部分的划分，当且仅当它们都分别是独立集时产生贡献1。相应的，$q$-着色问题的解就是$(S^q)(V)$，做$q$次卷积。

因此问题是，如何快速地计算集合卷积？我们有一个奇妙的方法，这个方法和用快速傅里叶变换计算多项式卷积有着精神上的相似性。或者说，“快速集合卷积”和“多项式卷积”都是某个更根本的东西的投影。在快速多项式卷积中，最关键的是我们把要做卷积的函数“变换”成了另一个函数，在这种变化下卷积被转化为了简单的乘法，而再通过逆变换我们由得到了这个函数的原始形态。由于“变换”的复杂度优于“卷积”的复杂度，因此我们得到了更高效的算法。快速集合卷积也是相似的，在这里“快速傅里叶变换”被我们的“快速Zeta变换”，而它的逆变换就是“快速莫比乌斯变换”。下面我们来证明这一点：

在证明之前，我们需要对我们要证明的对象进行一些细节上的修正：第一点是，我们需要修改集合卷积的定义，去掉“两个集合没有交集”这一条限制，定义“覆盖卷积”$*_c$为$(f *_c g)(Z)=\sum\limits_{X \cup Y=Z}f(X)g(Y)$。为了能够用覆盖卷积来表示集合卷积，我们修改函数$f,g$的定义，定义$f_i(X)=\mathbb{1}[|X|=i] \cdot f(X)$，也就是在原本函数上附加上一个限制大小的条件。这样我们就可以把原本的集合卷积写作$\sum\limits_{X\cup Y=Z,X \cap Y=\varnothing} f(X)\cdot g(Y)$写作$\sum\limits\limits_{i=0}^{n}\left(\sum\limits_{X \cup Y=Z}f_i(X)g_{n-i}(Y)\right)=\sum\limits_{i=0}^{n}(f_i*_c g_{n-i})(Z)$，也即$f*g=\sum\limits_{i=0}^{n}(f_i *_c g_{n-i})$。第二点是，要能够满足与傅里叶变换类似的性质，我们需要把$\zeta$函数$\zeta(x,y)=\mathbb{1}[x \leq y]$的定义修改为$\zeta(x,y)=\mathbb{1}[x \geq y]$。

这样我们就可以来证明“快速集合卷积”$\zeta(f *_c g)(Z)=\zeta f(Z)\cdot \zeta g(Z)$了。（其中$(Z)$就代表当前考虑结果向量的某一行。）直接通过定义来验证即可：$\zeta(f *_c g)(Z)=\sum\limits_{Y \subseteq Z}(f *_c g)(Y)$，根据覆盖卷积的定义，$=\sum\limits_{Y \subseteq Z}\sum\limits_{A \cup B=Y}f(A)g(B)$，这等价于$\sum\limits_{(A \cup B) \subseteq Z}f(A)f(B)$，先枚举$A$，在固定$A$的前提下枚举$B$，则等价于$\sum\limits_{A \subseteq Z}\left(f(A)\cdot \left(\sum\limits_{B \subseteq Z}g(B)\right)\right)$，两者相互独立，因此直接写作$\left(\sum\limits_{A \subseteq Z}f(A)\right)\left(\sum\limits_{B \subseteq Z}g(B)\right)$，而这就是与$\zeta$函数相乘的定义，因此就是$\zeta f(Z) \cdot \zeta g(Z)$。

这样我们就得到了一个快速解决$q$-着色问题的算法：首先我们要预处理函数$f(S)$，$S$的取值有$2^n$个，对于每个取值我们只需要遍历每条边验证即可，并预处理限制了大小的函数$f_i$，因此总复杂度不超过$O(2^n \cdot \text{poly}(n))$。我们总共做$O(q)$次集合卷积，每次集合卷积需要$O(n)$转化为覆盖卷积，求解每个覆盖卷积需要进行两次快速Zeta变换，相乘后再用快速莫比乌斯变换转化为原来的函数。以上的每一个步骤都是不超过$O(2^n \cdot \text{poly}(n))$的，因此最终复杂度就是$O(2^n \cdot \text{poly}(n))$。