二项式反演学习笔记

前言

万字长文！这里有我的一些思考和领会，网络上的教程都太潦草了。

并且我发现了新的反演公式！

概述

二项式反演用于转化两个具有特殊关系的函数 (f) 和 (g)，从而方便求解问题。一般来说，直接计算恰好满足 (n) 个限制的答案不好求，但是可以计算出“至少” / “至多”满足 (n) 个限制的答案，运用二项式反演，就能求出“恰好”满足 (n) 个限制的答案。

想直接看结论的可以戳我。

证明 & 推导

一些引理

引理 (1)：二项式定理

普通二项式定理为：

[large (a + b) ^ n = sum _ {i = 0} ^ n binom{n}{i} a^i b^{n-i} ]

证明可以用数学归纳法，不做展开。本篇主要利用 (a = -1, b = 1) 的特殊情形，即：

[begin{aligned} & quad sum _ {i = 0} ^ n binom{n}{i} (-1)^i \ &= sum _ {i = 0} ^ n binom{n}{i} (-1)^i 1^{n-i} \ &= Big (1 + (-1) Big )^n \ &= 0 ^ n end{aligned} ]

注意到当 (n = 0) 的时候，没有意义。观察原式发现此时 (dbinom{0}{0} (-1)^0 = 1)。所以我们有：

[large sum _ {i = 0} ^ n binom{n}{i} (-1)^i = [n = 0] ]

引理 (2)：多步容斥

记 (S_i)（(1 leq i leq n)）表示一个集合，我们有：

[large left vert bigcup_{i = 1}^{n} S_i right vert = sum _ {1 leq i leq n} Big vert S_i Big vert - sum _ {1 leq i lt j leq n} Big vert S_i cap S_j Big vert + cdots + (-1) ^ {n - 1} Bigg vert bigcap _ {i = 1} ^ n S_i Bigg vert ]

即：

[large left vert bigcup_{i = 1}^{n} S_i right vert = sum _ {m = 1} ^ n (-1) ^ {m - 1} sum _ {a_i < a_{i + 1}} Bigg vert bigcap _ {i = 1} ^ m S_{a_i} Bigg vert ]

证明该式等价于证明 (forall x in bigcup limits_{i = 1}^{n} S_i)，其在右边 (sum limits _ {a_i < a_{i + 1}} Bigg vert bigcap limits _ {i = 1} ^ m S_{a_i} Bigg vert) 计算的系数之和为 (1)。记所有包含 (x) 的集合为 (T_1, ldots, T_m)（(m neq 0)），则有：

[begin{aligned} & quad Big vert { T_i mid 1 leq i leq m } Big vert - Big vert { T_i cap T_j mid 1 leq i lt j leq m } Big vert + cdots \ &= binom{m}{1} - binom{m}{2} + cdots + cdots (-1) ^ {m - 1} binom{m}{m} \ &= sum _ {i = 1} ^ {m} (-1)^{i - 1} binom{m}{i} \ &= - sum _ {i = 1} ^ {m} (-1)^i binom{m}{i} \ &= binom{m}{0} - sum _ {i = 1} ^ {m} (-1)^i binom{m}{i} \ &= 1 - [m = 0] \ &= 1 end{aligned} ]

故成立。

引理 (3)：组合数

我们考虑变换 (dbinom{n}{i} dbinom{i}{j})。其组合意义为，(n) 个小球里选出 (i) 个，再从 (i) 个里面选出 (j) 的方案数。我们也可以先从 (n) 个里面选出 (j) 个，再从剩下 (n - j) 里选出 (i - j) 个。表达为：

[dbinom{n}{i} dbinom{i}{j} = binom{n}{j} binom{n - j}{i - j} ]

当然也可以代数证明：

[begin{aligned} dbinom{n}{i} dbinom{i}{j} &= frac{n!}{i! (n-i)!} frac{i!}{j! (i-j)!} \ &= frac{n!}{(n - i)! (i - j)! j!} \ &= frac{n! (n - j)!}{(n - i)! (i - j)! (n - j)! j!} \ &= frac{n!}{j! (n - j)!} frac{(n - j)!}{(n - i)! Big ((n - j) - (n - i) Big)!} \ &= binom{n}{j} binom{n - j}{i - j} end{aligned} ]

引理 (4)：(-1) 的幂次特点

((-1) ^ {a + b} = (-1) ^ {a - b})。这还用证明？

[begin{aligned} 2b &equiv 0 & pmod {2} \ b &equiv -b & pmod {2} \ a + b &equiv a - b & pmod {2} end{aligned} ]

模型 (0)

[large f(x) = sum _ {i = 0} ^ x (-1)^i binom{x}{i} g(i) Longleftrightarrow g(x) = sum _ {i = 0} ^ x (-1) ^ i binom{x}{i} f(i) ]

容斥证明

不妨记 (overline{S_i}) 表示 (S_i) 的补集，有：

[begin{aligned} left vert bigcap_{i = 1}^{n} overline{S_i} right vert &= left vert bigcup_{i = 1}^{n} S_i right vert - left vert bigcup_{i = 1}^{n} overline{S_i} right vert \ &= left vert bigcup_{i = 1}^{n} S_i right vert - sum _ {m = 1} ^ n (-1) ^ {m - 1} sum _ {a_i < a_{i + 1}} Bigg vert bigcap _ {i = 1} ^ m S_{a_i} Bigg vert \ &= left vert bigcup_{i = 1}^{n} S_i right vert + sum _ {m = 1} ^ n (-1) ^ m sum _ {a_i < a_{i + 1}} Bigg vert bigcap _ {i = 1} ^ m S_{a_i} Bigg vert \ &= sum _ {m = 0} ^ n (-1) ^ m sum _ {a_i < a_{i + 1}} Bigg vert bigcap _ {i = 1} ^ m S_{a_i} Bigg vert \ end{aligned} ]

由于 (overline{ overline{S_i} } = S_i)，所以得到类似的式子：

[left vert bigcap_{i = 1}^{n} S_i right vert = sum _ {m = 0} ^ n (-1) ^ m sum _ {a_i < a_{i + 1}} Bigg vert bigcap _ {i = 1} ^ m overline{S_{a_i}} Bigg vert ]

发现形式很像，但是还差一步构造。我们假设能够早出一组 (S_i)，使任意 (k) 个集合的交集大小相等。

不妨记 (f(x)) 表示任意 (x) 个补集的交集大小，对于原集同理记 (g(x))，上式可以分别改写为：

[f(n) = sum _ {i = 0} ^ n (-1) ^ i binom{n}{i} g(i) ]

[g(n) = sum _ {i = 0} ^ n (-1) ^ i binom{n}{i} f(i) ]

即证。

代数证明

容斥比较抽象，尝试代数证明。我们把 (g) 带到 (f) 中去，得到：

[begin{aligned} f(x) &= sum _ {i = 0} ^ x (-1)^i binom{x}{i} sum _ {j = 0} ^ i (-1) ^ j binom{i}{j} f(j) \ &= sum _ {i = 0} ^ x f(i) sum _ {j = i} ^ x (-1) ^ {i + j} binom{j}{i} binom{x}{j} \ &= sum _ {i = 0} ^ x f(i) sum _ {j = i} ^ x (-1) ^ {i + j} binom{x}{i} binom{x - i}{j - i} \ &= sum _ {i = 0} ^ x binom{x}{i} f(i) sum _ {j = i} ^ x (-1) ^ {i + j} binom{x - i}{j - i} \ &= sum _ {i = 0} ^ x binom{x}{i} f(i) sum _ {j = 0} ^ {x - i} (-1) ^ {2i + j} binom{x - i}{j} \ &= sum _ {i = 0} ^ x binom{x}{i} f(i) sum _ {j = 0} ^ {x - i} (-1) ^ j binom{x - i}{j} \ &= sum _ {i = 0} ^ x binom{x}{i} f(i) [x - i = 0] \ &= f(x) end{aligned} ]

即证。

模型 (1)：“至少” (Leftrightarrow) “恰好”

[large f(x) = sum _ {i = x} ^ n binom{i}{x} g(i) Longleftrightarrow g(x) = sum _ {i = x} ^ n (-1)^{i - x} binom{i}{x} f(i) ]

为了解决实际问题，考虑实际意义。考虑有 (n) 个限制，(f(x)) 表示至少满足 (x) 个限制，(g(x)) 表示恰好满足 (x) 个限制。

注意到，(f) 不是简单 (g) 的前缀和，因为会重复计数。

(g(x)) 即为我们的答案，而 (f(x)) 就是我们通过其他算法求出的结果。

通常来说，我们会钦定 (x) 个限制必须满足，剩下的限制可以满足可以不满足，这样就能不用考虑限制的问题，求出 (f)。

考虑如何用 (g) 表示出 (f)。有两种思考方式：

1. 我们考虑求 (g(x)) 的过程。初始令 (g(x) gets f(x))，这显然是不对的。我们考虑一个 (i > x)，(g(i)) 在 (f(x)) 中贡献次数是 (dbinom{i}{x})，所以得到：
   [g(x) = f(x) - sum _ {i = x + 1} ^ n binom{i}{x} g(i) ]

   移项后就有：

   [begin{aligned} f(x) &= g(x) + sum _ {i = x + 1} ^ n binom{i}{x} g(i) \ &= sum _ {i = x} ^ n binom{i}{x} g(i) end{aligned} ]

2. 更直接的思考方式为，我们考虑枚举钦定 (x) 个限制必须满足后，还有 (i - x) 个限制也被满足了，即一共有 (i) 个限制被满足，其中任选 (x) 个都能被计数，乘上 (dbinom{i}{x}) 后，求和就能不重不漏：
   [f(x) = sum _ {i = x} ^ n binom{i}{x} g(i) ]

这就是左边那一条等式了。证明右边等式是对的，可将其带入。

[begin{aligned} f(x) &= sum _ {i = x} ^ n binom{i}{x} sum _ {j = i} ^ n (-1)^{j - i} binom{j}{i} f(j) \ &= sum _ {i = x} ^ n f(i) sum _ {j = x} ^ i (-1) ^ {i - j} binom{j}{x} binom{i}{j} \ &= sum _ {i = x} ^ n f(i) sum _ {j = x} ^ i (-1) ^ {i - j} binom{i}{x} binom{i - x}{j - x} \ &= sum _ {i = x} ^ n binom{i}{x} f(i) sum _ {j = x} ^ i (-1) ^ {i - j} binom{i - x}{j - x} \ &= sum _ {i = x} ^ n binom{i}{x} f(i) sum _ {j = 0} ^ {i - x} (-1) ^ {i - (j + x)} binom{i - x}{j} \ &= sum _ {i = x} ^ n binom{i}{x} f(i) sum _ {j = 0} ^ {i - x} (-1) ^ {i - x - j} binom{i - x}{j} \ &= sum _ {i = x} ^ n binom{i}{x} f(i) [i - x = 0] \ &= f(x) end{aligned} ]

即证。

模型 (2)：“至多” (Leftrightarrow) “恰好”

[large f(x) = sum _ {i = 0} ^ x binom{x}{i} g(i) Leftrightarrow g(x) = sum limits _ {i = 0} ^ x (-1)^{x - i} dbinom{x}{i} f(i) ]

当然我们可以直接采用模型 (1) 的方式推式子。记 (f(x)) 表示至多满足 (x) 个限制的方案，(g(x)) 表示恰好。

首先用 (g) 表示出 (f)，这可以枚举并钦定 (i leq x) 个限制，最后求和得出：

[f(x) = sum _ {i = 0} ^ x binom{x}{i} g(i) ]

然后把它带到 (g(x) = sum limits _ {i = 0} ^ x (-1)^{x - i} dbinom{x}{i} f(i)) 中。

[begin{aligned} g(x) &= sum _ {i = 0} ^ x (-1)^{x - i} dbinom{x}{i} sum _ {j = 0} ^ i binom{i}{j} g(j) \ &= sum _ {i = 0} ^ x g(i) sum _ {j = i} ^ x (-1) ^ {x - j} binom{x}{j} binom{j}{i} \ &= sum _ {i = 0} ^ x g(i) sum _ {j = i} ^ x (-1) ^ {x - j} binom{x}{i} binom{x - i}{j - i} \ &= sum _ {i = 0} ^ x binom{x}{i} g(i) sum _ {j = i} ^ x (-1) ^ {x - j} binom{x - i}{j - i} \ &= sum _ {i = 0} ^ x binom{x}{i} g(i) sum _ {j = 0} ^ {x - i} binom{x - i}{j} (-1) ^ {x - (j + i)} \ &= sum _ {i = 0} ^ x binom{x}{i} g(i) sum _ {j = 0} ^ {x - i} binom{x - i}{j} (-1) ^ {x - i - j} 1 ^ {j} \ &= sum _ {i = 0} ^ x binom{x}{i} g(i) [x - i = 0] \ &= g(x) end{aligned} ]

得证。

当然，如果不考虑问题的实际意义，利用模型 (0) 也可以证明。设 (h(x) = (-1) ^ x g(x))，有：

[f(x) = sum _ {i = 0} ^ x binom{x}{i} h(i) ]

那么有：

[g(x) = frac{h(x)}{(-1) ^ x} = sum _ {i = 0} ^ x (-1) ^ i binom{x}{i} f(i) ]

则：

[begin{aligned} h(x) &= sum _ {i = 0} ^ x (-1) ^ {x + i} binom{x}{i} f(i) \ &= sum _ {i = 0} ^ x (-1) ^ {x - i} binom{x}{i} f(i) \ end{aligned} ]

将 (h) 视作命题中的 (g)，即证。

更多思考

注意到「至多满足 (x) 个条件」，可以看做「至少不满足 (n - x) 个条件」；同理，「至少满足 (x) 个条件」，可以看做「至多不满足 (n - x) 个条件」，然后就可以相互推导，形成新的一对反演公式，我愿称它们为形式 (2)。

模型 (1)：“至少” (Leftrightarrow) “恰好”

[large f(x) = sum _ {i = x} ^ n binom{n - x}{n - i} g(i) Leftrightarrow g(x) = sum _ {i = x} ^ n (-1)^{i - x} binom{n - x}{n - i} f(i) ]

记 (f(x) = f'(n - x))，表示至少满足 (x) 个条件，其中 (f') 就符合模型 (2) 了。有 (f'(x) = sum limits _ {i = 0} ^ x dbinom{x}{i} g'(i))，其中 (g'(x)) 表示恰好不满足 (x) 个条件，相当于 (g(n - x))，即恰好满足 (n - x) 个条件，可以得到：

[begin{aligned} f(n - x) &= sum _ {i = 0} ^ x binom{x}{i} g(n - i) \ f(x) &= sum _ {i = 0} ^ {n - x} binom{n - x}{i} g(n - i) \ &= sum _ {i = x} ^ n binom{n - x}{n - i} g(i) \ end{aligned} ]

由于 (g'(x) = sum limits _ {i = 0} ^ x (-1)^{x - i} dbinom{x}{i} f'(i))，所以有：

[begin{aligned} g(n - x) &= sum _ {i = 0} ^ x (-1)^{x - i} binom{x}{i} f(n - i) \ g(x) &= sum _ {i = 0} ^ {n - x} (-1)^{(n - x) - i} binom{n - x}{i} f(n - i) \ &= sum _ {i = x} ^ n (-1)^{(n - x) - (n - i)} binom{n - x}{n - i} f(i) \ &= sum _ {i = x} ^ n (-1)^{i - x} binom{n - x}{n - i} f(i) \ end{aligned} ]

所以成立。

模型 (2)：“至多” (Leftrightarrow) “恰好”

[large f(x) = sum limits _ {i = 0} ^ x dbinom{n - i}{n - x} g(i) Leftrightarrow g(x) = sum _ {i = 0} ^ x (-1)^{x - i} binom{n - i}{n - x} f(i) ]

类似地，记 (f(x) = f'(n - x))，表示至多满足 (x) 个条件，其中 (f') 就符合模型 (1) 了。有 (f'(x) = sum limits _ {i = x} ^ n dbinom{i}{x} g'(i))，其中 (g'(x)) 表示恰好不满足 (x) 个条件，相当于 (g(n - x))，即恰好满足 (n - x) 个条件。可以得到：

[begin{aligned} f(n - x) &= sum limits _ {i = x} ^ n dbinom{i}{x} g(n - i) \ f(x) &= sum limits _ {i = n - x} ^ n dbinom{i}{n - x} g(n - i) \ &= sum limits _ {i = 0} ^ x dbinom{n - i}{n - x} g(i) \ end{aligned} ]

由于 (g'(x) = sum limits_ {i = x} ^ n (-1)^{i - x} dbinom{i}{x} f'(i))，所以有：

[begin{aligned} g(n - x) &= sum _ {i = x} ^ n (-1)^{i - x} binom{i}{x} f(n - i) \ g(x) &= sum _ {i = n - x} ^ n (-1)^{i - (n - x)} binom{i}{n - x} f(n - i) \ &= sum _ {i = 0} ^ x (-1)^{(n - i) - (n - x)} binom{n - i}{n - x} f(i) \ &= sum _ {i = 0} ^ x (-1)^{x - i} binom{n - i}{n - x} f(i) \ end{aligned} ]

所以成立。

例题 & 习题

等有时间再写啦。

结论

模型 (0)

[Large f(x) = sum _ {i = 0} ^ x (-1)^i binom{x}{i} g(i) Longleftrightarrow g(x) = sum _ {i = 0} ^ x (-1) ^ i binom{x}{i} f(i) ]

模型 (1)：“至少” (Leftrightarrow) “恰好”

形式 (1)

[Large f(x) = sum _ {i = x} ^ n binom{i}{x} g(i) Longleftrightarrow g(x) = sum _ {i = x} ^ n (-1)^{i - x} binom{i}{x} f(i) ]

形式 (2)

[Large f(x) = sum _ {i = x} ^ n binom{n - x}{n - i} g(i) Leftrightarrow g(x) = sum _ {i = x} ^ n (-1)^{i - x} binom{n - x}{n - i} f(i) ]

模型 (2)：“至多” (Leftrightarrow) “恰好”

形式 (1)

[Large f(x) = sum _ {i = 0} ^ x binom{x}{i} g(i) Longleftrightarrow g(x) = sum limits _ {i = 0} ^ x (-1)^{x - i} dbinom{x}{i} f(i) ]

形式 (2)

[Large f(x) = sum limits _ {i = 0} ^ x dbinom{n - i}{n - x} g(i) Longleftrightarrow g(x) = sum _ {i = 0} ^ x (-1)^{x - i} binom{n - i}{n - x} f(i) ]