---
title: "OI 笔记"
cato: learn
labels:
  - oi
  - math
time: "2026-04-24"
---

## 二项式反演

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

$$\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]$ 依然起作用。

## 容斥原理