当前课程知识点:组合数学 > 神奇的序列 > Catalan数 > 计算机界的精灵
同学们好
这周我们继续来学习组合数学
这一周我们会给大家介绍一些
神奇的序列
可能有同学就会说了
诶 上一周我们不是学习了
斐波那契数列吗
确实
如果说斐波那契数列蕴含着
自然界的神秘的法则的话
那么今天我给大家介绍一个序列
它被称为是计算机界的精灵
它叫做什么呢
它就叫卡特兰数
为什么说是卡特兰数
是计算机界的的精灵呢
我们来举一个例子
大家都知道在计算机中
很常用的一种术语结构
就被称为 栈
栈 长什么样子呢
它就好像是一段的存储空间
但是这个存储空间呢
只能从上面进进出出
所以每次放数据和取数据
都必须在顶端进行操作
有了这样一个规定的话
我们就会考虑一个问题
如果我有一个无穷大的栈
它的入栈顺序已经确定了
就是从1一直到n
那么它有多少种不同的出栈顺利呢
这个问题我们拿一个
比较简单的例子来看
比如说就是4个元素1 2 3 4的话
它们依次入栈出栈
会有什么样的不同顺序呢
我们举个例子
比如说对于1 2 3 4来说
它可以1先入栈
然后1在栈底
接着2又入栈了
2这时候要拿出去用
所以2必须先出栈
1接着又要用到了
所以1也被出栈了
这时候我们发现实际上
我们已经有了部分的出栈顺序
也就是2先出
然后1再先出
那么接着3如果入栈的话
3同时又被使用了
这时候3也出栈
也可以4入栈
然后4出栈
这时候我们给了一个例子
这个例子就告诉大家4个元素
1 2 3 4
可以有这样一种的出栈顺序
也就是2出
1出
3出
4出
那么对应于不同的情况
到底有多少种不同的出栈顺序呢
我们来分析一下
实际上我们看
既然我们想要用递推关系来
表达的话
是不是可以把一个出栈问题
变成若干个小问题呢
我们有这样一个思路
是不是可以来看
它第一次出栈为空的时候
进行分步计算呢
还是拿刚才的例子看
我们看到了1入栈之后
2入栈了
接着2出去
然后1也出去了
这时候栈里面一个元素也没有
它第一次从有东西
变成了一个空的栈
那么我们拿这个作为时间点的话
会发现实际上
我们这时候就把出栈
变成了两个出栈问题
一部分出栈问题是
1和2进去了又出来
剩下的问题是3和4
依次要进去和出来
这时候我们就把原来的
出栈问题划分成了
两个小的出栈问题
那么怎么来分析
这样一个更小的问题呢
我们会发现第一次它变为空的时候
假设我们已经处理了
K个元素的出栈的话
那意味着这个最先进入的1
它的序号就正好是K
那意味着1这个序号
我们不考虑的话
剩下的前面一部分
应该是K减1个元素进去了
又出来
那么还剩下另外一个问题
比如说这里我们在栈的外面
还没有进栈的那些元素
它应该有多少个呢
它的个数刚好就是从K加1
一直到n
所以它们的元素应该有k个元素
这时候我们就分析了
对于一个k标志着
在第一次为空的时候
一共已经处理了k的元素
的出栈和入栈的话
那么它就把问题划分成
两个小部分了
抛掉这个第一个元素之外
我们会发现第一部分
我们实际上处理的是k减1个元素
而第二部分
我们刚好处理的是n减k个元素
那这时候我们就可以
比如说用fn来表示
一共有多少种出栈序列的话
对应于给定的k
fn就等于fk减1乘以fk减1
乘以fn减k
对应于不同的k的取值
k可以从0一直取到n减1
那么我们就可以写出来fn的等式
就是fn可以等于f0乘以fn减1
加上f1乘以fn减2
依次类推
直到最后一项fn减1乘以f0
这时候我们就得到了
对于出栈顺序的一个递推关系
刚才我们对栈进行了分析
其实在数理结构中
还有一个东西和它也是对应的
我们来看
这是一个二叉树
那么我们就可以分析对于
n个结点构成的一个二叉树
能有多少种不同的构造呢
这个问题我们同样也可以
采用将它进行分布的思路进行递推
比如说对于这样一棵树来说
我们可以拿它的根结点来进行划分
对应于根结点
它把一棵树划分成左边和右边
那左边到底有多少个结点
右边到底有多少个结点
就将原来的一个整棵二叉树
变成了左部分和右部分
利用乘法法则同样
可以把它进行递推关系
所以我们如果用t来表示
比如说tij表示
对应于从根结点来划分
划分之后左边有i个结点
右边有j个结点
那对应的我们就会知道
所有树的构形无非就是
t0n减1 t1n减2
依次类推
那么如果对应于每个构形的话
我们把它认为n个结点
构成的二叉树一共有fn个的话
那fn自然也得到了一个递推关系
等于f0乘以fn减1
加上f1乘以f减2
一直累加到fn减1乘以f0
这个式子和刚才我们递推出来的
栈的关系是一模一样的
那么有了这样一个递推关系
我们同样可以设它的初始值
假设f0等于1的话
那么我们依次可以得到f1 f2和f3
所以有了这样一个递推关系我们发现
它在计算机界非常有用
而这个关系代表的数字
就被称为是卡特兰数
当然卡特兰并不是第一个
提出这个数字的
在1751年的时候
欧拉就研究过这个问题
要知道欧拉一直和数学家们
保持着通信
尤其非常有名的是他和
哥德巴赫保持了若干年的通信
在他们通信中就有赫赫有名的
哥德巴赫猜想
而除了哥德巴赫猜想之外
欧拉还曾经写信给哥德巴赫
他说我想研究正n边形划分成
不同不重叠的三角形有多少种方法
这个问题实际上我们来看
如果对应于一个正五边形的话
我们可以通过连接不同的对角线
就可以得到不同的三角形的构造
大约一共有多少种呢
实际上欧拉当时
给了一个非常复杂的解答式子
实际上我们再来看一下
这个式子是不是也可以写成
递推关系呢
如果对应于一个正n边形来说
它的第一个点是v1点
它的最后一个点也就是vn点
那么我们就可以拿v1 vn
这条边来去找它对应的一个三角形
这个三角形里的另外一个顶点
我们用vk来表示
那么这个k的取值就可以从1到n
根据vk的不同取值
我们同样可以构造出来有这样
一个递推关系
cn等于c0乘以cn减1
一直累加下去
所以我们会发现
其实欧拉并没有得到一个递推关系
真正是在1758年由另外一个数学家
谢格奈提出了关于
划分问题的递推关系
而这个递推关系正好和我们分析的
栈以及二叉树的构造一一对应
但是时间过去了
人们仍然只知道它的递推关系
直到1838年的时候
掀起了一股研究的热潮
有数位科学家都在上面进行了
深入的研究
其中当然少不了比利时的数学家
卡特兰
卡特兰他实际上是在研究
汉诺塔的时候
突然发现了这样的奥秘
而且他研究了关于
括号的表达式的问题
当然还有其他的很多数学家
都在研究类似的问题
但是为什么现在这个数列被称为是
卡特兰数列呢
是因为在1900年的
一篇有名的著作中
他将这个序列归功于卡特兰
所以大家可以发现
如果你要写论文的时候
慎重的引用是多么的重要啊
但是实际上到底是谁最早研究了
卡特兰数呢
不是卡特兰
也不是欧拉
在1988年和1999年的文献
研究中发现
实际上真正研究卡特兰数的
最早的人是我们蒙古一位数学家
也就是在清朝的时候
我们有一位蒙古数学家
他比卡特兰更早地去研究了
他在1730年写的一本著作中
就研究了卡特兰数的构造
那么现在我们来看
卡特兰数已经成为了序列中
一个不可或缺的重要组成部分
它被列为OES中的第108号序列
我们可以看到
它的前几项
分别是1 2 5 14 42
依次往下
它的增长也是非常迅速的
那么我们带怎么计算卡特兰数呢
当然我们有这样一个递推关系
但是同时我们也会想
有没有一个直接表达式呢
这样一个递推关系和我们以前
见到递推关系稍有不同
为什么这么说呢
我们以前这样的递推关系多半都是
一个线性累加和
但是在卡特兰数中
我们却看到了两个卡特兰数
进行相累乘
因此这并不是我们所常说的
线性常系数齐次递推关系
我们需要一个崭新的方法
来求解卡特兰数的直接表达式
-什么是组合数学
--什么是组合数学
--讨论题
-最精巧的排列——幻方
--幻方
-漫谈组合数学--最精巧的排列——幻方
-苦难的羊皮纸卷
--羊皮纸卷
-苦难的羊皮纸卷--作业
-你的手机密码安全吗
-漫谈组合数学--你的手机密码安全吗
-暴力枚举和抽象转换
--世界杯引出的问题
--世界杯引出的问题--练习
--一一对应
--七桥问题
--小结
--讨论题
-大家谈组合数学(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
-知识点串串烧
--知识点串串烧
-期末测验--期末测验