组合数学上莫比乌斯反演证明不太好懂，可以先从数论及其应用这本书入手。

设f为算术函数，f的和函数F(n) = sigma(f(d))(d|n) 它是根据f的值决定的。

那么是否存在一种关系用F求出f我们令n=1,2,3...8则此时有

F(1) = f(1)

F(2) = f(1) + f(2)

F(3） = f(1) + f(3)

....

F(8) = f(1) + f(2) + f(4) +f(8)

我们可以解除f(n)

f(1) = F(1)

f(2) =F(2) - F(1)

..

f(8) = F(8) - F(4)

注意到f(n)是形式为+-F(n/d)的一些项的和，所以可能存在这样的等式

f(n) = sigma(u(d)F(n/d));

其中u是算术函数等式成立的话，我们可以计算出u(1) = 1u(2) = -1

u(7)= -1 u(8) = 0又有F(p) =f(1) + f(p)给出f(p) = F(p) - F(1)其中p是素数

则u(p) = -1又因为F(p*p) = f(1) + f(p) + f(p*p)

f(p*p) = F(p*p) - (F(p)-F(1)) -F(1) = F(p*p) -F(p)

u(p*p) = 0所以对于任意的素数p切k>1有u(p^k) = 0

定义莫比乌斯函数u(n)定义

u(n) = 1 (n=1)

        = (-1)^r (n=p1p2..pr,其中pr为不同的素数) 

        = 0

例题：

u(330) = u(2.3.5.11) = (-1)^4 = 1 ,u(660) = u(2^2 .3 .5 .11) = 0

莫比乌斯函数u(n)是乘性函数

假设m与n是互素的正整数，为了证明u(n)是乘法性质函数证明u(n) = u(m)u(n)

考虑n=1或者m=1的情况成立

假设m和n中至少一个被素数平方整除，那么mn也被素数平方整除则u(mn) = 0

考虑M和n都不会含有大于1的素数的平方因子，m = p1p2..pn

n = q1q2..qn其中q1q2..qn是不同的素数,由于mn互素，则mn是s+t个不同的互素乘积

所以u(mn) = (-1)^(s+t) = (-1)^s (-1)^t = u(m)u(n)

莫比乌斯函数的和函数在n出的值F(n) = sigma(u(d))(d|n)满足

F(n) = 1 (n=1) F(n) = 0(n>1)

证明如下：n=1的时候F(1) = sigma(u(d)) = u(1) = 1

n>1的时候，假设p是素数，k是正整数

F(p^k) = sigma(u(d)) = u(1) + u(p) + u(p*p) +...u(p^k)

= 1+ (-1) +0 + 0... = 0;

假设n是大于1的正整数，素数分解为n = p1^a1p2^a2..pt^at所以F(n) = F(p1^a1)...F(pt^at)

从而F(n) = 0

莫比乌斯反演公式若f是算术函数F为f的和函数

F(n) = sigma(f(d))(d|n)则对于任意正整数n有f(n) = sigma(u(d)F(n/d)) (d|n)

sigma(f(d))(d|n) = sigma(u(d)sigma(f(e)(e|n/d) )) = sigma(sigma (u(d))f(e)) (e|n/d)

因为d|n e|(n/d)同样有e|n 和 d|(n/e) 

所以化简为 sigma( sigma( f(e) u(d))(d|(n/e)) (e|n))

由于 sigma (u(d) ）= 0  除非 n/e = 1

sigma(u(d)F(n/d)) (d|n) = f(n) *1 = f(n)

入门题：

http://blog.csdn.net/qw4990/article/details/14055183