OI 笔记 | myLearn

二项式反演

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

\sum_{j = k}^{n} (- 1)^{j - k} (\binom{n}{j}) (\binom{j}{k}) = δ_{n k}

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

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

目标

已知：

f (n) = \sum_{k = 0}^{n} (\binom{n}{k}) g (k) \dots (1)

求证：

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

推导过程

第一步：代入

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

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

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

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

第二步：交换求和顺序

目前的求和范围是：

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

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

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

交换后：

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

注意：我们将与 $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$ 的值：

如果 $N > 0$ （即 $n > j$ ）：
$(1 - 1)^{N} = 0^{N} = 0$
所以整个求和结果为 0。
如果 $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 & if n = j \\ 0 & if n \neq j \end{cases} = δ_{n j}

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

S = (\binom{n}{j}) δ_{n j}

第五步：得出结论

回到第二步末尾的式子：

RHS = \sum_{j = 0}^{n} g (j) \cdot S = \sum_{j = 0}^{n} g (j) (\binom{n}{j}) δ_{n j}

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

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

RHS = g (n) = 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]$ 依然起作用。

hdu6035 Colorful Tree

AT_dp_u Grouping

AT_dp_v Subtree

FFT

P1002 [NOIP 2002 普及组] 过河卒

P1014 [NOIP 1999 普及组] Cantor 表

P1792 [国家集训队] 种树

P2014 [CTSC1997] 选课

P2748 [USACO16OPEN] Landscaping P

P4025 [PA 2014] Bohater

P5985 [PA 2019] Muzyka pop

P6691 选择题

二项式反演

目标

推导过程

第一步：代入

第二步：交换求和顺序

第三步：化简内层求和

第四步：利用二项式定理

第五步：得出结论

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

容斥原理

二项式反演 ​

目标 ​

推导过程 ​

第一步：代入 ​

第二步：交换求和顺序 ​

第三步：化简内层求和 ​

第四步：利用二项式定理 ​

第五步：得出结论 ​

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

容斥原理 ​

二项式反演

目标

推导过程

第一步：代入

第二步：交换求和顺序

第三步：化简内层求和

第四步：利用二项式定理

第五步：得出结论

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

容斥原理