莫比乌斯反演

前言

很早之前就像讲一讲莫比乌斯反演，但由于事务较为繁忙，一直耽误至今。一方面，莫比乌斯反演是数论中非常重要的一个变换，另一方面，我的博客名也受此启发而得（虽然莫比乌斯反演和莫比乌斯环没有半毛钱关系）。

废话不多说，下面我们进入正题。

莫比乌斯函数

要想学习莫比乌斯反演，首先必须了解的就是莫比乌斯函数 \(\mu(d)\) 。

什么是莫比乌斯函数呢？下面是它的定义：

1. \(\mu(1)=1\)；
2. 当 \(d\) 为素数时， \(\mu(d)=-1\)；
3. 当 \(d\) 为合数时，其必能唯一地表示成若干素数之积，不妨令

若 \(d\) 中 \(k\) 个不同的质因子中有任一项的系数 \(m_i\) 大于等于2，则 \(\mu(d)=0\) ,否则 \(\mu(d)=(-1)^k\) 。

由此，我们初步了解了莫比乌斯函数 \(\mu(d)\) 的定义。当然，它有一些非常有趣的性质：

1. 对于任意正整数 \(n\) ，\(\sum\limits_{d|n}{\mu(d)}=[n=1]\) （ \(d|n\) 的意思是 \(d\) 整除 \(n\) ， \([n=1]\) 表示只有当 \(n=1\) 时为 \(true(1)\) ，否则为 \(false(0)\) ）。
2. 对于任意正整数 \(n\) ，\(\sum\limits_{d|n}{\frac{\mu(d)}{d}}=\frac{\phi(n)}{n}\) ( \(\phi(n)\) 为欧拉函数）。

其中第一条性质尤为重要，具体该怎么证明呢？

首先当 \(n=1\) 时，其约数 \(d\) 只有 \(1\) ，所以 \(\sum\limits_{d|1}{\mu(d)}=\mu(1)=1\)。

当 \(n\geq 2\) 时，由离散数学的知识，\(n\) 必能表示成若干素数的乘积且唯一（这个用反证法即可证明），即

下面如何求 \(\sum\limits_{d|n}{\mu(d)}\) 呢？我们需要枚举 \(n\) 的约数 \(d\) 。显然， \(d\) 同样可以表示为若干质数的乘积（质数的幂可以为0）。对于分解成质数之积后存在一个质数的幂次大于1的 \(d\) 我们并不需要关注，因为这样的 \(d\) 的 \(\mu(d)=0\) 。我们只需要关注分解后所有的质数的幂次都小于等于1的 \(d\)。

这样的 \(d\) 到底有多少个呢？根据简单的排列组合知识可知共有 \(2^k\) 个（\(k\) 为 \(n\) 分解后不同质数的个数）。我们要将这 \(2^k\) 个进行分类。

其中分解后质数的个数为偶数（包括0）的共有\(\sum\limits_{i=0}^{\lfloor\frac{k}{2}\rfloor\cdot 2}{C_k ^i}\) 个，奇数的共有\(\sum\limits_{i=0}^{\lfloor\frac{k-1}{2}\rfloor\cdot 2+1}{C_k ^i}\) 个。

组合数中有一条重要的性质，就是奇数项之和等于偶数项之和，也就是说上面两个式子是相等的。也就是说 \(n\) 的约数 \(d\) 分解成若干幂次为1的质数之积后，质数个数为奇数的 \(d\) 与质数个数为偶数的 \(d\) 的个数相等。

再回到莫比乌斯函数本身，满足 \(\mu(d)=1\) 和 \(\mu(d)=-1\) 的 \(d\) 的个数相同，所以 \(\sum\limits_{d|n}{\mu(d)}=0\; (n\geq 2)\) 。

由此，第一条性质证明结束。

第二条性质证明比较难，涉及到欧拉函数的知识，这篇文章就不重点介绍了。

莫比乌斯反演

经过长篇幅的介绍莫比乌斯函数后，我们现在终于可以迎来本文的核心：莫比乌斯反演。

下面是莫比乌斯反演定理：

对于定义在非负整数集合上的两个函数 \(F(n)\) 和 \(f(n)\) ，并且满足条件：

则有结论

有定理就有证明，下面我就简单地证明一下：

倒数第二步的推导需要反过来思考（枚举约数 \(i\) )，至于最后一步就用到了之前的第一条性质，只有当 \(\frac{n}{i}=1\) 即 \(i=n\) 时 \(\sum\limits_{d|\frac{n}{i}}{\mu(d)}=1\) ，其余情况皆为 \(0\) ，所以最后推得结果为 \(f(n)\) 。

由此，莫比乌斯反演的介绍也差不多结束了。码字不易，感谢关注。