组合数学学习笔记 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} \] 证毕。