二项式反演

二项式反演有两种常见的形式

形式一

令 $f_i$ 表示恰好使用 $i$ 个元素、且满足条件的方案数， $g_n$ 表示从 $n$ 个元素选出 $i(i\in[0,n])$ 个元素、且满足条件的总方案数，则根据定义有

另一种理解方法： $g_n$ 表示至多 $n$ 个元素的方案数， $f_n$ 表示恰好 $n$ 个元素的方案数

g_n=\sum_{i=0}^n \binom{n}{i} f_i

通过二项式反演，我们可以通过 $g_i$ 求出 $f_i$ .

f_n=\sum_{i=0}^n\binom{n}{i}(-1)^{n-i} g_i

证明

形式二

另一种理解方法： $g_n$ 表示至少 $n$ 个元素的方案数， $f_n$ 恰好 $n$ 个元素的方案数

g_k=\sum_{i=k}^n \binom{i}{k} f_i

通过二项式反演，我们可以通过 $g_n$ 求出 $f_n$

f_k=\sum_{i=k}^n (-1)^{i-k} \binom{i}{k} g_i