前言
万字长文!这里有我的一些思考和领会,网络上的教程都太潦草了。
并且我发现了新的反演公式!
概述
二项式反演用于转化两个具有特殊关系的函数 \(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\)。有两种思考方式:
- 我们考虑求 \(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}
\]
- 更直接的思考方式为,我们考虑枚举钦定 \(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)
\]
版权声明:本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若内容造成侵权/违法违规/事实不符,请联系邮箱:jacktools123@163.com进行投诉反馈,一经查实,立即删除!