专栏文章

炫酷广义莫比乌斯反演魔术

__xm_
算法·理论参与者 5已保存评论 4

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
4 条
当前快照
2 份
快照标识符
@mk8jyw58
此快照首次捕获于
2026/01/11 01:02
上个月
此快照最后确认于
2026/02/19 01:21
14 小时前
查看原文
作者是蒟蒻，如果有错误请批评指正，您有改进的建议也请提出/kel

0. 引入

这是数论 mobius 反演：
f(n)=∑d∣ng(d)g(n)=∑d∣nμ(nd)f(d)\begin{align*} f(n) &= \sum_{d|n} g(d) \\ g(n) &= \sum_{d|n} \mu \left(\frac{n}{d}\right) f(d) \end{align*}
这是快速 mobius 变换：
f(S)=∑T⊆Sg(T)g(S)=∑T⊆S(−1)∣S∣−∣T∣f(T)\begin{align*} f(S) &= \sum_{T \subseteq S} g(T) \\ g(S) &= \sum_{T \subseteq S} (-1)^{|S| - |T|} f(T) \end{align*}
有没有发现这俩东西很像？
设 n=∏i=1kpiai (ai≥1)n = \prod_{i = 1}^{k} p_{i} ^ {a_i} \ (a_i \ge 1)。当 ∀ai=1\forall a_i = 1 时，数论 mobius 反演就是 mobius 变换，指数上 bi=0/1b_i = 0/1 可以对应为集合上的属于关系，这与 mobius 变换等价。
我们可以从更高的视角分析这个问题，下面将介绍炫酷广义 mobius 反演魔术！

1. 广义 mobius 变换

定义 1.1 偏序集

称 (X,≤)(X, \le) 为偏序集，其中 ≤\le 表示偏序关系：
X≤={(x,y)∈X×X∣x≤y}X^{\le} = \{ (x, y) \in X \times X \mid x \le y \}

定义 1.2 广义狄利克雷卷积

  • 定义函数 ff 为映射 X≤→RX^{\le} \rightarrow R，RR 是交换环（注意，按照定义，f(x,y)f(x, y) 一定满足 x≤yx \le y）。
  • 定义广义狄利克雷卷积为
(f∗g)(x,y)=∑x≤z≤yf(x,z)g(z,y)(f * g)(x, y) = \sum_{x \le z \le y} f(x, z)g(z, y)
  • 定义单位函数 ϵ\epsilon
ϵ(x,y)=[x=y]\epsilon(x, y) = [x = y]
  • 定义常数函数 1\bold{1}
1(x,y)=1\bold{1}(x, y) = 1
注意：广义 Dirichlet 卷积不满足交换律！

定义 1.2 广义 mobius 函数

定义 mobius 函数为 μ\mu，使得
μ∗1=1∗μ=ϵ\mu * \bold{1} = \bold{1} * \mu = \epsilon \\

定理 1.3 mobius 函数的存在性与唯一性

可以证明，莫比乌斯函数存在且唯一。
证明
根据定义，对任意 (x,y)∈X≤(x, y) \in X^{\le}：
(μ∗1)(x,y)=∑x≤z≤yμ(x,z)=ϵ(x,y)=[x=y](1.3.1)(\mu * \bold{1})(x, y) = \sum_{x \le z \le y} \mu(x, z) = \epsilon(x, y) = [x = y] \tag{1.3.1}
  • 若 x=yx = y，则得 μ(x,y)=1\mu(x, y) = 1
  • 若 x<yx < y，则 ∑x≤z≤yμ(x,z)=0\sum_{x \le z \le y} \mu(x, z) = 0，移项即得
μ(x,y)=−∑x≤z<yμ(x,z)(1.3.2)\mu(x, y) = -\sum_{x \le z < y} \mu(x, z) \tag{1.3.2}
可见 μ\mu 对于所有偏序集一定存在，且唯一。
式 (1.3.1)(1.3.1) 和式 (1.3.2)(1.3.2) 常用于推导 μ\mu 的表达式，注意 (1.3.2)(1.3.2) 的条件 x≤z<yx \le z < y 是左闭右开区间。

定理 1.4 广义 mobius 反演

设 XX 有最小元为 uu，则对任意映射 f,g:X→Rf, g : X \rightarrow R，如果对任意 y∈Xy \in X 都有
f(y)=∑u≤x≤yg(x)f(y) = \sum_{u \le x \le y} g(x)
那么对任意 y∈Xy \in X 都有
g(y)=∑u≤x≤yf(x)μ(x,y)g(y) = \sum_{u \le x \le y} f(x) \mu(x, y)
证明：
对于任意 G(x,y)G(x, y) 满足
G(x,y)=(G∗μ∗1)(x,y)=∑x≤z≤w≤yG(x,z)μ(z,w)1(w,y)=∑x≤z≤w≤yG(x,z)μ(w,y)\begin{align*} G(x, y) &= (G * \mu * \bold{1})(x, y) = \sum_{x \le z \le w \le y} G(x, z) \mu(z, w) \bold{1}(w, y) \\ &= \sum_{x \le z \le w \le y} G(x, z) \mu(w, y) \\ \end{align*}
令 G(u,y)=g(y)G(u, y) = g(y)，带入 g(y)g(y)，得到
g(y)=∑u≤z≤w≤yg(z)μ(w,y)=∑w≤yμ(w,y)∑u≤z≤wg(z)=∑w≤yf(w)μ(w,y)\begin{align*} g(y) &= \sum_{u \le z \le w \le y} g(z) \mu(w, y) \\ &= \sum_{w \le y} \mu(w, y) \sum_{u \le z \le w} g(z) \\ &= \sum_{w \le y} f(w) \mu(w, y) \end{align*}

2. 例子

前缀和

取偏序集 (N+,≤)(N_+, \le)，考察函数
f(n)=∑1≤i≤ng(i)f(n) = \sum_{1 \le i \le n} g(i)
显然 ff 是 gg 的前缀和
由 (1.3.1)(1.3.1) 可得 ∑i≤k≤jμ(i,j)=ϵ(i,j)=[i=j]\sum_{i \le k \le j} \mu(i, j) = \epsilon(i, j) = [i = j]。
  • 若 i=ji = j，有 μ(i,j)=[i=j]=1\mu(i, j) = [i = j] = 1
  • 若 j−i=1j - i = 1，则有 μ(i,j)+μ(i+1,j)=0⇒μ(i,j)=−1\mu(i, j) + \mu(i + 1, j) = 0 \Rightarrow \mu(i, j) = -1。
  • 若 j−i=2j - i = 2，则有 μ(i,j)+μ(i+1,j)+μ(i+2,j)=0⇒μ(i,j)=0\mu(i, j) + \mu(i + 1, j) + \mu(i + 2, j) = 0 \Rightarrow \mu(i, j) = 0。
归纳得：μ(i,j)=0\mu(i, j) = 0 当 j−i≥2j - i \ge 2。
所以 g(n)=f(n)−f(n−1)g(n) = f(n) - f(n - 1)，哎这不是差分吗。

数论 mobius 反演

取偏序集 (N+,∣)(N_+, |)，其中 ∣| 是整除，考察函数
f(n)=∑d∣ng(d)f(n) = \sum_{d | n} g(d)
由 (1.3.1)(1.3.1)，函数 μ\mu 由方程 ∑x∣z∣yμ(x,z)=ϵ(x,y)=[x=y]\sum_{x | z | y} \mu(x, z) = \epsilon(x, y) = [x = y] 给出。
  • 若 x=yx = y，μ(x,y)=1\mu(x, y) = 1
  • 若 x∣yx | y 且 x<yx < y，∑x∣z∣yμ(x,z)=0\sum_{x | z | y} \mu(x, z) = 0
观察：若 x∣yx|y，则有 μ(x,y)=μ(1,yx)\mu(x, y) = \mu \left(1, \frac{y}{x} \right)。
证明：
设局部偏序集：
L={(x,z)×X∣z∈X,x∣z∣y,x≤z<y}R={(1,z)×X∣z∈X,z∣yx,1≤z<yx}\begin{align*} L &= \{ (x, z) \times X \mid z \in X, x | z | y, x \le z < y \} \\ R &= \{ (1, z) \times X \mid z \in X, z | \frac{y}{x}, 1 \le z < \frac{y}{x} \} \end{align*}
根据 (1.3.2)(1.3.2) 有
μ(x,y)=−∑(x,z)∈Lμ(x,z)μ(1,yx)=−∑(1,z)∈Rμ(1,z)\begin{align*} \mu(x, y) &= -\sum_{(x, z) \in L} \mu(x, z) \\ \mu(1, \frac{y}{x}) &= -\sum_{(1, z) \in R} \mu(1, z) \end{align*}
左侧 LL 的元素 (x,z)(x, z) 通过映射 (x,z)↦(1,zx)(x, z) \mapsto (1, \frac{z}{x})，与右侧 RR 的元素一一对应。
我们对 (x,y)(x, y) 归纳证明，假设对于 (x′,y′)<(x,y)(x', y') < (x, y) 命题成立，且 L,RL, R 内的元素都满足小于 (x,y)(x, y)，根据归纳假设与上面推出的映射对应可得
∑(x,z)∈Lμ(x,z)=∑(1,z)∈Rμ(1,z)\sum_{(x, z) \in L} \mu(x, z) = \sum_{(1, z) \in R} \mu(1, z)
而初始情况 (1,1)(1, 1) 成立，所以 μ(x,y)=μ(1,yx)\mu(x, y) = \mu(1, \frac{y}{x})。
因此 μ(x,y)=μ(1,yx)\mu(x, y) = \mu(1, \frac{y}{x})，我们只需要找到 μ(1,n)\mu(1, n) 的通项公式即可，接下来的 μ(n)\mu(n) 表示 μ(1,n)\mu(1, n)。
由方程得到 ∑d∣nμ(1,d)=ϵ(1,n)=[n=1]\sum_{d | n}\mu(1, d) = \epsilon(1, n) = [n = 1]（莫反的核心式子，其实是源于广义莫比乌斯函数的定义）。
对于素数幂 pkp^k：
  • k=0k = 0：μ(1)=1\mu(1) = 1
  • k=1k = 1：μ(p)+μ(1)=0⇒μ(p)=−1\mu(p) + \mu(1) = 0 \Rightarrow \mu(p) = -1
  • k=2k = 2：μ(p2)+μ(p)+μ(1)=0⇒μ(p2)=0\mu(p^2) + \mu(p) + \mu(1) = 0 \Rightarrow \mu(p^2) = 0
归纳得：μ(pk)=0\mu(p^k) = 0 当 k≥2k \ge 2。
接下来证明函数积性：
假设对所有小于 nmnm 的正整数积性成立。考虑 nmnm，其中 gcd⁡(n,m)=1\gcd(n, m) = 1。
μ(nm)=−∑d∣nmd<nmμ(d)=−∑d1∣nd2∣md1d2<nmμ(d1)μ(d2)=−(∑d1∣nd1<nμ(d1)∑d2∣md2<mμ(d2))+μ(n)(∑d2∣md2<mμ(d2))+μ(m)(∑d1∣nd1<nμ(d1))=−μ(n)μ(m)+2μ(n)μ(m)=μ(n)μ(m)\begin{align*} \mu(nm) &= -\sum_{\substack{d|nm \\ d <nm}} \mu(d) = -\sum_{\substack{d1|n \\ d2|m \\ d1d2 < nm}} \mu(d1) \mu(d2) \\ &= -\left( \sum_{\substack{d1|n \\ d1 < n}} \mu(d1) \sum_{\substack{d2|m \\ d2 < m}} \mu(d2) \right) + \mu(n) \left( \sum_{\substack{d2|m \\ d2 < m}} \mu(d2) \right) + \mu(m) \left( \sum_{\substack{d1|n \\ d1 < n}} \mu(d1) \right) \\ &= -\mu(n)\mu(m) + 2\mu(n)\mu(m) = \mu(n)\mu(m) \end{align*}
综上，设 n=∏i=1kpiai (ai>1)n = \prod_{i = 1}^{k} {p_i}^{a_i} \ (a_i > 1)，我们得到了 μ(n)\mu(n) 的表达式（也就是一般语境下的“莫比乌斯函数”）：
μ(n)={1n=10∃ai≥2(−1)kotherwise\mu(n) = \begin{cases} 1 & n = 1 \\ 0 & \exist a_i \ge 2 \\ (−1)^k & \text{otherwise} \end{cases}
于是可得
g(n)=∑d∣nf(d)μ(d,n)=∑d∣nf(d)μ(nd)g(n) = \sum_{d | n} f(d) \mu(d, n) = \sum_{d | n} f(d) \mu\left(\frac{n}{d}\right)

快速莫比乌斯变换（FMT）

对于有限集 UU，取偏序集 (U,⊆)(U, \subseteq)，考察函数
f(S)=∑T⊆Sg(T)f(S) = \sum_{T \subseteq S} g(T)
由 (1.3.2)(1.3.2) 有 μ(I,J)=−∑I⊆K⊂Jμ(I,K)\displaystyle \mu(I, J) = -\sum_{I \subseteq K \subset J} \mu(I, K)。
观察：若 ∣I∣=∣I′∣,∣J∣=∣J′∣|I| = |I'|, |J| = |J'| 且 I⊆J,I′⊆J′I \subseteq J, I' \subseteq J'，则 μ(I,J)=μ(I′,J′)\mu(I, J) = \mu(I', J')。
证明思路：
与上题类似，设
L={(I,K)∣I⊆K⊂J}R={(I′,K)∣I′⊆K⊂J′}\begin{align*} L &= \{ (I, K) \mid I \subseteq K \subset J \} \\ R &= \{ (I', K) \mid I' \subseteq K \subset J' \} \end{align*}
由于 I,I′I,I' 和 J,J′J, J' 集合大小相同，任意一种双射 F:J→J′F : J \rightarrow J' 都可以使 L,RL, R 通过 FF 一一对应。（感性理解一下，将集合视作二进制数，标号一下就能对应上了）
然后归纳证明即可。
而 L,RL,R 又可以通过映射 K↦K\IK \mapsto K \backslash I 同构于 [∅,J\I][\varnothing, J \backslash I]，所以其实 μ(I,J)=μ(∅,J\I)\mu(I, J) = \mu(\varnothing, J \backslash I)，而 μ(∅,J\I)\mu(\varnothing, J \backslash I) 又只与 ∣J\I∣|J \backslash I| 有关，所以下文使用 μ(∣J∣−∣I∣)\mu(|J| - |I|) 表示 μ(I,J)\mu(I, J)。
重新整理
μ(I,J)=μ(∣J∣−∣I∣)=−∑I⊆K⊂Jμ(I,K)=−∑k=∣I∣∣J∣−1∑∣K∣=kI⊆K⊂Jμ(∣K∣−∣I∣)\mu(I, J) = \mu(|J| - |I|) = -\sum_{I \subseteq K \subset J} \mu(I, K) = -\sum_{k = |I|}^{|J| - 1} \sum_{\substack{|K| = k \\ I \subseteq K \subset J}} \mu(|K| - |I|)
而 I⊆K⊂JI \subseteq K \subset J 等价于 (I\I)⊆(K\I)⊂(J\I)(I \backslash I) \subseteq (K \backslash I) \subset (J \backslash I)，KK 的个数是 (∣J\I∣∣K\I∣)=(∣J∣−∣I∣∣K∣−∣I∣)\displaystyle\binom{|J \backslash I|}{|K \backslash I|} = \binom{|J| - |I|}{|K| - |I|}，可以得到
μ(∣J∣−∣I∣)=−∑k=∣I∣∣J∣−1∑∣K∣=kI⊆K⊂Jμ(∣K∣−∣I∣)=−∑k=∣I∣∣J∣−1(∣J∣−∣I∣k−∣I∣)μ(∣K∣−∣I∣)\mu(|J| - |I|) = -\sum_{k = |I|}^{|J| - 1} \sum_{\substack{|K| = k \\ I \subseteq K \subset J}} \mu(|K| - |I|) = -\sum_{k = |I|}^{|J| - 1} \binom{|J| - |I|}{k - |I|} \mu(|K| - |I|)
带入 I=∅I = \varnothing 方便我们推导
μ(∣J∣)=−∑k=0∣J∣−1(∣J∣k)μ(k)\mu(|J|) = -\sum_{k = 0}^{|J| - 1} \binom{|J|}{k} \mu(k)
可归纳证明 μ(n)=(−1)n\mu(n) = (-1)^n：
  • 当 n=0n = 0，μ(0)=1\mu(0) = 1
  • 当假设对所有 k<nk < n，有 μ(k)=(−1)kμ(k) = (−1)^k。则：
μ(n)=−∑k=0n−1(nk)μ(k)=−∑k=0n−1(nk)(−1)k=−(0−(−1)n)=(−1)n\mu(n) = -\sum_{k = 0}^{n - 1} \binom{n}{k} \mu(k) = -\sum_{k = 0}^{n - 1} \binom{n}{k} (-1)^k = -(0 - (-1)^n) = (-1)^n
所以
g(S)=∑T⊆Sf(T)μ(T,S)=∑T⊆S(−1)∣S∣−∣T∣f(T)g(S) = \sum_{T \subseteq S} f(T)\mu(T, S) = \sum_{T \subseteq S} (-1)^{|S| - |T|}f(T)
这是子集反演的推导，超集反演可以通过上面的式子变换一下符号得到。我们称集合 SS 的补集为 U−SU - S，超集反演的定义是
f(S)=∑S⊆Tg(T)=∑T⊆(U−S)g(T)f(S) = \sum_{S \subseteq T} g(T) = \sum_{T \subseteq (U - S)} g(T)
我们定义 F(U−S)=f(S)F(U - S) = f(S)，套用子集反演的结论，得到
g(S)=∑T⊆S(−1)∣S∣−∣T∣F(T)=∑(U−T)⊆S(−1)∣S∣−∣U−T∣f(U−T)=∑S⊆T(−1)∣S∣−∣T∣f(T)\begin{align*} g(S) &= \sum_{T \subseteq S} (-1)^{|S| - |T|} F(T) = \sum_{(U - T) \subseteq S} (-1)^{|S| - |U - T|} f(U - T) \\ &= \sum_{S \subseteq T} (-1)^{|S| - |T|} f(T) \end{align*}
上式的 (−1)∣S∣−∣T∣(-1)^{|S| - |T|} 大部分博客写做 (−1)∣T∣−∣S∣(-1)^{|T| - |S|} 的，本质相同。

3. 总结

广义 mobius 反演可以做所有 DAG 前缀和反演状物的东西，提供了一种更一般的视角看这类反演问题，可以加深数学理解。同时定理 (1.1.3)(1.1.3) 告知我们逆矩阵一定存在，但是如果 DAG 没有性质，求反演复杂度等价于求逆矩阵。
广义 mobius 反演也是一份强大的数学工具，出现在许多证明中。例如，它被大量用于迪尔沃斯定理的原始证明中，即有限偏序集合中，包含元素最多反链的元素数等于包含链数最少的链分解的链数。

评论

共 4 条评论，欢迎与作者交流。

正在加载评论...