莫比乌斯反演 ( 二 ): 莫比乌斯反演定理
首先设两个任意函数F(x)和f(x), 定义运算:
[F(x)=sum _{d|x} f(d)
]
这时就可以用f(x)表示F(x):
[F(1)=f(1)\
F(2)=f(1)+f(2)\
F(3)=f(3)+f(1)\
F(4)=f(4)+f(2)+f(1)\
F(5)=f(5)+f(1) \
F(6)=f(6)+f(3)+f(2)+f(1)\
......
]
这时可以试着用F(x)表示f(x):
[f(1)=F(1)\
f(2)=F(2)-f(1)=F(1)\
f(3)=F(3)-f(1)=F(3)-F(1)\
f(4)=F(4)-f(2)-f(1)=F(4)-F(2)\
f(5)=F(5)-f(1)=F(5)-F(1)\
f(6)=F(6)-f(3)-f(2)-f(1)=F(6)-F(3)-F(2)+F(1)\
......
]
这里总结出几个推论: 设质数p, 则可以写出F(x)函数表示f(p)的公式
[ecause F(p)=f(1)+f(p)\F(p^2)=f(1)+f(p)+f(p^2)\ herefore f(p)=F(p^2)-F(p)
]
其余情况下, 对任意数n, f(n)是由其因数的F(x)函数, 都是由n的因数的F(x)函数值加减得到的, 对于每一项的正负, 和
莫比乌斯函数μ(x)有关, 这就牵扯到上一篇文章:莫比乌斯函数
[ecause mu(p^2)=0 \f(p)=F(p^2)-F(1)\ herefore f(n)=sum _{d|n} mu(d)F(frac nd)
]
这便是莫比乌斯反演定理.