当前课程知识点:组合数学 >  神奇的序列 >  Catalan数 >  计算机界的精灵

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

计算机界的精灵在线视频

计算机界的精灵

下一节: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算法

--程序支持与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

-知识点串串烧

--知识点串串烧

期末测验

-期末测验--期末测验

计算机界的精灵笔记与讨论

也许你还感兴趣的课程:

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