反演笔记

前言

之前写的有点零散,现在整理一下。


反演是什么

  • 意义为已知一个函数(在OI通常为数列)对另一个函数的关系,推导出另一个函数对该函数的关系。
  • 因此能反演的,函数的关系一定是双向的。
  • 我们不妨把关系定义为一个矩阵 $\mathcal{A}[n,m]$ ,表示函数 $f(n)$ 与 $g(m)$ 的关系,写成通俗形式是这样子的:

$$ f(n)=\sum_{m=1}\mathcal{A}[n,m]g(m) $$


反演基本定理及推论

那么我们如何找到关系矩阵 $\mathcal{A}$ 的逆关系矩阵 $\mathcal{B}$ ,也即:

$$ g(m)=\sum_{m=1}\mathcal{B}[m,n]f(n) $$

定理

$$ \mathcal{A}*\mathcal{B}=\sum_{i=1}\mathcal{A}[n,i]*\mathcal{B}[i,m]=[n=m]=I $$

证明: 从定义出发, $f(n)=\sum\limits_{m=1}\mathcal{A}[n,m]g(m)=\sum\limits_{m=1}A[n,m]\sum\limits_{d=1}B[m,d]f(d)=\sum\limits_{d=1}[n=d]f(d)$ 。

推论

  • 互逆矩阵转置之后依旧互逆。
  • $-1$ 的幂可以在系数中移动

$$ \sum_{i=1}(-1)^i\mathcal{A}[n,i](-1)^m\mathcal{B}[i,m]=[n=m] $$

乘上 $(-1)^{m-n}$ 即可得到另外一种形式,但本质相同。

二项式反演

有了上面的基础,我们来看第一个例子

$$ f(n)=\sum_{k=1}\dbinom{n}{k}g(k)\Longleftrightarrow g(n)=\sum_{k=1}(-1)^{n-k}\dbinom{n}{k}f(k) $$

证明: $\sum\limits_{k=1}(-1)^{k-m}\dbinom{n}{k}\dbinom{k}{m}=\sum\limits_{k=1}(-1)^{k-m}\dbinom{n}{m}\dbinom{n-m}{k-m}=\dbinom{n}{m}(1+-1)^{n-m}=[n=m]$

根据上面的形式,可以推导出下面三种形式:

$$ \begin{aligned}f(n)=\sum_{k=1}(-1)^{k}\dbinom{n}{k}g(k)&\Longleftrightarrow g(n)=\sum_{k=1}(-1)^k\dbinom{n}{k}f(k)\\f(n)=\sum_{k=n}^m\dbinom{k}{n}g(k)&\Longleftrightarrow g(n)=\sum_{k=n}^m(-1)^{k-n}\dbinom{k}{n}f(k)\\f(n)=\sum_{k=n}^m(-1)^k\dbinom{k}{n}g(k)&\Longleftrightarrow g(n)=\sum_{k=n}^m(-1)^{k}\dbinom{k}{n}f(k)\end{aligned} $$

第一种和第三种比较常用。