当前课程知识点:组合数学 >  容斥原理和鸽巢原理 >  容斥原理的精妙 >  容斥原理的应用(3)

返回《组合数学》慕课在线视频课程列表

容斥原理的应用(3)在线视频

容斥原理的应用(3)

下一节:容斥原理的应用(4)

返回《组合数学》慕课在线视频列表

容斥原理的应用(3)课程教案、知识点、字幕

那么接下来呢

我们来研究一个

在数论里面

非常重要的概念

也就称之为是欧拉函数

所谓欧拉函数呢

实际上就表示的是

对于欧拉函数Fn

他是求小于N

而且和N互数的数的个数

我们来举个例子

比如说

要求欧拉函数8

意味着小于8

而且与8互数的数有几个

我们看

8实际上它只有一个因子

就是2

因此呢

在小于8的范围内

和8互数的无非就是

1 3 5 7

所以欧拉函数8等于4

这个欧拉函数实际上

在计算机界非常有用

比如说我们大家都熟知的

isa的公钥密码

算法就是以

欧拉函数为基础的

提起欧拉

大家对这张照片

肯定非常熟悉了

几乎每一个章节我们

都会看到他出现在这里

实际上

在这里真的想要和大家

分享一下欧拉的生平

可以说

欧拉奠基了整个现代数学

欧拉实在太牛了

多次我提到

他跟一些友人的通信

就开创了一些

非常引人入胜的数学领域

而他呢

自己又具备了非常强大的

计算能力

有人就曾经说

欧拉计算起来

简直毫不费力

就好像人在呼吸一样

所以他是历史上

最多常用的数学家之一

要知道

俄罗斯的圣彼得堡学院

为了整理他的手稿

整整花费了47年

要知道他有多么高效吗

他曾经也就是

吃晚饭的半个小时

就可以写出一篇

高水平论文

他曾经一度是

全世界发表论文

最多的数学家

总共加起来一共有75卷

直到后来

被保罗爱尔德使

打破了这个记录

但是

回首他的整个生平

其实是非常多灾多难的

大家看一下他的照片

会发现

实际上他的眼睛有一只

是完全是失明的

而且同时

在他正当当年的时候

最多产的时候

他经历了一场大火

几乎把他所有的手稿

全部烧光了

就凭着他惊人的记忆力

他在短短的几年之间

把他所有的论文全部恢复

而他的死更加的神奇

1783年9月18日

在他77岁的时候

他正在演算天王星的轨道

喝着茶

和他的孩子进行玩耍的时候

突然之间

他手中的烟斗掉在了地上

说了他人生中最后一句话

我要死了

从此

欧拉停止了计算

这是一个非常传奇的人生

他给我们留下了

实在太多太多的东西了

那么今天呢

我们来介绍以他命名的欧拉函数

具体该怎么计算

提到欧拉函数

实际上是求小于N

而且与N互数的数的个数

这时我们就想

互数的概念意味着没有因子

那么我们就去想

对应于任何一个N

我们能够分解成的

不同的素数的乘积

可以表示为

N等于P1的a一次方

P2的a二次方

直到PK的K次方

其中P1 P2

直到PK全部都是素数

这样的话

要想求和它

素故互数的数的个数

也就意味着对应的

他不应该包函内饰的因子

因此

假设1到N的N个数中

为PI的倍数的集合

分别是AI

那么我们要求的就是

AI的补集交

AJ一直累交过去

他们的个数是多少

这时候

我们要分别单独计算

单个单个集合的个数

对应于AI表示的是从

1到N的个数中

为PI的倍数有多少个

因为PI是N的一个因子

因此N除以PI肯定是

可以整除的

那么AI的个数

就等于N除以PI

每一个I相当于从1一直到K

对应的我们由于PI和PJ

是不相等的

那么AI交AJ就意味着

这里集合的数

应该既是PI的倍数

也是PJ的倍数

而且

PI乘以PJ

也是N的一个因子

因此N除以PIPJ

也是可以整除的

那么两两相交的集合

就等于AI交AJ的集合

等于N除以PIPJ

I和J又分别从1一直到K

因为I不等于J

所以这两个素数是

不相同的

那么

接下来呢

我们来继续求就会发现

我们想要求的欧拉函数

是什么呢

我们想要求的欧拉函数

就是说对应于

既不是P1的倍数

而且不是P2的倍数

一直到不是PK的倍数

就自然而然

这些数字是和N互素的

他的个数就相当于

应用容斥原理

等于全局的个数

减去单个单个集合的个数

刚才单个单个集合的个数

我们已经算出来

就是N除以P1

N除以P2

一直到N除以PK

那么接下来

两两相交的集合呢

两两相交的集合就是

N除以P1P2

N除以P2P3

一直累加到N除以P1PK

接下来

再加再减

再加再减

直到最后一项

是加或者减

N除以P1P2直到PK

这个式子我们

进一步的整理一下

会发现

实际上欧拉函数N就等于

把N提出来之后

进行一些式子的连乘

其中的式子就是1减去1

除以P1

乘以1减去1除以P2

一直累乘到1除以PK

这时候

我们就给了欧拉函数的

一个计算方法

那么利用这样的计算方法

我们来验证一下

比如说刚才提到的

8的欧拉函数

意味着是说

小于8的数中

只有1 3 5 7和它素数

因此

欧拉函数8就应该等于4

若带到上面去看

我们发现

对应于8来说

它只有一个素数因子

也就是2

那么这个式子就应该等于

N乘以1减去1除以P1

P1是2

所以是8乘以1

减去二分之一

刚好等于4

和我们进行枚举的结果

完全一致

如果再大一点呢

比如说60

60我们进行素数的

拆分之后

会发现

他的素数因子就是2 3 5

带到欧拉函数中

60乘以1减去二分之一

1减乘以三分之一

乘以1减五分之一

答案等于16

那么我们是不是

也可以枚举出来

所有的答案呢

我们通过枚举以后

会发现对应于比60小

而且呢和65无公因子

的数呢恰好就是只有16个

我们依次枚举之外

有7 11 13一直到59

另外呢

我们还不要忘掉有一个1

所以我们会发现

实际上欧拉函数告诉我们

一种互为素数的找的方法

而他的个数呢直接

可以通过对应的N乘以1

减去P分之一乘以1

减P2分之一

一直累乘下去就可以

很方便的得到了

组合数学课程列表:

漫谈组合数学

-什么是组合数学

--什么是组合数学

--讨论题

-最精巧的排列——幻方

--幻方

-漫谈组合数学--最精巧的排列——幻方

-苦难的羊皮纸卷

--羊皮纸卷

-苦难的羊皮纸卷--作业

-你的手机密码安全吗

--你的手机密码安全吗

-漫谈组合数学--你的手机密码安全吗

-暴力枚举和抽象转换

--世界杯引出的问题

--世界杯引出的问题--练习

--一一对应

--七桥问题

--小结

--讨论题

-大家谈组合数学(1)

--采访武永卫老师

-第一周作业

--作业说明

--H

--U

--G

--作业讨论区说明

-第一周演示程序

--程序讨论区说明

--幻方生成器

--换方计数

--屏幕解锁方案数

--欧拉路计数

--共享程序

小乒乓球的组合之旅

-加减乘除来计数

--计数的基本法则

-排列还是组合

--排列还是组合

--小乒乓球的组合之旅--排列还是组合

--格路模型与组合恒等式

-各种各样的排列

--圆排列和项链排列

--圆排列和项链排列--习题

--多重排列

--多重排列--练习

-多样的组合

--可重组合

--不相邻组合

--小乒乓球的组合之旅--多样的组合

-钟声里的全排列

--钟声里的全排列

--钟声里的全排列

--字典序法

--SJT算法

--程序支持与Stirling公式

-第二周作业

--H

--U

--G

--思考题

--公式测试

--作业讨论区说明

-第二周演示程序

--程序讨论区说明

--排列数和组合数的计算

--全排列生成

--组合生成器

--共享程序

-参考资料:Stirling估计式

--Stirling估计式

初识母函数

-母函数是函数的母亲吗

--母函数的定义(1)

--母函数的定义(1)--练习

--母函数的定义(2)

--母函数的定义(2)--练习

-母函数的简单应用

--母函数的简单应用(1)

--母函数的简单应用(2)

--初识母函数--母函数的简单应用

-整数拆分

--整数拆分(1)

--整数拆分(2)

-Ferrers图像

--Ferrers图像

--Ferrers图像--作业

-母函数与递推关系

--母函数能做什么

--Hanoi问题(1)

--Hanoi问题(2)

--偶数个5怎样算

--偶数个5怎样算(2)

--母函数小结

-大家谈组合数学(2)

--科研,找工作与组合数学

-第三周作业

--H

--U

--G

--思考题

--作业讨论区说明

-第三周演示程序

--程序讨论区说明

--整数拆分

--汉诺塔

--共享程序说明

线性常系数递推关系

-Fibonacci数列

--Fibonacci兔子

--Fibonacci恒等式

--线性常系数递推关系--Fibonacci数列

-Fibonacci数列的应用

--桌布魔术

--桌布魔术--练习

--Fibonacci的直接表达式

--Fibonacci优选法

--艾略特波浪曲线

-线性常系数齐次递推关系

--定义

--特征多项式

--母函数与特征多项式

--根据特征多项式求解递推关系通解(1)

--根据特征多项式求解递推关系通解(2)

--线性常系数递推关系--线性常系数齐次递推关系

-说“数”解题

--说“数”解题(1)

--说“数”解题(2)

-第四周作业

--H

--U

--G

--GT思考题

--作业讨论区说明

-第四周演示程序

--程序讨论区说明

--Fibonacci优选法

--Fibonacci数值计算

--程序共享说明

-爆笑花絮

--爆笑花絮

-参考资料:K线分析中的Fibonacci 相关理论

--Fibonacci retracement资料

神奇的序列

-Catalan数

--计算机界的精灵

--Catalan数的直接表达式

--Catalan数的各种实例

--神奇的序列--Catalan数

-指数型母函数

--指数型母函数

--指数型母函数的应用

--神奇的序列--指数型母函数

-错排

--错排1

--错排2

--神奇的序列--错排

-Stirling数

--第一类Stirling数

--神奇的序列--Stirling数

--第二类Stirling数

-母函数小结

--母函数小结

-大家谈组合数学(3)

--采访郭家宝(BYVoid)

-第五周作业

--H

--U

--G

--思考题

--作业讨论区说明

-第五周演示程序

--讨论区说明

--Catalan数

--第二类Stirling数

--程序共享

容斥原理和鸽巢原理

-且容且斥

--容斥原理

--容斥原理的证明

--容斥原理和鸽巢原理--且容且斥

-容斥原理的精妙

--容斥原理的应用(1)

--容斥原理的应用(2)

--容斥原理的应用(3)

-回忆过去,容斥新解

--容斥原理的应用(4)

--容斥原理的应用(5)

--容斥原理的应用(6)

--容斥原理和鸽巢原理--回忆过去,容斥新解

-鸽子抢巢

--鸽巢原理

--鸽巢原理--练习

--鸽巢原理的应用(1)

--鸽巢原理的应用(1)--练习

-看得见摸得着的鸽巢

--鸽巢原理的应用(2)

--韩信点兵

--中国剩余定理

--容斥原理和鸽巢原理--看得见摸得着的鸽巢

-6人行和Ramsey数

--6人行

--Ramsey数

--小结

-第六周作业

--H

--U

--G

--GT

--作业讨论区说明

-第六周演示程序

--讨论区说明

--Find a multiple

--程序共享说明

-可以转的世界

--可以转的世界

--可以转的世界--练习

--伽罗华与群

--群的定义

--群的定义--练习

--群的一些概念

-置换群

--置换群

--群--置换群

--共轭类

--对换

--对换--练习

--置换群的应用

-Burnside引理

--着色问题的等价类

--Burnside引理--作业

--Burnside引理

--Burnside引理的应用

-闲话群

--无处不在的群(1)

--无处不在的群(2)

-第七周作业

--H

--U

--G

--作业讨论区说明

Polya定理

-Burnside引理的困境

--Burnside引理的困境(1)

--Burnside引理的困境(2)

-从Burnside到Polya

--Polya定理

--Polya定理的应用(1)

--Polya定理的应用(2)

-立方体旋转

--立方体旋转(1)

--立方体旋转(2)

--立方体旋转--作业

--立方体旋转(3)

--立方体旋转--作业

--立方体旋转(4)

-母函数型Polya定理

--母函数型Polya定理(1)

--母函数型Polya定理(2)

--母函数型Polya定理(3)

--母函数型Polya定理(4)

--Polya定理--母函数型Polya定理

-图的计数

--图的计数

-总结

--本章小结

-第八周作业

--H

--U

--G

--GT

--作业讨论区说明

-大家谈组合数学(4)

--采访黄连生老师

组合之美

-组合之美

--组合之美之计数

--组合之美之排列组合

--组合之美之多样组合和全排列

-组合之美之线性常系数递推关系

--组合之美之线性常系数递推关系

-组合之美之多样的序列

--组合之美之多样的序列

-组合之美之鸽巢原理

--组合之美之鸽巢原理

-组合之美之转动群与染色

--组合之美之转动群与染色

-采访邹欣

--采访邹欣1

--采访邹欣2

-知识点串串烧

--知识点串串烧

期末测验

-期末测验--期末测验

容斥原理的应用(3)笔记与讨论

也许你还感兴趣的课程:

© 柠檬大学-慕课导航 课程版权归原始院校所有,
本网站仅通过互联网进行慕课课程索引,不提供在线课程学习和视频,请同学们点击报名到课程提供网站进行学习。