对称的反演

二项式反演的主要内容就是：

\[ f_n = \sum_{i = 0}^n (-1)^i {n \choose i} g_i \longleftrightarrow g_n = \sum_{i = 0}^n (-1)^i {n \choose i} f_i \]

这个反演的式子非常的优美：在这种形式下，它们是对称的。当然，亦可以写作：

\[ f_n = \sum_{i = 0}^n {n \choose i} g_i \longleftrightarrow g_n = \sum_{i = 0}^n (-1)^{n – i} {n \choose i} f_i \]

证明

考虑用喜闻乐见的暴力带入证明：

\[ \begin{aligned} f_n &= \sum_{i = 0}^n (-1)^i {n \choose i} \sum_{j = 0}^i (-1)^j {i \choose j} f_j \\ &= \sum_{i = 0}^n \sum_{j = 0}^n (-1)^{i + j} {n \choose i} {i \choose j} f_j [j \leq i] \end{aligned} \\
\text{其中} \\
\begin{aligned} {n \choose i} {i \choose j} &= \frac{n!i!}{i!(n – i)!(i – j)!j!} \\ &= \frac{n!}{j!(n – j)!} \frac{(n – j)!}{(n – i)!((n – j) – (n – i))!} \\ &= {n \choose j} {n – j \choose n – i} \end{aligned} \\
\text{带回原式} \\
\begin{aligned} f_n &= \sum_{i = 0}^n \sum_{j = 0}^n (-1)^{i + j} {n \choose i} {i \choose j} f_j [j \leq i] \\ &= \sum_{i = 0}^n \sum_{j = 0}^n (-1)^{i + j} {n – j \choose n – i} f_j [j \leq i] \\ &= \sum_{j = 0}^n {n \choose j} f_j \sum_{i = j}^n (-1)^{i + j} {n – j \choose n – i} \end{aligned} \\
\text{现在要证明} \sum_{i = j}^n (-1)^{i + j} {n – j \choose n – i} = [j = n] \\
\begin{aligned} \sum_{i = j}^n (-1)^{i + j} {n – j \choose n – i} &= (-1)^j \sum_{i = j}^n (-1)^i {n – j \choose n – i} \\ &= (-1)^j \sum_{i = 0}^{n – j} (-1)^{i + j} {n – j \choose n – (i + j)} \\ &= (-1)^j \sum_{i = 0}^{n – j} (-1)^{n – i} {n – j \choose i} \\ &= (-1)^{n + j} (1 – 1)^{n – j} = [j = n] \end{aligned} \\ \text{带回原式发现结果就是} f_n \]

二项式反演的应用

至少转恰好

有很多运用二项式反演的题都大概是用「至少」来转为「恰好」进行求解。如果是正常的至少转恰好，一般都可以列出并直接反演：

\[ g(x) = \sum_{i = 0}^n {n \choose i} f(i) \]

有些时候要转换成「至少\(k\)」。转换为这个的时候需要对二项式反演做一些调整。在这种情况下我们列出：

\[ g(k) = \sum_{i = k}^n {i \choose k} f(i) \]

这个需要特殊形式的反演：

\[ f(k) = \sum_{i = k}^n (-1)^{i – k} {i \choose k} g(i) \]

这就是例题 BZOJ 3622 的解法。用至少\(k\)来转换为恰好\(k\)。本质上就是容斥咯。