美文网首页
莫比乌斯变换-1-经典形式与狄利克雷卷积

莫比乌斯变换-1-经典形式与狄利克雷卷积

作者: 家中古词 | 来源:发表于2018-12-13 15:19 被阅读30次

经典形式

设 f 定义在正整数集合上，如果：

g(n) = \sum_{d|n} f(d), n \ge 1

g 称作是 f 的和函数[1]。

此时，无论 f 是什么，都有如下公式成立：

f(n) = \sum_{d|n} \mu(d) g(\frac{n}{d}), n \ge 1

其中的 \mu 是一个数论函数，称作莫比乌斯函数。

观察这两个式子，前者由 f 求得 g；后者反过来由 g 求得 f。后者应用在求 g 比 f 容易的情况下，用和函数反过来求原函数。这种过程一般称作莫比乌斯变换或者莫比乌斯反演。

狄利克雷卷积

经典表示方法虽然直接，但是显得繁琐。最常见的替代表示方案是使用狄利克雷卷积。

设 f, g 都是定义在正整数集合上的函数，他们的狄利克雷卷积是一个定义在同样范围内的函数，用 f*g 表示，满足：

(f*g)(n) = \sum_{d|n} f(d) g(\frac{n}{d})

或者写成：

(f*g)(n) = \sum_{ab=n} f(a) g(b)

其中 a,b 是正整数。

从定义中显然可以看出 * 运算满足的交换律：f*g = g*f[2]。也可以看出它满足结合定律 (f * g) * h = f * (g * h)。

下面取一些特殊函数做狄利克雷卷积。

设 \varepsilon(n) 在 n=1 时为 1，否则为 0。那么 f*\varepsilon = f。

设 1(n) = 1，那么 (f*1)(n) = \sum_{d|n}f(d)1(.) = \sum_{d|n}f(d)，是 f 的和函数。

用狄利克雷卷积，莫比乌斯反演可以这样表达：

如果 g = f*1，那么 f=g*\mu。

莫比乌斯函数

在上面的反演表达中，如果令 f = \varepsilon，那么得到：

\varepsilon = 1 * \mu

这个表达式是对 \mu 更直接的描述。如果 \mu 满足 \varepsilon = 1 * \mu，那么轻松可以证明 f = g * \mu：g * \mu = f * 1 * \mu = f * \varepsilon = f。所以，证明莫比乌斯反演成立的工作量，也就只有根据 \varepsilon = 1 * \mu 求出 \mu 的工作量。

  1. 实际上，有很多种和函数的定义，这里只取这一种。 ↩

  2. 这里以定义域、值域分别相同，并且同样的输入得到同样的输出，来表达函数相等。 ↩

相关文章

网友评论

      本文标题：莫比乌斯变换-1-经典形式与狄利克雷卷积

      本文链接：https://www.haomeiwen.com/subject/knavhqtx.html

      延伸阅读

      深度阅读

      • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

      栏目导航

      热点阅读

      关于我们|服务条款|联系我们|莫比乌斯变换-1-经典形式与狄利克雷卷积|投稿指南|网站地图|RSS订阅|排版工具|手机版

      提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

      Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

      备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

      本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

      所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！