当前课程知识点:组合数学 > 容斥原理和鸽巢原理 > 容斥原理的精妙 > 容斥原理的应用(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算法
-第二周作业
--H
--U
--G
--思考题
--公式测试
--作业讨论区说明
-第二周演示程序
--程序讨论区说明
--全排列生成
--组合生成器
--共享程序
-参考资料:Stirling估计式
-母函数是函数的母亲吗
--母函数的定义(1)--练习
--母函数的定义(2)--练习
-母函数的简单应用
--初识母函数--母函数的简单应用
-整数拆分
--整数拆分(1)
--整数拆分(2)
-Ferrers图像
--Ferrers图像--作业
-母函数与递推关系
--母函数能做什么
--偶数个5怎样算
--母函数小结
-大家谈组合数学(2)
-第三周作业
--H
--U
--G
--思考题
--作业讨论区说明
-第三周演示程序
--程序讨论区说明
--整数拆分
--汉诺塔
--共享程序说明
-Fibonacci数列
--线性常系数递推关系--Fibonacci数列
-Fibonacci数列的应用
--桌布魔术
--桌布魔术--练习
--艾略特波浪曲线
-线性常系数齐次递推关系
--定义
--特征多项式
--线性常系数递推关系--线性常系数齐次递推关系
-说“数”解题
-第四周作业
--H
--U
--G
--GT思考题
--作业讨论区说明
-第四周演示程序
--程序讨论区说明
--程序共享说明
-爆笑花絮
--爆笑花絮
-参考资料:K线分析中的Fibonacci 相关理论
-Catalan数
--计算机界的精灵
--神奇的序列--Catalan数
-指数型母函数
--指数型母函数
--神奇的序列--指数型母函数
-错排
--错排1
--错排2
--神奇的序列--错排
-Stirling数
--神奇的序列--Stirling数
-母函数小结
--母函数小结
-大家谈组合数学(3)
-第五周作业
--H
--U
--G
--思考题
--作业讨论区说明
-第五周演示程序
--讨论区说明
--Catalan数
--程序共享
-且容且斥
--容斥原理
--容斥原理的证明
--容斥原理和鸽巢原理--且容且斥
-容斥原理的精妙
-回忆过去,容斥新解
--容斥原理和鸽巢原理--回忆过去,容斥新解
-鸽子抢巢
--鸽巢原理
--鸽巢原理--练习
--鸽巢原理的应用(1)--练习
-看得见摸得着的鸽巢
--韩信点兵
--中国剩余定理
--容斥原理和鸽巢原理--看得见摸得着的鸽巢
-6人行和Ramsey数
--6人行
--Ramsey数
--小结
-第六周作业
--H
--U
--G
--GT
--作业讨论区说明
-第六周演示程序
--讨论区说明
--程序共享说明
-可以转的世界
--可以转的世界
--可以转的世界--练习
--伽罗华与群
--群的定义
--群的定义--练习
--群的一些概念
-置换群
--置换群
--群--置换群
--共轭类
--对换
--对换--练习
--置换群的应用
-Burnside引理
--着色问题的等价类
--Burnside引理--作业
-闲话群
-第七周作业
--H
--U
--G
--作业讨论区说明
-Burnside引理的困境
-从Burnside到Polya
--Polya定理
-立方体旋转
--立方体旋转(1)
--立方体旋转(2)
--立方体旋转--作业
--立方体旋转(3)
--立方体旋转--作业
--立方体旋转(4)
-母函数型Polya定理
--Polya定理--母函数型Polya定理
-图的计数
--图的计数
-总结
--本章小结
-第八周作业
--H
--U
--G
--GT
--作业讨论区说明
-大家谈组合数学(4)
--采访黄连生老师
-组合之美
--组合之美之计数
-组合之美之线性常系数递推关系
-组合之美之多样的序列
-组合之美之鸽巢原理
-组合之美之转动群与染色
-采访邹欣
--采访邹欣1
--采访邹欣2
-知识点串串烧
--知识点串串烧
-期末测验--期末测验