莫比乌斯反演与容斥

最近在学习容斥原理，发现了莫比乌斯反演的容斥证明，感觉很不错。

偏序集

首先定义下偏序集。偏序集是一个集合和一个偏序关系定义的。通常表示为$(X_n,\;\leqslant)$，其中$X_n$是一个有限或者无限的集合，$\leqslant$是代指偏序关系，而不是特指小于等于符号。我们这里用实数集和小于等于为例：$( R,\leqslant )$

它有三个性质：自反的、反对称的和可传递的。

自反的：$\forall x \in R,x \leqslant x$
反对称的：$\forall x,y \in R,x \leqslant y\ and \ y \leqslant x\ \Rightarrow \ x=y$
可传递的：$\forall x,y,z \in R,x \leqslant y\ and \ y \leqslant z\ \Rightarrow \ x \leqslant z$

偏序关系一般是比较符$\leqslant$、集合的$\subseteq$符号和整除$\;\mid\;$。

卷积

对于定义在偏序集$(X_n,\;\leqslant)$上的二元函数$f(x,\;y)$，我们假定当$x \not\leqslant y$时，$f(x,\;y)$均为$0$，这样是为了方便我们之后的讨论。

考虑偏序集$(X_n, \leqslant)$上的二元函数$f(x,\;y)$和$g(x,\;y)$，定义它们的卷积为：

$$
(f \times g)(x,\;y) = \sum_{x \leqslant z \leqslant y} f(x,\;z)g(z,\;y) \tag{2.1}
$$

这个卷积满足结合律：

$$
(f \times g) \times h = f \times (g \times h) \tag{2.2}
$$

注意，这个卷积不一定满足交换律。

以及三种强行定义的莫名其妙的函数：

$\delta$ (delta) 函数：

$$
\delta(x,\;y) = [x = y] \tag{2.3}
$$

任意函数卷$\delta$函数均会得到原函数。

$\zeta$ (zeta) 函数：

$$
\zeta(x,\;y) = [x \leqslant y] \tag{2.4}
$$

以及莫比乌斯$\mu$函数是定义为$\zeta$函数的逆函数，即：

$$
\mu \times \zeta = \zeta \times \mu = \delta \tag{2.5}
$$

展开卷积可得：

$$
\begin{align}
\delta = \mu \times \zeta \Longrightarrow \delta(x,\;y) & = \sum_{x \leqslant z \leqslant y} \mu(x,\;z)\zeta(z,\;y) \\
& = \sum_{x \leqslant z \leqslant y} \mu(x,\;z)
\end{align}
$$

因此，当$x \neq y$时：

$$
\mu(x,\;y) = – \sum_{x \leqslant z \lt y} \mu(x,\;z) \tag{2.6}
$$

莫比乌斯反演公式

(莫比乌斯反演公式)

对于有限偏序集$(X_n,\;\leqslant)$上的两个函数$F(x,\;y)$和$G(x,\;y)$，如果：

$$ G(x,\;y) = \sum_{x \leqslant z \leqslant y} F(x,\;z) \tag{3.1}$$

那么：

$$F(x,\;y) = \sum_{x \leqslant z \leqslant y} G(x,\;z)\mu(z,\;y) = (G \times \mu)(x,\;y) \tag{3.2}$$

证明 首先将式子展开：

$$
\begin{align}
F(x,\;y) & = \sum_{x \leqslant z \leqslant y} G(x,\;z)\mu(z,\;y) \\
& = \sum_{x \leqslant z \leqslant y} \mu(z,\;y) \sum_{x \leqslant m \leqslant z} F(x,\;m)
\end{align}
$$

我们使用$\zeta$函数来表示上下界，于是式子改写为以下形式：

$$
\sum_{x \leqslant z \leqslant y} \mu(z,\;y) \sum_{m \in X_n} F(x,\;m)\zeta(x,\;m)\zeta(m,\;z)
$$

改变求和的枚举顺序，先枚举$m$，其值依然不变：

$$
\sum_{m \in X_n} \sum_{x \leqslant z \leqslant y} \zeta(m,\;z)\mu(z,\;y)\zeta(x,\;m)F(x,\;m)
$$

由于当$m \lt x$的时候$\zeta(x,\;m)$为$0$，因此只用考虑$m \geqslant x$。

同理，我们可以得出$z \geqslant m$是必须的。

因此可以改写下界：

$$
\sum_{m \in X_n} \sum_{m \leqslant z \leqslant y} \zeta(m,\;z)\mu(z,\;y)F(x,\;m)
$$

然后变成了卷积的形式：

$$
\begin{align}
\sum_{m \in X_n} F(x,\;m) \sum_{m \leqslant z \leqslant y} \zeta(m,\;z)\mu(z,\;y) & = \sum_{m \in X_n} F(x,\;m) \delta(m,\;y) \\
& = F(x,\;y)
\end{align}
$$

当$m = y$时，$\delta(m,\;y)$才为$1$，所以综上所述：

$$
F(x,\;y) = \sum_{x \leqslant z \leqslant y} G(x,\;z)\mu(z,\;y) \tag{3.2}
$$

偏序集直积

对于两个偏序集$(A,\;\leqslant_1)$和$(B,\;\leqslant_2)$，它们的直积$C = A \times B = (A \times B,\;\leqslant)$也是偏序集，其中的元素为$(x,\;y)\;\;(x \in A,\;y \in B)$。其关系$\leqslant$的定义如下：

$$
(x_1,\;y_1) \leqslant (x_2,\;y_2) \Longleftrightarrow x_1 \leqslant_1 x_2 \land y_1 \leqslant_2 y_2
$$

对于偏序集的直积，我们有以下定理：

设$A$和$B$的莫比乌斯函数分别为$\mu_1$和$\mu_2$，那么$C$的莫比乌斯函数满足：

$$\mu((x_1,\;y_1),\;(x_2,\;y_2)) = \mu_1(x_1,\;x_2)\mu(y_1,\;y_2) \tag{4.1}$$

证明

对于$(x_1,\;y_1) \not\leqslant (x_2,\;y_2)$和$(x_1,\;y_1) = (x_2,\;y_2)$的情况，上式显然成立。

假设对于满足$(x_1,\;y_1) \leqslant (u,\;v) \lt (x_2,\;y_2)$的二元组均满足，那么有：
$$
\begin{align}
\mu((x_1,\;y_1),\;(x_2,\;y_2)) & = – \sum_{(x_1,\;y_1) \leqslant (u,\;v) \lt (x_2,\;y_2)} \mu((x_1,\;y_1),\;(u,\;v)) \\
& = – \sum_{(x_1,\;y_1) \leqslant (u,\;v) \lt (x_2,\;y_2)} \mu_1(x_1,\;u)\mu_2(y_1,\;v) & (\text{根据归纳假设}) \\
& = – \sum_{x_1 \leqslant_1 u \lt_1 x_2} \sum_{y_1 \leqslant_2 v \lt_2 y_2} \mu_1(x_1,\;u)\mu_2(y_1,\;v) & (\text{分别枚举}) \\
& = – \sum_{x_1 \leqslant_1 u \leqslant_1 x_2} \sum_{y_1 \leqslant_2 v \leqslant_2 y_2} \mu_1(x_1,\;u)\mu_2(y_1,\;v) \\
&\;\;\;\, + \mu_1(x_1,\;x_2)\sum_{y_1 \leqslant_2 v \leqslant_2 y_2} \mu_2(y_1,\;v) \\
&\;\;\;\, + \mu_2(y_1,\;y_2)\sum_{x_1 \leqslant_1 u \leqslant_1 x_2} \mu_1(x_1,\;u) \\
&\;\;\;\, \color{red}{+} \mu_1(x_1,\;x_2)\mu_2(y_1,\;y_2) & (\text{扩展上界})
\end{align}
$$

红色加号的证明

由于：

$$
\begin{align}
0
& = \sum_{y_1 \leqslant_2 v \leqslant_2 y_2} \mu_2(y_1,\;v) \\
& = \sum_{x_1 \leqslant_1 u \leqslant_1 x_2} \mu_1(x_1,\;u) \\
& = \sum_{x_1 \leqslant_1 u \leqslant_1 x_2} \sum_{y_1 \leqslant_2 v \leqslant_2 y_2} \mu_1(x_1,\;u)\mu_2(y_1,\;v)
\end{align}
$$

所以定理成立。

在$(X_n,\;\leqslant)$上的莫比乌斯函数

注意这里的是真正的小于等于号了。。

这个比较简单，分析一下就好了：

对于$y = x$，我们有：

$$
\mu(x,\;y) = \mu(x,\;x) = 1
$$

对于$y = x + 1$，我们有：

$$
\mu(x,\;y) = \mu(x,\;x + 1) = -\mu(x,\;x) = -1
$$

对于$y = x + 2$，我们有：

$$
\mu(x,\;y) = \mu(x,\;x + 2) = -\left[\mu(x,\;x) + \mu(x,\;x + 1)\right] = 0
$$

不难发现，对于$y \gt x + 1$的函数值就全都变为$0$了。

总结一下就是：

$$
\mu(x,\;y) =
\begin{cases}
1 & (y = x) \\
-1 & (y = x + 1) \\
0 & (\text{otherwise})
\end{cases}
\tag{5.1}
$$

在$(X_n,\;\subseteq)$上的莫比乌斯函数

试证明：

偏序集$(X_n,\;\subseteq)$的莫比乌斯函数是：

$$\mu(A,\;B) = (-1)^{|B| – |A|} \tag{6.1}$$

运用归纳法证明：

首先对于$A = B$，显然成立：

$$
\mu(A, B) = \mu(A, A) = 1 = (-1)^0
$$

假设对于$|B| – |A| \leqslant k$均成立，尝试证明对于$|B| – |A| = k + 1$也成立：

$$
\begin{align}
\mu(A,\;B) & = -\sum_{A \subseteq C \subset B} \mu(A,\;C) \\
& = -\sum_{A \subseteq C \subset B} (-1)^{|C| – |A|} \\
& = -\sum_{i = 0}^{k} {k + 1 \choose i}(-1)^i \\
& = -\left[(1 – 1)^{k + 1} – (-1)^{k + 1} \right] \\
& = (-1)^{k + 1} \\
& = (-1)^{|B| – |A|}
\end{align}
$$

在$(X_n,\;\mid)$上的莫比乌斯函数

对于$(X_n, \;\mid)$这个偏序集，有如下定理：

$$
a \mid b \Longrightarrow \mu(a,\;b) = \mu(1,\;\frac{b}a) \tag{7.1}
$$

证明

我们尝试使用归纳法证明。首先对于$a = b$的情况显然成立：

$$
\mu(a,\;b) = \mu(a,\;a) = \mu(1,\;1) = 1
$$

假设对于$a \leqslant c \lt b$的莫比乌斯函数$\mu(a,\;c)$均满足上述定理，下面证明对于$\mu(a,\;b)$也满足。

根据莫比乌斯函数的性质可得：

$$
\mu(a,\;b) = -\sum_{a \mid c \mid b, \;c \neq b} \mu(a,\;c)
$$

由于$a \mid b$，所以：

$$
-\sum_{c \mid (b / a), \;c \neq (b / a)} \mu(a,\;ac)
$$

根据归纳假设，可以将上式变为：

$$
-\sum_{c \mid (b / a), \;c \neq (b / a)} \mu(1,\;c) = \mu(1,\;\frac{b}a)
$$

因此定理成立。

由于有上面的定理，所以我们只用关心$\mu(1,\;n)$。

首先可以递归计算：

$$
\mu(1,\;n) = -\sum_{a \mid n,\;a\neq n} \mu(1,\;a)
$$

考虑对$n$进行质因数分解：

$$
n = p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_m^{\alpha_m}
$$

对于$n$的任意一个因子$d$都有：

$$
d = p_1^{\beta_1}p_2^{\beta_2}\cdots p_m^{\beta_m} \;\;\;\; (0 \leqslant \beta_i \leqslant \alpha_i)
$$

相当于可以看作$m$个大小为$\alpha_1 + 1,\;\alpha_2 + 1,\;\dots,\;\alpha_m + 1$的偏序集的直积的结果。

于是可以得到：

$$
\mu(1,\;n) = \prod_{i=1}^m\mu(1,\;p_i^{\alpha_i}) \tag{7.2}
$$

注意到，对于$\varphi(p) = p – 1$：

$$
\mu(1,\;1) = 1 \\
\mu(1,\;p) = -\mu(1,\;1) = -1 \;\; \\
\mu(1,\;p^2) = -\left[ \mu(1,\;1) + \mu(1,\;p) \right] = 0 \\
\dots
$$

总结一下就是：

$$
\mu(1,\;p^k) =
\begin{cases}
1 & (k = 0) \\
-1 & (k = 1) \\
0 & (\text{otherwise})
\end{cases}
\tag{7.3}
$$

运用直积，可以知道：

$$
\mu(1,\;n) =
\begin{cases}
1 & (n = 1) \\
(-1)^k & (n = p_1p_2\cdots p_k, \;\;\varphi(p_i) = p_i – 1) \\
0 & (\text{otherwise})
\end{cases}
\tag{7.4}
$$

为了方便，通常把$\mu(1,\;n)$记作$\mu(n)$，就变成常见的莫比乌斯函数了。

据此，我们可以证明莫比乌斯函数是积性函数，即：

$$
a \bot b \Longrightarrow \mu(ab) = \mu(a)\mu(b) \tag{7.5}
$$

证明：

1.如果$a$、$b$中有一者为$1$，结论显然成立。
2.如果$a$、$b$中有一者不为素数连乘的形式，它们的积也一定不会是素数连乘的形式，故等于$0$。
3.此时假设$a$、$b$都是素数连乘的形式，又因为$a$与$b$互质，所以它们的素因子中没有相同的。设$a = p_1p_2\cdots p_m$和$b = q_1q_2\cdots q_n$所以可以知道$\mu(ab) = (-1)^{n + m} = \mu(a)\mu(b)$。

反演示例：容斥原理

设$S$为有限集，$A_1,\;A_2,\;\dots,\;A_n$是$S$的子集，$K \subseteq {1,\;2,\;\dots,\;n}$。

定义函数$F(K)$计数$s$同时满足下列条件：

$$
s \not\in \bigcup_{i \in K} A_i \\
s \in \bigcap_{i \not\in K} A_i
$$

即：

$$
F(K) = \left| \bigcap_{i \not\in K} A_i – \bigcup_{i \in K} A_i \right| \tag{8.1}
$$

如何脑补这个函数？可以想象成是用$K$把$S$中的很多东西挖走了，然后剩下的集合再求交集。

对于此，再定义函数$G(K)$：

$$
G(K) = \sum_{L \subseteq K} F(L) \tag{8.2}
$$

这样计数的是：

$$
G(K) = \left| \bigcap_{i \not\in K} A_i \right| \tag{8.3}
$$

根据莫比乌斯反演公式可以知道：

$$
G(K) = \sum_{L \subseteq K} F(K) \Longrightarrow F(K) = \sum_{L \subseteq K} (-1)^{|K| – |L|} G(L)
$$

所以取$K = {1,\;2,\;\dots,\;n}$可以得到：

$$
F(K) = \sum_{L \subseteq K} (-1)^{n – |L|} G(L) \tag{8.4}
$$

这个时候的$F(K)$计数的东西有了新的含义：

$$
F(K) = \left|\bigcup_{i \in K} A_i\right| = \left|\bigcap_{i \in K} \overline{A}_i \right| \tag{8.5}
$$

用$F(K)$和$G(K)$本身的含义来替换，就可以得到容斥原理 ：

$$
\left|\bigcap_{i = 1}^n \overline{A}_i \right| = \sum_{K \subseteq {1,\;,2,\;,\dots,\;n}} (-1)^{|K|} \left| \bigcap_{i \in K} A_i \right| \tag{8.6}
$$

反演示例：$\varphi(n)$的通项公式

欧拉$\varphi(n)$函数计数的是不大于$n$的与$n$互质的正整数个数。

对于欧拉$\varphi$函数，我们有如下的定理：

$$
n = \sum_{d \mid n} \varphi(d) \tag{9.1}
$$

有两种证明方法：

第一种考虑不与$n$互质的数，如果存在一个数$d$与$n$不互质，那么必有$\gcd(d, n) = a \gt 1$，换言之$\gcd(d / a, n / a) = 1$，所以一个数不与$n$互质，那么必定与$n$的一个因子互质。所以上式成立。

另一种是使用归纳法证明：

首先考虑$1$，是显然成立的。

然后考虑质数$p$，$\varphi(1) + \varphi(p) = p$，所以也是成立的。

考虑质数$p$的幂$p^k$，它的因子有$1,\;p,\;p^2,\;\dots,\;p^k$，由于：

$$
\varphi(p^k) = (p – 1)p^{k-1} \;\;\;\; (\varphi(p) = p – 1)
$$

所以我们对其进行等比数列求和：

$$
\begin{align}
\sum_{d \mid n} \varphi(d) & = 1 + (p – 1)\sum_{i=0}^{k-1} p^i \\
& = 1 + (p – 1) \cdot {1 – p^k \over 1 – p} \\
& = 1 + p^k – 1 \\
& = p^k
\end{align}
$$

故对质数的幂也成立。

假设对于一个数$c$，所有小于$c$的数均成立，那么选取$n$的两个互质的因子$a$、$b$使得$ab = c$，那么有：

$$
\sum_{n \mid a} \varphi(n) \sum_{m \mid b} \varphi(m) = a \cdot b = c
$$

下面证明$\sum_{n \mid a} \varphi(n) \sum_{m \mid b} \varphi(m) = \sum_{d \mid c} \varphi(d)$，即可证明原式：

$$
\begin{align}
\sum_{n \mid a} \varphi(n) \sum_{m \mid b} \varphi(m) & = \sum_{n \mid a}\sum_{m \mid b}\varphi(n)\varphi(m) & (\text{改变枚举顺序}) \\
& = \sum_{n \mid a}\sum_{m \mid b} \varphi(nm) & (\text{由于}n \bot m) \\
& = \sum_{nm \mid ab} \varphi(nm) & (\text{由于}a \bot b) \\
& = \sum_{d \mid c} \varphi(d) & (\text{等价代换}) \\
& = c
\end{align}
$$

注意到$(9.1)$式是一个明显的莫比乌斯反演的形式。根据莫比乌斯反演公式，我们可以得到：

$$
\begin{align}
\varphi(n) & = \sum_{d \mid n} d \cdot \mu(d,\;n) \\
& = \sum_{d \mid n} d \cdot \mu(1,\;n / d) \\
& = \sum_{d \mid n} d \cdot \mu(n / d) \\
& = \sum_{d \mid n} \mu(d) \cdot n/d
\end{align}
$$

考虑一下$\mu$函数的取值，对于因子$1$，和式中的结果为$n$。对于由素数相乘的因子，这些素因子必定来自$n$。而其它情况就都为$0$。

设$n = p_1^{k_1}p_2^{k_2}\cdots p_m^{k_m}$。

因此可以得到下面的式子：

$$
\varphi(n) = n\left[1 – \sum \frac1{p_i} + \sum \frac1{p_ip_j} – \cdots + (-1)^{m}\sum \frac1{\prod_{i=1}^m p_i} \right] \tag{9.2}
$$

这恰好是下面的式子展开的形式：

$$
\varphi(n) = n\prod_{i=1}^m \left( 1 – \frac1{p_i} \right) \tag{9.3}
$$

因此：

$$
\varphi(n) = n\prod_{p \mid n,\;\varphi(p) = p – 1} \left( 1 – \frac1p\right) \tag{9.4}
$$