莫比乌斯反演Mobius inversion

数论部分

▎什么是莫比乌斯反演?

☞『引入』

首先来抛出一个定义，一个随随便便的函数：

$$F(n)=\sum_{d|n}f(d)$$
$f$是个什么玩意的嘞？这个东西不用管，它可以随便理解成一种函数。
d|n是什么呢？就是说$F(n)$等于所有的可以被n整除的d的$f(d)$的总和。
举个例子：

• $F(1)=f(1)$
• $F(2)=f(1)+f(2)$
• $F(3)=f(1)+f(3)$
• $F(4)=f(1)+f(2)+f(4)$
• $F(5)=f(1)+f(5)$
• $F(6)=f(1)+f(2)+f(3)+f(6)$
• $F(7)=f(1)+f(7)$
• $F(8)=f(1)+f(2)+f(4)+f(8)$

发现了什么规律？

☞『推导』

又上面的一堆东西推出：

• $f(1)=F(1)$
• $f(2)=F(2)-F(1)$
• $f(3)=F(3)-F(1)$
• $f(4)=F(4)-F(2)$
• $f(5)=F(5)-F(1)$
• $f(6)=F(6)-F(3)-F(2)-F(1)$
• $f(7)=F(7)-F(1)$
• $f(8)=F(8)-F(4)$

这样规律就越来越明显了。

☞『莫比乌斯反演公式』

易得：

$$F(n)=\sum_{d|n}f(d) => f(n)=\sum_{d|n} \mu(d)F( \frac{n}{d})$$
其中的$\mu$是莫比乌斯函数。

☞『莫比乌斯函数』

$\mu$是莫比乌斯函数，这个函数表示起来长这个样：

$$\mu(d)= \begin{cases} 1& d=1 \\ (-1)^k& d=p_1+p_2+p_3+…+p_k\\ 0& others \end{cases}$$
正因为此，莫比乌斯函数有一个特别的性质。

▎莫比乌斯函数的性质

☞『性质』

现在来思考这个东西等于什么：

$$\sum_{d|n} \mu(d)$$
这玩意儿得分类讨论的。
$$\sum_{d|n} \mu = \begin{cases} 1& n=1\\ 0& n>1 \end{cases}$$

☞『证明』

为什么呢？证明如下：

• 当n=1时，显然d只有等于1的情况，当d等于1时$\mu(d)$显然等于1。
• 当n>1时，我们可以试着拆分一下：
• n=$p_1^{a_1} p_2^{a_2} p_2^{a_3} …… p_k^{a_k}$
• 当$\mu(d)$不等于0时，显然$a_1,a_2,a_3,……,a_k$都要等于1。
• 那么我们设质因数个数为r的因子有$C_k^r$个。
• 根据莫比乌斯函数的取值情况，我们可知：
• $$\sum_{d|n}=C_k^0-C_k^1+C_k^2-C_k^3+C_k^4-C_k^5+……+(-1)^kC_k^k => \sum_{d|n}=\sum_{i=0}^k(-1)^iC_k^i$$
• 所以，我们现在的问题就是如何证明 $$\sum_{i=0}^n(-1)^iC_n^i=0$$
• 我们恰好需要用到一个叫做二项式定理的东西。
• 这玩意长这样： $$(x+y)^n=\sum_{i=0}^nC_n^ix^iy^{n-i}$$
• 当我们将x=-1，y=1代入后就长这样： $$0=\sum_{i=0}^n(-1)^iC_n^i$$ 右边完全一样啊，左边等于0。
• 证毕