to be fix :
“扩展”部分的式子是假的
二维子集反演
莫比乌斯反演
容斥原理 & 莫比乌斯反演
一、函数卷积：
定义函数卷积
\(f(x, y)\) 和 \(g(x, y)\) 是 \(X \times X \rightarrow \mathbb{R}\) 的函数
\[f \ast g = \begin{cases} \sum_{x \leq z \leq y}{f(x, z)g(z, y)} & x \leq y\\ 0 & \text{otherwise}\\ \end{cases} \]定义克罗内克函数
$\delta(x, y) = [x = y] $
此函数是卷积的单位元
定义 \(\zeta\) 函数
\(\zeta = [x \leq y]\)
\(\zeta\) 函数是偏序集的一种表示，包含了偏序集的信息
我们可以证明卷积的结合律
二、逆函数
设 \(f(x, y)\) 是 \(X \times X \rightarrow \mathbb{R}\) 的函数
其中 \(f(y, y) \neq 0\)
我们构造 \(g(x, y)\) 同时也是 \(X \times X \rightarrow \mathbb{R}\) 为其逆函数。
由于卷积满足结合律，所以 只需要证明 \(g \ast f = \delta\)
证明 \(g\) 是右逆函数：
设 \(f\) 的右逆函数为 \(h\)
\(g = g \ast \delta = g \ast (f \ast h) = (g \ast f) \ast h = h\)
考虑构造 \(g(x, y)\)
我们的目标是 \(\sum_{x \leq z \leq y} {g(x, z) \ast f(z, y) } = \delta(x, y)\)
首先考虑 设 \(x = y\)
\(\mathbf{LHS} = g(x,x) \ast f(x, x)\)
\(\mathbf{RHS} = \delta(x, x) = 1\)
所以 $g(x, x) = \frac{1}{f(x, x)} $
令 $g(x, y) = -\frac{1}{f(y, y)}\sum_{x \leq z < y}{g(x, z) \ast f(z, y)} $
解释一下，这一项
\(g(x, y) \ast f(y, l) = sum_{x \leq z < y}{g(x, z) \ast f(z, y)}\)
刚好是前面所有项的相反数，所以
\(\mathbf{LHS} = 0\)
\(\mathbf{RHS} = 0\)
三、莫比乌斯函数
定义 \(\mu\) 为 \(\zeta\) 的逆函数
我们使用上面的逆函数求法，得到
\(\sum_{x \leq z \leq y}{\mu(x, z) \zeta(z, y)} = \delta(x, y)\)
得到
\(\sum_{x \leq z \leq y}{\mu(x, z)} = \delta(x, y)\)
于是
\[\mu(x, y) = \begin{cases} 1 & x = y\\ -\sum_{x \leq z < y}{\mu(x, z)} & x < y \\ \end{cases} \]四、应用
1.子集反演
我们计算 \(\subseteq\) 的莫比乌斯函数
考虑归纳假设 $\mu(A, B) = (-1)^{|B|-|A|} $
$p = |B| - |A|,k = |C| - |A| $
\[\mu(A, B) = -\sum_{A \subseteq C \subsetneq B}{\mu(A, C)} \\ = -\sum_{A \subseteq C \subsetneq B}{(-1)^{|C|-|A|}} \\ = -\sum_{k = 0}^{p - 1}{(-1)^{k}\binom{p}{k}} \\ = -(-1)^{k}\binom{p}{p} = (-1)^{p} = (-1)^{|B|-|A|} \\ \]- 一般的反演
存在极小元的偏序集中，可以看做函数的第一个参数是极小元
$ F(x) = \sum_{z \leq x}{G(z)} $
$ G(x) = \sum_{y \leq x}{F(y) \mu(y, x)} $
证明 由于该偏序集存在极小元，所以整个偏序关系构成一个树
由下式可得
\[\sum_{y \leq x} {F(y) \mu(y, x)} = \\ =\sum_{y \leq x} {\mu(y, x)} \sum_{z \leq y} {G(z)} \\ =\sum_{z \in X} \sum_{y \leq x}{\mu(y, x)\zeta(z, y)G(z)} \\ =\sum_{z \in X}{G(z)} \sum_{y \leq x}{\zeta(z, y)\mu(y, x)} \\ =\sum_{z \in X}{G(z)} \sum_{z \leq y \leq x}{\zeta(z, y)\mu(y, x)}\\ =\sum_{z \in X}{G(z)} \delta(z, x) \\ =G(z) \]我们发现莫比乌斯反演的功能不够强大，只能处理系数为 \(1\) 的情况，如果处理其它反演的时候，需要对其简单扩展
3.莫比乌斯反演
略
五、扩展
一般情况下，我们有
$ F(x) = \sum_{y \leq x}{a(y, x)G(y)} $
$ G(x) = \sum_{y \leq x}{b(y, x)F(y)} $
希望得出 \(a\) 与 \(b\) 的关系
\[\sum_{y \leq x}{b(y, x)F(y)} \\ = \sum_{y \leq x}\sum_{z \leq y} a(z, y)G(z) \\ = \sum_{z \in X} \sum_{y \leq x} \zeta(z, y) a(z, y) b(y, x) \\ = \sum_{z \in X} \sum_{z \leq y \leq x} \zeta(z, y) a(z, y) b(y, x) \]可得
\(\zeta(z, y) \ast a(z, y) \ast b(y, x) = \delta(z, x)\)
\(\zeta \ast a \ast b = \delta\)
\(a \ast b = \mu\)
六、再应用
- $\leq $ 偏序关系
由上式可得
\(\sum_{x \leq y \leq z}{a(x, y)b(y, z)} = \delta(x, z)\)
- 二项式反演