反演与容斥 学习笔记
二项式反演
函数 \(f, g\)，有以下结论：
\[f_k = \sum_{i = 0}^k \binom{k}{i}g_i\Longleftrightarrow g_k = \sum_{i = 0}^k(-1)^{k - i} \binom{k}{i}f_i \]证明：
考虑右式
\[\begin{aligned} &\sum_{i = 0}^k(-1)^{k - i} \binom{k}{i}f_k\\ =&\sum_{i = 0}^k(-1)^{k - i} \binom{k}{i}\sum_{j = 0}^i \binom{i}{j}g_j\\ =&\sum_{j = 0}^k g_j\sum_{i = j}^k(-1)^{k - i} \binom{k}{i}\binom{i}{j}\\ =&\sum_{j = 0}^k g_j\sum_{i = j}^k(-1)^{k - i} \binom{k}{j}\binom{k - j}{i - j}\\ =&\sum_{j = 0}^k g_j\binom{k}{j}\sum_{i = j}^k(-1)^{k - i} \binom{k - j}{i - j}\\ =&\sum_{j = 0}^k g_j\binom{k}{j}\sum_{i = 0}^{k - j}(-1)^{k - i - j} \binom{k - j}{i}\\ &\because (1-1)^{k} = \sum_{i = 0}^k(-1)^{k - i}\binom{k}{i}\\ =&\sum_{j = 0}^k g_j\binom{k}{j}(1-1)^{k - j}\\ \end{aligned} \]当 \(k \ne j\) 时，这一项是 \(0\)，当 \(k = j\) 时，得到：
\[g_k\binom{k}{k} = g_k \]证毕。
类似的，有推论：
推论 1
\[f_k = \sum_{i = k}^n \binom{i}{k}g_i\Longleftrightarrow g_k = \sum_{i = k}^n(-1)^{i - k} \binom{i}{k}f_i \]推论 2
\[f_k = \sum_{i = 0}^k(-1)^{i} \binom{k}{i}g_i\Longleftrightarrow g_k = \sum_{i = 0}^k(-1)^{i} \binom{k}{i}f_i \]证明类似。
广义容斥原理
现在有一些物品，每个物品有若干性质，把拥有第 \(i\) 个性质的物品的集合设为 \(A_i\)，一共有 \(n\) 个性质，设全集为 \(\Omega\)。
则在这些物品种选取出若干物品，使得至少一共有 \(k\) 个不同性质的方案数为：\(\alpha_k\)。
则有：
\[\alpha_k = \sum_{T\subseteq\{1, 2, ..., n\}, |T| = k}|\bigcap_{i\in T}A_i| \]但是我们发现，对于一个拥有 \(t\) 个性质的物品，它被 \(\alpha_k\) 统计了 \(\binom{k}{t}\) 次。
设 \(\beta_k\) 为恰好有 \(k\) 个不同性质的方案数，因此有：
\[\beta_{k} = \alpha_k - \sum_{i = k + 1}^n\binom{i}{k}\beta_k\\ \alpha_k = \sum_{i = k}^n\binom{i}{k}\beta_k \]根据二项式反演推论 1，我们立即得到：
\[\beta_{k} = \sum_{i = k}^n(-1)^{i - k}\alpha_i \]这被称作广义容斥原理，容斥原理可以代入 \(k = 0\) 立即得到。
欧拉反演
\[n = \sum_{d|n}\varphi (d) \]证明：
考虑一组分数： \(\dfrac{1}{n}, \dfrac{2}{n}, \dfrac{3}{n}, ...,\dfrac{n}{n}\)，化简分数之后得到一组形如：\(\dfrac{a}{d}\) 的最简分数，其中 \((a, d) = 1\)，所以对于一个固定的 \(d\)，一共有 \(\varphi (d)\) 个 \(a\)，又因为分数化简的性质，\(d | n\)，所以分数的个数就是 \(\sum_{d | n}\varphi(d) = n\)。
证毕。
莫比乌斯反演
\[[n = 1] = \sum_{d | n} \mu(d) \]证明：
考虑算术基本定理的形式： \(n = \prod p_i^{\alpha_i}, m = \prod p_i\)，因为莫比乌斯函数在有平方因子的时候是 \(0\)，所以上式可以等价地写成：
\[\sum_{d | m}\mu(d) \]\(m\) 的每个因子相当于在 \(\{p_1, p_2, ..., p_k\}\) 中任选几个数乘起来。
所以得到：
\[\sum_{d | m}\mu(d) = \sum_{i = 0}^k\binom{k}{i}(-1)^{i} = (1-1)^k \]所以在 \(k = 0\Longleftrightarrow n = 1\) 时式子取 \(1\)，否则式子取 \(0\)。
证毕。