当前课程知识点:组合数学 > 初识母函数 > 整数拆分 > 整数拆分(2)
无序拆分数是一个非常有用的问题
它经常被用在密码学经济学和生物学中
对于这个拆分数我们通常用p(n)来表示
也就是说对于正整数n
把它拆分成若干个正整数的和
允许重复 而且数字顺序无关的话
我们就用p(n)来表示一共有多少种不同的拆分
举例 拿3为例
实际上p(3)就等于3
因为它只有3种无序拆分
举个简单的应用
对于我们来说经常用到服务器
那么服务器假如说有三台服务器的话
你要怎么去应用它呢
这就是一个典型的整数拆分问题
我是三个一块用还是说两个一起
另外一个单独用
或者我们三个分别使用
有了这样一个问题以后 我们看看
是谁最先发现了这样的一个问题和解法
实际上仍然回顾到欧拉时代
那个时候很多数学家都愿意和欧拉保持通信
其中有一位叫作诺地的先生
他有一次在通信中就写到
请问欧拉先生
您是否研究过整数拆分数问题呢
欧拉特别厉害 他当时并不知道什么叫母函数
他也没有这种计数的概念
但是他给了一个答案
他说整数拆分方案数
实际上就等于1加x加x的平方
累乘1加x的平方 加x的4次方
一直累乘到1加x的m次方
依次累乘中 x的n次方的系数
我们回头看欧拉的答案是什么意思呢
他要将一个整数n拆分成若干个1
若干个2 若干个3
那我首先看
1在这里如果用母函数来表示的话
它可以说1不出现
或者用x表示它出现一次
x的平方表示1出现两次
所以欧拉答案中第一项
就是对应的1的出现母函数
对于2来说也是一样啊
有可能2不出现
或者x的平方表示2出现一次
或者x的4次方表示2出现两次
依此类推
那对应的展开式中
x的n次方的系数就意味着n拆分成
若干个1 若干个2 一直到若干个m
有多少种不同的组合方式
整数拆分数作为一个非常有用的序列
实际上呢它已经被权威的数据库OEIS
列为第四十一号序列
说起OEIS实际上和我们组合数学非常相关
因为OEIS它的全称呢
实际上就是有关数学序列的一个权威数据库
那么我们说到的排列 组合 全排列等等
若干个序列都可以在OEIS上找到相应的解析
和它们的最新发展
所以同学们如果有兴趣的话
可以经常到OEIS上去发现一些问题
那么我们又回头再说起来这个整数拆分
整数拆分我们刚才说到了
对应于欧拉的方法
它实际上就用了若干个多项式相乘
求系数的方法来计算整数拆分数
当年可是十八世纪呀
欧拉用这个方法算出了第49位
也就是说
他算出了49可以拆分成多少个整数之和
有人就评价说
欧拉的方法确实精妙
但是并不一定是计算整数拆分数
最有效的方法
后来呢 有些人又用一些递归的方法
将整数拆分数做到了更大的一点
但是人们始终发现
非常非常的困难
尤其是欧拉的方法
它的瓶颈在哪里呢
大家回头看
在欧拉的方法中
他实际上依赖了很多的多项式乘法
要知道在欧拉的时候
是没有计算机的
连计算器都没有
所以即便像欧拉那样记忆力超凡的人
他的计算能力那么强
也只算到了第49位
随后将近两百年过去了
才有一位神奇的数学家拉马努金
将这个数字推到了200
他用的方法并不是欧拉的方法
他用了一种模式的方法
算出了p(200)是等于这个的
说到拉马努金啊
我们确实想花一点时间跟大家一起分享一下
拉马努金被称为是印度之子
有人这样评价他
说拉马努金是数学史
甚至是科学史上最奇怪的人
为什么这么说呢
拉马努金没有上过大学
他甚至没有经过正式的数学教育
但是他就凭借他的数学直觉
独立发现了
将近三千九百多个数学公式和命题
而且他把他的思想都写在了三大笔记本里面
这三个笔记本现在被大家视为数学界的盛典
其中有一位数学家就是因为证明了拉马努金
在1916年提出了一个猜想
所以在1973年的时候获得了菲尔兹奖
拉马努金非常的奇怪
他认为他所有的思想都是天神赐予的
而且他不写证明
他在他的笔记里面写了很多很多的命题
他认为是对的
所以他直接写在上面 没有任何的分析
经过了若干年之后
直到现在人们才发现
他上面的定理命题都是正确的
尤其在2012年的时候
有一位美国的著名的数学家和他的同事
证明了在拉马努金弥留之际
留下的一个神奇的函数
这个函数拉马努金的命题是正确的
他和我们宇宙黑洞的奥秘是直接相关
所以可以看到拉马努金
这样一个神奇的人物开创了数学
甚至现在给我们遗留了很多很多未知的问题
甚至美国佛罗里达大学还专门创办了一个
叫做拉马努金期刊
专门发表由这三大笔记
影响出来的数学领域的研究
所以可想而知 拉马努金当时利用模式的方法
把整数拆分数推到了p(200)
一度人们认为整数拆分数就到此为止了
不太可能再有更大的数字出现了
但是现在我们查一下OES
p(300)赫然在上面
甚至还有更多 这是为什么呢
大家可以想象其实是什么出现了
因为我们有了计算机
我们有了算法
对于欧拉的瓶颈 多项式乘法的手工计算
对我们根本不是问题了
所以我们可以来分析一下
如果让计算机来做欧拉的整数拆分数
该怎么做呢
所以我们要分析一下怎么用计算机
来实现母函数相乘
在这里G(x)可以等于1加x 加x的平方
累乘于1加x 平方 x的4次方
依此累乘下去
因为计算机它肯定不可能做到同时相乘
所以它是两两进行的局部相乘
首先我们来分析一下
先是头两个多项式进行相乘
这个里面实际上
就相当于我们要进行一个系数的卷积
假设系数分别放入数组f(k)和g(k)中
只要我们计算它的系数卷积
就可以得到一个新的多项式
之后新的多项式再和下一个多项式
进行进一步的累乘
依此类推下去
我们就可以不用利用手工计算
而利用计算机的方法
逐步循环得到多项式乘法的结果
我们编写了一个程序
来实现了一个多项式乘法的母函数算法演示
大家想拆分多大的数呢
比如说我们先算一个小的
也就是欧拉计算的49
它可以很快地计算出来
大家觉得最大能够拆分到多少呢
比如说我们试试拉马努金的200
也没有问题 300也没有问题
下面能不能更大呢
我们算一下416
P(416) 等于这么大一个数字
我可不可以更大一些呢
比如说417
我们发现这时候有问题了
它提示说计算417次幂的系数时
结果溢出了
大家一定觉得奇怪
为什么计算机来算整数拆分数
算到417就算不下去了呢
我们来分析一下
其实现在的计算机
也就是最多能够表示的整数位数是64位
那么它的具体范围呢是这么大
如果我们查一下
416对应的拆分数是这么大
最后只要稍微增加一位 变成417的话
它就已经远远超过了整数的最大表示范围
所以我们可以看到
即便有了计算机
如果用传统的普通方法来实现的话
多项式乘法的母函数方法也只能算到p(416)
那么瓶颈在哪里呢
实际上我们会发现真正的瓶颈
在于我们如何处理大数相乘
只要能够保证有一个更好的表示方法的话
我们可以做更大数字的整数拆分数
那么大家就会想
那现在到底能拆分到多大了呢
我们在OES这儿查到的最新的数据表明
它可以处理1000万的整数拆分数
这个数据实际上来之不易
不仅仅要求大家
去处理大型数字的乘法和加法
同时呢也需要使用一些模式的方法
其实整数拆分数到现在
仍然是一个非常活跃的学科
和它相关的有一个猜想
被列为是世界数学界十大问题之一
甚至有100万的奖金
如果你能够破解这样的问题的话
你将获得100万美元的奖金
那么同学们我想问问大家
如果你尝试之后
能够自己解开的最大的整数拆分数是多少呢
我们回顾一下母函数的定义的发展历史
会发现其实在1705年的时候
伯努利首先去研究了掷色子的问题
但是他并没有把它真正的形式化成某种形式
直到他的学生欧拉去研究了整数拆分数
虽然他已经给出了母函数形成的答案
但他仍然没有给出母函数的形式
直到100年之后
才有拉普拉斯把这个理论形式化
定义出了母函数这样的定义
所以我们可以看到
一个思想的发现并不是显而易见的
即便是我已经接触到它了
但也未必能够形成一个抽象的概念
最终还是由拉普拉斯总结了一百年之内
人们的工作
把母函数定义做成了这三行字
回头在看这三行字的背后
其实蕴含很多的思想
可以说我们和函数相比较
母函数和函数完全是不同的概念
不同的思维
它似函数 但是非函数
真正它是什么呢
它实际上是数学上非常有用的一种思想
就是映射
其实如果大家学了组合数学以后
会发现在很多地方
我们都要用到映射的思维
这种思维的引导下
能让我们去发现很多不一样的东西
-什么是组合数学
--什么是组合数学
--讨论题
-最精巧的排列——幻方
--幻方
-漫谈组合数学--最精巧的排列——幻方
-苦难的羊皮纸卷
--羊皮纸卷
-苦难的羊皮纸卷--作业
-你的手机密码安全吗
-漫谈组合数学--你的手机密码安全吗
-暴力枚举和抽象转换
--世界杯引出的问题
--世界杯引出的问题--练习
--一一对应
--七桥问题
--小结
--讨论题
-大家谈组合数学(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
-知识点串串烧
--知识点串串烧
-期末测验--期末测验