数论笔记：莫比乌斯反演 & 生成函数

· · 个人记录

写高联写到一题能用 GF 做的，查资料看到莫反。之前学 OI 时候一直没去看，干脆五一有空就补一下坑。

Mobius 函数

定义 \mu(x) 为莫比乌斯函数，其定义如下：

\mu(n)=\left\{\begin{aligned}&1\qquad\quad n=1\\&0\qquad\quad n\text{含相同素因子}\\&(-1)^k\quad\text{含}k\text{个相异素因子}\end{aligned}\right.

不妨设 n=\prod\limits_{i=1}^{k}p_i^{a_i}，则 n=1 时 \mu(n)=1 存在 a_i>1 时 \mu(n)=0，其余情况 \mu(n)=(-1)^k。莫比乌斯函数是积性函数，这即意味着对于 (s,t)=1 的两个正整数 s,t 存在 \mu(s\cdot t)=\mu(s)\cdot\mu(t)。于此同时，它还有一个广为人知的有趣性质：

\sum\limits_{d|n}\mu(d)=[n=1]

换言之，对于任意一个非 1 的整数，其所有因数的莫比乌斯函数值和为 0。这一点可以用迪利克雷卷积理解，从而它在迪利克雷式的生成函数中相当于 1/\zeta，也即黎曼函数的倒数，同时在迪利克雷卷积中作为 1 的逆元存在。下证：

设 n=\prod p_i^{c_i}，同时 n'=\prod p_i，也即每个素数取其一。进而写出他们的 \mu

\sum_{d|n}\mu(d)=\sum_{d|n'}\mu(d)=\sum C_k^i\cdot(-1)^i=0^k

上式是显而易见的，因为素因子个数超过一个的因数的 \mu 值等于 0，对和式没有贡献。通过二项式定理展开即可。为更好理解其和生成函数的联系，我们引入基本的生成函数概念。

基本生成函数

对于普通数列 \{a_n\} 而言，其 OGF 为：

F(x)=a_0+a_1x+a_2x^2\cdots=\sum_{i=0}^{\infty}a_ix^i

一般来说生成函数解决的是无穷数列的问题。此时将生成函数乘除 x 有平移作用，乘上全为 1 数列对应生成函数的封闭形式得到 S_n 的生成函数。此类处理手段颇为丰富有趣，读者可自行查阅相关资料。

但 OGF 在处理诸如 e^x 的泰勒展开式时略显乏力，因而我们引入 EGF，书写如下：

F(x)=a_0+a_1x+a_2\dfrac{x^2}{2!}+\cdots=\sum\limits_{i=0}^{\infty}a_i\dfrac{x^i}{i!}

通过将阶乘项表示为 EGF 正常携带的一部分，我们可以让函数更简单地与数列对应起来。与此同时 DGF 的写法也值得记录：

F(s)=a_1+\dfrac{a_2}{2^s}+\cdots=\sum\limits_{i=1}^{\infty}\dfrac{a_i}{i^s}

此处下标从 1 开始的理由是分母。

DGF 和黎曼函数

因而我们不妨将 \zeta 函数写出来：

\zeta(s)=1+\dfrac{1}{2^s}+\cdots=\sum\limits_{i=1}^{\infty}\dfrac{1}{i^s}

在 s=2 时是 巴塞尔问题，古早时期挖的坑，可能不会填了。总之可以看出 \zeta 函数事实上就是对应数列 \{1,1,1\cdots\} 的迪利克雷生成函数也即 DGF。

我们将两个 Dirichlet 生成函数相乘（也即求多项式卷积），不妨令他们的数列分别为 \{a_1,a_2,a_3\cdots\} 和 \{b_1,b_2,b_3\cdots\}，则比对分母的指数情况，不难发现 a_i\cdot b_j 的分母会是 (i\cdot j)^s，换个角度来看也就是新函数的第 n 项会等于其因数分解项乘积的加和。这是一个相当有趣的结论。

\zeta^2(s)=\sum\limits_{i=1}^{\infty}\sum_{d|n}\dfrac{a_db_{n/d}}{i^s}=\sum_{i=1}^{\infty}\dfrac{d(i)}{i^s}

又由于 a_i=b_i=1，内层和式应当等于 i 的因数个数，可以记作 d(i)。

\dfrac{1}{\zeta(s)}=\sum\limits_{i=1}^{\infty}\dfrac{\mu(i)}{i^s}

证明留诸读者。（其实是没时间证，可能也不会证。有证好的可以和我分享，感谢。）

莫比乌斯变换

令 f(n),g(n) 为两个数论函数。他们之间存在关系：

若 f(n)=\sum\limits_{d|n}g(d)，则存在 g(n)=\sum\limits_{d|n}\mu(d)f(\dfrac{n}{d})

这个式子的另一个形式是：

若 f(n)=\sum\limits_{d|n}g(d)，则存在 g(n)=\sum\limits_{d|n}\mu(\dfrac{n}{d})f(d)

此时 f(n) 是 g(n) 的莫比乌斯变换，反之称为莫比乌斯反演。不难看出 g(n) 的 Mobius 变换即为 g(n) 它与 1 的 Dirichlet 卷积。但我不会证，然后我去查了怎么证，它说有两种证法，此处给出较为直观的一种。

\sum\limits_{d|n}\mu(d)f(\dfrac{n}{d})=\sum_{d|n}\mu(d)\sum_{k|\frac{n}{d}}g(k)

先展开。然后调换求和顺序（自行查阅顺序调换的具体要求）：

\sum_{k|n}g(k)\sum_{d|\frac{n}{k}}\mu(d)=g(n)

如果不知道调换后为什么可以把第二个和式换掉，自行翻阅前文相关性质。

第二种证法即利用卷积，此处不赘述。

莫反可以做很多数论题目，并且在相当多推导中起到了至关重要的作用。按道理这里应该要有两三道例题及代码。可惜我现在是 MOer 写代码能力退化了，然后做题也用不着一些 OI 的技巧，所以就偷个懒不写了。

感谢阅读。