莫比乌斯反演

YZY Lv3
  2025-07-02 02:24:44 2025-07-02 02:24:44 Created   2025-07-02 02:24:44 2025-07-02 02:24:44 Updated      

莫比乌斯反演（Möbius inversion）是一种在数论中非常重要的工具，用于将一些累积求和公式反转。它通常用于处理数值序列的转换，尤其是在处理数学函数的和式时。简而言之，莫比乌斯反演允许我们通过已知的累积（或前缀和）公式，恢复原始的序列。

概念

假设我们有一个数列 和 ，它们之间通过以下关系关联：

其中， 表示 是 的约数，求和是对所有 的约数进行的。

莫比乌斯反演的核心思想就是通过已知的 ，反推出原始的 ：

这里的 是莫比乌斯函数，它的定义如下：

  • 如果 是一个没有重复质因数的正整数，且 的质因数个数为奇数，则
  • 如果 是一个包含重复质因数的正整数，则

莫比乌斯反演公式在许多数学问题中都有广泛应用，特别是在数论、组合数学和离散数学中。

例子

假设我们知道以下关系：

我们想从 推导出 ，使用莫比乌斯反演公式：

假设 已知，莫比乌斯反演可以帮助我们恢复原始的 。

直观理解

可以把莫比乌斯反演看作是“反向求和”的过程。我们通过对约数的反转关系，利用莫比乌斯函数的特性，去除掉多余的部分，恢复原始的数列。

莫比乌斯函数

含有平方因子为的本质不同质因子个数

莫反证明中要用到的莫比乌斯函数重要性质：

简单证明：

设

则 （组合数学：k个质因子的选法 + 二项式定理）

故该式子当且仅当 时，；否则为

引理1

，有

简单证明：

引理2

$$
\forall n\in N_+，则 \bigg|\left{\lfloor{\frac{n}{d}}\rfloor | d\in N_+,d \le n \right} \bigg| \le \lfloor{2\sqrt{n}}\rfloor
$$

简单证明：

对于所有的 ， 至多有 种取值

对于所有的 ，则 ，至多有 种取值

故加起来至多有 种取值

数论分块

考虑含有 的求和式子（ 为常数），对于任意 ，找出一个最大的 ，

此时

简单证明：

已经证明了 ，故证明命题现还需证明: 当 时，

（常用不等式：）（取倒数）

故

证明过程

设 为两个数论函数

如果有 ，那么有

如果有 ，那么有

一式证明

$$
\begin{align} \sum_{d|n}\mu(d)F(\frac{n}{d}) &= \sum_{d|n}\mu(d)\sum_{i|\frac{n}{d}}f(i) \ &= \sum_{i|n} f(i) \sum_{d|\frac{n}{i}}\mu(d) &\bigg(i|\frac{n}{d} \Rightarrow id|n \Rightarrow d| \frac{n}{i}\bigg)\ &= f(n) \end{align}
$$

二式证明

可以类比 二重积分 在离散情况下 交换积分次序 的手段，会帮助理解
不过 二重积分 是在连续的情况下，因此画出 积分区域 穿个线就好了
而离散情况下，精准的找出每个点，就需要用 整除的性质 ，推推公式 了

容斥原理

容斥原理（Inclusion-Exclusion Principle）是一个用于计算多个集合的并集大小的数学公式。它的核心思想是，通过逐个添加集合的大小，再减去集合交集的大小，从而避免重复计数。容斥原理通常用于计算“至少一个条件成立”或“多个条件联合成立”的问题。

对于两个集合 和 ，容斥原理的基本公式是：

对于三个集合 , , 和 ，容斥原理的扩展公式是：

二者联系

在处理一些离散数学问题时，特别是在计算某些集合的计数或求和时，莫比乌斯反演可以看作是容斥原理的反向操作。通过莫比乌斯反演，我们可以从“总和”中去除掉那些重复的部分，从而恢复原始的数列或集合。

具体

  1. 容斥原理的求和表示：
    容斥原理通常用来计算多个条件下的“总数”，比如，给定一系列的集合，计算它们的并集大小。设 是一系列集合，容斥原理可以表示为：

    这种求和方式其实是通过考虑各个集合的大小，并在重复计算时进行相应的加减操作，避免过多的重复计算。

  2. 莫比乌斯反演的反向操作：
    莫比乌斯反演就是在给定一个总和（比如容斥原理中的并集大小）后，通过利用莫比乌斯函数的加减法则，反向去除掉多重计数的部分，从而恢复到原始的数列或集合。

    具体来说，如果我们有一个关于集合的求和公式（比如容斥原理的表示），通过莫比乌斯反演可以得到一个反向求和的公式，恢复出每个单独集合的大小。例如，容斥原理通过计算并集的大小，往往会涉及到多个交集的计数，而莫比乌斯反演的作用就是通过加权的方式去除这些交集带来的多重计数。

公式

假设我们有 和 之间的关系，其中 是某些事件的计数， 是这些事件的累积计数。容斥原理中， 通常是通过对某些条件进行加减来计算的。如果我们知道 ，那么使用莫比乌斯反演可以恢复原始的 。

公式为：

这里， 是莫比乌斯函数，类似于容斥原理中的加减操作，它在“去重”时起到了重要作用。通过莫比乌斯反演，我们可以将累积的总和反转为单独的贡献。

例子

考虑一个数论问题，我们希望计算从1到 中能够被某些数整除的整数个数。通过容斥原理，我们可以先计算每个数的倍数的个数，再通过减去交集的倍数个数来避免重复计数。而通过莫比乌斯反演，我们可以从这些累积的结果中“反向”恢复出每个数的贡献。

总结

  • 容斥原理帮助我们计算多个集合的并集或交集的大小，通常涉及到逐层加减的操作。
  • 莫比乌斯反演是容斥原理的“反向操作”，它允许我们从总和中去除重复的部分，恢复原始的数列或集合的贡献。
  • 两者的核心思想相似，都是通过加减法则处理重叠部分，但莫比乌斯反演具有更为精妙的数学结构，使得它能够在数论和组合数学中广泛应用。

数论中的容斥

容斥原理可以帮助我们计算满足多个条件的整数个数。在数论中，这些条件通常是关于整数的“可除性”问题。具体来说，容斥原理通过以下步骤计算多个集合的交集和并集大小：

假设我们有一组集合 ，其中每个集合 包含满足某个条件的整数（如能被某个数整除的整数）。容斥原理可以帮助我们计算这些集合的并集的大小，即满足至少一个条件的整数的个数。

回顾容斥

对于两个集合 和 ，容斥原理的公式为：

对于三个集合 , , 和 ，容斥原理的扩展公式为：

对于 个集合 ，容斥原理的通用公式为：

在数论中的应用

数论中的容斥原理主要用于计算满足某些整除条件的整数个数。比如：

  1. 计算可被多个数整除的整数个数：
    假设我们要计算从 1 到 之间能被 这些数之一整除的整数个数。可以定义每个集合 为能被 整除的整数集合。那么，我们就可以使用容斥原理来计算这些集合的并集大小，即符合至少一个条件的整数个数。

    其中， 表示从 1 到 之间能被 整除的整数个数， 是最小公倍数。

  2. 应用举例：
    例如，计算 1 到 100 之间，能被 2 或 3 整除的整数个数。可以按照以下步骤使用容斥原理：

    • 计算能被 2 整除的数：
    • 计算能被 3 整除的数：
    • 计算能被 6（2 和 3 的最小公倍数）整除的数：

    于是，应用容斥原理得到的结果为：

    所以，1 到 100 之间能被 2 或 3 整除的整数共有 67 个。

更一般的

容斥原理在更一般的数论问题中，尤其是涉及整除性、分解、以及多个条件下的整数计数时，都能起到很好的作用。通过使用容斥原理，我们可以精确计算出在某些条件下的整数个数，同时避免重复计算。

问题分析

给定两个数 和 ，我们想求 的数对个数，即从 到 之间选择两个数 和 ，它们的最大公约数为 。

思路：

  1. 条件转化：

    • 首先，我们将所有的数对 的最大公约数为 的问题转化为：选择 和 ，使得 ，其中 和 是整数。
    • 也就是说，我们可以将原问题转化为：在 范围内，计算 的数对个数。

  2. 数对个数计算：

    • 在 范围内，，我们需要计算 的数对个数。
    • 如果直接计算所有数对的个数，总共有 个数对。但是，这些数对中并不全是互质的，需要使用容斥原理来排除掉不是互质的数对。

  3. 容斥原理的应用：

    • 假设 是欧拉函数，表示 中与 互质的数的个数。我们可以通过容斥原理，依次排除所有包含公因数的数对。
      具体步骤如下：
    • 计算总数对数：
    • 然后通过容斥原理排除掉所有 的数对：
      • 对每个质数 ，排除所有 和 都能被 整除的数对。即排除所有 都在 的倍数范围内。
      • 同理，对每对质数 ，排除所有 能被 整除的数对。

好的，这个例子中的数学公式和具体步骤的阐述确实存在一些问题，尤其是在质数 的选取条件以及示例的计算上。我们来一步步修正和澄清。

问题的核心：

我们要计算的是满足 且 的数对 的个数。
这个问题可以转化为：

  1. 令 ，。
  2. 则 。
  3. 同理，。
  4. 并且 。
  5. 设 。问题就变成了：计算满足 且 的数对 的个数。

正确的数学公式（使用莫比乌斯反演）：

满足 且 的数对 的个数可以通过莫比乌斯反演得到，其公式为：
数对个数
其中：

  • 是莫比乌斯函数：
    • 如果 是 个不同质数的乘积，，则 。
    • 如果 含有任何平方因子（即存在质数 使得 ），则 。
  • 表示对 向下取整。

与容斥原理的关系：
莫比乌斯反演公式本质上是容斥原理的一种紧凑表达：

  • ：所有可能的数对 的总数。
  • ：减去那些 都是质数 的倍数的数对。
  • ：加上那些 都是 的倍数的数对（因为它们在之前被减了两次）。
  • 以此类推。

注意： 原公式中 “” 的表述是不准确的，求和是针对所有 (或者说，当用质数展开时，是针对所有质数 ，以及它们的组合，只要 或 , 等)。

数学背景

我们要寻找数对 的个数，满足 且 。
首先，我们进行变量代换：令 ，。
则条件变为 且 。
这等价于 且 。
令 。问题转化为：计算 且 的数对 的个数。

数学公式：

使用莫比乌斯反演，数对个数为：
数对个数
其中 是莫比乌斯函数。

具体步骤（展开形式即为容斥原理）：

  1. 计算 。
  2. 计算初始总数（对应 , ）： 。
  3. 对于每一个质数 (使得 )，减去 都是 的倍数的数对数量（对应 , ）：从总数中减去 。
  4. 对于每一对不同的质数 (使得 )，加上 都是 的倍数的数对数量（对应 , ）：向总数中加入 。
  5. 以此类推，对于 个不同质数的乘积 (使得 )，根据 的奇偶性，加或减 。具体来说是乘以 。
  6. 如果 含有平方因子 (例如 )，则 ，这些项的贡献为0，可以忽略。
  7. 将所有这些项加起来得到最终结果。

示例：

假设 且 ，那么：

  1. 。
    我们需要计算 且 的数对个数。

  2. 使用莫比乌斯反演公式 ：

    • d = 1: .
      项为：。
      （这是所有 的数对总数）

    • d = 2 (质数): .
      项为：。
      （排除 都是2的倍数的数对）

    • d = 3 (质数): .
      项为：。
      （排除 都是3的倍数的数对）

    • d = 4 (, 有平方因子): .
      项为：。

    • d = 5 (质数): .
      项为：。
      （排除 都是5的倍数的数对）

    • 对于 ，例如 ，，所以这些项的贡献都为0。我们只需要计算到 。

  3. 最终结果 = 。

所以，对于 ，满足 且 的数对 有 19 对。

我们可以列举一下这些数对 使得 且 ：
(1,1), (1,2), (1,3), (1,4), (1,5)
(2,1), (2,3), (2,5)
(3,1), (3,2), (3,4), (3,5)
(4,1), (4,3), (4,5)
(5,1), (5,2), (5,3), (5,4)
总共 对。

容斥原理用于计算多个集合的并集或交集的大小，避免重复计数。

莫比乌斯反演是数论中一个重要的技巧，它处理的是形如 的和式与 （或类似形式）之间的转换关系。在我们这个问题中，它提供了一个直接计算 的数对数量的公式，这个公式本身就内含了容斥原理的思想。

在数论问题中，容斥原理和莫比乌斯反演常常结合使用或本质相通，帮助我们精确计算符合特定条件的整数或数对的个数。

  • Title: 莫比乌斯反演
  • Author: YZY
  • Created at : 2025-07-02 02:24:44
  • Updated at : 2025-07-02 02:24:44
  • Link: https://blog.dtoj.team/2025/07/02/莫比乌斯反演/
  • License: 三金家的Y同学
On this page
莫比乌斯反演
  1. 概念
  2. 例子
  3. 直观理解
  4. 莫比乌斯函数
  5. 引理1
  6. 引理2
  7. 数论分块
  • 证明过程
    1. 容斥原理
    2. 二者联系
    3. 公式
    4. 例子
    5. 总结
    6. 数论中的容斥
    7. 回顾容斥
  • 在数论中的应用
    1. 更一般的
    2. 问题分析
    3. 思路：
    4. 数学背景
    5. 数学公式：
    6. 具体步骤（展开形式即为容斥原理）：
    7. 示例：