科数网知识库
首页
目录
二项式反演
日期:
2023-01-06 09:03
查看:
104
次
记 $f_n$ 表示恰好使用 $n$ 个不同元素形成特定结构的方案数,$g_n$ 表示从 $n$ 个不同元素中选出 $i \geq 0$ 个元素形成特定结构的总方案数。 若已知 $f_n$ 求 $g_n$,那么显然有: $$ g_n = \sum_{i = 0}^{n} \binom{n}{i} f_i $$ 若已知 $g_n$ 求 $f_n$,那么: $$ f_n = \sum_{i = 0}^{n} \binom{n}{i} (-1)^{n-i} g_i $$ 上述已知 $g_n$ 求 $f_n$ 的过程,就称为 **二项式反演**。 证明 将反演公式的 $g_i$ 展开得到: $$ \begin{aligned} f_n &= \sum_{i = 0}^{n} \binom{n}{i} (-1)^{n-i} \left[\sum_{j = 0}^{i} \binom{i}{j} f_j\right] \\ &= \sum_{i = 0}^{n}\sum_{j = 0}^{i}\binom{n}{i}\binom{i}{j} (-1)^{n-i}f_j \end{aligned} $$ 先枚举 $j$,再枚举 $i$,得到: $$ \begin{aligned} f_n &= \sum_{j = 0}^{n}\sum_{i = j}^{n}\binom{n}{i}\binom{i}{j} (-1)^{n-i}f_j \\ &= \sum_{j = 0}^{n}f_j\sum_{i = j}^{n}\binom{n}{i}\binom{i}{j} (-1)^{n-i} \end{aligned} $$ 使用 [「组合数性质 | 二项式推论」](https://oi-wiki.org/math/combinatorics/combination/#%E7%BB%84%E5%90%88%E6%95%B0%E6%80%A7%E8%B4%A8--%E4%BA%8C%E9%A1%B9%E5%BC%8F%E6%8E%A8%E8%AE%BA) 的公式 (11) 得到: $$ \begin{aligned} f_n &= \sum_{j = 0}^{n}f_j\sum_{i = j}^{n}\binom{n}{j}\binom{n - j}{i - j} (-1)^{n-i} \\ &= \sum_{j = 0}^{n}\binom{n}{j}f_j\sum_{i = j}^{n}\binom{n - j}{i - j} (-1)^{n-i} \end{aligned} $$ 令 $k = i - j$。则 $i = k + j$,上式转换为: $$ f_n = \sum_{j = 0}^{n}\binom{n}{j}f_j\sum_{k = 0}^{n - j}\binom{n - j}{k} (-1)^{n-j-k}1^{k} $$ 使用 [「组合数性质 | 二项式推论」](https://oi-wiki.org/math/combinatorics/combination/#%E7%BB%84%E5%90%88%E6%95%B0%E6%80%A7%E8%B4%A8--%E4%BA%8C%E9%A1%B9%E5%BC%8F%E6%8E%A8%E8%AE%BA) 的公式 (5) 得到: $$ f_n = \sum_{j = 0}^{n}\binom{n}{j}f_j[n = j] = f_n $$ 证毕。
本系统使用
启明星知识库Kbase
搭建,最后更新于
2023-01-06 09:03
,如果您有意见或建议请点击
反馈
。