前言

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

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

概述

二项式反演用于转化两个具有特殊关系的函数
\(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)
\]

标签: none

添加新评论