二项式反演

引入

根据容斥原理

$\left|A_1 \cup A_2 \cup \cdots \cup A_n\right|=\sum_{1 \leq i \leq n}\left|A_i\right|-\sum_{1 \leq i<j \leq n}\left|A_i \cap A_j\right|+\cdots+(-1)^{n-1} \times\left|A_1 \cap A_2 \cap \cdots \cap A_n\right|$

的另一种形式

$\left|\overline{A_1} \cap \overline{A_2} \cap \cdots \cap \overline{A_n}\right|=|S|-\sum_{1 \leq i \leq n}\left|A_i\right|+\sum_{1 \leq i<j \leq n}\left|A_i \cap A_j\right|-\cdots+(-1)^n \times\left|A_1 \cap A_2 \cap \cdots \cap A_n\right|$

由于集合的补集的补集就是它自己，那么

$\left|A_1 \cap A_2 \cap \cdots \cap A_n\right|= |S|-\sum_{1 \leq i \leq n}\left|\overline{A_i}\right| +\sum_{1 \leq i<j \leq n}\left|\overline{A_i} \cap \overline{A_j}\right| -\cdots+(-1)^n \times\left|\overline{A_1} \cap \overline{A_2} \cap \cdots \cap \overline{A_n}\right|$

考虑一种特殊的情况：多个集合的交集大小只与集合的数目有关。

即 $f(n)$ 为 $n$ 个补集的交集大小， $g(n)$ 表示 $n$ 个集合（原）的大小，那么可以得到

$\begin{aligned} & f(n)=\sum_{i=0}^n(-1)^i\binom{n}{i} g(i) \\ & g(n)=\sum_{i=0}^n(-1)^i\binom{n}{i} f(i) \end{aligned}$

由于这两个公式是等价的，所以我们得到了二项式反演的初步形式

$f(n)=\sum_{i=0}^n(-1)^i\binom{n}{i} g(i) \quad\Leftrightarrow\quad g(n)=\sum_{i=0}^n(-1)^i\binom{n}{i} f(i)\tag{0}$

二项式反演

形式一

二项式反演的一种形式如下：

$f(n)=\sum_{i=0}^n\binom{n}{i} g(i) \quad\Leftrightarrow\quad g(n)=\sum_{i=0}^n(-1)^{n-i}\binom{n}{i} f(i) \tag{1}$

证明令 $h(n) = (-1)^ng(n)$ ，代入 $(0)$ 可知
$f(n)=\sum_{i=0}^n\binom{n}{i} h(i) \quad\Leftrightarrow\quad \frac{h(n)}{(-1)^n}=\sum_{i=0}^n(-1)^i\binom{n}{i} f(i)$
整理后即可得到 $(6)$ 。 $\square$

形式二（常见形式）

这个公式与形式一类似，不过更为常用

$f(n)=\sum_{i=n}^m\binom{i}{n} g(i) \quad\Leftrightarrow\quad g(n)=\sum_{i=n}^m(-1)^{i-n}\binom{i}{n} f(i) \tag{2}$

换一种不容易混淆的写法就是

$f_i=\sum_{j=i}^n\binom{j}{i} g_j \quad\Leftrightarrow\quad g_i=\sum_{j=i}^n(-1)^{j-i}\binom{j}{i} f_j$

证明将左侧代入右侧
$\begin{aligned} f(n) & =\sum_{i=n}^m\binom{i}{n} \sum_{j=i}^m(-1)^{j-i}\binom{j}{i} f(j) \\[6pt]& =\sum_{i=n}^m \sum_{j=i}^m(-1)^{j-i}\binom{i}{n}\binom{j}{i} f(j) \\[6pt]& =\sum_{j=n}^m f(j) \sum_{i=n}^j(-1)^{j-i}\binom{i}{n}\binom{j}{i} \\[6pt]& =\sum_{j=n}^m\binom{j}{n} f(j) \sum_{i=n}^j\binom{j-n}{j-i}(-1)^{j-i} \\[6pt]& =\sum_{j=n}^m\binom{j}{n} f(j) \sum_{t=0}^{j-n}\binom{j-n}{t}(-1)^t 1^{j-n-t} \\[6pt]& =\sum_{j=n}^m\binom{j}{n} f(j)(1-1)^{j-n} \\[6pt]& =\sum_{j=n}^m\binom{j}{n} f(j)[j=n] \\[6pt]& =\binom{n}{n} f(n) \\[6pt]& =f(n) \end{aligned}$
则有左右恒等。 $\square$