前言

本文引入了偏序集上的莫比乌斯反演，并从这个角度统一了子集反演、二项式反演、集合幂级数的莫比乌斯变换，和数论中经典的莫比乌斯反演。

目录

• 反演
  • 反演本质及其矩阵表示
• 莫比乌斯反演定理
• - $(\mathcal P(X_n),\subseteq)$ 上的 $\mu$ 函数 - 子集反演 - 容斥与二项式反演 - 莫比乌斯变换与集合并卷积
• 经典莫比乌斯反演
  • 可除性给出的莫反

反演

设集合 X 上附有一偏序关系 \leqslant_X，其构成了一个局部有限偏序集 (X,\leqslant_X)。记 \mathcal F(X) 表示只要 x\nleqslant_X y 就有 f(x,y)=0 的所有以下映射的集合：

f:X\times X\to \mathbb R

设函数 a,b\in\mathcal F。若对于任意两个函数 F,G:X\to\mathbb R 均有：

F(x)=\sum_{y}a(x,y)G(y)\Longleftrightarrow G(x)=\sum_{z}b(x,z)F(z)

则称该式右端为偏序集 (X,\leqslant_X) 上的一个反演。

我们如下定义一个至关重要的二变量卷积 *：

h(x,y)=\begin{cases}\sum\limits_{z:x\leqslant_{_X} z\leqslant_{_X} y}f(x,z)g(z,y)&\;x\leqslant_Xy\\0&\;\text{otherwise}\end{cases}

在进一步讨论二变量卷积和反演的关系前，首先给出两个重要函数。

克罗内克 \delta 函数：

\delta(x,y)=\begin{cases}1&x=y\\0&\text{otherwise}\end{cases}

\zeta 函数：

\zeta(x,y)=\begin{cases}1&x\leqslant_X y\\0&\text{otherwise}\end{cases}

\mathcal F(X) 的结构

关于二变量卷积的群

- **结合律**：$\forall f,g,h\in\mathcal F,(f*g)*h=f*(g*h)

• 单位元（恒等函数 \delta）：\forall f\in\mathcal F,\delta*f=f*\delta=f
• 逆函数：\forall f\in\mathcal F,\exists g\in\mathcal F,f*g=g*f=\delta

这里只证明第三条性质。设 f*g=\delta,h*f=\delta，那么 g=\delta*g=(h*f)*g=h*(f*g)=h*\delta=h，即 g=h，从而 f*g=g*f=\delta。

进一步，若定义运算“+”为普通的加法，则 \mathcal F 还构成一个环。

逆函数的求法

函数 g 是这么递归得到的。首先设：

g(y,y)=\frac{1}{f(y,y)}\qquad(y\in X)

然后令：

g(x,y)=-\frac{1}{f(y,y)}\sum_{z:x\leqslant_{_X} z<y}g(x,z)f(z,y) Proof.

由定义，当 x=y 时 (g*f)(x,x)=1。当 x\leqslant_X y 时：

\begin{aligned}(g*f)(x,y)&=\sum_{x\leqslant_X z<y}g(x,z)f(z,y)+g(x,y)f(y,y)\\&=\sum_{x\leqslant_X z<y}g(x,z)f(z,y)-f(y,y)\left(\frac{1}{f(y,y)}\sum_{z:x\leqslant_{_X} z<y}g(x,z)f(z,y)\right)\\&=0\end{aligned}

即当 x\neq y 时 (h*f)(x,y)=0。这就证明了 g*f=\delta。由于左逆和右逆相同，故 g 是 f 的逆。\square

反演本质及其矩阵表示

反演成立条件

上述给出的反演是成立的，如果二变量函数 a,b 满足：

\delta=a*b=b*a

也即：

\delta(x,z)=\sum_{z:x\leqslant_{_X} z\leqslant_{_X} y}a(x,z)b(z,y)=\sum_{z:x\leqslant_{_X} z\leqslant_{_X} y}b(x,z)a(z,y)

反演的矩阵表示

设矩阵 A=(a)_{ij}=a(p_i,p_j),B=(b)_{ij}=b(p_i,p_j)，那么反演成立条件以 AB=I 表示，即：

\begin{pmatrix} F(p_1)\\ F(p_2)\\ \vdots\\ F(p_i)\\ \vdots \end{pmatrix}= \begin{pmatrix} a_{{11}}&a_{12}&\cdots&a_{1j}&\cdots&\\ a_{{21}}&a_{22}&\cdots&a_{2j}&\cdots&\\ \vdots&\vdots&\ddots&\vdots&\cdots\\ a_{{i1}}&a_{i2}&\cdots&a_{ij}&\cdots&\\ \vdots&\vdots&\vdots&\vdots&\ddots\\ \end{pmatrix} \begin{pmatrix} G(p_1)\\ G(p_2)\\ \vdots\\ G(p_j)\\ \vdots \end{pmatrix} \begin{pmatrix} G(p_1)\\ G(p_2)\\ \vdots\\ G(p_i)\\ \vdots \end{pmatrix}= \begin{pmatrix} b_{{11}}&b_{12}&\cdots&b_{1j}&\cdots&\\ b_{{21}}&b_{22}&\cdots&b_{2j}&\cdots&\\ \vdots&\vdots&\ddots&\vdots&\cdots\\ b_{{i1}}&b_{i2}&\cdots&b_{ij}&\cdots&\\ \vdots&\vdots&\vdots&\vdots&\ddots\\ \end{pmatrix} \begin{pmatrix} F(p_1)\\ F(p_2)\\ \vdots\\ F(p_j)\\ \vdots \end{pmatrix}

其中：

\begin{pmatrix} b_{{11}}&b_{12}&\cdots&b_{1j}&\cdots&\\ b_{{21}}&b_{22}&\cdots&b_{2j}&\cdots&\\ \vdots&\vdots&\ddots&\vdots&\cdots\\ b_{{i1}}&b_{i2}&\cdots&b_{ij}&\cdots&\\ \vdots&\vdots&\vdots&\vdots&\ddots\\ \end{pmatrix}= \begin{pmatrix} a_{{11}}&a_{12}&\cdots&a_{1j}&\cdots&\\ a_{{21}}&a_{22}&\cdots&a_{2j}&\cdots&\\ \vdots&\vdots&\ddots&\vdots&\cdots\\ a_{{i1}}&a_{i2}&\cdots&a_{ij}&\cdots&\\ \vdots&\vdots&\vdots&\vdots&\ddots\\ \end{pmatrix}^{-1}

莫比乌斯反演定理

建立在任意有限偏序集 (X,\leqslant_X) 上的莫比乌斯函数 \mu 是一个二变量函数 \mu(x,y)。其定义为 \zeta 的逆函数，即：

\mu*\zeta=\delta

根据定义明显有 \sum_{z:x\leqslant z\leqslant y}\mu(x,z)=\delta(x,y)。

关于莫比乌斯函数，我们给出一个莫比乌斯反演定理：

\boxed{G(x)=\sum_{z:z\leqslant x}F(z)\iff F(x)=\sum_{y:y\leqslant x}G(y)\mu(y,x)} Proof. \begin{aligned}\sum_{\{y:y\leqslant x\}}&G(y)\mu(y,x)=\sum_{\{y:y\leqslant x\}}\sum_{\{z:z\leqslant y\}}F(z)\mu(y,x)\\ &=\sum_{\{y:y\leqslant x\}}\mu(y,x)\sum_{z\in X}\zeta(z,y)F(z)\\&=\sum_{z\in X}\sum_{\{y:y\leqslant x\}}\mu(y,x)\zeta(z,y)F(z)\\ &=\sum_{z\in X}\delta(z,x)F(z)=F(x).\quad\square\end{aligned}

(\mathcal P(X_n),\subseteq) 上的莫比乌斯反演

(\mathcal P(X_n),\subseteq) 上的 \mu 函数

我们需要求出在偏序关系 (\mathcal P(X_n),\subseteq) 下的莫比乌斯函数 \mu(A,B)。

定理\quad\mu(A,B)=(-1)^{|B|-|A|}

Proof.

显然 \mu(A,A)=1。 设 B\neq A,p=|B\backslash A|=|B|-|A|，使用数学归纳法：

\begin{aligned}\mu(A,B)&=-\sum_{C:A\subseteq C\subset B}\mu(A,C)\\&=-\sum_{C:A\subseteq C\subset B}(-1)^{|C|-|A|}=-\sum_{k=0}^{p-1}(-1)^k\binom{p}{k}\\&=-\left(-(-1)^p\binom{p}{p}+\sum_{k=0}^p(-1)^k\binom{p}{k}\right)\\&=(-1)^p\binom{p}{p}=(-1)^{|B|-|A|}\end{aligned}

从而 \mu(A,B)=(-1)^{|B|-|A|}。

子集反演

\boxed{G(K)=\sum\limits_{L\subseteq K}F(L)\iff F(K)=\sum_{L\subseteq K}(-1)^{|K|-|L|}G(L)}

将莫比乌斯反演定理的任意偏序关系确定为偏序关系 (P(X_n),\subseteq)，就得到了子集反演。G 也称为 F 的莫比乌斯变换，也写作 \widehat F，F 称 \widehat F 的莫比乌斯逆变换。

容斥与二项式反演

下面讨论一个子集反演的更基础的情况。

设 X_n=\{1,2,\dots,n\}，考虑 \mathcal P(X_n) 上的子集反演。

设 A_i 是有限集 S 的子集，设集合 K\subseteq\{1,2,\dots,n\}。定义 F(K) 表示 S 中只属于所有满足 i\notin K 的集合 A_i 的元素个数。

设函数：

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

则 G(K) 为对于所有只同时属于 \overline{L} 的元素的集合的大小的和。所有参与求和的集合的元素都是互不重复的，且它们的大小的和 G(K) 为：

G(K)=\Bigg|\bigcap\limits_{i\notin K}A_i\Bigg|

子集反演得：

F(K)=\sum_{L\subseteq K}(-1)^{\left|K\right|-\left|L\right|}G(L)=\sum_{L\subseteq K}(-1)^{\left|K\right|-\left|L\right|}\left|\bigcap\limits_{i\notin L}A_i\right|

容斥原理

取 K=\{1,2,\cdots,n\}=X_n，显然此时 F(X_n)=\left|\overline{A_1}\bigcap\overline{A_2}\bigcap\ \cdots\ \bigcap\overline{A_n}\right|。那么：

\left|\overline{A_1}\bigcap\overline{A_2}\bigcap\ \cdots\ \bigcap\overline{A_n}\right|=\sum_{L\subseteq X_n}(-1)^{n-\left|L\right|}\left|\bigcap\limits_{i\notin L}A_i\right|

若用 L 在 X_n 中的补 J 代替 L，则有 \left|\overline{A_1}\bigcap\overline{A_2}\bigcap\ \cdots\ \bigcap\overline{A_n}\right|=\sum_{J\subseteq X_n}(-1)^{|J|}\Big|\bigcap\limits_{i\in J}A_i\Big|，即：

\begin{aligned}\left|\overline{A_1}\bigcap\overline{A_2}\bigcap\ \cdots\ \bigcap\overline{A_m}\right|=&\Big|S\Big|\\&-\sum\Big| A_i\Big|\\&+\sum\Big| A_i\bigcap A_j\Big|\\&\ \cdots\ \\&+(-1)^m \Big|A_1\bigcap\ \cdots\ \bigcap A_m\Big|\end{aligned}

这是我们熟知的容斥原理。

二项式反演

\boxed{ g(n)=\sum_{k=0}^n\binom{n}{k}f(k)\iff f(n)=\sum_{k=0}^n(-1)^{n-k}\binom{n}{k}g(k)} 当 $F(K),G(K)$ 的值只与 $\left|K\right|$ 有关时，我们设 $g(n)=G(\left|K\right|),f(n)=F(\left|K\right|)$，其中 $n=\left|K\right|$。设集合 $L\subseteq K$ 的大小为 $k$，那么立即得到： $$ g(n)=\sum_{L\subseteq K}F(L)=\sum_{k=0}^n\binom{n}{k}f(k) $$ $$ \quad\;\;\;f(n)=F(K)=\sum_{L\subseteq K}(-1)^{\left|K\right|-\left|L\right|}G(L)=\sum_{k=0}^n(-1)^{n-k}\binom{n}{k}g(k).\quad\square $$ 然而我们在实际处理问题时 $f$ 和 $g$ 往往不是针对但个集合，而是对所有集合大小为 $n$ 的情形以某种方式求和。即便如此，这种形式的求和仍然出现在关系式中。假如我们要求 $g(n)=\sum\limits_{|T|=n}\sum\limits_{S\supseteq T}f'(|S|)$，其中 $\sum\limits_{|T|=n}f'(|T|)=f(n)$，端详： $$ \begin{aligned} g(i)&=\sum_{|T|=i}\sum_{S\supseteq T}f'(|S|)\\ &=\sum_{k=i}^n\sum_{|S|=k}f'(|S|)\sum_{|T|=i,T\subseteq S}1\\ &=\sum_{k=i}^n\binom{k}{i}\sum_{|S|=k}f'(|S|)\\ &=\sum_{k=i}\binom{k}{i}f(k) \end{aligned} $$ 综上所述，容斥定理是当 $K=X_n$ 时子集反演的展开形式，而二项式反演是当 $F,G$ 的值只与集合大小有关时的一个特殊情形的子集反演。特别需要指出的是，从上述讨论可知，二项式反演是对包含某个特定子集的集合的大小的计数，因此各类“钦定”一般都不是所谓的“至少”，而会带一个二项式系数。 ## 莫比乌斯变换与集合并卷积 设映射 $\mathcal P(X)\to F$，其中 $F$ 是一个域。域 $F$ 的一个关于该映射的集合幂级数以如下形式定义： $$ f=\sum_{S\subseteq\mathcal P(X)}f(S) x^S $$ 加法的定义是显然的。对于乘法而言，我们希望其对于加法具有左右分配律。则要求： $$ \left(f(K)x^K\right)\left(g(L)x^L\right)=f(K)g(L)x^{K*^*L} $$ 显然 $*^*$ 是一集合运算。使其具有交换律和结合律是基础的，同时，我们令空集 $\varnothing$ 为其单位元。从而我们对于一个符合要求的 $*^*$，这样的集合幂级数就构成了一个交换环。此处并不讨论这些交换环的更加深入的各类性质。 令 $*^*$ 表示集合的并，则： $$ f*g=\left(\sum_{K\subseteq\mathcal P(X)}f(K) x^K\right)\left(\sum_{L\subseteq\mathcal P(X)}g(L)x^L\right) =\sum_{S\subseteq\mathcal P(X)}\left(\sum_{K\cup L=S}f(K)g(L)\right)x^{K\cup L} $$ 我们称乘积中 $x^{K\cup L}$ 项的系数称之为集合幂级数的集合并卷积 $*_{\cup}$： $$ (f*_{\cup}g)(S)=\sum_{K\cup L=S}f(K)g(L) $$ 令 $h(S)=(f*_{\cup} g)(S)$。现在设 $\hat h,\hat f,\hat g$ 为 $h,f,g$ 的莫比乌斯变换，则： $$ \begin{aligned} \hat h(S)&=\sum_{K\subseteq S}h(K)=\sum_{K\subseteq S}\sum_{A\cup B=K}f(A)g(B)\\ &=\sum_{A\subseteq S}\sum_{B\subseteq S}f(A)g(B)=\sum_{A\subseteq S}f(A)\sum_{B\subseteq S}g(B)\\ &=\hat f(S)\hat g(S) \end{aligned} $$ 即，我们得到了：集合并卷积的莫比乌斯变换等于莫比乌斯变换的乘积。这与傅里叶变换“时域卷积，频域乘积”的性质有异曲同工之妙。 ------------ # 经典莫比乌斯反演 ## 引理 ### 线性有序集的莫比乌斯函数 设 $X_n=\{1,2,\dots,n\}$，考虑线性有序集 $(X_n,\leqslant)$，其中 $1<2<\dots<n$。我们有 $\mu(k,k)=1$，且对于 $k>l$，有 $\mu(k,l)=0$。而又由于： $$ \sum_{j:k\leqslant j\leqslant k+1}\mu(k,j)=\delta(k,k+1)=0 $$ 从而 $\mu(k,k+1)=0-\mu(k,k)=-1$。再将求和做到 $k+2$ 并以此类推，不难得到： $$ \mu(x,y)=\begin{cases}1&y=x\\-1&y=x+1\\0&other\end{cases} $$ ### 直积的莫比乌斯函数 设 $(X,\leqslant_1),(Y,\leqslant_2)$，那么**直积** $(X\times Y,\leqslant)$ 是一个偏序集，其 $\leqslant$ 定义为： $$ (x,y)\leqslant(x',y')\quad\text{iff}\quad x\leqslant_1 x',y\leqslant_2 y' $$ **定理**$\quad$ $\mu((x,y),(x',y'))=\mu_1(x,x')\mu_2(y,y')$。 ## 可除性给出的莫反 现在我们将任意的偏序关系 $\leqslant$ 替换为确定的偏序关系 $\,|\,$。即对于正整数序列 $X_n$ 构成的集合，确定为由可除性给出的偏序集 $D_n=(X_n,\,|\,)$。我们亦把 $\delta(1,n)$ 称作**单位函数** $\epsilon(n)$，将 $\zeta(1,n)$ 简称**常函数** $1(n)$。 由唯一分解定理，$n=p_1^{c_{_1}}p_2^{c_{_2}}...p_m^{c_{_m}}$。根据莫比乌斯函数的递归求解形式： $$ \mu(1,n)=-\sum\limits_{\{m:1\leqslant m<n,m|n\}}\mu(1,m) $$ 从而我们只需考虑 $(X^{*}_n,\mid)$，其中 $X^{*}_n$ 为 $X_n$ 中满足 $k\mid n$ 的正整数 $k$ 组成的子集。设 $r,s$ 为其中的整数，则： $$ r=\prod_{i=1}^mp_i^{\alpha_i}\,,\;s=\prod_{i=1}^mp_i^{\beta_i} $$ 其中 $0\leqslant \alpha_i,\beta_i\leqslant c_i$。于是 $r\mid s$ 当且仅当 $\alpha_i\leqslant \beta_i$，因此偏序集 $X^{*}_n$ 正是大小为 $c_1+1,c_2+1,\cdots,c_m+1$ 的 $k$ 个线性序的直积。从而根据直积的莫比乌斯函数，我们得到 $\mu(1,n)=\prod_{i=1}^m\mu(1,p_i^{c_i})$。 通过对线性序的莫比乌斯函数计算，我们得到： $$ \mu(1,p_i^{c_i})=\begin{cases}1&c_i=0\\-1&c_i=1\\0&c_i\geqslant 2\end{cases} $$ 从而： $$ \mu(1,n)=\begin{cases}0&\exists \ i\in [1.m],c_i>1\\1&m≡0\ (\bmod 2),\forall \ i\in[1,m],c_i=1\\-1&m≡1\ (\bmod 2),\forall \ i\in[1,m],c_i=1\end{cases} $$ 若 $\mu(1,n)$ 简写为 $\mu(n)$，我们就得到了以下经典的莫比乌斯反演公式： $$ \boxed{G(n)=\sum\limits_{k\mid n}F(k)\iff F(n)=\sum\limits_{k\mid n}\mu(k)G\left(\frac{n}{k}\right)} $$ ## $\rm Dirichlet$ 卷积与积性 反演公式中蕴含了**狄利克雷卷积** $*$： $$ f*g(n)=\sum_{d\mid n}f(d)g\left(\frac{n}{d}\right) $$ 狄利克雷卷积具有以下性质。设 $\mathcal F$ 为全体 $f:\mathbb N^*\to\mathbb R$ 且 $f$ 积性的函数构成的集合： - 对于积性函数的**封闭性**：设 $f,g$ 为积性函数，那么 $f*g$ 为积性函数。 - **交换律**：$f*g=g*f

• 结合律：(f*g)*h=f*(g*h)
• 单位元 \epsilon：\forall f\in\mathcal F,\epsilon*f=f*\epsilon =f
• 逆元素：\forall f\in\mathcal F,\exists g\in\mathcal F,f*g=g*f=\epsilon

综上所述，全体积性函数关于狄利克雷卷积运算构成一个交换群。

$$ \begin{aligned} f*g(nm)&=\sum_{d\mid nm}f(d)g\left(\frac{nm}{d}\right)\\&=\sum_{d_1\mid n,d_2\mid m}f(d_1d_2)g\left(\frac{nm}{d_1d_2}\right)\\ &=\left(\sum_{d_1\mid n}f(d)g\left(\frac{n}{d_1}\right)\right)\left(\sum_{d_2\mid m}f(d)g\left(\frac{m}{d_2}\right)\right)\\ &=(f*g)(n)(f*g)(m) \end{aligned} $$ 而狄利克雷逆元素是如下递归得到的： $$ f^{-1}(n)=\frac{1}{f(1)}\left([n=1]-\sum_{d\mid n,d<n}f^{-1}(d)f\left(\frac{n}{d}\right)\right) $$ 这个交换群大概与本文开头介绍的 $\mathcal F$ 关于 $*$ 构成的群是对应的。 ### 数论函数环 对于非积性的数论函数全体 $f:\mathbb N^*\to\mathbb R$，记为 $\mathcal F$，我们有： - $\rm Dirichlet$ 卷积的交换律和结合律 - 函数的加法交换律和结合律 - 关于卷积和加法的左分配律：$f*(g+h)(n)=f*g(n)+f*h(n)

• 关于卷积和加法的右分配律：(f+g)*h(n)=f*h(n)+g*h(n)
• 零元素和负元素

综上所述，全体数论函数的集合 \mathcal F 关于狄利克雷卷积 * 构成一个数论函数环 (\mathcal F,*)。

参考：《组合数学》，Richard A.Brualdi，冯速 等译。