反演

· · 个人记录

最近有点彷徨……正如钱老师所说，自己有些内耗

可能还是看到自己刚刚学的东西，很多曾经的同学两三年前就会了。。。感到有点失落。

而且自己的数据结构越来越不行了。今年NOIPT4什么都没想出来。还不知道怎样补......因为不知道问题所在

不如先放首光辉岁月听听吧

反演

1.什么是反演

将

F(n)=\sum\limits_{i}A_{n,i}G(i)

转换成

G(n)=\sum\limits_{i}B_{n,i}F(i)

的形式，叫做反演。

2.反演的性质

首先，我们可以发现

F=A*G$ 和 $G=B*F

于是 F=A*B*F 即 A*B=E (E 表示单位矩阵)，也就是说 A=B^{-1}

而且由于 (AB)^T=B^TA^T，我们将矩阵转置一下仍然是互逆的（不会上述性质的童鞋，只需要记住，把一对互逆的矩阵行列倒过来，俩人仍然互逆）

对于矩阵里有 (-1)^i 的，可以把它转移到另外一个矩阵里。可以得到无 -1 因子的矩阵和另一个矩阵互逆的结论。

3.反演的例子

这里 $A_{n,i}=(-1)^iC_n^i=(-1)^i\dbinom{n}{i}

证明：令 C=A^2，则 C_{i,j}=\sum\limits_k{A_{i,k}B_{k,j}}=\sum\limits_k{(-1)^{k-j}\dbinom{i}{k}\dbinom{k}{j}}=\dbinom{i}{j}\sum\limits_k(-1)^{k-j}\dbinom{i-j}{k}=\dbinom{i}{j}[i=j]=[i=j]

因此 C=E，证毕

如果有 f*A=g，那么有 g*A=f

这里用到了恒等式 \dbinom{i}{k}\dbinom{k}{j}=\dbinom{i}{j}\dbinom{i-j}{k-j}，从组合意义和代数角度都较为好证

还用到了恒等式 \sum\limits_k(-1)^k{\dbinom{n}{k}}=[n=0]，用的是二项式定理里面，(1-1)^n 的展开式。

[i=j]=C_{i,j}=\sum\limits_k{A_{i,k}B_{k,j}}=\sum\limits_k{\dbinom{i}{k}(-1)^{k-j}\dbinom{k}{j}}

我们发现，如果矩阵 A 满足 A_{n,i}=\dbinom{n}{i}，矩阵 B 满足 B_{n,i}=(-1)^{n-i}\dbinom{n}{i}，那么两者互逆。

也就是如果有 f*A=g，那么有 g*B=f

还可以用转置推出另外两个反演式子，此处省略。

斯特林数反演

先咕了。