# 莫比乌斯反演

Donny
October 25, 2017
336
-

Tags in blue are handcrafted tags; Tags in green are generated using AutoTag.

## Mobius Inversion Formula

$$g(n)=\sum_{d|n} f(d) \hspace{1em} (n \geq 1)$$

$$f(n)=\sum_{d|n} \mu(d) g(n/d) \hspace{1em} (n \geq 1)$$

## Basic Concept

### 1. Convolution / 卷积

$$(f\ast g)(n)=\sum_{ij=n}f(i)g(j)$$

1. 交换律：$$f\ast g=g\ast f$$
2. 结合律：$$(f\ast g)\ast h=f\ast (g\ast h)$$
3. 存在单位元$$\iota$$. $$\iota\ast f=f$$. 不难知道$$\iota$$定义应为：
$$\iota(n)= \begin{cases} 1& n = 1 \\ 0& n \neq 1 \end{cases}$$

### 3. 莫比乌斯函数

$$u$$在卷积意义下的逆元，称为莫比乌斯函数$$\mu$$。即
$$u\ast \mu=\iota$$

$$\sum_{d|n} \mu(d) = \iota(n)$$

$$\mu$$ 定义为：
$$\mu(n)= \begin{cases} 1& \text{n is a square-free positive integer,} \\ & \text{with an even number of prime factors} \\ -1& \text{n is a square-free positive integer,} \\ & \text{with an odd number of prime factors} \\ 0& \text{n has a square prime factor} \end{cases}$$

$$\mu(n)= \begin{cases} 1& \text{n = 1} \\ (-1)^{k}& \text{n is a positive integer,} \\ & \text{with k distint prime factors} \\ 0& \text{other circumstances} \end{cases}$$

## Prove

$$f=g\ast u \iff g=f\ast \mu$$

\begin{align} f=g\ast u \Rightarrow& f\ast \mu=(g\ast u)\ast \mu \\ \Rightarrow& f\ast\mu=g\ast(u\ast\mu) \\ \Rightarrow& f\ast\mu=g\ast\iota \\ \Rightarrow& f\ast\mu=g \end{align}

\begin{align} g=f\ast\mu \Rightarrow& g\ast u=(f\ast\mu)\ast u \\ \Rightarrow& g\ast u=f\ast(\mu\ast u) \\ \Rightarrow& g\ast u=f\ast\iota \\ \Rightarrow& g\ast u=f \end{align}

## Reference

[1] 知乎 - 如何证明莫比乌斯反演 - Syu Gau 的回答
[2] Wikipedia Mobius Inversion Formula
ACM 相关题目（使我接触到莫比乌斯反演的博客）：
[1] forever97 - 莫比乌斯反演