一文带你精通二项式反演！不服来看！-数字星空

前言

原题：《二项式反演学习笔记》。

这里有我关于二项式反演的一些思考和领会，包含理论推导和在信息学竞赛中的应用。网络上的教程都太潦草了，难以深入理解。因此，这里将以详细的证明为主，介绍二项式反演在 OI 中的使用。

如果你只想快速浏览结论，可以点击这里查看结论。

概述

反演是一种将两个函数 \(f\) 和 \(g\) 相互转化的数学工具。假设我们知道如何用 \(g(x)\) 表示出 \(f(x)\)，并以此反推出了 \(g(x)\) 关于 \(f(x)\) 的表达式，这个反推的过程，就是反演。

二项式反演是一种特殊的反演，用于转化两个具有特殊关系的函数 \(f\) 和 \(g\)。一般来说，解题的过程中，如果遇到直接计算「恰好」满足 \(n\) 个限制的答案 \(g(n)\) 较为困难，但是我们可以计算出「至少」/「至多」满足 \(n\) 个限制的答案 \(f(n)\)。这时运用二项式反演，就能求出「恰好」满足 \(n\) 个限制的答案 \(g(n)\)。这就是二项式反演的两大模型：「至少」\(\Leftrightarrow\)「恰好」、「至多」\(\Leftrightarrow\)「恰好」。并且，求解「至少」和「至多」的过程又分为「钦定类问题」和「选择类问题」，所以这两大模型又分别对应两个子模型。我们接下来通过详细的证明与推导，逐步来理解这些模型。

基础引理

如果你有组合计数类问题的基础，可以跳过引理部分。

引理 \(1\)：二项式定理

\[\sum _ {i = 0} ^ n \binom{n}{i} (-1)^i = [n = 0] \tag{Lemma 1} \label{lem1} \]

考虑从二项式定理证明。普通二项式定理为：

\[(a + b) ^ n = \sum _ {i = 0} ^ n \binom{n}{i} a^i b^{n-i} \]

该定理可以通过数学归纳法证明，本文不再详细展开。通过设定 \(a = -1, b = 1\) 的特殊情形，可以得出：

\[\begin{aligned} & \quad \ \sum _ {i = 0} ^ n \binom{n}{i} (-1)^i \\ &= \sum _ {i = 0} ^ n \binom{n}{i} (-1)^i 1^{n-i} \\ &= \Big (1 + (-1) \Big )^n \\ &= 0 ^ n \end{aligned} \]

注意到当 \(n = 0\) 的时候，该式没有意义。观察原式发现此时 \(\dbinom{0}{0} (-1)^0 = 1\)。所以综上我们就有 \(\ref{lem1}\)。

引理 \(2\)：多步容斥

\[\large \left \vert \bigcup_{i = 1}^{n} S_i \right \vert = \sum _ {m = 1} ^ n (-1) ^ {m - 1} \sum _ {a_i < a_{i + 1}} \Bigg \vert \bigcap _ {i = 1} ^ m S_{a_i} \Bigg \vert \tag{Lemma 2} \label{lem2} \]

记 \(S_i\)（\(1 \leq i \leq n\)）表示一个集合，根据容斥原理，我们有：

\[\large \left \vert \bigcup_{i = 1}^{n} S_i \right \vert = \sum _ {1 \leq i \leq n} \Big \vert S_i \Big \vert - \sum _ {1 \leq i \lt j \leq n} \Big \vert S_i \cap S_j \Big \vert + \cdots + (-1) ^ {n - 1} \Bigg \vert \bigcap _ {i = 1} ^ n S_i \Bigg \vert \]

也就是 \(\ref{lem2}\)。

不妨记 \(U\) 表示这 \(n\) 个集合的全集。那么证明该式等价于证明 \(\forall x \in U\)，\(x\) 在右边 \(\sum \limits _ {a_i < a_{i + 1}} \Bigg \vert \bigcap \limits _ {i = 1} ^ m S_{a_i} \Bigg \vert\) 中计算的系数之和为 \(1\)。记所有包含 \(x\) 的集合为 \(T_1, \ldots, T_m\)（\(m \neq 0\)），则有：

\[\begin{aligned} & \quad \ \Big \vert \{ T_i \mid 1 \leq i \leq m \} \Big \vert - \Big \vert \{ T_i \cap T_j \mid 1 \leq i \lt j \leq m \} \Big \vert + \cdots \\ &= \binom{m}{1} - \binom{m}{2} + \cdots + (-1) ^ {m - 1} \binom{m}{m} \\ &= \sum _ {i = 1} ^ {m} (-1)^{i - 1} \binom{m}{i} \\ &= - \sum _ {i = 1} ^ {m} (-1)^i \binom{m}{i} \\ &= \binom{m}{0} - \sum _ {i = 0} ^ {m} (-1)^i \binom{m}{i} \\ \end{aligned} \]

根据 \(\ref{lem1}\)，得：

\[\begin{aligned} & \quad \ \binom{m}{0} - \sum _ {i = 0} ^ {m} (-1)^i \binom{m}{i} \\ &= 1 - [m = 0] \\ &= 1 \end{aligned} \]

故该容斥公式成立。

引理 \(3\)：组合数

\[\dbinom{n}{i} \dbinom{i}{j} = \binom{n}{j} \binom{n - j}{i - j} \tag{Lemma 3} \label{lem3} \]

考虑左式的组合意义，\(\dbinom{n}{i} \dbinom{i}{j}\) 表示 \(n\) 个小球里选出 \(i\) 个，再从 \(i\) 个里面选出 \(j\) 的方案数。我们也可以先从 \(n\) 个里面选出 \(j\) 个，再从剩下 \(n - j\) 里选出 \(i - j\) 个。也就是 \(\binom{n}{j} \binom{n - j}{i - j}\)。也就证明了 \(\ref{lem3}\)。

当然也可以代数证明：

\[\begin{aligned} \dbinom{n}{i} \dbinom{i}{j} &= \frac{n!}{i! (n-i)!} \frac{i!}{j! (i-j)!} \\ &= \frac{n!}{(n - i)! (i - j)! j!} \\ &= \frac{n! (n - j)!}{(n - i)! (i - j)! (n - j)! j!} \\ &= \frac{n!}{j! (n - j)!} \frac{(n - j)!}{(n - i)! \Big ((n - j) - (n - i) \Big)!} \\ &= \binom{n}{j} \binom{n - j}{i - j} \end{aligned} \]

证明 & 推导

模型 \(0\)

\[\large f(x) = \sum _ {i = 0} ^ x (-1)^i \binom{x}{i} g(i) \Longleftrightarrow g(x) = \sum _ {i = 0} ^ x (-1) ^ i \binom{x}{i} f(i) \tag{Thm 0} \label{thm0} \]

尽管该模型的实际应用较少，但是作为最基础的反演公式，有必要进行介绍。由于模型的相似性，学习这个模型的证明过程，有助于大家理解后面模型的证明过程。

容斥证明

不妨记 \(\overline{S_i}\) 表示 \(S_i\) 的补集。由于 \(n\) 个集合的交等价于 \(n\) 个集合的并的补集，得到以下表达式：

\[\left \vert \bigcap_{i = 1}^{n} \overline{S_i} \right \vert = \left \vert U \right \vert - \left \vert \bigcup_{i = 1}^{n} \overline{S_i} \right \vert \]

由 \(\ref{lem2}\) 展开，得到：

\[\begin{aligned} \left \vert \bigcap_{i = 1}^{n} \overline{S_i} \right \vert &= \left \vert U \right \vert - \sum _ {m = 1} ^ n (-1) ^ {m - 1} \sum _ {a_i < a_{i + 1}} \Bigg \vert \bigcap _ {i = 1} ^ m S_{a_i} \Bigg \vert \\ &= \left \vert U \right \vert + \sum _ {m = 1} ^ n (-1) ^ m \sum _ {a_i < a_{i + 1}} \Bigg \vert \bigcap _ {i = 1} ^ m S_{a_i} \Bigg \vert \\ \end{aligned} \]

由于 \(\overline{\ \overline{S_i}\ } = S_i\)，所以得到类似的式子：

\[\left \vert \bigcap_{i = 1}^{n} S_i \right \vert = \left \vert U \right \vert + \sum _ {m = 1} ^ n (-1) ^ m \sum _ {a_i < a_{i + 1}} \Bigg \vert \bigcap _ {i = 1} ^ m \overline{S_{a_i}} \Bigg \vert \]

发现形式很像，但是还差一步构造。我们假设能构造出一组 \(S_i\)，使任意 \(k\) 个集合的交集大小相等。

不妨记 \(f(x)\) 表示任意 \(x\) 个补集的交集大小，对于原集同理记 \(g(x)\) 表示任意 \(x\) 个原集的交集大小，上式可以分别改写为：

\[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) \]

这两者是等价的，也就证明了 \(\ref{thm0}\)。

事实上，从这里我们会发现，「二项式反演」和「容斥」有着千丝万缕的联系。如果你在此时意识到这是容斥原理的应用，那么说明你对「二项式反演」的理解已经更进一步。

代数证明

容斥比较抽象，我们接下来通过代数方法进行证明。我们想要证明左右两式是等价的、可以相互转化的，可以把 \(g\) 代到 \(f\) 中去，即把右式代到左式中。如果得到一个恒等式，就能证明其正确性。这也是我们学习「二项式反演」一直在用的证明方法，弄懂它就能理解后文的证明。

\[f(x) = \sum _ {i = 0} ^ x (-1)^i \binom{x}{i} \sum _ {j = 0} ^ i (-1) ^ j \binom{i}{j} f(j) \]

形象地展示出来为：

\[\begin{array}{cc|cccccc} & j & 0 & 1 & 2 & 3 & \cdots & x-1 & x \\ i & & c_0 & c_1 & c_2 & c_3 & \cdots & c_{x-1} & c_x \\ \hline 0 & v_0 & f(j) & & & & & & \\ 1 & v_1 & f(j) & f(j) & & & & & \\ 2 & v_2 & f(j) & f(j) & f(j) & & & & \\ 3 & v_3 & f(j) & f(j) & f(j) & f(j) & & & \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots & & \\ {\tiny x-1} & v_{\tiny x-1} & f(j) & f(j) & f(j) & f(j) & \cdots & f(j) & \\ x & v_x & f(j) & f(j) & f(j) & f(j) & \cdots & f(j) & f(j) \\ \end{array} \]

其中，\(v_i\) 表示关于 \(i\) 的系数，即 \((-1)^i \dbinom{x}{i}\)。\(c_j\) 同理为 \((-1) ^ j \dbinom{i}{j}\)。我们求的就是这个形如「三角形」中所有 \(v_ic_jf(j)\) 的和。在上一条式子中，我们先枚举 \(i\) 再枚举 \(j\)，其意义是，按照行的顺序，一行一行扫过来求和。我们不妨使用另一种遍历方法，改变枚举顺序，按照列的顺序，一列一列扫过来求和。见下图。

先枚举行（左）；先枚举列（右）

表示成式子就是：

\[f(x) = \sum _ {i = 0} ^ x f(i) \sum _ {j = i} ^ x (-1) ^ {i + j} \binom{j}{i} \binom{x}{j} \]

使用 \(\ref{lem3}\)，变换得：

\[\begin{aligned} f(x) &= \sum _ {i = 0} ^ x f(i) \sum _ {j = i} ^ x (-1) ^ {i + j} \binom{x}{i} \binom{x - i}{j - i} \\ &= \sum _ {i = 0} ^ x \binom{x}{i} f(i) \sum _ {j = i} ^ x (-1) ^ {i + j} \binom{x - i}{j - i} \\ &= \sum _ {i = 0} ^ x \binom{x}{i} f(i) \sum _ {j = 0} ^ {x - i} (-1) ^ {2i + j} \binom{x - i}{j} \\ &= \sum _ {i = 0} ^ x \binom{x}{i} f(i) \sum _ {j = 0} ^ {x - i} (-1) ^ j \binom{x - i}{j} \\ \end{aligned} \]

有二项式定理的样子，运用 \(\ref{lem1}\)，得到：

\[f(x) = \sum _ {i = 0} ^ x \binom{x}{i} f(i) [x - i = 0] \]

显然，\(x - i = 0\) 即 \(i = x\) 时，有 \(f(x) = \dbinom{x}{x} f(x)\)，发现即为 \(f(x)\) 恒等于 \(f(x)\)，也就证明了 \(\ref{thm0}\)。我们来回顾整个证明过程：

\[\begin{aligned} f(x) &= \sum _ {i = 0} ^ x (-1)^i \binom{x}{i} \sum _ {j = 0} ^ i (-1) ^ j \binom{i}{j} f(j) \\ &= \sum _ {i = 0} ^ x f(i) \sum _ {j = i} ^ x (-1) ^ {i + j} \binom{j}{i} \binom{x}{j} \\ &= \sum _ {i = 0} ^ x f(i) \sum _ {j = i} ^ x (-1) ^ {i + j} \binom{x}{i} \binom{x - i}{j - i} \\ &= \sum _ {i = 0} ^ x \binom{x}{i} f(i) \sum _ {j = i} ^ x (-1) ^ {i + j} \binom{x - i}{j - i} \\ &= \sum _ {i = 0} ^ x \binom{x}{i} f(i) \sum _ {j = 0} ^ {x - i} (-1) ^ {2i + j} \binom{x - i}{j} \\ &= \sum _ {i = 0} ^ x \binom{x}{i} f(i) \sum _ {j = 0} ^ {x - i} (-1) ^ j \binom{x - i}{j} \\ &= \sum _ {i = 0} ^ x \binom{x}{i} f(i) [x - i = 0] \\ &= f(x) \end{aligned} \]

首先将 \(g\) 代入 \(f\)，改变求和枚举顺序，变换组合数，提出不变量，最后运用二项式定理，证明恒等式。这就是之后我们证明的一般套路了，读者可以尝试自己重新推导一遍，以加深印象。

有了以上基础，接下来我们正式进入「二项式定理」的学习中。接下来将按照从「钦定类问题」到「选择类问题」的顺序，逐步分别分析两大模型。

「钦定类问题」

概述

所谓「钦定类问题」，指的是我们在解决问题时，强制选择某些限制必须满足，不管剩下的限制，即剩下的限制可以满足可以不满足。这个强制选择某些限制必须满足的过程，就是「钦定」。我们发现，在「钦定」后的基础上求解问题，就不需要考虑限制的问题，也就方便了我们对问题的求解。

在「钦定意义」下，我们能够求出「至少」满足 \(x\) 个限制的答案；也可以通过「钦定」\(n - x\) 个限制不能满足，求出在「钦定意义」下，「至多」满足 \(x\) 个限制的答案，这将在下文进一步说明。注意到，这里的「至少」/「至多」是「钦定意义」下的，不是通常意义下的。也就是说可能会有重复计数的问题，我们将在下文进一步分析。

为了方便叙述，假设下文的「至少」和「恰好」均为「钦定意义」下的。

模型 \(1\)：「至少」\(\Leftrightarrow\)「恰好」

\[\large f(x) = \sum _ {i = x} ^ n \binom{i}{x} g(i) \Longleftrightarrow g(x) = \sum _ {i = x} ^ n (-1)^{i - x} \binom{i}{x} f(i) \tag{Thm 1.1} \label{thm11} \]

此模型用来解决「钦定意义」下「至少」和「恰好」的转化。假设原问题有 \(n\) 个限制，我们设 \(f(x)\) 表示「至少」满足 \(x\) 个限制的方案数，\(g(x)\) 表示「恰好」满足 \(x\) 个限制的方案数。那么 \(g(x)\) 即为我们的答案，而 \(f(x)\) 就是我们通过其他算法求出的结果。

注意到，这里 \(f\) 和 \(g\) 其实囊括了所有 \(x\) 种限制的选择。比如 \(f(3)\) 表示 \(\dbinom{n}{3}\) 种钦定方案下，方案数的总和。

然后，我们考虑由「恰好」表示出「至少」，也就是得出 \(\ref{thm11}\) 左侧的式子。在思考这个问题之前，我们先来想一想，为什么「钦定」后会重复计数，以及如何重复计数的。

考虑一种满足了 \(i > x\) 个限制的局面，我们如果「钦定」这 \(i\) 个限制中任意 \(x\) 个，都会统计到这种局面，所以它重复贡献次数为 \(\dbinom{i}{x}\)。读者需要好好理解这句话。

明白了「钦定」的重复计数后，有两种思考方式：

一种更直接的思考方式为，我们考虑枚举「钦定」\(x\) 个限制必须满足后，实际上一共有 \(i \geq x\) 个限制被满足，把 \(g(i)\) 乘上上文中提到的重复贡献的系数，求和就得到 \(f(x)\)。得到：
\[f(x) = \sum _ {i = x} ^ n \binom{i}{x} g(i) \]
这就是 \(\ref{thm11}\) 左侧的式子。
另一种绕了个小弯的思考方式是，先考虑如何表示出 \(g(x)\)。\(g(x)\) 可以表示为 \(f(x)\) 中减去所有满足了 \(i > x\) 个限制的局面。又因为上文提到的重复贡献，需要把 \(\dbinom{i}{x}\) 次贡献都去除。不难得到：
\[g(x) = f(x) - \sum _ {i = x + 1} ^ n \binom{i}{x} g(i) \]
移项后就得到：
\[\begin{aligned} f(x) &= g(x) + \sum _ {i = x + 1} ^ n \binom{i}{x} g(i) \\ &= \sum _ {i = x} ^ n \binom{i}{x} g(i) \end{aligned} \]
同样得到 \(\ref{thm11}\) 左侧的式子。

该等式阐述了如何由「恰好」表示出「至少」。接下来就是二项式反演的关键步骤，即用「至少」表示出「恰好」。直接推出右边的等式较难，但是如果我们只是为了证明右边等式的正确性，可以借鉴 \(\ref{thm0}\) 的证明方式推导。如果推导结果成立，就表明该转化是正确的。

\[\begin{aligned} f(x) &= \sum _ {i = x} ^ n \binom{i}{x} \sum _ {j = i} ^ n (-1)^{j - i} \binom{j}{i} f(j) \\ &= \sum _ {i = x} ^ n f(i) \sum _ {j = x} ^ i (-1) ^ {i - j} \binom{j}{x} \binom{i}{j} \\ &= \sum _ {i = x} ^ n f(i) \sum _ {j = x} ^ i (-1) ^ {i - j} \binom{i}{x} \binom{i - x}{j - x} \\ &= \sum _ {i = x} ^ n \binom{i}{x} f(i) \sum _ {j = x} ^ i (-1) ^ {i - j} \binom{i - x}{j - x} \\ &= \sum _ {i = x} ^ n \binom{i}{x} f(i) \sum _ {j = 0} ^ {i - x} (-1) ^ {i - (j + x)} \binom{i - x}{j} \\ &= \sum _ {i = x} ^ n \binom{i}{x} f(i) \sum _ {j = 0} ^ {i - x} (-1) ^ {i - x - j} \binom{i - x}{j} \\ &= \sum _ {i = x} ^ n \binom{i}{x} f(i) [i - x = 0] \\ &= f(x) \end{aligned} \]

这是一条恒等式，即证。我们发现，为了求出答案 \(g(x)\)，使用右边的等式，可以轻松使用「至少」的结果表示出「恰好」的答案，也就解决了原问题。

模型 \(2\)：「至多」\(\Leftrightarrow\)「恰好」

\[\large f(x) = \sum \limits _ {i = 0} ^ x \dbinom{n - i}{n - x} g(i) \Longleftrightarrow g(x) = \sum _ {i = 0} ^ x (-1)^{x - i} \binom{n - i}{n - x} f(i) \tag{Thm 2.1} \label{thm21} \]

使用「钦定」求出的答案一般来说都是「至少」满足的答案。但是，有一些问题，我们会通过「钦定」\(n - x\) 个限制不能满足，求出在「钦定意义」下，「至多」满足 \(x\) 个限制的答案。具体例子将在后文例题 & 习题部分呈现。

在「钦定意义」下，「至多满足 \(x\) 个限制」等价于「至少不满足 \(n - x\) 个限制」。因为我们总是可以把「不满足原问题限制」看做一个新的限制。

那么我们不妨尝试套用模型 \(1\) 的反演公式。记 \(f(x) = f'(n - x)\)，表示至少满足 \(x\) 个条件，其中 \(f'\) 就符合模型 \(1\) 的「至少」到「恰好」的转化了。根据 \(\ref{thm11}\)，有 \(f'(x) = \sum \limits _ {i = x} ^ n \dbinom{i}{x} g'(i)\)，其中 \(g'(x)\) 表示「恰好」不满足 \(x\) 个条件，相当于 \(g(n - x)\)，即「恰好」满足 \(n - x\) 个条件。通过基础变形可以得到：

\[\begin{aligned} f(n - x) &= \sum \limits _ {i = x} ^ n \dbinom{i}{x} g(n - i) \\ f(x) &= \sum \limits _ {i = n - x} ^ n \dbinom{i}{n - x} g(n - i) \\ &= \sum \limits _ {i = 0} ^ x \dbinom{n - i}{n - x} g(i) \\ \end{aligned} \]

这就是 \(\ref{thm21}\) 左侧的等式。同样类似地，根据 \(\ref{thm11}\)，由于 \(g'(x) = \sum \limits_ {i = x} ^ n (-1)^{i - x} \dbinom{i}{x} f'(i)\)，所以有：

\[\begin{aligned} g(n - x) &= \sum _ {i = x} ^ n (-1)^{i - x} \binom{i}{x} f(n - i) \\ g(x) &= \sum _ {i = n - x} ^ n (-1)^{i - (n - x)} \binom{i}{n - x} f(n - i) \\ &= \sum _ {i = 0} ^ x (-1)^{(n - i) - (n - x)} \binom{n - i}{n - x} f(i) \\ &= \sum _ {i = 0} ^ x (-1)^{x - i} \binom{n - i}{n - x} f(i) \\ \end{aligned} \]

这就是 \(\ref{thm21}\) 右侧的等式。我们也就得出了「钦定意义」下「至多」到「恰好」的转化。

为了更加严谨，当然我们也可以尝试类似证明。留给读者作为习题。

「选择类问题」

概述

「选择类问题」问题下的「至少」/「至多」其实就是「传统意义」下的「至少」/「至多」。但是之所以称作其为「选择类问题」，就是为了和上文提到的「钦定类问题」做区别。和「钦定意义」下的「至少」/「至多」不同，「选择意义」下的「至少」/「至多」并不会重复统计，这是这两类问题不同的关键之所在。「传统意义」下「至多」满足 \(x\) 个限制的答案，不就像采用「选择」的方式，从 \(x\) 个限制中，选择出若干限制并满足吗？「至少」也同理。

并且这类问题的限制是等价的，比如染 \(n\) 种颜色，如果把染第 \(i\) 中颜色看做限制 \(i\)，那么这 \(n\) 种颜色是完全等价的；又比如有 \(n\) 行，行与行之间互不干扰，那么这 \(n\) 行是完全等价的。

在「选择意义」下，我们能够求出「至多」满足 \(x\) 个限制的答案；类似地，通过在 \(n - x\) 个限制中，「选择」出不满足的限制，可以求出在「选择意义」下，「至少」满足 \(x\) 个限制的答案。

为了方便叙述，假设下文的「至少」和「恰好」均为「选择意义」下的。

模型 \(2\)：「至多」\(\Leftrightarrow\)「恰好」

\[\large f(x) = \sum _ {i = 0} ^ x \binom{x}{i} g(i) \Leftrightarrow g(x) = \sum \limits _ {i = 0} ^ x (-1)^{x - i} \dbinom{x}{i} f(i) \tag{Thm 2.2} \label{thm22} \]

注意，由于直接「选择」求出的是「至多」，我们先来分析「选择意义」下「至多」到「恰好」的转化。

记 \(f(x)\) 表示「至多」满足 \(x\) 个限制的方案数，\(g(x)\) 表示「恰好」满足 \(x\) 个限制的方案数。

由于这 \(n\) 种限制等价，所以这里 \(f(x)\) 并不包括从 \(n\) 种限制中选出 \(x\) 种限制，也就是没有 \(\dbinom{n}{x}\) 的系数。\(g(x)\) 同理。这和「钦定类问题」是不同的。

首先为了得到 \(\ref{thm22}\) 左侧式子，一样从「恰好」推出「至多」。由于是从 \(x\) 个限制里「选择」，所以可能有一些限制没有被选中，这也是为什么求出来是「至多」的原因。

考虑我们从 \(x\) 种限制中「选择」，实际上只有 \(i\) 种限制被选中，剩余 \(x - i\) 种限制没有被选中。从 \(x\) 中任选 \(i\) 种限制，方案数为 \(\dbinom{x}{i}\)，乘上「恰好」满足 \(i\) 种限制的 \(g(i)\)，求和即可：

\[f(x) = \sum _ {i = 0} ^ x \binom{x}{i} g(i) \]

然后类似地，我们想要证明右边等式成立，可以将其带入左边等式。

\[\begin{aligned} g(x) &= \sum _ {i = 0} ^ x (-1)^{x - i} \dbinom{x}{i} \sum _ {j = 0} ^ i \binom{i}{j} g(j) \\ &= \sum _ {i = 0} ^ x g(i) \sum _ {j = i} ^ x (-1) ^ {x - j} \binom{x}{j} \binom{j}{i} \\ &= \sum _ {i = 0} ^ x g(i) \sum _ {j = i} ^ x (-1) ^ {x - j} \binom{x}{i} \binom{x - i}{j - i} \\ &= \sum _ {i = 0} ^ x \binom{x}{i} g(i) \sum _ {j = i} ^ x (-1) ^ {x - j} \binom{x - i}{j - i} \\ &= \sum _ {i = 0} ^ x \binom{x}{i} g(i) \sum _ {j = 0} ^ {x - i} \binom{x - i}{j} (-1) ^ {x - (j + i)} \\ &= \sum _ {i = 0} ^ x \binom{x}{i} g(i) \sum _ {j = 0} ^ {x - i} \binom{x - i}{j} (-1) ^ {x - i - j} 1 ^ {j} \\ &= \sum _ {i = 0} ^ x \binom{x}{i} g(i) [x - i = 0] \\ &= g(x) \end{aligned} \]

不出意外地，同样发现这是一条恒等式，说明了 \(\ref{thm22}\) 正确性。

事实上，如果不考虑问题的实际意义，利用模型 \(0\) 的 \(\ref{thm0}\) 也可以证明。

点击展开详细证明

设 \(h(x) = (-1) ^ x g(x)\)，有：

\[f(x) = \sum _ {i = 0} ^ x \binom{x}{i} h(i) \]
那么有：

\[g(x) = \frac{h(x)}{(-1) ^ x} = \sum _ {i = 0} ^ x (-1) ^ i \binom{x}{i} f(i) \]
则：

\[\begin{aligned} h(x) &= \sum _ {i = 0} ^ x (-1) ^ {x + i} \binom{x}{i} f(i) \\ &= \sum _ {i = 0} ^ x (-1) ^ {x - i} \binom{x}{i} f(i) \\ \end{aligned} \]
将 \(h\) 视作命题中的 \(g\)，即证。

模型 \(1\)：「至少」\(\Leftrightarrow\)「恰好」

\[\large f(x) = \sum _ {i = x} ^ n \binom{n - x}{n - i} g(i) \Leftrightarrow g(x) = \sum _ {i = x} ^ n (-1)^{i - x} \binom{n - x}{n - i} f(i) \tag{Thm 1.2} \label{thm12} \]

同样，对于某些问题，我们会通过在 \(n - x\) 个限制中，「选择」出不满足的限制，求出在「选择意义」下，「至少」满足 \(x\) 个限制的答案。

在「选择意义」下，同样有「至少满足 \(x\) 个限制」等价于「至多不满足 \(n - x\) 个限制」。我们如法炮制，套用模型 \(2\) 的反演公式。

记 \(f(x) = f'(n - x)\)，表示至少满足 \(x\) 个条件，其中 \(f'\) 就符合模型 \(2\) 的「至多」到「恰好」的转化了。根据 \(\ref{thm22}\)，有 \(f'(x) = \sum \limits _ {i = 0} ^ x \dbinom{x}{i} g'(i)\)，其中 \(g'(x)\) 表示「恰好」不满足 \(x\) 个条件，相当于 \(g(n - x)\)，即「恰好」满足 \(n - x\) 个条件，可以得到：

\[\begin{aligned} f(n - x) &= \sum _ {i = 0} ^ x \binom{x}{i} g(n - i) \\ f(x) &= \sum _ {i = 0} ^ {n - x} \binom{n - x}{i} g(n - i) \\ &= \sum _ {i = x} ^ n \binom{n - x}{n - i} g(i) \\ \end{aligned} \]

这便是 \(\ref{thm12}\) 的左侧式子。借用 \(\ref{thm22}\) 右侧式子 \(g'(x) = \sum \limits _ {i = 0} ^ x (-1)^{x - i} \dbinom{x}{i} f'(i)\) 有：

\[\begin{aligned} g(n - x) &= \sum _ {i = 0} ^ x (-1)^{x - i} \binom{x}{i} f(n - i) \\ g(x) &= \sum _ {i = 0} ^ {n - x} (-1)^{(n - x) - i} \binom{n - x}{i} f(n - i) \\ &= \sum _ {i = x} ^ n (-1)^{(n - x) - (n - i)} \binom{n - x}{n - i} f(i) \\ &= \sum _ {i = x} ^ n (-1)^{i - x} \binom{n - x}{n - i} f(i) \\ \end{aligned} \]

这就是 \(\ref{thm12}\) 右侧的等式。我们也就得出了「选择意义」下「至少」到「恰好」的转化。

为了更加严谨，当然我们也可以尝试类似证明。留给读者作为习题。

例题 & 习题

为了更直观地理解二项式反演的实际应用，我们通过例题来分别说明它在「钦定意义」下和「选择意义」下，如何解决「至少」/「至多」与「恰好」之间的转化关系。

例一、洛谷 P6512 [CEOI2010 day2] pin

「钦定意义」下「至少」与「恰好」的转化。

题意简述：

yzh 给你 \(n\) 个长度为 \(4\) 的字符串，你需要在其中挑出两个送给她，满足恰好有 \(m\) 位不同，请问你有多少种选择的方案。

首先，「相同」往往比「不同」更好考虑，令 \(m \gets 4 - m\)，接下来求解「恰好」有 \(m\) 位相同。此时，二项式反演能提供有效的思路。

首先，将第 \(i\) 位相同视为一个限制，总共有 \(4\) 位，因此共有 \(4\) 个限制。我们要求的是「恰好」满足其中 \(m\) 个限制的方案数。

在处理这类问题时，套路化地，若我们先计算出「至少」或「至多」满足 \(m\) 位相同的方案数，那么通过二项式反演，就能反推出「恰好」满足 \(m\) 位相同的方案数。

此题我们不妨考虑「钦定」\(x\) 个限制必须满足，即保证某 \(x\) 位必须相等，求出方案数。

具体来说，我们枚举并「钦定」\(4\) 位中的某些位必须相同，设其为 \(S \subseteq \{ i \} _ {i = 1} ^ 4\)。接下来，针对挑选出的两个串，只需要保证 \(S\) 中的这几位必须相同。我们可以使用字符串哈希，并且是仅对 \(S\) 中的那些位进行哈希，从而快速统计有多少对字符串，仅考虑 \(S\) 中的那些位，是相等的。最后，将其累加到 \(f(\vert S \vert)\)，通过反演公式 \(\ref{thm11}\) 右侧 \(g\) 关于 \(f\) 的表达式，求出 \(g(m)\) 即为答案。

点击查看代码

#include <iostream>
#include <cstdio>
#include <unordered_map>
using namespace std;

using ull = unsigned long long;

int n, m;
char str[50010][5];
long long f[5];

const int frac[5] = {1, 1, 2, 6, 24};
inline int C(int n, int m) {
	return frac[n] / frac[m] / frac[n - m];
}

signed main() {
	scanf("%d%d", &n, &m), m = 4 - m;
	for (int i = 1; i <= n; ++i) scanf("%s", str[i]);
	for (int mask = 0; mask < 1 << 4; ++mask) {
		long long res = 0;
		unordered_map<ull, int> table;
		for (int i = 1; i <= n; ++i) {
			ull hsh = 0;
			for (int j = 0; j < 4; ++j) {
				hsh *= 131;
				if (mask & 1 << j) hsh += str[i][j];
			}
			res += table[hsh];
			++table[hsh];
		}
		f[__builtin_popcount(mask)] += res;
	}
	long long ans = 0;
	for (int k = m; k <= 4; ++k) {
        if ((k - m) & 1)
            ans -= C(k, m) * f[k];
        else
            ans += C(k, m) * f[k];
	}
	printf("%lld", ans);
	return 0;
}

例二、「FJWC2020Day4-IJN」夕张的改造

「钦定意义」下「至多」与「恰好」的转化。

题意简述：

给定一棵 \(n\) 个节点的树。一次操作为断边再连边，需保证仍为树。求 \(k\) 次操作后树的形态个数。

一句话题解：Prufer 序列求出「钦定意义」下「至多」\(k\) 条边不变的方案数，用 \(\ref{thm21}\) 反演出「恰好」\(k\) 条边不变的方案数。

更详细的题解及代码见我的题解。

例三、洛谷 P6076 [JSOI2015] 染色问题

「选择意义」下「至多」与「恰好」的转化。

题意简述：

yzh 有一个 \(n \times m\) 的矩形棋盘。她需要用 \(c\) 种颜色对这个棋盘染色，满足下列条件：

棋盘的每一个小方格既可以染色，也可以不染色。

棋盘的每一行至少有一个小方格被染色。

棋盘的每一列至少有一个小方格被染色。

每种颜色都在棋盘上出现至少一次。

首先，将「每一」替换成「恰好」，原题转化成要求棋盘中「恰好」有 \(n\) 行被染色，「恰好」有 \(m\) 列被染色，「恰好」出现了 \(c\) 种颜色。

考虑使用「选择」的方式，一步步拆解问题。

首先拆掉颜色的限制。考虑计算出「选择意义」下，「至多」出现 \(x\) 种颜色的方案数。也就是说我们每个格子要么不染色，要么染的颜色为这 \(x\) 种中的一种。这样，我们相当于在 \(x\) 个限制中，选出了若干限制的方案数。

类似地，逐步拆去列、行的限制，最后得出这样一个问题：一个 \(n \times m\) 的棋盘，「至多」有 \(n\) 行被染色，「至多」有 \(m\) 列被染色，「至多」出现 \(c\) 种颜色。这个问题的方案数就是 \((c + 1)^{nm}\)。

再一步步用 \(\ref{thm22}\) 反演回来，得到答案的表达式为：

\[\sum _ {t = 0} ^ c \binom{c}{t} (-1)^{c - t} \sum _ {j = 0} ^ m \binom{m}{j} (-1)^{m - j} \sum _ {i = 0} ^ n \binom{n}{i} (-1)^{n - i} (t + 1) ^ {ij} \]

时间复杂度是 \(\Theta(nmc)\)，能通过此题。

点击查看代码

#include <iostream>
#include <cstdio>
using namespace std;

const int mod = 1e9 + 7;

constexpr inline int add(const int a, const int b) {
    return a + b >= mod ? a + b - mod : a + b;
}

constexpr inline int sub(const int a, const int b) {
    return a - b < 0 ? a - b + mod : a - b;
}

constexpr inline int mul(const int a, const int b) {
    return 1ll * a * b % mod;
}

int n, m, c, frac[520], ifrac[520], Inv[520];
int f[520], pw[520 * 520];

int C(int n, int m) {
	return mul(frac[n], mul(ifrac[m], ifrac[n - m]));
}

signed main() {
	scanf("%d%d%d", &n, &m, &c);
	frac[0] = ifrac[0] = 1;
	for (int i = 1; i <= 400; ++i) {
		frac[i] = mul(frac[i - 1], i);
		Inv[i] = i == 1 ? 1 : sub(0, mul(mod / i, Inv[mod % i]));
		ifrac[i] = mul(ifrac[i - 1], Inv[i]);
	}
    int ans = 0;
    for (int t = 0; t <= c; ++t) {
        pw[0] = 1;
        for (int i = 1; i <= n * m; ++i)
            pw[i] = mul(pw[i - 1], t + 1);
        for (int j = 0; j <= m; ++j) {
            for (int i = 0; i <= n; ++i) {
                int res = mul(pw[i * j], mul(mul(C(n, i), C(m, j)), C(c, t)));
                if (((c - t) ^ (m - j) ^ (n - i)) & 1)
                    ans = sub(ans, res);
                else
                    ans = add(ans, res);
            }
        }
    }
	printf("%d", ans);
	return 0;
}

其实可以优化。拆限制不要全拆掉，到了这个问题其实可以停下了：一个 \(n \times m\) 的棋盘，「恰好」有 \(n\) 行被染色，「至多」有 \(m\) 列被染色，「至多」出现 \(c\) 种颜色。考虑一行被染色的方案数为 \((c + 1) ^ m - 1\)，这个问题的方案数就是 \(\Big( (c + 1) ^ m - 1 \Big ) ^ n\)。

所以答案为：

\[\sum _ {t = 0} ^ c \binom{c}{t} (-1)^{c - t} \sum _ {j = 0} ^ m \binom{m}{j} (-1)^{m - j} \Big( (t + 1) ^ j - 1 \Big ) ^ n \]

时间复杂度：\(\Theta(c \min \{ n, m \} \log \max \{ n, m \})\)

点击查看代码

#include <iostream>
#include <cstdio>
using namespace std;

const int mod = 1e9 + 7;

constexpr inline int add(const int a, const int b) {
    return a + b >= mod ? a + b - mod : a + b;
}

constexpr inline int sub(const int a, const int b) {
    return a - b < 0 ? a - b + mod : a - b;
}

constexpr inline int mul(const int a, const int b) {
    return 1ll * a * b % mod;
}

constexpr inline int pow(const int a, const int p) {
    int res = 1, base = a % mod, b = p;
    while (b){
        if (b & 1) res = mul(res, base);
        base = mul(base, base), b >>= 1;
    }
    return res;
}


int n, m, c, frac[520], ifrac[520], Inv[520];
int f[520];

int C(int n, int m) {
	return mul(frac[n], mul(ifrac[m], ifrac[n - m]));
}

signed main() {
	scanf("%d%d%d", &n, &m, &c);
    if (n > m) swap(n, m);
	frac[0] = ifrac[0] = 1;
	for (int i = 1; i <= 400; ++i) {
		frac[i] = mul(frac[i - 1], i);
		Inv[i] = i == 1 ? 1 : sub(0, mul(mod / i, Inv[mod % i]));
		ifrac[i] = mul(ifrac[i - 1], Inv[i]);
	}
    int ans = 0;
    for (int t = 0; t <= c; ++t) {
        for (int j = 0, pw = 1; j <= n; ++j, pw = mul(pw, t + 1)) {
            int res = mul(pow(sub(pw, 1), m), mul(C(c, t), C(n, j)));
            if (((c - t) ^ (n - j)) & 1)
                ans = sub(ans, res);
            else
                ans = add(ans, res);
        }
    }
	printf("%d", ans);
	return 0;
}

例四、yzh 的生日礼物

「选择意义」下「至少」与「恰好」的转化。

点击展开题意描述

yzh 生日要到啦！你想为她准备一份精美的生日礼物。以你对她的了解，她早就喜欢上一个价值 \((10^9 + 520)^{10^9 + 1314}\) 的项链已久啦。可是~~由于你的钱包吃紧~~，由于你希望自己亲手制作一个送给她，因为虽然你不懂浪漫，但你认为亲手制作的是 \(\infty\) 价之宝！

这个项链由 \(n\) 颗彩色的珠子串成。你手头只有 \(c\) 种颜色的珠子，并且恰巧就是她喜欢的 \(c\) 种颜色！

你希望在她 \(x\) 岁时，送给她的项链恰好有 \(x\) 种颜色没有出现。你幻想着，随着岁月流转，你送给她的项链的颜色越来越少，直到只剩下某一种颜色。越来越少的颜色，正象征着你们之间感情的愈加纯粹和坚定。你们的岁月如项链般一圈圈相连，色彩减少，但心意愈加珍贵。每一年的项链，都是你们一路走来的情感见证，串联起你们共同度过的每一个美好时刻。

你和她之间的点点滴滴又浮现在你的脑海中，你感到幸福、也感到快乐。你忘不了你们在一起看过的每一场电影，忘不了你们一同在漫天璀璨星辰下散步，更忘不了最初见到彼此的那一瞬间的悸动。

想到这，你脑中突然蹦出一个问题：对于 \(1 \sim c\) 的每一年，你送给她的项链有多少种方案？

题意简述：

给出一个长为 \(n\) 的环，要用 \(c\) 颜色染色。求出对于每一个 \(i \in [1, c]\)，恰好没出现 \(i\) 种颜色的方案数。

「恰好」没出现 \(i\) 种颜色的方案数不好求，可以转成求「至少」没出现 \(i\) 种颜色的方案数。这相当于从 \(c - i\) 中颜色中挑选，方案数为 \(\cfrac{(c - i)^n}{n}\)，最后用 \(\ref{thm12}\) 反演一下就行了。答案就是 \(\binom{c}{c - i} f(i)\)。

题目不难，可能有一个 \(\cfrac{1}{n}\) 的坑点？如果稍稍转化一下能用「选择意义」下「至多」与「恰好」的转化解决。

例五、错排

题目链接：HDU；洛谷。

题意简述：

求长为 \(n\) 的排列的错排有几种。即 \(\forall i \in [1, n], p_i \neq i\)。

为了哄好 yzh，你需要使用二项式反演的解法。

把「\(i\) 错排了」看做第 \(i\) 个限制。有两种思考方式：

「选择意义」下「至多」与「恰好」的转化。
考虑「选择意义」下「至多」满足 \(x\) 个限制的答案，即错排的数字只能从 \(x\) 中「选择」，剩下 \(n - x\) 种颜色没有错排，待在各自的位置上。这时，方案数就是 \(x!\)，这是没有重复计数的，符合「选择意义」。用 \(\ref{thm22}\) 反演即可。
\[g(x) = \sum _ {i = 0} ^ x (-1)^{x - i} \dbinom{x}{i} i! \]
答案 \(g(n) = \sum \limits _ {i = 0} ^ x (-1)^{x - i} \dbinom{x}{i} i!\)。
「钦定意义」下「至多」与「恰好」的转化。
考虑「钦定意义」下「至多」满足 \(x\) 个限制的答案。我们钦定 \(n - x\) 个限制必不满足，剩下 \(x\) 个限制随便排，方案数即为 \(\dbinom{n}{n - x} x!\)。用 \(\ref{thm21}\) 反演即可。
\[\begin{aligned} g(x) &= \sum _ {i = 0} ^ x (-1)^{x - i} \binom{n - i}{n - x} \dbinom{n}{n - i} i! \\ &= \sum _ {i = 0} ^ x (-1)^{x - i} \binom{n}{n - x} \binom{x}{x - i} i! \\ &= \sum _ {i = 0} ^ x (-1)^{x - i} \binom{n}{n - x} \binom{x}{i} i! \\ \end{aligned} \]
答案同样为 \(g(n) = \sum \limits _ {i = 0} ^ x (-1)^{x - i} \dbinom{x}{x - i} i!\)。

从这题我们发现「钦定」和「选择」有时候也是可以相互转化的。

习题

这里总结了一些习题，大家可以练练手。

欢迎补充。

总结

二项式反演为我们提供了一种灵活处理「至少」/「至多」与「恰好」之间转换的方法。在信息学竞赛中的许多问题，特别是涉及到组合计数、限制条件的题目中，二项式反演是非常有效的工具。

并且我们弄清算出的「至少」/「至多」有没有重复计数的问题，思考是「钦定类问题」还是「选择类问题」，从而选择正确的模型解决问题。

希望这篇文章能帮助你更好地理解和应用二项式反演。

结论

模型 \(0\)

\[\Large f(x) = \sum _ {i = 0} ^ x (-1)^i \binom{x}{i} g(i) \Longleftrightarrow g(x) = \sum _ {i = 0} ^ x (-1) ^ i \binom{x}{i} f(i) \tag{\ref{thm0}} \]

模型 \(1\)：「至少」\(\Leftrightarrow\)「恰好」

「钦定类问题」

\[\Large f(x) = \sum _ {i = x} ^ n \binom{i}{x} g(i) \Longleftrightarrow g(x) = \sum _ {i = x} ^ n (-1)^{i - x} \binom{i}{x} f(i) \tag{\ref{thm11}} \]

「选择类问题」

\[\Large f(x) = \sum _ {i = x} ^ n \binom{n - x}{n - i} g(i) \Longleftrightarrow g(x) = \sum _ {i = x} ^ n (-1)^{i - x} \binom{n - x}{n - i} f(i) \tag{\ref{thm12}} \]

模型 \(2\)：「至多」\(\Leftrightarrow\)「恰好」

「钦定类问题」

\[\Large f(x) = \sum \limits _ {i = 0} ^ x \dbinom{n - i}{n - x} g(i) \Longleftrightarrow g(x) = \sum _ {i = 0} ^ x (-1)^{x - i} \binom{n - i}{n - x} f(i) \tag{\ref{thm21}} \]

「选择类问题」

\[\Large f(x) = \sum _ {i = 0} ^ x \binom{x}{i} g(i) \Longleftrightarrow g(x) = \sum \limits _ {i = 0} ^ x (-1)^{x - i} \dbinom{x}{i} f(i) \tag{\ref{thm22}} \]

<!-- script -->
<script>
sidebarToggle()
</script>