二项式反演

引入

根据容斥原理

$$\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$

---

组合意义

记 $f_i$ 为“钦定选 $i$ 个”（然而常常会重复计算一些情况），并记 $g_i$ 为 “恰好选 $i$ 个”

则对于任意 $j \ge i$ ，$g_j$ 在 $f_i$ 中被计算了 $\binom{j}{i}$ 次，故

$$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 \tag{2}$$

其中 $n$ 为数目的上界。

---

例题

参考 洛谷P4859 已经没有什么好害怕的了 题解

还有 洛谷P10596 & BZOJ2839 集合计数 题解 ，不过这题的二项式反演解法是后来补的（

---

参考文献：

[1] https://www.cnblogs.com/GXZlegend/p/11407185.html