经典形式
设 定义在正整数集合上,如果:
称作是
的和函数[1]。
此时,无论 是什么,都有如下公式成立:
其中的 是一个数论函数,称作莫比乌斯函数。
观察这两个式子,前者由 求得
;后者反过来由
求得
。后者应用在求
比
容易的情况下,用和函数反过来求原函数。这种过程一般称作莫比乌斯变换或者莫比乌斯反演。
狄利克雷卷积
经典表示方法虽然直接,但是显得繁琐。最常见的替代表示方案是使用狄利克雷卷积。
设 都是定义在正整数集合上的函数,他们的狄利克雷卷积是一个定义在同样范围内的函数,用
表示,满足:
或者写成:
其中 是正整数。
从定义中显然可以看出 运算满足的交换律:
[2]。也可以看出它满足结合定律
。
下面取一些特殊函数做狄利克雷卷积。
设 在
时为 1,否则为 0。那么
。
设 ,那么
,是
的和函数。
用狄利克雷卷积,莫比乌斯反演可以这样表达:
如果
,那么
。
莫比乌斯函数
在上面的反演表达中,如果令 ,那么得到:
这个表达式是对 更直接的描述。如果
满足
,那么轻松可以证明
:
。所以,证明莫比乌斯反演成立的工作量,也就只有根据
求出
的工作量。