反演公式
BzhH
·
·
个人记录
反演
首先讲一下什么是反演，定义两个序列 |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)
证毕