二项式反演
本质上与广义容斥定理做的事情相同。
什么是反演
我们称一对关于序列的正向与逆向操作为一种反演（Inversion）。
具体的，前缀和与差分就可以被看作是一种反演。
公式
1、前缀和型：
对于非负整数 \(n\)，若数列 \(f_n,g_n\) 满足：
\[f_n = \sum ^n _{i=0} {n \choose i} g_i
\]
则必有：
\[g_n = \sum ^n _{i=0} (-1)^{n-i} {n \choose i} f_i
\]
反之亦然。
2、后缀和型（常用）：
对于 \(0 \le k \le n\)，若数列 \(f_k,g_k\) 满足：
\[f_k = \sum ^n _{i=k} {i \choose k} g_i
\]
则必有：
\[g_k = \sum ^n _{i=k} (-1)^{i-k} {i \choose k} f_i
\]
反之亦然。
这个证明同广义容斥原理，此处略去。
应用
第二类斯特林数：
定义 \(g_k\) 为恰好 \(k\) 个盒子为空的方案数，\(f_k\) 为“至少” \(k\) 个盒子为空的方案数。目标显然是求 \(g_0\)。
有 \(f_k = {m \choose k} (m-k)^n\)，代入公式即得答案为 \(S(n,m) \times m!\)。
染色问题：
注意点
识别题目：\(f_k\) 好求（可使用组合公式 / dp），\(g_k\) 不好求。
易错：\(f_k\) 是“所有 \(k\) 元固定集合的方案数之和“，一个恰好 \(i\) 个的方案会被算 \(i \choose k\) 次。