反演主要用于替换组合式求和，重点在于推式子，原理暂略。

二项式反演

形式 $0$：

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

形式 $1$：

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

形式 $2$：

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

这里默认数列具有有限支撑，即存在 $N$ 使得 $i>N$ 时 $f(i)=0$，从而两个看似无限的和实际都是有限和。令

$$F(x)=\sum _{i=0}^{N}f(i)x^i,G(x)=\sum _{i=0}^{N}g(i)x^i,$$

则正变换等价于 $G(x)=F(1+x)$，代入 $x-1$ 即得到逆变换。若用于真正的无限数列，必须另外保证相关级数收敛且允许交换求和次序；仅写成普通形式幂级数并不会自动使每个系数中的无限和有定义，还需要局部有限性或相应的拓扑收敛条件。

欧拉反演

Euler 函数恒等式为

$$n=\sum _{d\mid n}\phi (d).$$

对其使用 Möbius 反演，可得对应的反演式

$$\phi (n)=\sum _{d\mid n}\mu (d)\frac{n}{d}=n\sum _{d\mid n}\frac{\mu (d)}{d}.$$

因此这一节是 Möbius 反演在 Euler 函数上的特殊应用，而不是另一种独立的通用反演。

莫比乌斯反演

$$g(n)=\sum _{d\mid n}f(d)\iff f(n)=\sum _{d\mid n}\mu (d)g(\frac{n}{d})$$

特殊地，$\sum _{d\mid n}\mu (d)=[n=1]$

更特殊地，$\sum _{d\mid gcd(i,j)}\mu (d)=[gcd(i,j)=1]$

子集反演

以下 $S,T$ 均为同一个有限全集 $U$ 的子集。对子集方向求和时，有

$$g(S)=\sum _{T\subseteq S}f(T)\iff f(S)=\sum _{T\subseteq S}(-1{)}^{|S|-|T|}g(T).$$

另一组是对超集方向求和：

$$g(S)=\sum _{S\subseteq T\subseteq U}f(T)\iff f(S)=\sum _{S\subseteq T\subseteq U}(-1{)}^{|T|-|S|}g(T).$$

两组公式方向不同，第二组不能仅由第一组的前提推出。

单位根反演

设 $m\ge 1$，并在域 $K$ 上运算。要求 $m$ 在 $K$ 中可逆，且 $K$ 中存在一个 $m$ 次本原单位根 ${\omega }_m$。在复数域中可以取 ${\omega }_m=e^{2\pi i/m}$；在素域 ${\mathbb{F}}_p$ 中使用时，常见条件是 $m\mid (p-1)$，此时本原单位根和 $m^{-1}$ 都存在。

$${\displaystyle \frac{1}{m}}\sum _{i=0}^{m-1}({\omega }_m{)}^{i\times d}=[m\mid d]$$

扩展到 $d\equiv k(\mathrm{mod}m)$ 的情况：

$${\displaystyle \frac{1}{m}}\sum _{i=0}^{m-1}{\omega }_m^{i\times (d-k)}=[d\equiv k(\mathrm{mod}m)]$$

把这个形式放到多项式上：对于多项式 $f(x)=\sum _{i=0}^n{a}_i{x}^i$，求所有下标模 $m$ 同余于 $k$ 的系数之和。

$$\begin{array}{rl}\sum _{i=0}^n{a}_i[i\equiv k(\mathrm{mod}m)]& =\sum _{i=0}^n{a}_i\frac{1}{m}\sum _{j=0}^{m-1}{\omega }_m^{j(i-k)}\\ & =\frac{1}{m}\sum _{j=0}^{m-1}{\omega }_m^{-jk}\sum _{i=0}^n{a}_i({\omega }_m^j{)}^i\\ & =\frac{1}{m}\sum _{j=0}^{m-1}{\omega }_m^{-jk}f({\omega }_m^j).\end{array}$$

时间复杂度：$O(mT(n))$，其中 $T(n)$ 表示多项式单点求值的时间复杂度。

斯特林反演

$$f(n)=\sum _{i=0}^n\left\{\begin{array}{c}n\\ i\end{array}\right\}g(i)\iff g(n)=\sum _{i=0}^n(-1{)}^{n-i}\left[\begin{array}{c}n\\ i\end{array}\right]f(i)$$