Möbius 反演

Möbius 反演是组合学中的结论. 其经典版本来源于初等数论, 该结论是说, 对数论函数 $f:{\mathbb{N}}_{+}\to \mathbb{C}$, 若定义数论函数 $g$ 为$$g(n)=\sum _{d\mid n}f(d),$$这里对 $n$ 的所有正因数 $d$ 求和, 则 $f$ 可以反过来用 $g$ 表示出来:$$f(n)=\sum _{d\mid n}g(d)\mu \left(\frac{n}{d}\right),$$(1)其中 $\mu$ 是 Möbius 函数. 此时称 $g$ 为 $f$ 的 Möbius 变换, 而式 (1) 就称为 Möbius 反演.

大致来说, 式 (1) 成立的原因是, 若将每个 $g(d)$ 按其定义展开, 写成一些 $f(d^{\prime })$ 的和, 其中 $d^{\prime }\mid d$, 则对固定的 $d^{\prime }$, 式中出现的所有 $f(d^{\prime })$ 在乘以系数 $\mu (n/d)=\pm 1$ 后都被抵消, 只有当 $d^{\prime }=n$ 的那一项留了下来, 因此整个和式只剩下一项 $f(n)$.

一般的 Möbius 反演是上述结论向偏序集的推广. 在上述结论中, 我们取的是正整数集 ${\mathbb{N}}_{+}$ 在整除关系下构成的偏序集. 在一般情况下, 上述 Möbius 函数 $\mu (n/d)$ 需要换成一个二元函数 $\mu (d,n)$, 称为该偏序集的 Möbius 函数.

1陈述

设 $(X,\le )$ 为偏序集. 记$$X^{\le }=\{(x,y)\in X\times X\mid x\le y\}.$$

定义 1.1 (局部有限偏序集). 称偏序集 $(X,\le )$ 为局部有限偏序集, 若对任意 $(x,y)\in X^{\le }$, 区间$$[x,y]=\{z\in X\mid x\le z\le y\}$$是有限集.

定义 1.2 (卷积代数). 设 $(X,\le )$ 是局部有限偏序集 (定义 1.1), $R$ 是交换环. 定义 $X$ 的卷积代数 $I(X;R)$ 为下述 $R$-结合代数:

•	其元素为映射 $f:X^{\le }\to R$.

•	其乘法为如下定义的卷积. 对 $f,g\in I(X;R)$, 定义其卷积 $f\ast g\in I(X;R)$ 为$$(f\ast g)(x,y)=\sum _{x\le z\le y}f(x,z)g(z,y).$$

•	其单位元为以下定义的 $\mathbf{\delta }$ 函数: $$\delta (x,y)=\{\begin{array}{ll}1,& x=y,\\ 0,& x\ne y.\end{array}$$

定理 1.3 (Möbius 函数). 设 $(X,\le )$ 是局部有限偏序集 (定义 1.1), $R$ 是交换环. 则存在唯一元素 $\mu \in I(X;R)$, 称为 Möbius 函数, 使得$$\mu \ast e=e\ast \mu =\delta ,$$其中 $e\in I(X;R)$ 是由 $e(x,y)\equiv 1$ 定义的常值函数.

证明概要. 我们对区间 $[x,y]$ 的元素个数归纳定义 $\mu (x,y)$. 若该区间只有 $1$ 个元素, 则 $x=y$, 定义 $\mu (x,x)=1$. 否则, 定义$$\mu (x,y)=-\sum _{x\le z<y}\mu (x,z),$$其中右边的 $\mu (x,z)$ 已由归纳假设定义. 可以验证, 该定义保证了 $\mu \ast e=e\ast \mu =\delta$. 唯一性也由证明过程得到.

$\square$

推论 1.4 (Möbius 反演). 设 $(X,\le )$ 是局部有限偏序集 (定义 1.1), $R$ 是交换环. 设 $X$ 有最小元. 则对任意映射 $f,g:X\to R$, 如果对任意 $y\in X$ 都有$$g(y)=\sum _{x\le y}f(x),$$那么对任意 $y\in X$ 都有$$f(y)=\sum _{x\le y}g(x)\mu (x,y)$$

证明. 对任意 $F\in I(X;R)$, 有$$F(x,y)=(F\ast e\ast \mu )(x,y)=\sum _{x\le z\le y}\sum _{x\le w\le z}F(x,w)\mu (z,y).$$令 $F(x,y)=f(y)$, 并在上式中取 $x$ 为 $X$ 的最小元, 得到$$f(y)=\sum _{z\le y}\sum _{w\le z}f(w)\mu (z,y),$$即为要证的等式.

$\square$

2例子

在数论中

取偏序集 $(X,\le )$ 为 $({\mathbb{N}}_{+},|)$, 其中 $|$ 表示整除, 则推论 1.4 即为引言所述的初等数论情形.

容斥原理

容斥原理是 Möbius 反演的特例: 对有限集 $K$, 取偏序集 $X$ 为 $K$ 的所有子集构成的格. 则对子集 $I\subseteq J\subseteq K$, 有$$\mu (I,J)=(-1{)}^{|J|-|I|},$$从而对任意 $f:X\to \mathbb{Z}$, 若定义 $g(J)={\sum }_{I\subseteq J}f(I)$, 则$$f(J)=\sum _{I\subseteq J}(-1{)}^{|J|-|I|}g(I).$$在应用中, 常取有限集 $Y$ 及一族子集 $(Y_k\subseteq Y{)}_{k\in K}$, 满足 $Y={\bigcup }_{k\in K}{Y}_k$, 并对 $I\subseteq K$, 定义$$\begin{array}{rl}f(I)& =|\{y\in Y\mid k\notin I\iff y\in Y_k\}|,\\ g(I)& =|\{y\in Y\mid k\notin I\Rightarrow y\in Y_k\}|.\end{array}$$此时, $$0=f(K)=\sum _{I\subseteq K}(-1{)}^{|K|-|I|}g(I),$$从而$$|Y|=g(K)=\sum _{I⫋K}(-1{)}^{|K|-|I|-1}g(I),$$此即容斥原理.

3相关概念

术语翻译

Möbius 反演 • 英文 Möbius inversion