反演

符号

1. 元函数 $\epsilon (n):=[n=1]$
2. 常数函数 $1(n):=1$
3. 恒等函数 $\mathrm{id}(n):=n$

狄利克雷卷积

设 $f(n)$ 和 $g(n)$ 是两个积性函数，则

$$(f\ast g)(n):=\sum _{d|n}f(d)g\left(\frac{n}{d}\right).$$

性质

1. 交换律 $f\ast g=g\ast f$
2. 结合律 $(f\ast g)\ast h=f\ast (g\ast h)$
3. 分配律 $(f+g)\ast h=f\ast h+g\ast h$

常用卷积关系

1. ${\sum }_{d|n}\mu (n)=[n=1]\iff \mu \ast 1=\epsilon$
2. ${\sum }_{d|n}\phi (d)=n\iff \phi \ast 1=\mathrm{id}$
3. ${\sum }_{d|n}\mu (d)\frac{n}{d}=\phi (n)\iff \mu \ast \mathrm{id}=\phi$
4. $f\ast \epsilon =f$

莫比乌斯反演

形式一：因子

若 $f(n)$ 和 $g(n)$ 是积性函数，则

$$f(n)=\sum _{d|n}g(n)\iff g(n)=\sum _{d|n}\mu (d)f\left(\frac{n}{d}\right).$$

形式二：倍数

若 $f(n)$ 和 $g(n)$ 是积性函数，则

$$f(n)=\sum _{n|d}g(d)\iff g(n)=\sum _{n|d}\mu \left(\frac{d}{n}\right)f(d).$$

二项式反演

$$f_n=\sum _{i=0}^n(-1{)}^i(\genfrac{}{}{0ex}{}{n}{i})g_i\iff g_n=\sum _{i=0}^n(-1{)}^i\left(\genfrac{}{}{0ex}{}{n}{i}\right)f_i.$$