莫比乌斯反演

介绍

1、莫比乌斯反演是组合数学中很重要的内容，可以用于解决很多组合数学的问题。

2、莫比乌斯反演是数论中的重要内容，在许多情况下能够简化运算。

3、是个很神奇的东西。

引入

考虑以下求和函数

$f_n=\sum_{d|n}g_d$

那么根据定义我们可以知道

$f_1$
=

$g_1$

$f_2$
=

$g_1$
+

$g_2$

$f_3$
=

$g_1$
+

$g_3$

$f_4$
=

$g_1$
+

$g_2$
+

$g_4$

$f_5$
=

$g_1$
+

$g_5$

$f_6$
=

$g_1$
+

$g_2$
+

$g_3$
+

$g_6$

$f_7$
=

$g_1$
+

$g_7$

$f_8$
=

$g_1$
+

$g_2$
+

$g_4$
+

$g_8$

$f_9$
=

$g_1$
+

$g_3$
+

$g_9$

$f_{10}$
=

$g_1$
+

$g_2$
+

$g_5$
+

$g_{10}$

$f_{11}$
=

$g_1$
+

$g_{11}$

$f_{12}$
=

$g_1$
+

$g_2$
+

$g_3$
+

$g_4$
+

$g_6$
+

$g_{12}$

……

现在反过来，用

$f$
表示

$g$
。

$g_1$
=

$f_1$

$g_2$
=

$f_2$
–

$f_1$

$g_3$
=

$f_3$
–

$f_1$

$g_4$
=

$f_4$
–

$f_2$

$g_5$
=

$f_5$
–

$f_1$

$g_6$
=

$f_6$
–

$f_3$
–

$f_2$
+

$f_1$

$g_7$
=

$f_7$
–

$f_1$

$g_8$
=

$f_8$
–

$f_4$

$g_9$
=

$f_9$
–

$f_3$

$g_{10}$
=

$f_{10}$
–

$f_5$
–

$f_2$
+

$f_1$

$g_{11}$
=

$f_{11}$
–

$f_1$

$g_{12}$
=

$f_{12}$
–

$f_6$
–

$f_4$
+

$f_2$

……

根据上面的部分，我们发现了类似于这样的这样的式子:

$g_n$
=

$\sum_{d|n}f_d$
*

$?$

我们还可以发现

$?$
的值对于一个定值

$d$
，我们可以发现

$n$
的不同，会导致

$?$
的值不同，

但我们发现

$?$
的值与

$n \over d$
有关系，所以我们可以把

$?$
看成某个当自变量为

$n \over d$
的函数的函数值，我们设这个函数为

$mu(i)$
。

则原式子可以写成:

$g_n$
=

$\sum_{d|n}f_d$
*

$mu({n \over d})$

内容

$\mu_{d}$
为莫比乌斯函数，定义如下:

1、当

$d$
=

$1$
，

$\mu{(d)}$
=1

2、若

$d$
=

$P_1$
*

$P_2$
*

$P_3$
* …… *

$P_k$
，其中

$P_i$
(1<=i<=k)为

互异

的素数，则

$\mu {(d)}$
=

$(-1)^k$

3、其余情况，

$\mu{(d)}$
=0

莫比乌斯反演的内容如下:

如果满足

$f_n$
=

$\sum_{d|n}g_d$

则存在

$g_n$
=

$\sum_{d|n}f_d$
*

$\mu {({n \over d})}$

$\mu$
函数的性质

现在给出莫比乌斯函数

$\mu$
的两个性质。

性质1、

$\mu$
为积性函数。

积性函数的定义为，如果

$a$
，

$b$
两数互质，就会满足

$f(a*b)$
=

$f(a)$
*

$f(b)$
,那我们就说这个函数为积性函数。

这个证明没什么难的，对

$a$
和

$b$
的值按照

$\mu$
函数定义分类讨论一下就可以证出了。

性质2、对于任意正整数

$n$
,有

(1)若

$n$
=1，

$\sum_{d|n}\mu{(d)}$
=1

(2)若

$n$
>1，

$\sum_{d|n}\mu{(d)}$
=0

证明如下:

<1>当

$n$
=1时，

$\sum_{d|n}\mu{(d)}$
=

$\mu(1)$
=1，得证。

<2>当

$n$
>1时，设

$d$
=

$P_1^{t_1}$
*

$P_2^{t_2}$
*

$P_3^{t_3}$
*

$P_4^{t_4}$
* ….. *

$P_k^{t_k}$

当

$t_i$
>1时，

$\mu(d)$
=0，所以我们只讨论

$t_i$
=0或1 的情况。

假设

$d$
含有

$n$
的

$e$
个互不相同质因数，且质因数的指数为1，这样的

$d$
的

$\mu$
值为

$(-1)^e$
这样的

$d$
有

$C_{k}^{e}$
个。

则

$\sum_{d|n}\mu (d)$
=

$\sum_{e=0}^{k}$

$C_{k}^{e}$

$(-1)^e$
=

$\sum_{e=0}^{k}$

$C_{k}^{e}$

$(-1)^e$
*

$1^{(k-e)}$

根据牛顿二项式定理

$(a$
+

$b)^n$
=

$\sum_{i=0}^{n}$

$C_{n}^{i}$
*

$a^ib^{(n-i)}$

可知

$\sum_{e=0}^{k}$

$C_{k}^{e}$
*

$(-1)^e$
*

$1^{(k-e)}$
=

$($
–

$1$
+

$1)^k$
=0，即

$\sum_{d|n}\mu{(d)}$
=0，得证。

证明

有了

$\mu$
函数的性质，我们就可以证出莫比乌斯反演的正确性了。

$\sum_{d|n}f_d$
*

$\mu {({n \over d})}$

=

$\sum_{d|n}\mu {(d)}$
*

$f({n \over d})$

=

$\sum_{d|n}\mu {(d)}$
*

$\sum_{i|{n \over d}}$

$g(i)$

交换主体，原式等价于

$\sum_{i|n}$

$g(i)$
*

$\sum_{d|{n\over i}}$

$\mu(d)$

根据

$\mu$
函数

的

性质2

可知

(1)当

$i=n$
时，

$n \over i$
=1，所以

$\sum_{d|{n\over i}}$

$\mu(d)$
=

$1$
，因此

$g(i)$
的系数为1。

(2)当

$i<n$
时，

$n \over i$
>1，所以

$\sum_{d|{n\over i}}$

$\mu(d)$
=

$0$
，因此

$g(i)$
的系数为0。

综上所述

$\sum_{i|n}$

$f(i)$
*

$\sum_{d|{n\over i}}$

$\mu(d)$
=

$g(i_1)$
*

$0$
+

$g(i_2)$
*

$0$
+……+

$g(n)$
*1=

$g(n)$

即

$g_n$
=

$\sum_{i|n}$

$f(i)$
*

$\sum_{d|{n\over i}}$

$\mu(d)$
=

$\sum_{d|n}f_d$
*

$\mu {({n \over d})}$
，得证。

$\mu$
的求值

关于

$\mu$
的求值可以用线性筛法求素数求得。

如果不会线性筛法可以看我写的博客，链接如下:

http://blog.csdn.net/xianhaoming/article/details/50954056

程序如下(Pascal)

for i:=1 to n do
begin
    if bz[i]=false then
    begin
        inc(o);
        s[o]:=i;  
        mu[i]:=true; //素数的mu值为(-1)^1=-1
    end;
    for j:=1 to o do
    begin 
        bz[i*s[j]]:=true;
        if (i mod s[j]=0) or (i*s[j]>n) then 
        begin
            mu[i*s[j]]=0; //如果i mod s[j]=0 说明i*s[j]含有至少两个相同的素因子，所以mu的值为0.
            break;
        end;  
        mu[i*s[j]]:=mu[i]*mu[s[j]]; //根据mu是一个积性函数可得。(i和s[j]互质)
    end;
end; //每个合数和质数都会被搜到且仅被搜到一次，故时间复杂度为O(n)