二项式反演

$g_n=\sum\limits_{i=0}^n(-1)^i\displaystyle\binom{n}{i}f_i\quad↔\quad f_n=\sum\limits_{i=0}^n(-1)^i\displaystyle\binom{n}{i}g_i$

证明:

$$ \begin{align} &\sum\limits_{i=0}^n(-1)^i\binom{n}{i}g_i\\ =&\sum_{i=0}^n(-1)^i\binom{n}{i}\sum_{j=0}^i(-1)^j\binom{i}{j}f_j\\ =&\sum_{i=0}^n\sum_{j=0}^i(-1)^{i}(-1)^j\frac{n!}{i!(n-i)!}·\frac{i!}{j!(i-j!)}f_j\\ =&\sum_{i=0}^n\sum_{j=0}^i(-1)^{i}(-1)^j\frac{n!}{(n-i)!j!(i-j!)}f_j\\ =&\sum_{i=0}^n\sum_{j=0}^i(-1)^{i}(-1)^j\frac{n!(n-j)!}{(n-j)!(n-i)!j!(i-j!)}f_j\\ =&\sum_{i=0}^n\sum_{j=0}^i(-1)^{i}(-1)^j\frac{n!}{(n-j)!j!}·\frac{(n-j)!}{(n-i)!(i-j!)}f_j\\ =&\sum_{i=0}^n\sum_{j=0}^i(-1)^{i}(-1)^j\binom{n}{j}·\binom{n-j}{i-j}f_j\\ =&\sum_{j=0}^n(-1)^j\binom{n}{j}f_j\sum_{i=j}^n(-1)^i\binom{n-j}{i-j}\\ &i←i-j\\ =&\sum_{j=0}^n(-1)^j\binom{n}{j}f_j\sum_{i=0}^{n-j}(-1)^{i+j}\binom{n-j}{i}\\ =&\sum_{j=0}^nf_j\binom{n}{j}\sum_{i=0}^{n-j}(-1)^{i}\binom{n-j}{i}\\ =&\sum_{j=0}^nf_j\binom{n}{j}[n==j]\\ =&f_n \end{align} $$

倒数第二步可以把后面那一坨变为 $(1-1)^{n-j}$ 显然等价于 $[n==j]$ 。

于是就有

$$ f_n=\sum_{i=0}^n\binom{n}{i}g_i\quad↔\quad g_n=\sum_{i=0}^n(-1)^{n-i}\binom{n}{i}f_i $$

可以令 $G_n=(-1)^ng_n$ 再带入最上面的式子,就有了一样的形式了。


应用

假设要求计数 恰好 $k$ 个某物的方案数,$1\leq k\leq n$。

1.我们令 $g_i$ 表示 恰好 $i$ 个某物的方案数,$f_i$ 为 至多 $i$ 个某物的方案数。

这个满足 $f_k=\sum\limits_{i=0}^k\displaystyle\binom{k}{i}g_i$ ,假设我们能求出 $f_{0,1,2,..k}$ ,就可以用二项式反演求回 $ g_k=\sum_{i=0}^k(-1)^{k-i}\displaystyle\binom{k}{i}f_i $了。

2.我们令 $g_i$ 表示 恰好 $i$ 个某物的方案数,$f_i$ 为 至少 $i$ 个某物的方案数。

这个满足 $f_k=\sum\limits_{i=k}^n\displaystyle\binom{i}{k}g_i\quad ↔\quad g_k=\sum\limits_{i=k}^n(-1)^{i-k}\displaystyle\binom{i}{k}f_i$。

不会证,所以暴力拆开。

$$ \begin{align} &\sum_{i=k}^n\binom{i}{k}g_i\\ =&\sum_{i=k}^n\binom{i}{k}\sum_{j=i}^n(-1)^{j-i}\binom{j}{i}f_j\\ =&\sum_{i=k}^n\sum_{j=i}^n\binom{j}{i}\binom{i}{k}(-1)^{j-i}f_j\\ =&\sum_{i=k}^n\sum_{j=i}^n\binom{j}{k}\binom{j-k}{i-k}(-1)^{j-i}f_j\\ =&\sum_{j=k}^nf_j\sum_{i=k}^j(-1)^{j-i}\binom{j}{k}\binom{j-k}{i-k}\\ &i←i-k\\ =&\sum_{j=k}^nf_j\binom{j}{k}\sum_{i=0}^{j-k}(-1)^{j-k-i}\binom{j-k}{i}\\ =&\sum_{j=k}^nf_j\binom{j}{k}[j==k]\\ =&f_k \end{align} $$

于是也可以先求出 $f_{0,1,2...k}$ 再二项式反演回 $g_k$ 了。

这个貌似就是广义容斥,把求恰好的问题转化为求至多,至少的问题。

例题

最后修改:2021 年 04 月 19 日 10 : 38 PM