翻了两年前 cmd 的博客看（

发现大部分都可以通过容斥原理解释。

定义

反演：一个函数通过某种求和关系变成另一个函数，另一个也能用另一种求和关系变回来，称这一对关系为反演关系。

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

关系矩阵：将函数认为是数列，则满足 \(F = G \times A\) 的矩阵 \(A\) 是关系矩阵。即其描述了反演的求和关系。

此时 \(G\) 到 \(F\) 的变换显然是 \(A^{-1}\) 。

几个常见反演

二项式反演

第一个式子长这样：

\[f(n) = \sum _{i=1} ^n (-1)^i { n \choose i} g(i) \Leftrightarrow g(n)= (-1)^i \sum _{i=1} ^n {n \choose i} f(i) \]

实际上是经典的容斥形式？（系数 \((-1)^i\) ）

严谨的证明如下：

要证明反演关系成立，只要证明关系矩阵互逆即可。

这里两个关系矩阵相同，记为 \(\{A_{ij}\}\) ，易知 \(A_{ij}= \left[ i \le j \right] \left(-1\right)^{i} {j \choose i}\) 。

\[\begin{align*} \left(A \times A\right)_{ij} &= \sum_{k=0}^{+\infin} A_{ik} A_{kj}\\ &=\sum_{k=i}^{j} \left( -1 \right)^{i} {k \choose i} \left( -1 \right)^{k} {j \choose k}\\ &=\left( -1 \right)^{i} {j \choose i} \sum_{k=i}^{j} \left( -1 \right)^k {j-i \choose k-i}\\ &=\left( -1 \right)^{i} {j \choose i} \sum_{k=0}^{j-i} \left( -1 \right)^{k+i} {j-i \choose k}\\ &=(1-1)^{j-i} {j \choose i} = \left[ i==j \right] \end{align*} \]

所以

\[AA=I \]

证毕。

min-max 反演（容斥）

呵呵这个甚至直接叫做容斥了。

\[\max\{ S \} =\sum_{S \subseteq T} (-1)^{ \vert T \vert + 1} \min\{ T \} \]

很好理解，除了最大值之外每个值都会被统计偶数次，这偶数次恰好 \(\vert T \vert\) 奇数情况和偶数情况一样多。而最大值只会被统计一次，即只有自身的时候。

同时适用于期望，即

\[E(\max\{ S \}) = \sum_{S \subseteq T} (-1)^{\vert T \vert +1} E(\min \{ T \}) \]

根据原本式子的证明过程容易看出这是正确的。

莫比乌斯反演

基于狄利克雷卷积，内容较多，稍后再补