反演 - 洛谷保存站

## 本质

对于函数 $f$ 和 $g$，构造两个二元函数 $a$ 和 $b$，使得满足
$$
f(n)=\sum_{i=0}^{n}a(n,i)g(i)\\
g(n)=\sum_{i=0}^{n}b(n,i)f(i)
$$

已知 $f$ 求 $g$ 的过程称为反演。

---

将 $g$ 带入得到
$$
\begin{aligned}
f(n)&=\sum_{i=0}^{n}a(n,i)\sum_{j=0}^{i}b(i,j)f(j)\\
&=\sum_{j=0}^{n}f(j)\sum_{i=j}^{n}a(n,i)b(i,j)
\end{aligned}
$$

显然 $b$ 需要满足
$$
\sum_{i=j}^{n}a(n,i)b(i,j)=[j=n]
$$

证明反演成立等价于证明该式。

## 二项式反演

$$
f(n)=\sum_{i=0}^{n}\binom{n}{i}g(i)\\
g(n)=\sum_{i=0}^{n}(-1)^{n-i}\binom{n}{i}f(i)
$$

即证 $\displaystyle
\sum_{i=j}^{n}\binom{n}{i}\binom{i}{j}(-1)^{i-j}=[j=n]$。

$$
\begin{aligned}
\sum_{i=j}^{n}\binom{n}{i}\binom{i}{j}(-1)^{i-j}&=\binom{n}{j}\sum_{i=0}^{n}\binom{n-j}{i-j}(-1)^{i-j}\\
&=\binom{n}{j}\sum_{i=0}^{n-j}\binom{n-j}{i}(-1)^i\\
&=\binom{n}{j}0^{n-j}
\end{aligned}
$$

当且仅当 $n=j$ 时原式为 $1$。

## 斯特林反演

$$
f(n)=\sum_{i=0}^{n}{n\brace i}g(i)\\
g(n)=\sum_{i=0}^{n}(-1)^{n-i}{n\brack i}f(i)
$$

考虑两个式子

$$
x^n=\sum_{i=0}^{n}{n\brace i}x^{\underline{i}}\\
x^{\underline{i}}=\sum_{i=0}^{n}(-1)^{n-i}{n\brack i}x^i

带入得到
$$
\begin{aligned}
x^n&=\sum_{i=0}^{n}{n\brace i}\sum_{j=0}^{i}(-1)^{i-j}{i\brace j}x^j\\
&=\sum_{j=0}^{n}x^{j}\sum_{i=j}^{n}{n\brace i}(-1)^{i-j}{i\brack j}
\end{aligned}
$$

所以直接得到
$$
\sum_{i=j}^{n}{n\brace i}(-1)^{i-j}{i\brace j}=[j=n]
$$

正在渲染内容...