二项式反演

1. 反演的定义

演绎推理是我们在数学中经常遇到的方法。对于数列来说，通过原数列计算出新数列叫作演绎，而通过计算出的数列反推出原数列则被称为反演。

举个例子，假设有两个数列 \(f(x)\) 和 \(g(x)\)，\(f(x)\) 为原数列，\(g(x)\) 为新数列。我们从 \(f(x)\) 推出 \(g(x)\) 的过程就叫做演绎，而利用 \(g(x)\) 反推出 \(f(x)\)的过程就叫做反演。

一般来说，有了两个数列的相互关系，我们才能相互推算。在一些特定的情况下，相互关系会有一些特殊的性质，人们将重要的、常见的相互关系命名，并深入研究其性质，如二项式反演、莫比乌斯反演、单位根反演、子集反演等。

再举个例子，我们假设 \(g(x)\) 与 \(f(x)\) 满足：

\[\begin{aligned} g(x) &= \sum_{i=0}^x {a_i f(i)} \end{aligned}\]

我们可以利用它们的关系式，从 \(f(x)\) 推到 \(g(x)\)，也可以通过解 \(n\) 元一次方程组，从 \(g(x)\) 推到 \(f(x)\)。当然，这个关系式的反演过程只需要简单地进行解方程组，所以并没有特别的名字。

2. 通过容斥原理推导二项式反演

不会容斥原理的可以来看我的另一篇博客

我们设全集 \(U = \{S_1, S_2, \dots, S_{n - 1}, S_n \}\) 中的任意 \(i\) 个元素的并集大小相等，任意 \(i\) 个元素的交集大小也相等。

设 \(g(n)\) 代表任意 \(n\) 个集合的交集，\(f(n)\) 代表任意 \(n\) 个集合的补集的交集。特别地，\(g(0) = f(0) = |U|\)

那么我们就能得到下面两条容斥式子：

\[\begin{aligned} g(n) &= |S_1 \cap S_2 \cap \dots \cap S_{n - 1} \cap S_n| \\ &= |U| - |\overline{S_1}| - |\overline{S_2}| - \dots + (-1)^n \times |\overline{S_1} \cap \overline{S_2} \cap \dots \cap \overline{S_{n-1}} \cap \overline{S_n}| \\ &= \sum_{i = 0}^n(-1)^i \dbinom{n}{i}f(i) \end{aligned}\]

\[\begin{aligned} f(n) &= |\overline{S_1} \cap \overline{S_2} \cap \dots \cap \overline{S_{n - 1}} \cap \overline{S_n}| \\ &= |U| - |S_1| - |S_2| - \dots + (-1)^n \times |S_1 \cap S_2 \cap \dots \cap S_{n-1} \cap S_n| \\ &= \sum_{i = 0}^n(-1)^i \dbinom{n}{i}g(i) \end{aligned}\]

所以我们得到了优美的 ~~一点都不优美的~~ 二项式反演式子：

\[\begin{aligned} g(n) &= \sum_{i = 0}^n(-1)^i \dbinom{n}{i} f(i) \Leftrightarrow f(n) = \sum_{i = 0}^n(-1)^i \dbinom{n}{i}g(i) \end{aligned}\]

3. 二项式反演的常用形式

形式一：

已知公式：

\[\begin{aligned} g(n) &= \sum_{i = 0}^n (-1)^i \dbinom{n}{i} f(i) \Leftrightarrow f(n) = \sum_{i = 0}^n (-1)^i \dbinom{n}{i}g(i) \end{aligned}\]

我们假设 \(h(n) = (-1)^n f(n)\)，则有：

\[\begin{aligned} g(n) &= \sum_{i = 0}^n \dbinom{n}{i} h(i) \Leftrightarrow \frac{h(n)}{(-1)^n} = \sum_{i = 0}^n (-1)^i \dbinom{n}{i}g(i) \end{aligned}\]

即

\[\begin{aligned} g(n) &= \sum_{i = 0}^n \dbinom{n}{i} h(i) \Leftrightarrow h(n) = \sum_{i = 0}^n (-1)^{i + n} \dbinom{n}{i}g(i) \end{aligned}\]

而对于整数 \(i\)，\(n - i = n + i - 2 \cdot i\)，所以在对 \(2\) 取模的意义下，有 \(n + i \equiv n - i\ ( mod\ 2)\)。

所以有

\[\begin{aligned} g(n) &= \sum_{i = 0}^n \dbinom{n}{i} h(i) \Leftrightarrow h(n) = \sum_{i = 0}^n (-1)^{n - i} \dbinom{n}{i}g(i) \end{aligned}\]

即常见的：

\[\begin{aligned} g(n) &= \sum_{i = 0}^n \dbinom{n}{i} f(i) \Leftrightarrow f(n) = \sum_{i = 0}^n (-1)^{n - i} \dbinom{n}{i}g(i) \end{aligned}\]

这也就是第一个常用的形式，不过这里 \(g(x)\) 与 \(f(x)\) 的定义视情况而定。

形式二

先给出形式：

\[\begin{aligned} f(n) = \sum_{i = n}^m {i \choose n} g(i) \Leftrightarrow g(n) = \sum_{i = n}^m (-1)^{i - n} {i \choose n} f(i) \end{aligned}\]

将右式代入左式，则

\[\begin{split} f(n) &= \sum_{i = n}^m{i \choose n} \sum_{j = i}^m (-1)^{j - i}{j \choose i} f(j)\\ &= \sum_{i = n}^m \sum_{j=i}^m(-1)^{j-i}{i\choose n}{j\choose i}f(j)\\ &= \sum_{j = n}^m f(j) \sum_{i=n}^j(-1)^{j-i}{i\choose n}{j\choose i}\\ &= \sum_{j = n}^m{j \choose n} f(j) \sum_{i=n}^j {j - n\choose j - i} (-1)^{j - i}\\ &= \sum_{j = n}^m{j \choose n} f(j) \sum_{t = 0}^{j - n}{j - n \choose t} (-1)^{t}1^{j-n-t}\\ &= \sum_{j = n}^m{j \choose n} f(j) (1 - 1)^{j - n}\\ &= \sum_{j = n}^m{j \choose n} f(j) [j = n]\\ &= {n \choose n} f(n)\\ &= f(n) \end{split}\]

等式两边恒等，故恒成立。

4. 二项式反演在题目中的应用

4.1 几个经典问题

4.1.1 全错位排列问题

错位就是原来在某一位置上的数不能在这个位置上，或者说 \(a_i \ne i\)

全排列就不再解释了

对于这个问题，我们可以定义 \(g(x)\) 表示 \(n\) 个数中，至多有 \(x\) 个 \(a_i \ne i\) 的总方案数。\(f(x)\) 表示 \(x\) 个数的全错位排列的方案数。

所以有：

\[\begin{aligned} g(n) &= \sum_{i = 0}^n {n \choose i} f(i) \\ \end{aligned}\]

从 \(g(x)\) 的定义来看，有

\[\begin{aligned} g(x) &= x! \end{aligned}\]

所以我们可以用二项式反演得到 \(f(n)\) ：

\[\begin{aligned} f(n) &= \sum_{i = 0}^n (-1)^{n - i} {n \choose i} g(i) \\ &= \sum_{i = 0}^n (-1)^{n - i} {n \choose i} i! \\ &= \sum_{i = 0}^n (-1)^{n - i} \frac{n!}{(n - i)!} \end{aligned}\]

在求和式中，把 \(n!\) 提出来，再用 \(i\) 代换 \(n - i\)，式子不变，得到

\[\begin{aligned} f(n) &= n! \sum_{i = 0}^n \frac{(-1)^i}{i!} \end{aligned}\]

这也就是所谓的全错位排列公式。