二项式反演
$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$ 了。
这个貌似就是广义容斥，把求恰好的问题转化为求至多，至少的问题。