二项式反演 证明

· · 算法·理论

只写了最常见的形式，想必应该都差不多吧。

现证明：

f(k) = \sum_{i = k}^{n}\binom{i}{k}g(i) \Leftrightarrow g(k) = \sum_{i = k}^{n}(-1)^{i - k}\binom{i}{k}f(i)

以吾之拙见，容斥的本质是通过调整系数使答案正确。

考虑对于 g(i) 的系数等于：

\begin{aligned} &\ \ \ \ \ \sum_{j=k}^{i}(-1)^{j - k}\binom{j}{k}\binom{i}{j}\\ &=\sum_{j=k}^{i}(-1)^{j - k}\binom{i}{k}\binom{i - k}{j - k}\\ &=\binom{i}{k}\sum_{j = k}^{i}(-1)^{j - k}\binom{i - k}{j - k}\\ &=\binom{i}{k}(1-1)^{i - k}\\ \end{aligned}

显然当 i = k 时其系数为 1，其他均为 0，符合预期。