二项式反演

二项式反演的推导核心在于利用组合恒等式和交换求和顺序。最关键的数学工具是以下这个正交性恒等式：

$\sum_{j=k}^{n} (-1)^{j-k} \binom{n}{j} \binom{j}{k} = \delta_{nk}$

其中 $\delta_{nk}$ 是克罗内克函数（当 $n=k$ 时为 1，否则为 0）。
Also [n=k]

下面我将分步推导最常用的形式一：

目标

已知：

$f(n) = \sum_{k=0}^{n} \binom{n}{k} g(k) \quad \cdots (1)$

求证：

$g(n) = \sum_{k=0}^{n} (-1)^{n-k} \binom{n}{k} f(k) \quad \cdots (2)$

---

推导过程

第一步：代入

我们将公式 (1) 中的 $f(k)$ 代入到公式 (2) 的右边（RHS），看看能否化简得到左边的 $g(n)$。

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

将 $f(k) = \sum_{j=0}^{k} \binom{k}{j} g(j)$ 代入上式：

$\text{RHS} = \sum_{k=0}^{n} (-1)^{n-k} \binom{n}{k} \left[ \sum_{j=0}^{k} \binom{k}{j} g(j) \right]$

第二步：交换求和顺序

目前的求和范围是：

• 外层 $k$ 从 $0$ 到 $n$
• 内层 $j$ 从 $0$ 到 $k$

这等价于满足条件 $0 \le j \le k \le n$ 的所有整数对 $(j, k)$。 我们可以先枚举 $j$，再枚举 $k$：

• $j$ 的范围是从 $0$ 到 $n$
• 对于固定的 $j$， $k$ 的范围是从 $j$ 到 $n$

交换后：

$\text{RHS} = \sum_{j=0}^{n} g(j) \left[ \sum_{k=j}^{n} (-1)^{n-k} \binom{n}{k} \binom{k}{j} \right]$

注意：我们将与 $k$ 无关的 $g(j)$ 提到了内层求和符号的外面。

第三步：化简内层求和

我们要处理方括号内的部分：

$S = \sum_{k=j}^{n} (-1)^{n-k} \binom{n}{k} \binom{k}{j}$

利用组合数性质 $\binom{n}{k} \binom{k}{j} = \binom{n}{j} \binom{n-j}{k-j}$： 直观理解：从 $n$ 个里选 $k$ 个，再从这 $k$ 个里选 $j$ 个，等价于先从 $n$ 个里直接选出那最终的 $j$ 个 ($\binom{n}{j}$)，然后从剩下的 $n-j$ 个里选出 $k-j$ 个来凑齐 $k$ 个 ($\binom{n-j}{k-j}$)。

代入 $S$：

$S = \sum_{k=j}^{n} (-1)^{n-k} \binom{n}{j} \binom{n-j}{k-j}$

提取与 $k$ 无关的 $\binom{n}{j}$：

$S = \binom{n}{j} \sum_{k=j}^{n} (-1)^{n-k} \binom{n-j}{k-j}$

令 $m = k - j$。当 $k=j$ 时 $m=0$；当 $k=n$ 时 $m=n-j$。 同时，指数 $n-k = n-(m+j) = (n-j)-m$。

$S = \binom{n}{j} \sum_{m=0}^{n-j} (-1)^{(n-j)-m} \binom{n-j}{m}$

第四步：利用二项式定理

观察求和部分 $\sum_{m=0}^{N} (-1)^{N-m} \binom{N}{m}$，其中 $N = n-j$。 根据二项式定理：

$(x+y)^N = \sum_{m=0}^{N} \binom{N}{m} x^{N-m} y^m$

令 $x=1, y=-1$，则：

$(1-1)^N = \sum_{m=0}^{N} \binom{N}{m} (1)^{N-m} (-1)^m = \sum_{m=0}^{N} (-1)^m \binom{N}{m}$

等等，我们的式子是 $(-1)^{N-m}$。由于 $(-1)^{N-m} = (-1)^N \cdot (-1)^{-m} = (-1)^N \cdot (-1)^m$（因为 $(-1)^{-m} = (-1)^m$），所以：

$\sum_{m=0}^{N} (-1)^{N-m} \binom{N}{m} = (-1)^N \sum_{m=0}^{N} (-1)^m \binom{N}{m} = (-1)^N (1-1)^N$

这里需要讨论 $N$ 的值：

1. 如果 $N > 0$（即 $n > j$）：

   $(1-1)^N = 0^N = 0$

   所以整个求和结果为 0。

2. 如果 $N = 0$（即 $n = j$）： 求和只有一项 $m=0$：

   $(-1)^{0-0} \binom{0}{0} = 1 \cdot 1 = 1$

   或者看公式：$(-1)^0 (1-1)^0 = 1 \cdot 1 = 1$（约定 $0^0=1$）。

综上所述：

$\sum_{m=0}^{n-j} (-1)^{(n-j)-m} \binom{n-j}{m} = \begin{cases} 1 & \text{if } n=j \\ 0 & \text{if } n \neq j \end{cases} = \delta_{nj}$

因此，内层求和 $S$ 简化为：

$S = \binom{n}{j} \delta_{nj}$

第五步：得出结论

回到第二步末尾的式子：

$\text{RHS} = \sum_{j=0}^{n} g(j) \cdot S = \sum_{j=0}^{n} g(j) \binom{n}{j} \delta_{nj}$

由于 $\delta_{nj}$ 仅在 $j=n$ 时为 1，其他情况为 0，求和中只有 $j=n$ 这一项保留下来：

$\text{RHS} = g(n) \binom{n}{n} \cdot 1 = g(n) \cdot 1 = g(n)$

$\text{RHS} = g(n) = \text{LHS}$

证毕。

---

补充：形式二的简要推导思路

形式二： 已知 $f(n) = \sum_{k=n}^{N} \binom{k}{n} g(k)$，求 $g(n)$。

这种形式通常通过变量代换转化为形式一，或者使用生成函数。 另一种常见的推导是利用下指标反转或差分算子。

但在竞赛中，最稳妥的方法是记住形式一，如果遇到形式二，可以通过重新定义下标或集合关系将其转化为形式一的结构，或者直接记忆结论：

$g(n) = \sum_{k=n}^{N} (-1)^{k-n} \binom{k}{n} f(k)$

其推导逻辑与上面完全一致，只是求和的上下限和组合数的物理意义（“至少” vs “至多”）发生了变化，核心的正交性恒等式 $\sum (-1)^k \binom{n}{k} = [n=0]$ 依然起作用。

容斥原理