从卷积到反演

(本文章是以前一篇有关莫比乌斯反演和狄利克雷卷积的完整版)

狄利克雷卷积

对于卷积,我们应该并不陌生。最简单的卷积从我们常见的竖式乘法开始,再到生成函数(多项式)的相乘,无处不在。

多项式相乘就是一种卷积。次数为a和b的项的系数相乘得到系数为$(a+b)$项的系数。

$$
C[n]=\sum_{i=0}^{n}A[i]B[n-i]
$$

同样,狄利克雷卷积也是一种类似的卷积。

$$
C[n]=\sum_{ij=n}A[i]B[j]
$$

如果把A和B都理解成一种函数,A[i]是函数在x=i时的取值,那么我们就可以把狄利克雷卷积这样表示:

$$
(F\times G)(n)=\sum_{ij=n}A(i)B(j)
$$

同样,多项式的卷积也能够这样表示,不过为了加以区分,我们用方括号:

$$
[F\times G](n)=\sum_{i+j=n}A(i)B(j)
$$

之后,我们将用$(F\times G)(n)$表示离散函数F和G的狄利克雷卷积,$[F\times G](n)$表示离散函数F和G的多项式卷积。

多项式卷积及其反演

交换律($f\times g=g\times f$)

这个应该是显然的,因为多项式卷积本身是一个对称的过程。

结合律($[f\times g]\times g=f\times [g\times h]$)

这也是显然的,多项式的相乘不分先后。

存在单位元($e$)

单位元的意思,就好比小学数学中的1,矩阵中的单位矩阵。它乘以任何东西,那个东西都不会变。

于是乎,我们要求一个离散函数$e$,使得:

$$
e\times f=f
$$

显然,我们需要的单位元是:

$$
e(n)=\begin{cases}
1 & (n=0)\\
0 & (n\neq 0)
\end{cases}
$$

因为,这样的$e$才能保证$[e\times f]$的每一项就是$f$的每一项。

存在逆元($f^{-1}$)

对于离散函数$f$,我们把它看成是一个多项式,或者说生成函数,那么它的逆元就是:$\frac{1}{f}$。


以上的性质已经说明,离散函数$(f, g, h)$与多项式卷积构成了一个乘法群。以上的性质已经可以帮助我们非常容易地理解什么是反演了。

一般反演

这里的反演的一般定义是:对于数列$f,g$,如果他们可以写成如下的形式:

$$
\begin{align}
g_n &= \sum_{i=0}^{n}a_{n-i}f_i \\
f_n &= \sum_{i=0}^{n}b_{n-i}g_i
\end{align}
$$

那么称这两个序列是互反的。现在,我们可以把这两个序列理解为离散函数,那么:

$$
\begin{aligned}
g & =a\times f \\
f & =b\times g
\end{aligned}
$$

而反演的意义在于,当$f$不是很好求,而$g$非常好求的时候,我们可以用反演求出$f$。那么首先,我们需要知道$a,b$之间存在怎样的关系。

根据之前提到的,离散函数的四大性质,我们可以作出如下推断:

$$
\begin{aligned}
f & = b\times g\\
f & = b\times a\times f\\
b\times a & = e
\end{aligned}
$$

也就是说,$b,a$代表的离散函数在多项式卷积下互逆。哈,一般反演说到这里就结束了。

二项式反演与矩阵

二项式反演是一般反演的加强版:

$$
\begin{align}
g_n &= \sum_{i=0}^{n}a_{ni}f_i \\
f_n &= \sum_{i=0}^{n}b_{ni}g_i
\end{align}
$$

这里的$a$对于不同的$n$是完全不同的数列了,$b$也同样。那么这时,我们需要将$a,b$看成一些二维的东西,比如矩阵。矩阵的乘法实际上可以看成是高维的卷积。

$$
\begin{align}
\begin{bmatrix}
g_0\\
g_1\\
g_2\\
\end{bmatrix} &=
\begin{bmatrix}
a_{00} & 0 & 0\\
a_{10} & a_{11} & 0\\
a_{20} & a_{21} & a_{22}\\
\end{bmatrix} \times
\begin{bmatrix}
f_0\\
f_1\\
f_2\\
\end{bmatrix}\\
\begin{bmatrix}
f_0\\
f_1\\
f_2\\
\end{bmatrix} &=
\begin{bmatrix}
b_{00} & 0 & 0\\
b_{10} & b_{11} & 0\\
b_{20} & b_{21} & b_{22}\\
\end{bmatrix} \times
\begin{bmatrix}
g_0\\
g_1\\
g_2\\
\end{bmatrix}\\
\end{align}
$$

现在,像上次一样,我们要知道当$f,g$互反时,$a,b$应满足怎样的关系。下面用列向量表示$f,g$,用方阵表示$a,b$:
$$
\begin{align}
\vec{F} &= A\times \vec{G}\\
\vec{G} &= B\times \vec{F}\\
\Rightarrow \vec{F} = A\times \vec{G} &= A\times B\times\vec{F} \\
A\times B &= E
\end{align}
$$
而$A\times B = E$展开后的表示就是:
$$
\sum_{j=m}^{n}b_{ni}a_{im} = \begin{cases}
0 & (n \neq m)\\
1 & (n = m)
\end{cases}
$$

而满足这样的典型的$a,b$就包括:

$$
\begin{align}
g_n & = \sum_{i=0}^{n}C_n^if_i \\
f_n & = \sum_{i=0}^{n}(-1)^{n-i}C_n^ig_i
\end{align}
$$

以及:
$$
\begin{align}
g_n & = \sum_{i=0}^{n}(-1)^iC_n^if_i \\
f_n & = \sum_{i=0}^{n}(-1)^iC_n^ig_i
\end{align}
$$

上面两个式子的证明并不复杂:
式1:

$$
\begin{align}
A\times B & = \sum_{i=m}^{n}b_{ni}a_{im}\\
& = \sum_{i=m}^{n}(-1)^{i-m}C_n^iC_i^m\\
& = \sum_{i=m}^{n}(-1)^{i-m}C_n^mC_{n-m}^{n-i}\\
& = (-1)^{i-m}C_n^m\sum_{i=m}^{n}C_{n-m}^{n-i}\\
& = (-1)^{n-i-m}C_n^m\sum_{i=0}^{n-m}C_{n-m}^{i}\\
& = (-1)^{n-m}C_n^m\sum_{i=0}^{n-m}(-1)^iC_{n-m}^{i}\\
& = (-1)^{n-m}C_n^m(1-1)^{n-m}
\end{align}
$$

因此,$A\times B = E$。式2的证明同理。

狄利克雷卷积及其反演

交换律($f\times g=g\times f$)

和多项式乘法一样,狄利克雷卷积也满足交换律。证明嘛。。。显然的。

结合律 ($(f\times g)\times h=f\times (g\times h)$)

对于$(fg)h$在n处的取值,我们进行如下证明:

$$
\begin{aligned}
((f\times g)\times h)(n) & =\sum_{ij=n}(f\times g)(i)h(j) \\
& =\sum_{ij=n}(\sum_{kl=i}f(k)g(l))h(j) \\
& =\sum_{ijk=n}f(i)g(j)h(k)
\end{aligned}
$$

同理,对于$f\times (g\times h)$在n处的取值,我们也把它变成上面的形式:

$$
\begin{aligned}
(f\times (g\times h))(n) & =\sum_{ij=n}f(i)(g\times h)(j) \\
& =\sum_{ijk=n}f(i)g(j)h(k)
\end{aligned}
$$

所以结合律在这个卷积中存在。

存在单位元($e$)

同多项式卷积的单位元,我们可以写出狄利克雷卷积的单位元:

$$
e(n) = \begin{cases}
1 & (n=1) \\
0 & (n\neq 1)
\end{cases}
$$

存在逆元($f^{-1}$)

对于一个函数$f!=0$,我们总能找到一个函数$g$,使得$f*g=e$,则$g$一定是$f$的逆元。并且这个$g$一定是唯一的。


以上的这些结论,已经可以说明这些离散函数$(f,g,h)$在狄利克雷卷积意义下构成了一个乘法群。但是这并不重要。重要的是我们为什么可以用卷积的方式更简单地分析莫比乌斯反演。

莫比乌斯函数

我们通常见到的莫比乌斯反演总是这样的:

$$
f(n)=\sum_{d|n}g(d) \Rightarrow g(d)=\sum_{d|n}f(d)\mu(\frac{n}{d})
$$

我们把它先用卷积的形式写一下:

$$
f=u\times g \Rightarrow g=f\times \mu
$$

其中$u$是一个恒为1的函数。

哈哈,这样,我们只需要说明$u$和$\mu$互为反函数就行啦。

因为,如果u和g互为反函数(即$u\times g=e$),我们可以证明:

$$
\begin{aligned}
f & = g\times u \\
f\times \mu & = g\times u\times \mu \\
f\times \mu & = g\times e \\
f\times \mu & = g
\end{aligned}
$$

$\mu$的定义

我们直接定义$u*\mu=e$,即$\sum_{d|n}\mu(d)=\cases{1 & n=1\\0 & n>1}$

然后我们随手构造一个$\mu(d)$的取值表,使他满足这个东西就好啦。

$\mu$的构造

前人已经发现了$\mu$的构造方法。

$\mu(1)=1$

$\mu(n)=(-1)^k$,如果n可以写成k个不同质数的积

$\mu(n)=0$,其他n

按照这种定义,显然n=1时$\sum_{d|n}\mu(d)=1$

对于其他n,我们可以尝试证明一下。

首先,我们把n唯一分解一下,变成若干个素数的积,然后选择n的因数d,把他们的$\mu(d)$加起来。注意下面的证明中只把非0的$\mu(d)$加了起来。

$$
\begin{aligned}
\sum_{d|n}\mu(d)& =\mu(1)+\mu(p_1)+\mu(p_2)+\dots+\mu(p_1p_2)+\dots+\mu(p_1p_2\dots p_k) \\
& =\sum_{i=0}^k C_k^i(-1)^i \\
& = 0
\end{aligned}
$$

分类: 文章

1 条评论

【算法】 简单容斥模型 -boshi – K-XZY · 2018年10月12日 3:59 下午

[…] 本文将简单介绍几种常见的容斥模型,以及容斥方法。容斥和反演是离不开的,因为实际上它们就是同一种东西的两种表现形式,一种出现于小学课本,另一种出现于大学的教材。但是,容斥原理所运用的手段与技巧完全是基于反演理论的,因此,想熟练运用容斥原理,第一步就是完全搞清楚反演是什么。文章:从卷积到反演 […]

发表评论

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

你是机器人吗? =。= *