不一样的反演魔术

好吧,其实是高中没学好,大学回来补。大篇幅参考了 Introductory Combinatorics Fifth Edition 容斥原理一章莫比乌斯反演一节,修正了书上错误的内容,加上了一些证明的内容。虽然我想说的和网上已有的资料大同小异——容斥原理、二项式反演和数论反演——不过本文打算从最一般、定义在偏序集上的 Möbius 反演开始。

本文可能过于理论化,所以入门还是推荐使用其它资料。刷题记录扔在另一篇文章反演水题 Collection 中,可能这篇更适合算法竞赛中的反演入门。

前置知识

偏序关系

偏序是一种二元关系,较为常见的偏序关系有实数域 \mathbb R 上的 \le 关系、集合之间的子集 \subseteq 还有整数之间的整除 | 关系等。

更抽象地,偏序被定义为一个集合和一个关系的二元组,如实数上的 \le 关系即为形如 (\mathbb R,\le) 的二元组。

对于偏序关系 (S,\le) ,满足性质:

  • 自反性: \forall a\in S: a\le a
  • 传递性: \forall a,b,c\in S:a\le b\land b\le c\implies a\le c
  • 反对称性: \forall a,b\in S: a\le b\land b\le a\implies a=b

方便起见,定义关系 a=b:(a\le b)\land(b\le a)a<b:(a\le b)\land(a\neq b)a>b:b<a

卷积

下文中只考虑实值函数(实际上只要值域和值域上的加法运算组成的二元组满足交换群即可)集合 \mathcal F(D,\le) ,满足 \forall f\in \mathcal F(D,\le):(f:D\times D\to\mathbb R) ,且该集合满足其中的所有函数 \forall f\in\mathcal F(D,\le) 对于所有定义域中的元素 \forall x,y\in D: x>y\implies f(x,y)=0\land x=y\implies f(x,y)\neq 0

设函数 f,g\in\mathcal F(D,\le) ,定义卷积 *(f*g)(x,y)=\left\{\begin{array}{c}\sum\limits_{x\le z\le y}f(x,z)g(z,y) &\text{for }x\le y\\0&\text{otherwise}\end{array}\right.

显然有结合律 (f*g)*h=f*(g*h) ,但无交换律。

事实上,若 D 可数且 \mathcal F(D,\le) 满足全序关系的话,定义域中的元素按行纵依序排列,以对应的函数值填充矩阵,这实际上就是一个上三角矩阵,函数卷积即为矩阵乘法(从另一方向说明了没有交换律)。

Iverson 括号

定义 Iverson 括号

[cond]=\begin{cases}1&\text{if }cond\text{ is true}\\0&\text{otherwise}\end{cases}

Kronecker delta 函数

定义 Kronecker delta 函数 \delta(x,y)=[x=y]

和积分中的克罗内克函数类似,此处定义的克罗内克函数满足对于任意 f\in\mathcal F(D,\le):\delta*f=f*\delta=f

实际上, delta 函数即为群 (\mathcal F(D,\le),*) 中的单位元。在可数全序集上这是一个单位矩阵。

Riemann zeta 函数

定义 Riemann zeta 函数 \zeta(x,y)=[x\le y]

这里的 zeta 函数其实就是偏序集的一种表示。在可数全序集上这是一个全 1 的上三角矩阵。

Möbius mu 函数

定义

对于所有 f\in\mathcal F(D,\le) ,定义 f^{-1}f^{-1}(x,y)=\begin{cases}-\displaystyle{\frac1{f(y,y)}\sum_{x\le z<y}f^{-1}(x,z)f(z,y)}&\text{for }x<y\\\displaystyle\frac1{f(y,y)}&\text{for }x=y\\0&\text{for }x>y\end{cases}

需要注意,虽然 f^{-1}(x,y)\text{ for }x<y 的定义依赖到了f^{-1}(x,z)\text{ for }x\le z<y ,但是不存在反向的依赖,因此可递归定义。

显然(把分母乘回去) f^{-1}*f=\delta ,可证明 f*f^{-1}=\deltaf^{-1} 的唯一性。因此 \mathcal F(D,\le) 的元素均有唯一逆元。于是我们在此定义 Möbius 函数 \mu=\zeta^{-1}

唯一性证明:

f*g=\delta, h*f=\delta ,有 g=g*\delta=g*f*h=\delta*h=h

性质

根据卷积定义, \sum\limits_{x\le z\le y}\mu(x,z)\zeta(z,y)=\delta(x,y) ,根据 \zeta 定义我们有 \sum\limits_{x\le z\le y}\mu(x,z)=\delta(x,y) ,这等价于 \mu(x,y)=\begin{cases}-\sum\limits_{x\le z<y}\mu(x,z)&\text{for }x<y\\1&\text{for }x=y\\0&\text{for }x>y\end{cases}

(\mathbb N,\le)

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

结论是很显然的,递推一下就得到了。

事实上这个结论对于所有可数的全序集而言均符合。

(\mathcal P(S),\subseteq)

\mu(X,Y)=(-1)^{|Y|-|X|}

归纳证明:

\begin{aligned}\mu(X,Y)&=-\sum_{X\subseteq Z\subset Y}\mu(X,Z)\\&=-\sum_{X\subseteq Z\subset Y}(-1)^{|Z|-|X|}\\&=-\sum_{k=|X|-|X|}^{|Y|-|X|-1}\binom {|Y|-|X|}k(-1)^k\\&=(-1)^{|Y|-|X|}-\sum_{k=0}^{|Y|-|X|}\binom{|Y|-|X|}k(-1)^k\\&=(-1)^{|Y|-|X|}-(1-1)^{|Y|-|X|}&\triangleright\text{Binomial theorem}\\&=(-1)^{|Y|-|X|}\end{aligned}

偏序集直积

设两个偏序集 (X,\le_X)(Y,\le_Y) ,直积 (X,\le_X)\times(Y,\le_Y)=(X\times Y,\le) ,这里要求 \le 满足 \forall (x,y),(x',y')\in X\times Y:(x,y)\le(x',y')\iff(x\le_X x')\land(y\le_Yy')

(X,\le_X) 的 Möbius 函数为 \mu_X(Y,\le_Y) 的 Möbius 函数为 \mu_Y ,其直积的 Möbius 函数为 \mu ,则有:

\forall x,x'\in X,y,y'\in Y:\mu((x,y),(x',y'))=\mu_X(x,x')\mu_Y(y,y')

还是归纳法证明:

\begin{aligned}\mu((x,y),(x',y'))&=&-&\sum_{(x,y)\le(x'',y'')<(x',y')}\mu((x,y),(x'',y''))\\&=&-&\sum_{(x,y)\le(x'',y'')<(x',y')}\mu_X(x,x'')\mu_Y(y,y'')\\&=&-&\sum_{x\le_Xx''\le_Xx'}\mu_X(x,x'')\sum_{y\le_Yy''\le_Yy'}\mu_Y(y,y'')&&\triangleright\sum_{i\le k\le j}\mu(i,k)=\delta(i,j)\\&&+&\mu_X(x,x')\mu_Y(y,y')\\&=&&\mu_X(x,x')\mu_Y(y,y')\end{aligned}

这个结论在接下来的求解自然数关于整除关系形成的偏序集上的 Möbius 函数用到。

(\mathbb N,|)

对于任意定义域中的 x,y ,当 x|y ,有 \mu(x,y)=\mu\left(1,\displaystyle{\frac yx}\right) 。这个结论是很显然的,证明的话归纳即可,两侧参数相等时结论显然,不等时:

\begin{aligned}\mu(x,y)&=-\sum_{z|\frac yx}\mu(x,xz)&&\triangleright\text{here }z\left|\frac yx\right.\text{ but }z\neq\frac yx\\&=-\sum_{z|\frac yx}\mu(1,z)\\&=\mu\left(1,\frac yx\right)\end{aligned}

\mathbb P_mm 的素因数集合,则有:

\mu(1,m)=\begin{cases}1&\text{for }m=1\\(-1)^{|\mathbb P_m|}&\text{for }m=\prod\limits_{p\in \mathbb P_m}p\\0&\text{otherwise}\end{cases}

证明:

n 的唯一素因数分解为 n=\prod\limits_{k}p_k^{\alpha_k}p_kn 的素因子, \alpha_kp_k 对应的幂次。

对于任何可以整除 n 的数字 s=\prod\limits_{k}p_k^{\beta_k}, t=\prod\limits_{k}p_k^{\gamma_k} 来说,若 s|t ,有 \forall k:\beta_k\le\gamma_k 。所以 n 的因子组成的偏序集可以认为是 k\alpha_k+1 大小的偏序集的直积。

由于每个偏序集都是只由 p_k 的幂次组成,实际上这些都是全序集。前面已经证明了对于所有的全序集的 \mu 函数情况,此处同理:

\mu(1,p_k^r)=\begin{cases}1&\text{for }r=0\\-1&\text{for }r=1\\0&\text{otherwise}\end{cases}

于是利用 Möbius 直积公式可证明结论。

当我们限制 Möbius 函数的第一项参数为 1 并略去时,得到的形式即为数论中的 Möbius 函数,数论 Möbius 函数满足积性 m\bot n\implies\mu(mn)=\mu(m)\mu(n) 。前几项的值如下图所示:

Möbius mu function plot

Möbius 反演

设对于 G,F\in\mathcal F(D,\le) 两个函数满足: G(x,y)=\sum_{x\le z\le y}F(x,z)

则有 F(x,y)=\sum_{x\le z\le x}G(x,z)\mu(z,y)

证明:

\begin{aligned}\sum_{x\le z\le y}G(x,z)\mu(z,y)&=\sum_{x\le z\le y}\mu(z,y)\sum_{x\le w\le z}F(x,w)\\&=\sum_{x\le z\le y}\mu(z,y)\sum_{w\in D}F(x,w)\zeta(w,z)\\&=\sum_{w\in D}F(x,w)\sum_{w\le z\le y}\zeta(w,z)\mu(z,y)\\&=\sum_{w\in D}F(x,w)\delta(w,y)\\&=F(x,y)\end{aligned}

上面是一般的 Möbius 反演公式。在偏序集具有最小元(下面假设为 0 )且函数下界取到最小元的时候,二元函数可以默认第一个参数为 0 简写为一元函数,也就是 Introduction Combinatorics Fifth Edition 上的形式:

F,G\in\mathcal F(D,\le) 满足 G(0,x)=\sum\limits_{y\le x}F(0,y) 时,有 F(0,x)=\sum\limits_{y\le x}G(0,y)\mu(y,x)

在数论中,存在最小元为 1 , Möbius 反演可以化为另一种形式:

G(n)=\sum_{k|n}F(k)\iff F(n)=\sum_{k|n}\mu(n/k)G(k)

容斥原理

设有集合 A_1,A_2,A_3,A_4,\cdots,A_n ,求 \left|\bigcup_{i=1}^nA_i\right|

利用容斥原理,我们知道这个的结果为 \left|\bigcup_{k=1}^nA_k\right|=\sum _{\mathcal T\subseteq\{A_1,A_2,\ldots,A_n\}\land\mathcal T\neq\varnothing}(-1)^{|\mathcal T|-1}\left|\bigcap _{A\in\mathcal T}A\right|

证明:

设集合族 \mathcal A=\{A_1,A_2,A_3,A_4,\cdots,A_n\} ,则设全集 U=\bigcup\limits_{A\in\mathcal A}A ,定义函数 F(\mathcal S)=\left|\left(\bigcap_{A\in\mathcal S}A\right)\cap\left(\bigcap_{A\in\mathcal A\setminus\mathcal S}U\setminus A\right)\right|

换句话说,函数 F(\mathcal S) 的结果是所有 \mathcal S 中集合的交减去不在 \mathcal S 中的集合的并。因此 F 等价于 F(\mathcal S)=\left|\left(\bigcap_{A\in\mathcal S}A\right)\setminus\left(\bigcup_{A\in\mathcal A\setminus S}A\right)\right|

G(\mathcal T)=\left|\bigcap_{A\in\mathcal T}A\right|

有个显然的结论是: G(\mathcal T)=\sum_{\mathcal S\supseteq\mathcal T}F(\mathcal S)

这里是一个关于 \supseteq 的偏序集。我们已经得到 \subseteq 偏序关系的 Möbius 函数,通过引入一个不加证明(很容易证明)的结论: \mu_\le(a,b)=\mu_\ge(b,a) ,可以直接得到 \supseteq 的 Möbius 函数。

运用 Möbius 反演可以得到: F(\mathcal S)=\sum_{\mathcal A\supseteq\mathcal T\supseteq\mathcal S}\mu(\mathcal T,\mathcal S)G(\mathcal T)=\sum_{\mathcal A\supseteq\mathcal T\supseteq\mathcal S}(-1)^{|\mathcal T|-|\mathcal S|}G(\mathcal T)

接下来取 \mathcal S=\varnothing ,有 F(\varnothing)=\left|U\setminus\left(\bigcup_{A\in\mathcal A}A\right)\right|

回代得到结论: \left|U\setminus\left(\bigcup_{A\in\mathcal A}A\right)\right|=\sum_{\mathcal A\supseteq\mathcal T}(-1)^{|\mathcal T|}\left|\bigcap_{A\in\mathcal T}A\right|

当把全集 U 的影响去掉之后,就得到本段开始所写的容斥原理公式。

二项式反演

二项式反演的公式是 g(n)=\sum_{m=0}^n(-1)^m\binom nmf(m)\iff f(n)=\sum_{m=0}^n(-1)^m\binom nmg(m)

上面从 Möbius 反演出发证明了容斥原理,本节则从容斥原理构造特殊的集族证明二项式反演。

构造 n 个集合,使得 \forall k\in\{1,2,3,4,\cdots,n\} 满足任选 k 个集合的交均为固定值,设为 g(k) 。这样的集族不难构造, \forall\mathcal S:|\mathcal S|=1\implies F(\mathcal S)=1 就是一个例子。

\begin{aligned}g(k)&=|A_1\cap A_2\cap A_3\cap A_4\cap\cdots\cap A_k|\\&=\left|\overline{\overline{A_1}\cup\overline{A_2}\cup\overline{A_3}\cup\overline{A_4}\cup\cdots\cup\overline{A_k}}\right|\end{aligned}

\ \begin{aligned}f(k)&=\left|\overline{A_1}\cap\overline{A_2}\cap\overline{A_3}\cap\overline{A_4}\cap\cdots\cap\overline{A_k}\right|\\&=\left|\overline{A_1\cup A_2\cup A_3\cup A_4\cup\cdots\cup A_k}\right|\end{aligned}

应用容斥原理,同时可得 g(n)=\sum_{m=0}^n(-1)^m\binom nmf(m)f(n)=\sum_{m=0}^n(-1)^m\binom nmg(m)

当然我们也可以从定义出发证明二项式反演,和证明 Möbius 反演的过程类似,只需要证明 \,\displaystyle{\sum_{k=m}^n(-1)^{k-m}\binom nk\binom km=\delta(n,m)} 即可。事实上,只要满足 \,\displaystyle{\sum_{k=m}^n(-1)^{k-m}A(n,k)B(k,m)=\delta(n,m)} 的数列 A,B 均有可反演的性质。

除了二项式系数自成一对外,还有 \sum\limits_{k=m}^n(-1)^{k-m}\left[n\atop k\right]\left\{k\atop m\right\}=\delta(m,n)\sum\limits_{k=m}^n(-1)^{k-m}\left\{n\atop k\right\}\left[k\atop m\right]=\delta(m,n)\sum\limits_{k=m}^n(-1)^{k-m}\left\lfloor n\atop k\right\rfloor\left\lfloor k\atop m\right\rfloor=\delta(m,n) 。上面的式子中,\left[\atop\right] 表示第一类 Stirling 数\left\{\atop\right\} 表示第二类 Stirling 数\left\lfloor\atop\right\rfloor 表示 Lah 数

数论反演

其实就是定义在 (\mathbb N,|) 偏序集上的函数的 Möbius 反演。

对于数论函数 f,g ,有 g(n)=\sum_{d|n}f(d)\iff f(n)=\sum_{d|n}\mu(d,n)g(d)

因为前面证明过 \mu(a,b)=\mu(1,b/a) 而且默认情况下会把 \mu(1,m) 表示成 \mu(m) ,上式就可以化为网上常见的一般的形式,也就是 Dirichlet 卷积形式。

发表评论

电子邮件地址不会被公开。 必填项已用*标注