反演的本质

有两个式子： $$ \begin{align} G_n=\sum_{i=0}^na_{n,i}F_i\\ F_n=\sum_{i=0}^nb_{n,i}G_i \end{align} $$ 代入得： $$ G_n=\sum_{i=0}^na_{n,i}\sum_{j=0}^ib_{i,j}G_j\\ G_n=\sum_{j=0}^nG_j\sum_{i=j}^na_{n,i}b_{i,j} $$ 也就是说如果 $\sum_{j=i}^na_{n,j}b_{j,i}=[n=i]$ ，那么两个式子就可以相互反演。

莫比乌斯反演

$$ \sum_{j=i}^n[j|n][i|j]\mu(\frac j i)=[n=i] $$

于是有： $$ \begin{align} f(n)&=\sum_{d=1}^n[d|n]g(d)\\ g(n)&=\sum_{d=1}^n[d|n]\mu(\frac n d)f(d) \end{align} $$

二项式反演

$$ \sum_{j=i}^n{n\choose j}{j\choose i}(-1)^{j-i}=[n=i] $$

于是有： $$ \begin{align} f(n)&=\sum_{i=1}^n{n\choose i}g(i)\\ g(n)&=\sum_{i=1}^n(-1)^{n-i}{n\choose i}f(d) \end{align} $$

子集反演

$$ \sum_{i\subseteq j,j\subseteq n}(-1)^{|n|-|j|}=[n=i] $$

于是有： $$ \begin{align} f(S)&=\sum_{T\subseteq S}g(T)\\ g(S)&=\sum_{T\subseteq S}(-1)^{|S|-|T|}f(T) \end{align} $$

斯特林反演

$$ \sum_{j=i}^n\left\{\begin{aligned}n\\j\,\end{aligned}\right\}\left[\begin{aligned}j\\i\end{aligned}\right](-1)^{j-i}=[n=i]\\ \sum_{j=i}^n\left[\begin{aligned}n\\j\,\end{aligned}\right]\left\{\begin{aligned}j\\i\end{aligned}\right\}(-1)^{j-i}=[n=i]\\ $$

于是有： $$ \begin{align} f(n)&=\sum_{i=1}^n\left\{\begin{aligned}n\\i\,\end{aligned}\right\}g(i)\\ g(n)&=\sum_{i=1}^n(-1)^{n-i}\left[\begin{aligned}n\\i\,\end{aligned}\right]f(i) \end{align} $$

单位根反演

拉格朗日反演