莫比乌斯反演定理
定理
第一种形式的莫比乌斯反演
存在 f ( x ) f(x) f(x) 和 g ( x ) g(x) g(x) 是定义在非负整数域的函数，并且满足
f ( n ) = ∑ d ∣ n g ( d ) f(n) = \sum_{d|n}g(d) f(n)=d∣n∑g(d)
式子等价于
g ( n ) = ∑ d ∣ n μ ( d ) f ( n d ) g(n) = \sum_{d|n}\mu(d)f(\frac{n}{d}) g(n)=d∣n∑μ(d)f(dn)
第二种形式的莫比乌斯反演
莫比乌斯反演还存在另一种形式：
证明
第一种形式的证明
简单朴素证明：
只需证右边 ∑ d ∣ n μ ( d ) f ( n d ) \sum_{d|n}\mu(d)f(\frac{n}{d}) ∑d∣nμ(d)f(dn) 等于左边的 g ( n ) g(n) g(n) 即可。
∑ d ∣ n μ ( d ) f ( n d ) = ∑ d ∣ n μ ( d ) ∑ i ∣ n d g ( i ) = ∑ d ∣ n ∑ i ∣ n d μ ( d ) g ( i ) = ∑ i ∣ n ∑ d ∣ n i μ ( d ) g ( i ) = ∑ d ∣ n μ ( d ) ∑ i ∣ n d g ( i ) = g ( n ) \begin{aligned} \sum_{d|n}\mu(d)f(\frac{n}{d}) & = \sum_{d|n}\mu(d)\sum_{i|\frac{n}{d}}g(i)\\ &=\sum_{d|n}\sum_{i|\frac{n}{d}}\mu(d)g(i)\\ &=\sum_{i|n}\sum_{d|\frac{n}{i}}\mu(d)g(i)\\ &=\sum_{d|n}\mu(d)\sum_{i|\frac{n}{d}}g(i)\\ &=g(n)\\ \end{aligned} d∣n∑μ(d)f(dn)=d∣n∑μ(d)i∣dn∑g(i)=d∣n∑i∣dn∑μ(d)g(i)=i∣n∑d∣in∑μ(d)g(i)=d∣n∑μ(d)i∣dn∑g(i)=g(n)
如上， g ( n ) = ∑ d ∣ n μ ( d ) f ( n d ) g(n)=\sum_{d|n}\mu(d)f(\frac{n}{d}) g(n)=∑d∣nμ(d)f(dn) 得证。
卷积证明：
已知 μ \mu μ 为莫比乌斯函数， u u u 为乘法单位元， e e e 为单位元。
它们存在以下三个性质：1. u = μ − 1 u = \mu^{-1} u=μ−1 。2. u ∗ μ = e u*\mu=e u∗μ=e 。3. e ∗ f = f e*f=f e∗f=f 。
求证： f = g ∗ u ⇔ g = f ∗ μ f = g * u \Leftrightarrow g = f*\mu f=g∗u⇔g=f∗μ
先证： f = g ∗ u ⇒ g = f ∗ μ f=g*u\Rightarrow g = f*\mu f=g∗u⇒g=f∗μ
f = g ∗ u ⇒ g = f ∗ μ ⇒ g ∗ u = f ∗ μ ∗ u ⇒ g ∗ u = f ∗ ( μ ∗ u ) ⇒ g ∗ u = f ∗ e ⇒ g ∗ u = f \begin{aligned} f=g*u & \Rightarrow g = f * \mu\\ & \Rightarrow g*u = f*\mu*u\\ & \Rightarrow g*u= f*(\mu*u)\\ & \Rightarrow g*u=f*e\\ & \Rightarrow g*u=f\\ \end{aligned} f=g∗u⇒g=f∗μ⇒g∗u=f∗μ∗u⇒g∗u=f∗(μ∗u)⇒g∗u=f∗e⇒g∗u=f
如上， f ( n ) = ∑ d ∣ n g ( d ) ⇒ g ( n ) = ∑ d ∣ n μ ( d ) f ( n d ) f(n) = \sum_{d|n}g(d) \Rightarrow g(n) = \sum_{d|n}\mu(d)f(\frac{n}{d}) f(n)=∑d∣ng(d)⇒g(n)=∑d∣nμ(d)f(dn) 得证。
再证： g = f ∗ μ ⇒ f = g ∗ u g = f * \mu \Rightarrow f=g*u g=f∗μ⇒f=g∗u
g = f ∗ μ ⇒ f = g ∗ u ⇒ f ∗ μ = g ∗ u ∗ μ ⇒ f ∗ μ = g ∗ ( u ∗ μ ) ⇒ f ∗ μ = g ∗ e ⇒ f ∗ μ = g \begin{aligned} g = f*\mu & \Rightarrow f=g*u\\ & \Rightarrow f*\mu=g*u*\mu\\ & \Rightarrow f*\mu=g*(u*\mu)\\ & \Rightarrow f*\mu=g*e\\ & \Rightarrow f*\mu=g\\ \end{aligned} g=f∗μ⇒f=g∗u⇒f∗μ=g∗u∗μ⇒f∗μ=g∗(u∗μ)⇒f∗μ=g∗e⇒f∗μ=g
如上， g = f ∗ μ ⇒ f = g ∗ u g = f * \mu \Rightarrow f=g*u g=f∗μ⇒f=g∗u 得证。
即 f ( n ) = ∑ d ∣ n g ( d ) ⇔ g ( n ) = ∑ d ∣ n μ ( d ) f ( n d ) f(n) = \sum_{d|n}g(d) \Leftrightarrow g(n) = \sum_{d|n}\mu(d)f(\frac{n}{d}) f(n)=∑d∣ng(d)⇔g(n)=∑d∣nμ(d)f(dn) 得证。
第二种形式的证明
简单朴素证明
求证 f ( n ) = ∑ n ∣ d g ( d ) ⇔ g ( n ) = ∑ n ∣ d μ ( d n ) f ( d ) f(n)=\sum_{n|d}g(d) \Leftrightarrow g(n)=\sum_{n|d}\mu(\frac{d}{n})f(d) f(n)=∑n∣dg(d)⇔g(n)=∑n∣dμ(nd)f(d)
令 k = d n k={d\over n} k=nd ，
g ( n ) = ∑ n ∣ d μ ( d n ) f ( d ) = ∑ k = 1 + ∞ μ ( k ) f ( n k ) = ∑ k = 1 + ∞ μ ( k ) ∑ n k ∣ i g ( i ) = ∑ k = 1 + ∞ ∑ n k ∣ i μ ( k ) g ( i ) = ∑ n ∣ i ∑ k ∣ i n μ ( k ) g ( i ) = ∑ n ∣ i g ( i ) ∑ k ∣ i n μ ( k ) \begin{aligned} g(n)&=\sum_{n|d}\mu(\frac{d}{n})f(d)\\ &=\sum_{k=1}^{+\infty}\mu(k)f(nk)\\ &=\sum_{k=1}^{+\infty}\mu(k)\sum_{nk|i}g(i)\\ &=\sum_{k=1}^{+\infty}\sum_{nk|i}\mu(k)g(i)\\ &=\sum_{n|i}\sum_{k|{i\over n}}\mu(k)g(i)\\ &=\sum_{n|i}g(i)\sum_{k|{i\over n}}\mu(k)\\ \end{aligned} g(n)=n∣d∑μ(nd)f(d)=k=1∑+∞μ(k)f(nk)=k=1∑+∞μ(k)nk∣i∑g(i)=k=1∑+∞nk∣i∑μ(k)g(i)=n∣i∑k∣ni∑μ(k)g(i)=n∣i∑g(i)k∣ni∑μ(k)
观察 ∑ n ∣ i g ( i ) ∑ k ∣ i n μ ( k ) \sum_{n|i}g(i)\sum_{k|{i\over n}}\mu(k) ∑n∣ig(i)∑k∣niμ(k) ，当且仅当 i n = 1 {i\over n}=1 ni=1，即 i = n i=n i=n 时， ∑ k ∣ i n μ ( k ) = 1 \sum_{k|{i\over n}}\mu(k)=1 ∑k∣niμ(k)=1，其余都是 0 0 0。因此
∑ n ∣ i g ( i ) ∑ k ∣ i n μ ( k ) = g ( n ) \sum_{n|i}g(i)\sum_{k|{i\over n}}\mu(k)=g(n) n∣i∑g(i)k∣ni∑μ(k)=g(n)
得证。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/225361.html原文链接：https://javaforall.net
