广义容斥原理与二项式反演

容斥原理

先来复习一下容斥原理

容斥原理

设 \(\mathbf S_1, \mathbf S_2, \cdots, \mathbf S_n\) 为有限集，则：

\[ \left|\bigcup_{i = 1}^n \mathbf S_i\right| = \sum_{1 \leq i \leq n} \left|\mathbf S_i\right| - \sum_{1 \leq i, j \leq n} \left|\mathbf S_i \cap \mathbf S_j \right| + \cdots + (-1)^{n - 1} \left|\bigcap_{i = 1}^n \mathbf S_i\right| \\ \]

广义容斥原理

定义

容斥原理可以看成给定 \(n\) 个条件，求不满足任何一个条件的元素个数。广义容斥原理则是求恰好满足 \(k\) 个条件的情况个数。

广义容斥原理

给定 \(n\) 个条件，设 \(f(x)\) 为恰好满足 \(k\) 个条件的情况数，\(g(x)\) 为钦定 \(x\) 个条件必须满足，剩下的条件满不满足都行的情况数，也就是：

\[ g(x) = \sum_{i = x}^n \binom{i}{x} f(x) \\ \]

那么有：

\[ f(x) = \sum_{i = x}^n (-1)^{i - x} \binom{i}{x} g(i) \\ \]

Tip

我们有时将「钦定 \(x\) 个条件必须满足，剩下的条件满不满足都行」称为「“至少”满足 \(x\) 个条件」，这里“至少”并不是传统意义上的至少，这点需要注意。

为什么 \(g(x)\) 可以用 \(f(x)\) 表示

假设我们选出恰好满足的 \(x\) 个条件，它们构成集合 \(\mathbf S\)；选出“至少”满足的 \(y\) 个条件，它们构成集合 \(\mathbf T\)（其中，第一种钦定方式只对应一种情况，第二种钦定方式对应多种情况）。第一种钦定方式对应的情况如果对第二种钦定方式有贡献，当且仅当 \(\mathbf T \subset \mathbf S\)。也就是说，每一种恰好满足 \(i\) 个条件的情况，对 \(g(x)\) 的贡献为 \(\dbinom{i}{x}\)，而恰好满足 \(i\) 个条件的情况数为 \(f(i)\)，因此 \(f\) 对 \(g(x)\) 的贡献即为 \(\displaystyle\sum_{i = x}^n \binom{i}{x} f(x)\)。通过列举“至少”满足 \(x\) 个条件的所有情况，可以发现每一种情况都是一个恰好满足 \(i\) 个条件（\(i \geq x\)）的情况，也就是说 \(g(x)\) 只有来自 \(f(i), i \geq x\) 的贡献，因此满足上面的关系。

（证明在下文）

应用

例题

有 \(n\) 个球，\(n\) 个盒，球和盒都有 \(1 \sim n\) 的编号。求恰好 \(m\) 个球在对应编号的盒里的情况数。

一般解法

我们都知道错排的公式：

\[ D(n) = n! \sum_{i = 0}^n \frac{(-1)^i}{i!} \\ \]

我们只需要令 \(n\) 个球中的 \(n - m\) 个球进行错排即可，情况数为：

\[ \binom{n}{n - m} D(n - m) = \frac{n!}{m!} \sum_{i = 0}^{n - m} \frac{(-1)^i}{i!} \]

广义容斥解法

虽然用广义容斥解更加麻烦，但是我们可以使用这个例题来帮助理解广义容斥。

设 \(f(x)\) 为 \(n\) 个球中，恰好 \(x\) 个球在对应编号的盒里的情况数，\(g(x)\) 为 \(n\) 个球中，“至少” \(x\) 个球在对应编号的盒里的情况数。\(f(m)\) 即为答案。易得：

\[ g(x) = \binom{n}{x} (n - x)! = \frac{n!}{x!} \\ \]

根据广义容斥原理，有：

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

所求即 \(f(m)\)，与前一种解法结果相同。

二项式反演

定义

二项式反演的四种形式

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

广义容斥原理即形式 4。

证明

前置知识

\[ \begin{aligned} \binom{a}{b}\binom{b}{c} &= \frac{a!}{b! (a - b)!} \times \frac{b!}{c! (b - c)!} \\ &= \frac{a!}{(a - b)! c! (b - c)!} \\ &= \frac{(a - c)!}{(a - b)! (b - c)!} \times \frac{a!}{c! (a - c)!} \\ &= \binom{a - c}{b - c}\binom{a}{c} \\ &= \binom{a - c}{a - b}\binom{a}{c} \\ \end{aligned} \]

形式 1

将 \(f(x) = \displaystyle\sum_{i = 0}^x (-1)^i \dbinom{x}{i} g(i)\) 代入 \(\displaystyle\sum_{i = 0}^x (-1)^i \dbinom{x}{i} f(i)\)，得：

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

因为两侧的形式是对称的，所以形式 1 得证。

Warning

在倒数第三行这里，因为二项式定理不适用于指数为 \(0\) 的情况，因此需要讲 \(j = x\) 的情况单独拆开。

形式 2

\[ \begin{aligned} f(x) &= \sum_{i = 0}^x \binom{x}{i} g(i) \\ &= \sum_{i = 0}^x (-1)^i \binom{x}{i} (-1)^i g(i) \\ \text{令 } G(x) &= (-1)^x g(x) \\ f(x) &= \sum_{i = 0}^x (-1)^i \binom{x}{i} G(i) \\ G(x) &= \sum_{i = 0}^x (-1)^i \binom{x}{i} f(i) \\ (-1)^x g(x) &= \sum_{i = 0}^x (-1)^i \binom{x}{i} f(i) \\ g(x) &= \sum_{i = 0}^x (-1)^{x - i} \binom{x}{i} f(i) \\ \end{aligned} \]

因为变换均等价，所以形式 2 得证。

形式 4

\[ \begin{aligned} f(x) &= \sum_{i = x}^n \binom{i}{x} g(i) \\ f(n - x) &= \sum_{i = n - x}^n \binom{i}{n - x} g(i) \\ &= \sum_{i = 0}^x \binom{n - i}{n - x} g(n - i) \\ \frac{f(n - x)}{\binom{n}{x}} &= \sum_{i = 0}^x \frac{\binom{n - i}{n - x}}{\binom{n}{x}} g(n -i) \\ \frac{f(n - x)}{\binom{n}{n - x}} &= \sum_{i = 0}^x \binom{x}{i} \frac{g(n - i)}{\binom{n}{i}} \\ \text{令 } F(x) &= \frac{f(n - x)}{\binom{n}{n - x}}, G(x) = \frac{g(n - x)}{\binom{n}{n - x}} \\ F(x) &= \sum_{i = 0}^x \binom{x}{i} G(i) \\ G(x) &= \sum_{i = 0}^x (-1)^{x - i} \binom{x}{i} F(i) \\ \frac{g(n - x)}{\binom{n}{x}} &= \sum_{i = 0}^x (-1)^{x - i} \binom{x}{i} \frac{f(n - i)}{\binom{n}{i}} \\ \frac{g(n - x)}{\binom{n}{x}} &= \sum_{i = 0}^x (-1)^{x - i} \binom{x}{i} \frac{f(n - i)}{\binom{n}{i}} \\ \frac{g(n - x)}{\binom{n}{x}} &= \sum_{i = 0}^x (-1)^{x - i} \frac{\binom{n - i}{n - x}}{\binom{n}{x}} f(n - i) \\ g(n - x) &= \sum_{i = 0}^x (-1)^{x - i} \binom{n - i}{n - x} f(n - i) \\ g(n - x) &= \sum_{i = n - x}^n (-1)^{x - n + i} \binom{i}{n - x} f(i) \\ g(n - x) &= \sum_{i = n - x}^n (-1)^{n - x - i} \binom{i}{n - x} f(i) \\ g(x) = &= \sum_{i = x}^n (-1)^{x - i} \binom{i}{x} f(i) \\ \end{aligned} \]

因为变换均等价，所以形式 4 得证。

形式 3

\[ \begin{aligned} f(x) &= \sum_{i = x}^n (-1)^i \binom{i}{x} g(i) \\ &\text{令 } G(x) = (-1)^x g(x) \\ f(x) &= \sum_{i = x}^n \binom{i}{x} G(i) \\ G(x) &= \sum_{i = x}^n (-1)^{x - i} \binom{i}{x} f(i) \\ (-1)^x g(x) &= \sum_{i = x}^n (-1)^{x - i} \binom{i}{x} f(i) \\ g(x) &= \sum_{i = x}^n (-1)^i \binom{i}{x} f(i) \\ \end{aligned} \]

因为变换均等价，所以形式 3 得证。

比起广义容斥原理，二项式反演的其他形式更像是一种公式，不一定具有广义容斥原理那样的组合意义。

应用

还是错排

有 \(n\) 个球，\(n\) 个盒，球和盒都有 \(1 \sim n\) 的编号。求所有球都不在对应编号盒子里的情况数。

二项式反演解法

虽然用二项式反演解更加麻烦，但是我们可以使用这个例题来帮助理解二项式反演。

设 \(f(x)\) 为 \(x\) 个球，\(x\) 个盒，所有球都不在对应编号盒子里的情况数，\(g(x)\) 为 \(x\) 个球，\(x\) 个盒随便放的情况数。那么有：

\[ g(x) = x! = \sum_{i = 0}^x \binom{x}{i} f(i) \\ \]

根据二项式反演，有：

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

与用容斥解法的结果相同。