精华内容
下载资源
问答
  • 莫比乌斯反演定理证明(两种形式)

    千次阅读 多人点赞 2016-01-26 16:38:33
    PoPoQQQ没有给出形式二的证明,我恨PoPoQQQ,证了好久。 证明之前,请先看看PoPoQQQ的ppt,当你看完发现没有证明想哭的时候,看看这篇博客。 形式一: F(n)=∑d|nf(d)=>f(n)=∑d|nμ(d)F(nd)F(n)=\sum_{d|n}f(d)=...

    PoPoQQQ没有给出形式二的证明,我恨PoPoQQQ,证了好久。
    证明之前,请先看看PoPoQQQ的ppt,当你看完发现没有证明想哭的时候,看看这篇博客。
    莫比乌斯反演定理形式一:

    F(n)=d|nf(d)=>f(n)=d|nμ(d)F(nd)

    证明:
    恒等变形得:
    f(n)=d|nμ(d)F(nd)=d|nμ(d)k|ndf(k)=k|nf(k)d|nkμ(d)

    因为之前证明的这个定理:

    d|nμ(d)={10n==1n>1

    所以当且仅当 nk=1 ,即n=k时, d|nkμ(d)=1 ,其余时候等于0。

    k|nf(k)d|nkμ(d)=f(n)

    莫比乌斯反演定理形式二:

    F(n)=n|df(d)=>f(n)=n|dμ(dn)F(d)

    证明:
    k=dn ,那么,就得到
    f(n)=k=1+μ(k)F(nk)=k=1+μ(k)nk|tf(t)=n|tf(t)k|tnμ(k)

    所以当且仅当 tn=1 ,即t=n时, k|tnμ(k)=1 ,其余时候等于0。
    故得到
    n|tf(t)k|tnμ(k)=f(n)

    证明完毕。

    展开全文
  • 莫比乌斯反演定理证明

    千次阅读 2017-07-29 19:15:19
    https://www.zhihu.com/question/23764267/answer/26007647 直接去上面这个网址看吧,看一位叫做Syu Gau的大神的证明,写得非常清晰,本人不太会传图片(╯#-_-)╯,所以就不在此处再写一遍了。。。

    https://www.zhihu.com/question/23764267/answer/26007647
    直接去上面这个网址看吧,看一位叫做Syu Gau的大神的证明,写得非常清晰,本人不太会传图片(╯#-_-)╯,所以就不在此处再写一遍了。。。

    展开全文
  • 莫比乌斯反演定理形式一: F(n)=∑d|nf(d)=>f(n)=∑d|nμ(d)F(nd) 证明: 恒等变形得: f(n)=∑d|nμ(d)F(nd)=∑d|nμ(d)∑k|ndf(k)=∑k|nf(k)∑d|nkμ(d) 因为之前证明的这个定理: ∑d|nμ(d)={...
    莫比乌斯反演定理形式一: 
    
    F(n)=d|nf(d)=>f(n)=d|nμ(d)F(nd)

    证明:
    恒等变形得:
    f(n)=d|nμ(d)F(nd)=d|nμ(d)k|ndf(k)=k|nf(k)d|nkμ(d)

    因为之前证明的这个定理:

    d|nμ(d)={10n==1n>1

    所以当且仅当 nk=1 ,即n=k时, d|nkμ(d)=1 ,其余时候等于0。

    k|nf(k)d|nkμ(d)=f(n)

    莫比乌斯反演定理形式二:

    F(n)=n|df(d)=>f(n)=n|dμ(dn)F(d)

    证明:
    k=dn ,那么,就得到
    f(n)=k=1+μ(k)F(nk)=k=1+μ(k)nk|tf(t)=n|tf(t)k|tnμ(k)

    所以当且仅当 tn=1 ,即t=n时, k|tnμ(k)=1 ,其余时候等于0。
    故得到
    n|tf(t)k|tnμ(k)=f(n)

    证明完毕。
    展开全文
  • 莫比乌斯反演定理证明。 ps:ps:ps:初学给自己做个笔记,怕以后忘了。 前置知识:莫比乌斯函数μ\muμ的两个性质: 1.∑d∣nμ(d)=[n==1]1.\sum\limits_{d|n}\mu(d)=[n==1]1.d∣n∑​μ(d)=[n==1] 2.∑d∣nμ(d)d=...

    莫比乌斯反演定理的证明。

    p s : ps: ps:初学给自己做个笔记,怕以后忘了。

    前置知识:莫比乌斯函数 μ \mu μ的两个性质:

    1. ∑ d ∣ n μ ( d ) = [ n = = 1 ] 1.\sum\limits_{d|n}\mu(d)=[n==1] 1.dnμ(d)=[n==1]

    证明:
    在这里插入图片描述

    2. ∑ d ∣ n μ ( d ) d = φ ( n ) n 2.\sum\limits_{d|n}\dfrac{\mu(d)}{d}=\dfrac{\varphi(n)}{n} 2.dndμ(d)=nφ(n) (这里证明用不到)

    定理:若有定义在 N + N^+ N+上的函数 F ( n ) , f ( n ) F(n),f(n) F(n),f(n)满足关系:

    F ( n ) = ∑ d ∣ n f ( d ) F(n)=\sum\limits_{d|n}f(d) F(n)=dnf(d),则有: f ( n ) = ∑ d ∣ n μ ( d ) F ( n d ) f(n)=\sum\limits_{d|n}\mu(d)F(\dfrac{n}{d}) f(n)=dnμ(d)F(dn)

    证明:我们只需证上述等式右边等于左边即可。

    ∑ d ∣ n μ ( d ) F ( n d ) \sum\limits_{d|n}\mu(d)F(\dfrac{n}{d}) dnμ(d)F(dn)

    = ∑ d ∣ n μ ( d ) ∑ e ∣ n d f ( e ) \sum\limits_{d|n}\mu(d)\sum\limits_{e|\frac{n}{d}}f(e) dnμ(d)ednf(e) (定义) (1)

    = ∑ d ∣ n ∑ e ∣ n d μ ( d ) f ( e ) \sum\limits_{d|n}\sum\limits_{e|\frac{n}{d}}\mu(d)f(e) dnednμ(d)f(e) (分配律) (2)

    = ∑ e ∣ n ∑ d ∣ n e μ ( d ) f ( e ) \sum\limits_{e|n}\sum\limits_{d|\frac{n}{e}}\mu(d)f(e) endenμ(d)f(e) ( e , d e,d e,d的地位是可交换的) (3)

    = ∑ e ∣ n f ( e ) ∑ d ∣ n e μ ( d ) \sum\limits_{e|n}f(e)\sum\limits_{{d|\frac{n}{e}}}\mu(d) enf(e)denμ(d) (结合律) (4)

    = f ( n ) f(n) f(n) ( μ \mu μ性质1) (5)

    证毕。

    如果这里还是看不懂请看下面。

    对于 ( 2 ) → ( 3 ) (2)\rightarrow(3) (2)(3)的解释:

    因为 e ∣ n d ⇔ e d ∣ n e|\dfrac{n}{d}\Leftrightarrow ed|n ednedn

    可以理解为对每个 n n n的因子 d d d求出所有满足 e d ∣ n ed|n edn e e e,即二元组 ( d , e ) (d,e) (d,e)的个数。

    举个例子: n = 6 n=6 n=6.

    d = 1 , e = { 1 , 2 , 3 , 6 } d=1,e=\{1,2,3,6\} d=1,e={1,2,3,6}

    d = 2 , e = { 1 , 3 } d=2,e=\{1,3\} d=2,e={1,3}

    d = 3 , e = { 1 , 2 } d=3,e=\{1,2\} d=3,e={1,2}

    d = 6 , e = { 1 } d=6,e=\{1\} d=6,e={1}

    因为 e , d e,d e,d都是 n n n的因子,所以地位等价。

    即条件可以改为 d ∣ n e ⇔ d e ∣ n d|\dfrac{n}{e}\Leftrightarrow de|n denden

    每个 n n n的因子 e e e求出所有满足 d e ∣ n de|n den e e e,即二元组 ( e , d ) (e,d) (e,d)的个数。

    e = 1 , d = { 1 , 2 , 3 , 6 } e=1,d=\{1,2,3,6\} e=1,d={1,2,3,6}

    e = 2 , d = { 1 , 3 } e=2,d=\{1,3\} e=2,d={1,3}

    e = 3 , d = { 1 , 2 } e=3,d=\{1,2\} e=3,d={1,2}

    e = 6 , d = { 1 } e=6,d=\{1\} e=6,d={1}

    ( 4 ) → ( 5 ) (4)\rightarrow(5) (4)(5)的解释:

    显然当 n e ≠ 1 \dfrac{n}{e}\neq1 en=1时, ∑ d ∣ n e μ ( d ) = 0 \sum\limits_{{d|\frac{n}{e}}}\mu(d)=0 denμ(d)=0

    只有当 n e = 1 → e = n \dfrac{n}{e}=1\rightarrow e=n en=1e=n时, ∑ d ∣ n e μ ( d ) = 1 \sum\limits_{{d|\frac{n}{e}}}\mu(d)=1 denμ(d)=1

    ∑ e ∣ n f ( e ) ∑ d ∣ n e μ ( d ) \sum\limits_{e|n}f(e)\sum\limits_{{d|\frac{n}{e}}}\mu(d) enf(e)denμ(d)= f ( n ) × 1 = f ( n ) f(n)\times 1=f(n) f(n)×1=f(n)

    卷积证明见置顶回答

    展开全文
  • 反演定理及其应用

    千次阅读 2018-08-04 13:09:07
    一、莫比乌斯反演 莫比乌斯反演公式: 若 F(n)=∑i|nf(i)F(n)=∑i|nf(i)F(n)=\sum_{i|n}f(i) 则 f(n)=∑i|nμ(i)F(ni)f(n)=∑i|nμ...请看证明: 由于莫比乌斯函数具有性质∑i|nμ(i)=[n=1]∑i|nμ(i)=[n=1]\...
  • 莫比乌斯反演公式 Möbius inversion formula
  • 拉格朗日反演证明

    2019-04-04 06:53:00
    那么这也就证明出了拉格朗日反演中的定理: \[[x^n] G(x) = [x^{-1}] {1\over n} {1\over F^n(x) }\] 然后我们让 f(x) 表示 F(x) 除去 x 后的多项式,那么原本的答案就是: \[[x^n] G(x) = [x^{n-1}] {1\over ...
  • 二项式反演证明

    2018-01-31 11:48:41
    式一、 an=∑i=0n(ni)bi⇒bn=∑i=0n(−1)n−i(ni)aian=∑i=0n(ni)bi⇒bn=∑i=0n(−1)n−i(ni)aia_n=\sum\limits_{i=0}^n{n\choose i}b_i \Rightarrow b_n=\sum\limits_{i=...证明:   &nbsp...
  • 定义,求法,打表及反演定理在这篇博客进行了介绍 给出两个反演公式 f(n)=∑d∣ng(d)⟺g(n)=∑d∣nμ(d)f(nd)(1)f(n)=\sum_{d|n}g(d)\Longleftrightarrow g(n)=\sum_{d|n}\mu(d)f(\frac{n}{d})\tag1f(n)=d∣n∑​g(d)...
  • 莫比乌斯反演

    2019-02-14 15:35:00
    莫比乌斯反演定理 证明:$$f(n) = \sum_{d|n} \mu(d) F(\lfloor \frac{n}{d} \rfloor) = \sum_{d|n} \mu(d) \sum_{k|\frac{n}{d}}f(k) = \sum_{k|n}f(k) \sum_{d|\frac{n}{k}} \mu(d)$$  由上面的性质1可知,当...
  • 莫比乌斯反演题目

    2019-05-03 21:01:47
    莫比乌斯反演定理两种形式的证明 目录 1.luogoP2568GCD 2.luoguP2257 YY的GCD 1.luogoP2568 GCD 题目链接 莫比乌斯反演的入门题。 思路: 设 代码: #include<iostream> #...
  • 终于讲到反演定理了,反演定理这种东西记一下公式就好了,反正我是证明不出来的~(~o ̄▽ ̄)~o 首先,著名的反演公式 我先简单的写一下o( ̄ヘ ̄*o) 比如下面这个公式 f(n) = g(1) + g(2) + g(3) ...
  • 近期学习了莫比乌斯反演,算是一个学习笔记吧… 在这里首先要说明: 1:本文讨论的所有函数为数论函数,即定义域为D=N∗D=N^*D=N∗的函数; 2:∑d∣nf(d)\sum \limits_{d|n}f(d)d∣n∑​f(d)表示ddd取遍nnn的...
  • 莫比乌斯反演定理

    2018-06-02 19:11:56
    [toc] // 先挖坑,有空填 莫比乌斯反演定理 百度百科 我感觉百度百科就讲的不错
  • Mobius反演定理-BZOJ2154

    2017-03-14 20:13:00
    This article is made by Jason-Cow.Welcome to reprint.But please post the article's address....莫比乌斯定理(未完待续......): 形式1: 形式2: 引理: 证明1: 右边=带入左边等式,得  ...
  • 隐函数存在定理 证明

    2010-09-26 10:23:50
    隐函数存在定理 隐函数微分法一个方程一个自变量的情形
  • 二项式反演又名广义容斥定理。 下次再看题解时要注意了。 解锁新姿势。 说白了就是之前会的姿势太少了。 正题: 说白了就是有这样两条恒等的式子: f n = ∑ i = 0 n ( − 1 ) i C n i g i ⟺ g n = ...
  • 莫比乌斯反演定理推导 ∑ d | n μ ( d ) F ( n d ) = ∑ d | n μ ( d ) ∑ k | n d f ( k ) \sum_{d|n}{μ(d)F({n \over d})}=\sum_{d|n}{μ(d)}\sum_{k|{n\over d}}{f(k)} ∑ d | n μ ( d ) ∑ k | n d f...
  • 拉格朗日反演

    2018-09-24 16:45:00
    拉格朗日反演定理 如果生成函数\(A(z)\)满足函数方程\(z=f(A(z))\),其中\(f(z)\)满足\(f(0)=0\),且\(f’(0) \neq 0\),则\[a_n = [z^n]A(z) = \frac{1}{n}[u^{n-1}](\frac{u}{f(u)})^n\] \[[z^n](A(z))^m = \frac{m}...
  • 话说好久没写博客了~~ 不久前一道考试题暴露了数学渣渣的本质: ... 二项式定理(不会)-> 善用搜索引擎 -> 杨辉三角(打个表找规律终于会了) 今天又有一道数学题,想骗个分结果exgcd不会写...
  • 莫比乌斯函数和反演定理的理解

    千次阅读 2016-08-30 09:34:41
    现在就谈谈莫比乌斯函数的性质和反演定理的理解。 首先定义 u(x)u(x) 为莫比乌斯函数。他有以下性质: 1.∑d|mu(x)=[m==1]\sum\limits_{d|m} u(x) = [m == 1] 其中m == 1 指m == 1 的逻辑值,也就是如果m == 1 则...
  • 圆的反演数学证明

    2019-08-03 14:27:37
    点的反演: 本质上是点与点的映射。 是一个点(x,y)(x,y)(x,y)根据另一个定点(a,b)(a,b)(a,b)(一般取原点)和一个常数kkk,进行变换得到一个新点(x′,y′)(x&#x27;,y&#x27;)(x′,y′),满足(x,y),(x′,y′),...
  • Mobius反演(莫比乌斯反演

    千次阅读 2018-07-16 16:00:36
    有了上面的知识,现在我们来证明莫比乌斯反演定理证明 证明完毕! 嗯,有了莫比乌斯反演,很多问题都可以简化了,接下来我们来看看莫比乌斯反演在数论中如何简化运算的。 题目:...
  • 莫比乌斯反演定理 定理 存在 f(x)f(x)f(x) 和 g(x)g(x)g(x) 是定义在非负整数域的函数,并且满足 f(n)=∑d∣ng(d)f(n) = \sum_{d|n}g(d)f(n)=d∣n∑​g(d) 式子等价于 g(n)=∑d∣nμ(d)f(⌊nd⌋)g(n) = \sum_{d|n}\...
  • 莫比乌斯反演也是反演定理的一种 既然我们已经学了二项式反演定理 那莫比乌斯反演定理与二项式反演定理一样,不求甚解,只求会用 莫比乌斯反演长下面这个样子(=・ω・=) d|n,表示n能够整除d,也...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,761
精华内容 704
关键字:

反演定理证明