当前课程知识点:组合数学 > 线性常系数递推关系 > Fibonacci数列 > Fibonacci兔子
很高兴能和大家再次相聚
一起学习组合数学
要说起组合数学里面我最喜欢什么
我会毫不犹豫地说
就是斐波那契数
斐波那契数实在太神奇了
它的故事实际上是从一群兔子开始的
在第一个月两只小兔子相遇了
一雄一雌
在第二个月它们结婚了
第三个月它们生出了小兔子
而这生出来的小兔子也恰巧是两只
一雄一雌
而且这些兔子非常神奇
它们永生不死
那么请问你
如果在第五十个月
这兔子能达到多少只呢
这就是最有名的斐波那契兔子问题
那我们来分析一下
它到底怎么去计算呢
比如说我们来看
在第一个月的时候
两只兔子相遇了
而第二个月它们只是结婚了
所以个数没有发生变化
仍然是2只兔子
但是到了第三个月
因为它们生了小baby
所以现在变成了4只兔子
一共两对兔子
那么接下来它们的兔子照样可以成长
照样可以去结婚生子
所以在后面呢 我们会发现
每只兔子一旦成熟之后
它在下一个月都会生两只一雄一雌的兔子
而新生出来的兔子呢
它下一个月才慢慢成熟
直到下下个月才会生出新的兔子
那么我们分析一下
如说第四个月该多少只兔子呢
这时候我们发现
实际上有一部分兔子就来源于最老的那只兔子
它自己活下来了
同时它又新生了一对兔子
而这边呢
刚才第三个月的兔子呢
它又持续活到了第四个月
接着依次往复
所以我们会发现
每一个月的兔子来源于两个部分
一部分是上一个月的兔子依然在下个月活着
而另外一部分呢
是这个月新生出来的兔子
而新生的兔子
和什么数量相等呢
正好是在上上个月的兔子
这个月都会生小兔子
所以兔子的含量实际上包括两部分
一个部分也就是n减1个月它有多少只兔子
另外一部分来源于它的上上个月
也就是n减2个月有多少只兔子
这我们就列出了斐波那契兔子的一个递推公式
也就是说我们要求第n个月一共会有多少只兔子
用fn来表示的话
那么fn就等于fn减1加上fn减2
所以我们来看斐波那契序列
实际上斐波那契序列中第一个数就是1
第二个数呢
仍然是1
第三个数等于前面两个数之和
1加1等于2
接着往下
1加2等于3
2加3等于5
因此 我们就可以通过递推关系得到斐波那契数列
它的递推关系就是fn等于fn减1加上fn减2
一般情况下
我们认为为了能够算出f0的话
这里面的n应该大于等于2
那么除了它的关系之外
我们还需要递推式的初始值
这里面我们可以看到
如果要计算n等于2的时候
我们需要一个数值
f0
f0实际上等于0
因此在原来序列中
我们一定要注意
1、1、2、3、5是从1开始算起的
但是其实前面还有一个f0
也就是0
第二个数字呢
就应该是f1等于1
因此对于递推关系斐波那契数列来说
的初始值就是f0等于0
和f1等于1
这个序列非常重要
在我们经常提到的OEIS数据库中
它被列为是第45号序列
为什么它被称为是斐波那契数列呢
当然它和斐波那契密不可分
斐波那契
实际上是意大利的一位学者
它的本名并不叫斐波那契
斐波那契只是他的小名
他的真名实际上叫做
Leonardo of Pisa
可以看到
他就是意大利的比萨市的人
而他呢
实际上(呢)这个问题
也不是他始作俑者(始作俑者的感情色彩。。。)
在1105年的时候
印度学者就已经研究了长度为1
和长度为2的小方块
累加在一起摆成一条路的话
会有多少种不同的方案
实际上这就是
斐波那契最早的原形
而真正把它发扬光大的
就是Leonardo of Pisa
他做了什么呢
实际上他写的一本书
在1202年的时候
他写的一本叫做
《算盘全书》的书
这本书第一次
向西方世界
给大家介绍了东方数学的魅力
所以有人也说到
说除了希腊数学之外
西方的数学大部分都源于
斐波那契
而斐波那契
为什么有这样的机会
能够去东方学数学呢
离不开他的家族背景
他的父亲
实际上就是在
Leonardo of Pisa他二十二岁的时候
带着他一块去了
东方 印度 阿拉伯
所以在那里
他能够有机会接触到
东方的数学
尤其是印度的数学
而他回到了意大利之后
把这些发扬光大
所以我们可以看到
其实东西合璧
才是真正数学走的一条必经之路
说到这里呢
我们回头再看
为什么我说斐波那契数太神奇了
大家一定还很熟悉
我们的杨辉三角吧
而斐波那契数列
和杨辉三角密不可分
以往我们总是两两的去加
这样杨辉三角的数字
如果我们把它
斜着一条一条加过来的话
发现每一条线的和
正好就是斐波那契数
而斐波那契数
是自然界的秘密法则
我们看一颗树
一颗树成长起来以后
它就会分枝开叶
它会分成不同的枝条
而它的枝条数目
一定是满足斐波那契数列的
也就是
1、2、3、5、8依次向上
我们再看那些花朵
你去找世界上所有的花朵
它的花瓣数目
一定是斐波那契数
学术界为了探究
斐波那契数列的秘密
在1963年
专门设立了一个刊物
就叫做TheFibonacci Quarterly
专门刊登
这个序列发现的新研究
它太神奇了
在数学上
有很多意想不到的结果
会发现
它的每一位数字
在每六十位会重复
而最后的两位数字
每三百位都会重复
每三位数字
到了一千五百个
就会不断重复
而这样的pattern
会不断地循环往复
而同时我们会发现
在斐波那契序列中
每三个数
就可以被2整除
而每第四个数
就可以被3整除
每第五个数可以被5整除
每第六个数可以被8整除
而这些除数
同样是斐波那契序列的
那么说到整除
自然大家就想
那有没有素数呢
实际上一个非常神秘的数字
被称为是Fibonacci prime
大家知道
素数是我们数论中一颗奇葩
而斐波那契又是那么有魅力
它们两个既然可以结合在一起
什么叫做Fibonacci prime
也就是说在斐波那契数列中
有多少个素数我拿出来
就可以构成一个序列
这个序列在OEIS中
被列为是5478号
而我们可以看到
除了n等于4这个序号之外
所有的斐波那契素数
序号都是素数
但是反过来
并不是所有序号
都是素数的斐波那契数
都是素数
这时候大家就会想了
那么在斐波那契数中
到底有多少个素数呢
会不会随着斐波那契
无穷地涨下去
它的素数
也会无穷地增加呢
到目前为止
这样一个想法仍然是猜想
没有得到证明
而我们已经找到的
最大的素数
实际上它也是斐波那契数
它的位数
已经达到了
17103位
所以可以看到
研究斐波那契数
实际上也帮我们找到了一个途径
去研究素数
看到斐波那契数
有这么多美丽的性质
我们自然就想一想
数学上
它会有什么样不同的表现呢
下一节
我们来分析斐波那契数的数学表现
-什么是组合数学
--什么是组合数学
--讨论题
-最精巧的排列——幻方
--幻方
-漫谈组合数学--最精巧的排列——幻方
-苦难的羊皮纸卷
--羊皮纸卷
-苦难的羊皮纸卷--作业
-你的手机密码安全吗
-漫谈组合数学--你的手机密码安全吗
-暴力枚举和抽象转换
--世界杯引出的问题
--世界杯引出的问题--练习
--一一对应
--七桥问题
--小结
--讨论题
-大家谈组合数学(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
-知识点串串烧
--知识点串串烧
-期末测验--期末测验