用户: Fyx1123581347/Mobius函数

偏序集上的 Möbius 函数推广了数论中的 Möbius 函数, 它可以解决许多计数问题.

1偏序集上函数的卷积

设 $(X,\le )$ 是局部有限的偏序集, 即对任何 $a\le b$, 区间 $\{x:a\le x\le b\}$ 都是有限集. 对于结合环 $R$, 考虑所有二元函数$$f:X\times X\to R,$$使得对任意 $x>y$, $f(x,y)=0$, 也就是在偏序集的态射集上定义的函数. 这样的函数全体记为 $\mathcal{F}(X,R)$. 通常 $R$ 取为实数. 可以在 $\mathcal{F}(X,R)$ 上定义卷积如下$$(f\ast g)(x,y)=\sum _{z,x\le z\le y}f(x,z)g(z,y),$$其中 $z$ 取遍区间 $[x,y]$. 若并非有 $x\le y$, 则取值为 $0$.

命题 1.1 (卷积的结合律). $$(f\ast g)\ast h=f\ast (g\ast h).$$

定义$$\delta (x,y)=1_{x=y}.$$其是卷积中的单位函数:$$f\ast \delta =\delta \ast f=f.$$定义$$\zeta (x,y)=1_{x\le y}.$$

对于 $f\in \mathcal{F}(X,R)$, 且对任何 $x\in X$, $f(x,x)$ 可逆. 对 $x\in X$, 定义$$g(x,x)=\frac{1}{f(x,x)}.$$对 $y>x$, 按 $y$ 到 $x$ 的最短路长度可以递归地定义$$g(x,y)=-\frac{1}{f(y,y)}\sum _{z,x\le z<y}g(x,z)f(z,y).$$

据此定义, 我们有$$g\ast f=\delta .$$

类似地, 我们可以构造 $f$ 的右逆函数 $h$, 结合律表明 $g=h$, 即 $f$ 有逆.

定义 1.2. Möbius 函数 $\mu$ 是 $\zeta$ 的逆函数, 即$$\sum _{z,x\le z\le y}\mu (x,z)=\delta (x,y).$$

例 1.3.

•	设 $S$ 是 $n$ 元有限集, $X=(\mathcal{P}(S),\subseteq )$. 则对 $A\subseteq B$, $$\mu (A,B)=(-1{)}^{|B|-|A|}.$$

2Möbius 反演

定理 2.1. 设 $(X,\le )$ 有最小元 $0$, $F:X\to R$, $$G(x)=\sum _{z\le x}F(z),x\in X.$$则有$$F(x)=\sum _{y\le x}\mu (y,x)G(y).$$

证明.

证明. $$\begin{array}{rl}\sum _{y\le x}G(y)\mu (y,x)& =\sum _{y,y\le x}\sum _{z,z\le y}F(z)\mu (y,x)\\ & =\sum _{y,y\le x}\mu (y,x)\sum _z\zeta (z,y)F(z)\\ & =\sum _z\sum _{y,y\le x}\zeta (z,y)\mu (y,x)F(z)\\ & =\sum _z(\sum _{y,z\le y\le x}\zeta (z,y)\mu (y,x))F(z)\\ & =\sum _z\delta (z,x)F(z)\\ & =F(x).\end{array}$$

$\square$

命题 2.2. 设 $(X_1,{\le }_1),(X_2,{\le }_2)$ 为局部有限偏序集, Möbius 函数为 ${\mu }_1,{\mu }_2$. 则两偏序集直积的 Möbius 函数 $\mu$ 为 ${\mu }_1$ 和 ${\mu }_2$ 的张量积, 即$$\mu ((x_1,x_2),(y_1,y_2))={\mu }_1(x_1,y_1){\mu }_2(x_2,y_2).$$