二项式反演与序列变换

形式陈述

设 $a_0,a_1,\ldots$ 与 $b_0,b_1,\ldots$ 为有理数序列。使用二项式系数，二项式反演断言

b_n=\sum_{k=0}^n\binom nk a_k \quad\Longleftrightarrow\quad a_n=\sum_{k=0}^n(-1)^{n-k}\binom nk b_k.

每个和有限，所以也能在任意阿贝尔群中用整数倍解释。后面除以阶乘的 EGF 公式才需要允许有理数运算。

如果 $A(z)=\sum a_nz^n$ 、 $B(z)=\sum b_nz^n$ 为普通生成函数，则

B(z)=\frac1{1-z}A\left(\frac z{1-z}\right),\qquad A(z)=\frac1{1+z}B\left(\frac z{1+z}\right).

如果改用指数生成函数 $\widehat A(z)=\sum a_nz^n/n!$ ，则 $\widehat B=e^z\widehat A$ ，逆变换为乘 $e^{-z}$ 。两个编码各有自己的翻译，不能遗漏前因子或把 OGF 代换搬给 EGF。

直觉

$b_n$ 常记录“在 $n$ 个标签中选一个活跃子集，再给该子集一份结构”。若 $k$ 元活跃集上的结构数总是 $a_k$ ，就有 $\binom nk a_k$ 个对象。知道所有总体 $b_n$ ，反演便逐层去掉较小活跃集的贡献。

直接消去证明

把 $b_k$ 的定义代入候选逆式，交换有限求和。 $a_j$ 的系数是

\sum_{k=j}^n(-1)^{n-k}\binom nk\binom kj =\binom nj\sum_{k=j}^n(-1)^{n-k}\binom{n-j}{k-j}.

二项式定理使最后的和为 $(1-1)^{n-j}$ ： $j<n$ 时为零， $j=n$ 时为一。故最终只剩 $a_n$ 。反向计算同样成立，也可用对角元为一的三角递推唯一性推回去。

OGF 版本使用 $\sum_{n\ge k}\binom nkz^n=z^k/(1-z)^{k+1}$ 。这项恒等式由 $(1-z)^{-k-1}$ 的隔板计数展开得到。逐次代入后就是主公式；内层 $z/(1-z)$ 常数项为零，故复合在形式上合法。EGF 版本则直接用 $\binom nk/n!=1/(k!(n-k)!)$ ，剩下的卷积恰为 $e^z\widehat A$ 。

例子与边界

一份 $n$ 元排列由“哪些点移动”和移动点上的错排唯一确定。因此

n!=\sum_{k=0}^n\binom nkD_k.

反演立即给 $D_n=\sum_{k=0}^n(-1)^{n-k}\binom nk k!$ 。在 $n=4$ 时按正向复核： $24=1+6\cdot1+4\cdot2+9$ ，依次对应移动零、二、三、四个点；不存在恰移动一个点的排列。反向为 $D_4=1-4+12-24+24=9$ 。

再取 $a_n=2^n$ ，二项式定理给 $b_n=3^n$ 。OGF 校验为

\frac1{1-z}\frac1{1-2z/(1-z)}=\frac1{1-3z}.

EGF 则是 $e^z e^{2z}=e^{3z}$ 。同一序列变换对应两种外观完全不同的函数操作。

什么时候不能按大小合并

设有限标签集 $X$ ，每个子集 $S$ 都有局部贡献 $a(S)$ 。累计量为 $b(T)=\sum_{S\subseteq T}a(S)$ 时，总能用布尔格 Möbius 反演恢复。但只有 $a(S)$ 对所有同样大小的 $S$ 相同时，才能压缩为单一序列 $a_{|S|}$ 与 $\binom nk$ 。禁位棋盘里不同的二格集合可能冲突也可能兼容，不能仅因都含两格就给它们相同交集数；车数正是在补这个结构。

变换也不保持非负性。若人为指定 $b_0=1,b_1=0$ ，逆向给 $a_1=-1$ 。它依然是合法代数反演，却不能自动解释为一类对象的数量。

推论与应用

令 $b_n=f(n)$ ，逆式正是 $a_n=\Delta^nf(0)$ ；正向式又是整数节点的 Newton 公式 $f(n)=\sum_k\binom nk\Delta^kf(0)$ 。因此有限差分表与容斥变换实际上共享同一个三角消去机制。

本页使用的“无符号正向、交替符号逆向”约定不自反。有些文献定义 $b_n=\sum_k(-1)^k\binom nk a_k$ ，那一个变换才是自身的逆；看到“二项式变换是对合”时必须先核对符号。

任意无限数值级数的求值还需要收敛条件。本页的 OGF 等式只作逐系数形式运算；即使序列为 $n!$ ，导致非零点处 OGF 发散，反演本身仍完全有效。

参考资料

Richard P. Stanley，Enumerative Combinatorics, Vol. 1，作者第二版书稿，§2.1，式2.9–2.10与随后矩阵反演，书稿印页225–226；§2.2，Example 2.2.1：错排。§1.9，式1.98–1.99：有限差分对应。
Herbert S. Wilf，generatingfunctionology，作者公开第二版，Chapter 2；本页 OGF 与 EGF 两式已在正文逐系数推导，该链接作为进一步阅读。

形式陈述 ​

直接消去证明 ​

什么时候不能按大小合并 ​

反向链接

形式陈述

直接消去证明

什么时候不能按大小合并