莫比乌斯反演初探

乌斯反演初探"/>

莫比乌斯反演初探

莫比乌斯反演初探

文章目录

• 莫比乌斯反演初探
• • 1. 莫比乌斯函数的定义
  • 2. S(x)函数
  • 3. 莫比乌斯反演定理
  • 4. 莫比乌斯反演的应用

1. 莫比乌斯函数的定义

首先将正整数x写成分解形式:

x = p 1 α 1 ∗ p 2 α 2 ∗ . . . ∗ p k α k x=p_1^{\alpha_1}*p_2^{\alpha_2}*...*p_k^{\alpha_k} x=p1α1​​∗p2α2​​∗...∗pkαk​​

则莫比乌斯函数定义为:

μ ( x ) = { 1 , x = 1 0 , ∃ α i ≥ 2 ( − 1 ) k , ∀ α i = 1  其中 k 是 x 包含的不同质因子的个数 \mu(x)=\begin{cases} 1, &x=1\\ 0, &\exists \alpha_i \geq2 \\ (-1)^k, &\forall \alpha_i =1 \end{cases} \qquad \text{ 其中 k 是 x 包含的不同质因子的个数} μ(x)=⎩⎪⎨⎪⎧​1,0,(−1)k,​x=1∃αi​≥2∀αi​=1​ 其中 k 是 x 包含的不同质因子的个数

例如:
μ ( 6 ) = 1 , μ ( 7 ) = − 1 , μ ( 8 ) = 0 ， μ ( p ) = − 1 ( p 为 质 数 ) \mu(6)=1,\quad\quad\mu(7)=-1,\quad\quad\mu(8)=0，\quad\mu(p)=-1(p为质数) μ(6)=1,μ(7)=−1,μ(8)=0，μ(p)=−1(p为质数)

2. S(x)函数

我们定义:

S ( x ) = ∑ d ∣ x μ ( d ) S(x)=\sum_{d|x}\mu(d) S(x)=d∣x∑​μ(d)

则:

S ( x ) = { 1 , x = 1 0 , x > 1 = [ x = 1 ] S(x)=\begin{cases} 1, &x=1\\ 0, &x>1 \end{cases} =[x=1] S(x)={1,0,​x=1x>1​=[x=1]

证明如下:

当x=1时:

S ( x ) = S ( 1 ) = μ ( 1 ) = 1 S(x)=S(1)=\mu(1)=1 S(x)=S(1)=μ(1)=1

当x>1时:

因 为 x = p 1 α 1 ∗ p 2 α 2 ∗ . . . ∗ p k α k , 故 x 的 约 数 d = p 1 β 1 ∗ p 2 β 2 ∗ . . . ∗ p k β k ( 其 中 0 ≤ β i ≤ α i ) 若 ∃ β i ≥ 2 , 则 μ ( x ) = 0 ; 故 我 们 只 需 要 考 虑 β i 取 1 和 0 的 情 况 , 即 考 虑 k 个 β i 中 有 多 少 个 β i 取 1 , 显 然 , 可 能 有 0 个 β i 取 1 , 1 个 β i 取 1 , . . . , k 个 β i 取 1 , 则 S ( x ) = μ ( d 0 ) + μ ( d 1 ) + μ ( d 2 ) + . . . + μ ( d k ) = C k 0 ( − 1 ) 0 + C k 1 ( − 1 ) 1 + . . . + C k k ( − 1 ) k = ( − 1 + 1 ) k = 0 因为x=p_1^{\alpha_1}*p_2^{\alpha_2}*...*p_k^{\alpha_k},故x的约数d=p_1^{\beta_1}*p_2^{\beta_2}*...*p_k^{\beta_k}(其中0 \leq \beta_i \leq \alpha_i)\\ 若 \exists \beta_i\geq2,则\mu(x)=0;\\ 故我们只需要考虑\beta_i取1和0的情况,即考虑k个\beta_i中有多少个\beta_i取1,\\ 显然,可能有0个\beta_i取1,1个\beta_i取1,...,k个\beta_i取1,\\ \begin{aligned}则S(x) &=\mu(d_0)+\mu(d_1)+\mu(d_2)+...+\mu(d_k)\\ &=C_k^0 (-1)^0+C_k^1(-1)^1+...+C_k^k(-1)^k\\&=(-1+1)^k\\&=0\end{aligned} 因为x=p1α1​​∗p2α2​​∗...∗pkαk​​,故x的约数d=p1β1​​∗p2β2​​∗...∗pkβk​​(其中0≤βi​≤αi​)若∃βi​≥2,则μ(x)=0;故我们只需要考虑βi​取1和0的情况,即考虑k个βi​中有多少个βi​取1,显然,可能有0个βi​取1,1个βi​取1,...,k个βi​取1,则S(x)​=μ(d0​)+μ(d1​)+μ(d2​)+...+μ(dk​)=Ck0​(−1)0+C