二项式反演推导

2020-01-12 本文已影响0人 Tacmon_old

请大家注意：

因为作者写的文章中的梯等式公式总是莫名的显示错误，所以作者的许多文章中的梯等式都暴力拆成一步一个等式了。
造成的不适，请谅解。
同时，如果文章中还有其他错误，请联系作者，谢谢。

反演公式：
$f_n = \sum_{i=0}^{n} (-1)^i C(n,i) g_i \Leftrightarrow g_n = \sum_{i=0}^{n} (-1)^i C(n,i) f_i$
$f_n = \sum_{i=0}^{n} C(n,i) g_i \Leftrightarrow g_n = \sum_{i=0}^{n} (-1)^{n-i} C(n,i) f_i$

第一个式子的推导：

已知 $f_n=\sum_{i=0}^{n}(-1)^ig_i$
设： $g_n=\sum_{i=0}^{n}t_{n,i}f_i$ ，其中 $t_{n,i}$ 是待定的系数。
那么有：
$f_n = \sum_{i=0}^{n} (-1)^i C(n,i) \sum_{j=0}^{i} t_{i,j} f_j$
$f_n = \sum_{j=0}^{n} f_j \sum_{i=j}^{n} (-1)^iC(n,i)t_{i,j}$
可能有很多构造 $t_{i,j}$ 的方法，我们只考虑构造 $t_{i,j}$ 满足：
$[j=n] = \sum_{i=j}^{n} (-1)^i C(n,i) t_{i,j}$
注意到
$[n=0] = \sum_{i=0}^{n} (-1)^i C(n,i)$
那么
$[j=n] = \sum_{i=0}^{n-j} (-1)^i C(n-j,i)$
证明很显然， $[j=n] \Leftrightarrow [n-j=0]$
可以发现， $t_{i,j}$ 中应该有一个组合数因子，所以给上式配一个组合数：
$[j=n] = \sum_{i=0}^{n-j} (-1)^i C(n-j,i) C(n,j)$
又因为
$C(n-j,i)C(n,j) = C(n,i+j)C(i+j,j)$
所以有
$[j=n] = \sum_{i=0}^{n-j} (-1)^i C(n,i+j)C(i+j,j)$
对比 $(7)$ 式和 $(12)$ 式可以得出：
$t_{i,j} = (-1)^j C(i,j)$
于是乎 $(3)$ 式得证。

第二个式子的推导：

这个可以用 $EGF$ 推：
$f_n = \sum_{i=0}^{n} C(n,i) g_i \Leftrightarrow \frac{f_n}{n!} = \sum_{i=0}^{n} \frac{g_i}{i!} \times \frac{1}{(n-i)!}$
那么 $\left\{ \frac{f_n}{n!} \right\}$ 的 $EGF$ 就是
$F = \sum_{i=0}^{+\infty} f_i x^i$
以及 $\left\{ \frac{g_n}{n!} \right\}$ 的 $EGF$ 就是
$G = \sum_{i=0}^{+\infty} g_i x^i$
又因为
$e^x = \sum_{i=0}^{+\infty} \frac{x^i}{i!}$
$e^{-x} = \sum_{i=0}^{+\infty} \frac{(-x)^i}{i!}$
$e^{-x} = \sum_{i=0}^{+\infty} (-1)^i \frac{x^i}{i!}$

所以
$F = G \times e^x$
于是
$G = F \times e^{-x}$
重新展开就有
$\frac{g_n}{n!} = \sum_{i=0}^{n} \frac{f_i}{i!} (-1)^{n-i} \frac{1}{(n-i)!}$
即
$g_n = \sum_{i=0}^{n} (-1)^i C(n,i) f_i$
于是乎 $(4)$ 式得证。

二项式反演推导

请大家注意：

第一个式子的推导：

第二个式子的推导：

猜你喜欢

热点阅读