查看“︁Möbius 反演”︁的源代码

[[分类:数论函数]]
[[分类:以 Möbius 命名]]
{{InfoBox
|name=莫比乌斯反演
|eng_name=Möbius inversion formula
|name=莫比乌斯反演公式
}}
{{InfoBox
|name=莫比乌斯变换
|eng_name=Möbius transform
}}
{{InfoBox
|name=莫比乌斯逆变换
|eng_name=inverse Möbius transform
}}
'''<ins>莫比乌斯</ins>反演公式'''('''Möbius inversion formula''')指两个[[数论函数]]之间的关系，其中之一相当于另一个对全部正因数使用并求和。
可以用于难以求解的函数分解成对因数或倍数的另一个函数求和。

== 定义 ==

对两个数论函数 <math>f</math> 和 <math>F</math> ，若

<math>F(n) = \sum_{d \mid n} f(d)</math>

其中 <math>\sum_{d \mid n}</math> 代表对全部正因数求和，此时有

<math>f(n) = \sum_{d \mid n} \mu(d) F\left(\frac{n}{d}\right)</math>

其中 <math>\mu(n)</math> 是 [[Möbius 函数]]。
并称函数 <math>F(n)</math> 是函数 <math>f(n)</math> 的'''Möbius 变换'''('''Möbius transform''')，函数 <math>f(n)</math> 是函数 <math>F(n)</math> 的'''Möbius 逆变换'''('''inverse Möbius transform''')，这一对公式被称为 '''Möbius 反演公式'''('''Möbius inversion formula''')。

=== Dirichlet 卷积形式 ===

可以通过 [[Dirichlet 卷积]]描述这一过程，即：

<math>F = 1 * f \Leftrightarrow f = \mu * F</math>

=== 倍数版本 ===

对两个数论函数 <math>f</math> 和 <math>F</math> ，若

<math>F(n) = \sum_{n \mid m} f(n)</math>

其中 <math>\sum_{n \mid m}</math> 代表对全部正倍数求和，此时有

<math>f(n) = \sum_{n \mid m} \mu(m) F\left(\frac{m}{n}\right)</math>

其中 <math>\mu(n)</math> 是 Möbius 函数。

== 性质 ==

<math>F(1)=f(1)</math> ，且若 <math>n = p_1^{k_1} p_2^{k_2} \dots p_m^{k_m}</math> 是[[标准质因数分解]]，则 <math>F(n) = \sum_{h_1 = 1}^{k_1} \sum_{h_2 = 1}^{k_2} \dots \sum_{h_m = 1}^{k_m} f(p_1^{h_1} p_2^{h_2} \dots p_m^{h_m})</math> 。

[[乘性函数]]进行 Möbius 反演后得到的也是乘性函数，反过来也成立。因此 <math>F(n) = \prod_{j=1}^m (1 + f(p_j) + \dots + f(p_j^{k_j})) = \prod_{p^h\|n} (1 + f(p) + \dots + f(p^h))</math> ，其中 <math>\prod_{p^h\|n}</math> 表示对所有[[恰整除]] <math>n</math> 的 <math>p,h</math> 求和。

进一步地，如果是一个[[完全乘性函数]]，指数可以拿出来，有 <math>F(n) = \prod_{j=1}^m (1 + f(p_j) + \dots + (f(p_j))^{k_j}) = \prod_{p^h\|n} (1 + f(p) + \dots + (f(p))^h)</math> ，变成一系列等比级数的乘积。

特别地，对于乘性函数 <math>f(n)</math> 和 <math>F(n)</math> ，有 <math>\sum_{d\mid n} \mu(d)f(d) = \prod_{p\mid n}(1 - f(p)), \sum_{d\mid n} (\mu(d))^2f(d) = \prod_{p\mid n}(1 - f(p)</math> 以及 <math>f(p^k) = F(p^k) - F(p^{k-1})</math> ，并且可以利用乘性计算任意合数对应的函数值。

Möbius 反演中的加法实际上只要求是交换群上的运算，若把式中的累和与乘法改为累积与乘方，依旧成立，即 <math>F(n) = \prod_{d\mid n} f(d) \Rightarrow f(n) = \prod_{d\mid n} F\left(\frac{n}{d}\right)^{\mu(d)}</math>。


{{数论函数}}