二项式反演

二项式反演

前言

这个东西学过一段时间，当时基本没理顺，现在感觉还行，就简单点讲讲。

可能需要对容斥有一点理解。

公式推导

来点看得懂的工业化程序。

假设我们已有两个定义在非负整数集上的函数 $F(x),f(x)$。

他们满足这样的关系

$F(n) = \sum_{k = 0}^{n} \dbinom{n}{k} f(k)$

那么必然有

$f(n) = \sum_{k = 0}^{n} (-1)^{n-k} \dbinom{n}{k} F(k)$

注意清楚他们的逻辑关系，现在给出一个推导

$\sum_{k = 0}^{n} (-1)^{n - k} \dbinom{n}{k} F(k) \\ =\sum_{k = 0}^{n} (-1)^{n - k} \dbinom{n}{k} \sum_{i = 0}^{k} \dbinom{k}{i} f(i) \\ =\sum_{k = 0}^{n} \sum_{i = 0}^{k} (-1)^{n-k} \dbinom{n}{k}\dbinom{k}{i}f(i)$

这里借助一个组合恒等式帮助证明

$\dbinom{n}{r}\dbinom{r}{k} = \dbinom{n}{k}\dbinom{n - k}{r - k}$

并交换枚举顺序，那么就有

$\sum_{k = 0}^{n} \sum_{i = 0}^{k} ( - 1)^{n - k} \dbinom{n}{k}\dbinom{k}{i}f(i) \\ = \sum_{k = 0}^{n}\sum_{i = 0}^{k} ( - 1)^{n - k} \dbinom{n}{i}\dbinom{n - i}{k - i} f(i) \\ = \sum_{i = 0}^{n} \dbinom{n}{i} f(i) \sum_{k = i}^{n} \dbinom{n - i}{k - i} ( - 1)^{n - k} \\$

此时考虑将枚举 $k$ 时下调 $i$，那么就有

$\sum_{i = 0}^{n} \dbinom{n}{i} f(i) \sum_{k = i}^{n} \dbinom{n - i}{k - i} ( - 1)^{n - k} \\ = \sum_{i = 0}^{n} \dbinom{n}{i} f(i) \sum_{k = 0}^{n - i} \binom{n - i}{k} ( - 1)^{n - i - k}$

此时再用二项式定理化简

$(a + b)^{n} = \sum_{i = 0}^{n} \dbinom{n}{i} a^i b^{n - i}$

所以有

$\sum_{i = 0}^{n} \dbinom{n}{i} f(i) \sum_{k = 0}^{n - i} \binom{n - i}{k} ( - 1)^{n - i - k} \\ = \sum_{i = 0}^{n} \dbinom{n}{i} f(i) (1 - 1)^{n - i}$

故仅当 $i = n$ 时 $(1 - 1)^0 = 1$，故

$F(n) = \sum_{k = 0}^{n} \dbinom{n}{k} f(k)$

证毕。

组合意义

然而我们在平时做题时很难得到能够直接使用二项式反演的公式，故我们考虑对于函数 $F(x),f(x)$ 赋予一定的实际意义，从而使用到二项式反演。

通常，$f(x)$ 表示我们钦定在已满足有关 $x$ 级别时的方案数，而 $F(x)$ 表示我们恰好满足有关 $x$ 级别时的方案数。

现在举个例子方便我们说明和理解。

错位排列

恰好的我们也找到了一个在学习组合数学时也会遇到的一个问题。

此时我们考虑 $f(x)$ 表示钦定有 $x$ 个位置是正确排序的，那么 $F(x)$ 则表示恰好有 $x$ 个位置是正确排序的。同时 $D_i$ 表示排列大小为 $i$ 的错排方案数。

那我们考虑枚举哪些数是正确排序，而其他数随意排序来表示 $f(x)$。

$f(i) = \dbinom{n}{i} (n - i)!$

同时我们可以通过 $f(k)$ 的定义得到 $F(i)$ 的表达式为

$f(i) = \sum_{j = i}^{n} \dbinom{j}{i} F(j)$

稍微感性一点理解，我们发现对于恰好有 $j$ 个位置正确排序一定是在钦定了 $i$ 个位置正确排序后会被枚举 $\dbinom{j}{i}$ 次。那么二项式反演后

$F(j) = \sum_{i=j}^{n} ( - 1)^{j - i} \dbinom{i}{j}f(i)$

是否有一点奇怪？这同样也是二项式反演，只是表达的是另一种经典形式

$f(n) = \sum_{i = n}^{m} \dbinom{i}{n} F(i) \\ F(n) = \sum_{i = n}^{m} \dbinom{i}{n} ( - 1)^{i-n} f(n)$

以及

$f(n) = \sum_{i = 0}^{n} ( - 1)^{i} \dbinom{n}{i} F(i) \\ F(n) = \sum_{i = 0}^{n} ( - 1)^{i} \dbinom{n}{i} f(i)$

以上三种都是二项式反演的三种经典形式，第二种则是最常用的形式。

应用

现在到了真正的错位排列环节。

考虑到所有的排列方案数为 $n!$，那么我们枚举其中 $i$ 个是正确排列而其余均为错位排列，即

$n! = \sum_{i = 0}^{n} \dbinom{n}{i} D_{n-i} \\ n! = \sum_{i = 0}^{n} \dbinom{n}{i} D_i$

套一个二项式反演即可得到

$D_n = \sum_{i = 0}^{n} \dbinom{n}{i}( - 1)^{n - i} i!$

于是得到了错排方案数的线性求解式。