反演公式

###反演

首先讲一下什么是反演，定义两个序列 $|F(n)|,|f(n)|$,$F_i=\alpha(i)f(i)$,表示|F(n)|与|f(n)|之间满足某种关系,

我们需要求得 $|f(n)|$,那么就可以通过反演公式求得 $f(i)=\beta(i)F(i)$.

###莫比乌斯反演

首先引入个函数, 莫比乌斯函数,记作 $\mu(x)$,令 $x=p_1^{a_1}p_2^{a_2}...p_k^{a_k}$,该函数有三种取值

$$\mu=\begin{cases}0,a_i \ge 2\\1,k \mod 2 = 0\\-1,k \mod 2 \ne 0\end{cases}$$

令 $S(x)=\sum\limits_{i|x}^{x}\mu(i),S(x)=\begin{cases}1,x=1\\0,x>1\end{cases}$

证明

对于 $x$ 与 $x$ 的任意一个约数 $t$,有

$$x=p_1^{a_1}p_2^{a_2}...p_k^{a_k}$$

$$t=p_1^{b_1}p_2^{b_2}...p_k^{b^k},0\le b_i \le a_i$$

对于任意一个含有大于2的指数的约数,我们可以不考虑,因为它对 $S(x)$ 无影响,那么我们就可以得到 $b_i=0,1$

于是就有$S(x)=C_k^0 (-1)^0+C_k^1 (-1)^1+...+C_k^k (-1)^k$

根据二项式定理$(a+b)^k=C_k^0 a^k b_0+C_k^1 a^{k-1} b_1+...+C_k^k a_0 b_k$

得到$S(x)=(1-1)^k=0$

证毕

若 $F(n)=\sum\limits_{d|n} f(d)$,则 $f(n)=\sum\limits_{d|n} \mu(d)F({\frac{n}{d}})$

证明

$$\sum\limits_{d|n} \mu(d)F_{\frac{n}{d}} = \sum\limits_{d|n} {\mu(d)\sum\limits_{i|\frac{n}{d}} f(i)}$$

考虑交换一下枚举的顺序, $i|\frac{n}{d} \Rightarrow i|n$, $i|\frac{n}{d} \Rightarrow d|\frac{n}{i}$

得到 $\sum\limits_{d|n} {\mu(d)\sum\limits_{i|\frac{n}{d}} f(i)} = \sum\limits_{i|n} f(i)\sum\limits_{d|\frac{n}{i}} \mu(d)$

仔细观察一下 $\sum\limits_{d|\frac{n}{i}} \mu(d)$,就等于 $S(\frac{n}{i})$

所以,当 $i = n$时, $\sum\limits_{d|n} \mu(d)F_{\frac{n}{d}} = f(i)$

证毕

关于莫比乌斯反演的另一种形式

若$F(n)=\sum\limits_{n|d}^\infty f(d)$,则 $f_n=\sum\limits_{n|d}^\infty \mu{\frac{d}{n}}F(d)$

证明过程与上面大同小异,令 $d`=\frac{d}{n}$

$$f(n)=\sum\limits_{n|d}^\infty \mu{d`} \sum\limits_{d|i}^\infty f(i)\\=\sum\limits_{n|i}^\infty f(i) \sum\limits_{d`|\frac{i}{n}}^\infty \mu{d`}=f(i)$$

###二项式反演

$$f(n)=\sum\limits_{i=0}^nC^i_n g(i)\Leftrightarrow g(n)=\sum\limits_{i=0}^n(−1)^{n−i}C^i_nf(i)$$

证明

$$\sum\limits_{i=0}^n (-1)^{n-i}C_n^i f(i)=\sum\limits_{i=0}^n (-1)^{n-i}C_n^i \sum\limits_{j=0}^i C^j_i g(j)\\=\sum\limits_{i=0}^n \sum\limits_{j=0}^i (-1)^{n-i}C_n^iC_i^j g(j)$$

$$C_n^iC_i^j=\frac{n!}{i!(n-i)!}\frac{i!}{j!(i-j)!}=\frac{n!}{j!(n-j)!}\frac{(n-j)!}{(n-i)!(i-j)!}=C_n^jC_{n-j}^{n-i}\\\Rightarrow \sum\limits_{i=0}^n (-1)^{n-i}C_n^i f(i)=\sum\limits_{i=0}^n \sum\limits_{j=0}^i (-1)^{n-i}C_n^jC_{n-j}^{n-i} g(j)$$

交换一下循环顺序

$$\sum\limits_{i=0}^n \sum\limits_{j=0}^i (-1)^{n-i}C_n^jC_{n-j}^{n-i} g(j)=\sum\limits_{j=0}^n \sum\limits_{i=j}^n(-1)^{n-i}C_n^jC_{n-j}^{n-i} g(j)=\sum\limits_{j=0}^n C_n^jg(j)\sum\limits_{i=j}^n(-1)^{n-i}C_{n-j}^{n-i}$$

我们着眼于 $\sum\limits_{i=j}^n (-1)^{n-i}C_{n-j}^{n-i}=\sum\limits_{k=0}^{n-j} (-1)^kC_{n-j}^k$

若 $n-j\ne 0$,根据二项式定理$\sum\limits_{k=0}^{n-j} (-1)^kC_{n-j}^k=(1-1)^{n-j}=0$

若 $n-j=0 \Rightarrow \sum\limits_{k=0}^{n-j} (-1)^kC_{n-j}^k=(1-1)^{n-j}=(-1)^0C_0^0=1$

则只有当 $j=n$ 时, $\sum\limits_{i=0}^n (-1)^{n-i}C_n^i f(i)=g(j)$

证毕

另一种形式 $f(k)=\sum\limits_{i=k}^n C_i^kg(i) \Leftrightarrow g(k)=\sum\limits_{i=k}^n (-1)^{i-k}C_i^kf(i)$