二项式反演

引入

根据容斥原理 \[ \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\) 为数目的上界。

2024-07-03 OI

二项式反演

引入