莫比乌斯反演的相关概念
莫比乌斯函数的定义: 莫比乌斯函数是一个定义在正整数域上的一个函数,记作 μ(x)。我们先将 x 进行质因数分解 x=pα11pα22…pαkk,其中 pi 均为质数,αi≥1。则莫比乌斯函数的具体定义如下:
μ(x)={∃αi≥2, μ(x)=0∀αi=1, μ(x)=(−1)k
特别地,我们规定 1 没有质数,也就是对于 1 进行质因数分解后 k 为 0,因此 μ(1)=1
莫比乌斯函数的性质: 我们定义 S(n)=∑d|nμ(d),也就是 n 的所有约数的莫比乌斯函数的和。那么 S(n) 一定存在如下性质:
S(n)={1, n=10, n>1
我们可以证明一下当 n>1 时为什么 S(n)=0,假设此时 n=pα11pα22…pαkk,由于 n>1,所以此时 n 至少包含一个质因子,即 k≥1。
此时对于 n 的任意一个约数 d=pβ11pβ22…pβ3k, 0≤βi≤αi,如果某一个 pi 的次数 βi≥2,那么这个 d 的莫比乌斯函数就是 0,我们先将所有莫比乌斯函数为 0 的约数都忽略。
此时剩下的所有约数 d 的 βi 不是 0 就是 1。这意味着 β1∼βk 不是取 1 就是取 0,而 d 的莫比乌斯函数 μ(d) 的取值就取决于有多少个 βi 取 1,如果有 m 个 βi 取 1,那么 μ(d)=(−1)m。
那么此时这 k 个 βi 一共有 k+1 种方案,第一种是 k 个数中有 0 个 1,此时他们的贡献应该是 C0k(−1)0,第二种是 k 个数中有 1 个 1,此时他们的贡献应该是 C1k(−1)1,以此类推。因此 n 的所有约数 d 的莫比乌斯函数的和也就是 S(n) 就应该是 C0k(−1)0+C1k(−1)1+…+Ckk(−1)k,而这个式子我们可以用二项式定理来做,我们由于 1 的任何次方都是 1,因此我们可以将 S(n) 看成 C0k1k(−1)0+C1k1k−1(−1)1+…+Ckk10(−1)k,可以发现这就是 (1−1)k,由于 k≥1,所以 (1−1)k 必然是 0。由此得证。
莫比乌斯反演定理: 对于定义在正整数域上的两个函数 F(n) 和 f(n),若 F(n)=∑d|nf(d),则 f(n)=∑d|nμ(d)F(nd)
证明也比较简单,我们先将 F(nd) 的展开,∑d|nμ(d)F(nd)=∑d|nμ(d)∑i|ndf(i)。然后可以进行求和次序变换,可以发现当 d=1 是 i 是可以取遍 n 的所有约数的,并且 i|nd 通过等价变换能得到 d|ni,因此对于每个 i,能和他配对 d 都满足 d|ni,因此就可以将原式变成 ∑i|nf(i)∑d|niμ(d)。
而 ∑d|niμ(d) 就是 S(ni),而 S(ni) 只有 0 和 1 两种取值,当 ni=1 时取 1,当 ni>1 时取 0,因此当 i=n 时,ni=1,当 i<n 时,ni=0,因此整个式子就应该等于 f(n)。
由此证明出了莫比乌斯反演定理。
莫比乌斯反演的推论: 对于定义在正整数域上的两个函数 F(n) 和 f(n),若 F(n)=∑n|df(d),则 f(n)=∑n|dμ(dn)F(d),也就是枚举 d 的时候枚举的不是 n 的约数,而是 n 的倍数,这是莫比乌斯反演更常用的一个推论。
推论的证明略不同于定理,同样是展开 F(d),∑n|dμ(dn)F(d)=∑n|dμ(dn)∑d|if(i),同样进行求和次序变换,当 d=n 时 i 会取遍 n 的所有倍数,然后我们设 dn=d′,那么 d=d′n,所以 d′ 需要满足 d′|in,因此就能变换成 ∑n|if(i)∑d′|inμ(d′),而 ∑d′|inμ(d′) 就是 S(in),到这里就跟定理的证明一样了,同理可以证明整个式子等于 f(n)。
由此证明出了莫比乌斯反演推论。
莫比乌斯反演的应用: 莫比乌斯反演最常用的是推论公式,一般都是先将 F(n) 和 f(n) 都定义出来,然后就能用 F(n) 去算出 f(n)。