组合数学学习笔记 02 二项式反演

进入分类索引，阅读该专题下的往期笔记。

二、二项式反演

2.1 基本形式

对于定义在域 $X$ 上的实值函数 $F(n)$ 与 $G(n)$，若由如下递推关系

$G(n)=\sum\limits_{i=0}^n\binom n i F(i) \tag{1}$

得到 $G(n)$ 关于 $F(i)$ 的表达式，则可以通过如下的递推关系通过 $G(i)$ 反解 $F(n)$：

$\boxed{F(n)=\sum\limits_{i=0}^n\binom n i (-1)^{n-i} G(i) \tag{2}}$

上述通过 $G$ 反解 $F$ 的过程称为二项式反演。

要证明二项式反演，下面引入两个二项式系数引理。

引理 1 $\dbinom n i\dbinom i k=\dbinom n k \dbinom {n-k} {i-k}$。

证明考虑组合意义：在 $n$ 个元素中先取出 $i$ 个元素，再在 $i$ 个元素中取出 $k$ 个元素的方案数，显然等价于，在 $n$ 个元素中直接取出 $k$ 个元素，而后在剩下 $n-k$ 个元素中再选出来 $i-k$ 个元素的方案数。

引理 2 $\sum\limits_{i=0}^n(-1)^{i}\dbinom n k=[n=0]$。

证明考虑二项式定理在 $x=1,y=-1$ 时的特殊情况，有 $\sum\limits_{i=0}^n\dbinom n i (-1)^i1^{n-i}=0^n=[n=0]$。

下面给出二项式反演的证明。

证明将 $(1)$ 式直接代入 $(2)$式，应用引理 1，有

$\begin{aligned} F(n)&=\sum\limits_{i=0}^n\binom n i (-1)^{n-i}\sum\limits_{j=0}^i\binom i j F(j) \\ &=\sum\limits_{i=0}^n\sum\limits_{j=0}^i\binom n i \binom i j (-1)^{n-i}F(j)\\ &=\sum\limits_{i=0}^n\sum\limits_{j=0}^i\binom n j \binom {n-j} {i-j} (-1)^{n-i}F(j)\\ &=\sum\limits_{j=0}^n\binom n j F(j)\sum_{i=j}^n(-1)^{n-i}\binom {n-j} {i-j} \end{aligned}$

令 $t=i-j$，则 $i=t+j$，应用引理 2，继续推上面的式子，有

$\begin{aligned} F(n)&=\sum\limits_{j=0}^n\binom n j F(j)\sum_{i=j}^n(-1)^{n-i}\binom {n-j} {i-j} \\ &=\sum\limits_{j=0}^n\binom n j F(j)\sum\limits_{t=0}^{n-j}(-1)^{n-t-j}\binom {n-j}{t} \\ &=\sum\limits_{j=0}^n\binom n j F(j)[n-j=0] \\ &=\binom n n F(n) \\ &=F(n) \end{aligned}$

证毕。

2.2 第二种形式

还是对于定义在域 $X$ 上的实值函数 $F(n)$ 与 $G(n)$，若由如下递推关系

$G(n)=\sum\limits_{i=n}^m\binom i n F(i) \tag{3}$

则可以通过下面的递推关系利用 $G(i)$ 反解 $F(n)$：

$\boxed{F(n)=\sum\limits_{i=n}^m\binom i n (-1)^{i-n}G(i) \tag{4}}$

下面给出这种形式的证明。

证明将 $(3)$ 式直接代入 $(4)$ 式，再次利用上述引理，有

$\begin{aligned} F(n)&=\sum\limits_{i=n}^m\binom i n (-1)^{i-n}\sum\limits_{j=i}^m\binom j iF(j) \\ &=\sum\limits_{i=n}^m\sum\limits_{j=i}^m\binom j i \binom i n (-1)^{i-n}F(j) \\ &=\sum\limits_{i=n}^m\sum\limits_{j=i}^m\binom j n \binom {j-n} {i-n} (-1)^{i-n}F(j) \\ &=\sum\limits_{j=n}^m\binom j n F(j)\sum\limits_{i=n}^j\binom {j-n}{i-n}(-1)^{i-n} \end{aligned}$

令 $t=i-n$，则 $i=t+n$，继续推上面的式子，有

$\begin{aligned} F(n)&=\sum\limits_{j=n}^m\binom j n F(j)\sum\limits_{i=n}^j\binom {j-n}{i-n}(-1)^{i-n} \\ &=\sum\limits_{j=n}^m\binom j n F(j)\sum\limits_{t=0}^{j-n}(-1)^{t} \binom {j-n}{t} \\ &=\sum\limits_{j=n}^m\binom j n F(j) [j-n=0] \\ &=\binom n n F(n) \\ &=F(n) \end{aligned}$

证毕。