反演

符号

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

莫比乌斯函数

$$\mu (x):=\{\begin{array}{ll}1,& n=1\\ 0,& \text{n 含有次数大于 1 的因子}\\ (-1{)}^k,& \text{其他情况，其中 k 为 x 的本质不同质因子个数}\end{array}$$

可以用线性筛处理出莫比乌斯函数。

狄利克雷卷积

设 $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$
4. 积性函数的乘积、狄利克雷卷积还是积性函数

常用性质

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$
5. $\gcd (n,m)={\sum }_{d|n}\phi (d)[d|m]$，用性质 2 证明
6. $\epsilon (\gcd (n,m))={\sum }_{d|\gcd (n,m)}\mu (d)$，用性质 1 证明

莫比乌斯反演

形式一：因子

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

$$f(n)=\sum _{d|n}g(d)\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.$$

形式二

组合意义：

• $f_n$ 表示任一大小为 $n$ 的集合的子集方案数（不一定是个数）之和，不同集合的子集之间可以重复；
• $g_n$ 表示任一大小为 $n$ 的集合的方案数。

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

形式三

组合意义：

• $f_n$ 表示任一大小为 $n$ 的集合的超集方案数（不一定是个数）之和，不同集合的超集之间可以重复；
• $g_n$ 表示任一大小为 $n$ 的集合的方案数之和。

$$f(n)=\sum _{i=n}^{\infty }\left(\genfrac{}{}{0ex}{}{i}{n}\right)g(i)\iff g(n)=\sum _{i=n}^{\infty }(-1{)}^{i-n}(\genfrac{}{}{0ex}{}{i}{n})f(i).$$