写在前面
这次总结一下计算 Möbius 函数的一些内容, 包括一些例子, 具体地给出 Möbius 函数的一些用途.
一个平凡的例子: 微积分基本定理的有限差分模拟
设$P=\mathbb N$,(chain, 链) 则由 Möbius 函数的归纳定义, 代入计算,
\[\begin{cases} \mu(x,x)=1,\quad\forall x\in P, \\[5pt] \mu(x,y)=-\sum_\limits{x\le z<y}\mu(x,z),\ \forall x<y\in P, \end{cases}\tag1\]可以得到:$\forall i,j\in P$,
\[\mu(i,j)=\begin{cases} 1,&i=j,\\ -1,&i+1=j,\\ 0,&\mbox{otherwise}, \end{cases}\]其 Möbius 反演公式如下:
设$P$为所有主序理想有限的偏序集, 令$f,g: P\to\mathbb C$, 有
\[g(x)=\sum_{y\le x}f(y),\quad\forall x\in P,\tag2\]当且仅当
\[f(x)=\sum_{y\le x}g(y)\mu(y,x),\quad \forall x\in P.\]
对$\forall n\ge0$,
\[g(n)=\sum_{i=0}^nf(i)\iff f(0)=g(0),\]并且$\forall n>0$, 有
\[f(n)=g(n)-g(n-1)=\Delta g,\]可以看出, $\Sigma$和$\Delta$互为逆($\Sigma$需给定适当初值), 这个结论也被称为微积分基本定理的有限差分模拟.
一些结论
乘积定理
设$P,Q$为局部有限偏序集, $P\times Q$为二者的直积, 如果在$P\times Q$中有$(x,y)\le(x’,y’)$, 则
\[\mu_{P\times Q}((x,y),(x',y'))=\mu_P(x,x')\mu_Q(y,y').\]证明:
设$(x,y)\le(x’,y’)$, 则
\[\begin{aligned} \sum_{(x,y)\le(u,v)\le(x',y')}\mu_P(x,u)\mu_Q(y,v) &=\left(\sum_{x\le u\le x'}\mu_P(x,u)\right)\left(\sum_{y\le v\le y'}\mu_Q(y,v)\right)\\ &=\delta_{xx'}\delta_{yy'}=\delta_{(x,y),(x',y')} \end{aligned}\]比较$(1)$可得到结论.
下面是一个对乘积定理更加一般的表示方法:(采用张量积, 不熟悉的话可以看这一系列的第一篇)
\[I(P\times Q)=I(P)\otimes_{\mathbb C}I(Q), \quad \zeta_{P\times Q}=\zeta_P\otimes\zeta_Q,\]于是得到:
\[\mu_{P\times Q}=\mu_P\otimes \mu_Q.\]第二个例子:容斥原理
设$P=B_n$为秩为$n$的布尔代数, 现有$B_n\cong\mathbf2^n$, 链$\mathbf2={1,2}$的 Möbius 函数由下述参数给出:
\[\mu(1,1)=\mu(2,2)=1, \mu(1,2)=-1,\]将$B_n$等同于一个$n$元集合$X$的所有子集构成的集合, 通过乘积定理得到:
\[\mu(T,S)=(-1)^{|S-T|}=(-1)^{\ell(S,T)}.\]再由上述结论计算 Möbius 反演, 设$f,g:\ B_n\to\mathbb C$, 有:
\[g(S)=\sum_{T\subseteq S}f(T),\quad \forall S\subseteq X,\]当且仅当:
\[f(S)=\sum_{T\subseteq S}(-1)^{|S-T|}g(T),\quad \forall S\subseteq X.\]这就是容斥原理的集合表示形式.