当前课程知识点:组合数学 >  神奇的序列 >  Catalan数 >  Catalan数的直接表达式

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

Catalan数的直接表达式在线视频

Catalan数的直接表达式

下一节:Catalan数的各种实例

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

Catalan数的直接表达式课程教案、知识点、字幕

我们刚才已经通过不同的例题

来分析了卡特兰数

对应的一个递推关系

当然根据的递推关系我们也可以

依次写出每一个卡特兰数

比如说C1等于什么

C2 C3 C4

依次累加下去

但是这样一个递推关系

并不是一个很好的计算方法

因为比如说我们想算C100的话

那么它就相当于

有将近几百项进行相加和相乘

这是一个非常复杂的运算过程

我们希望能有一个

直接简单的计算方法

那么我们来分析一下

如果大家还有点印象的话

你在第二周的时候

曾经遇到过一个习题

也就是w2g1

在这道题中

我们曾经问

如果我有八个人排队去买票

4个人拿了10块钱

而4个人拿了20块钱

如果售票处一开始

是没有准备零钱的话

请问能够顺利买票的方案数

有多少种

大家一开始的时候

对这个问题好象有些同学

都没有思路

但是我们从论坛上就可以看到

有些同学直接就看出来了

这就是一个出栈问题呀

甚至有的同学还直接就说

这不就是个卡特兰数嘛

确实是

这个问题如果我们画成格路的话

会发现其实这种格路问题

和出栈问题是一一对应的

而这种格路问题从形式化来讲

就意味着对应于这样一个格路

xy xy进行走的时候

我要求它不穿过对角线

而这样一个问题

实际上有一个正式的名字

它被称为是Dyck Path

那么怎么来求解呢

我们当时并没有用递推关系

我们直接用了传统的排列组合方法

就得到了最终答案

思路是什么呢

我们对应于比如说想要

从(0,0)点走到(n,n)点

这时候我有一个要求

也就是说它必须不能穿过

甚至接触这条对角线

那么我们这时候

要处理这个问题的时候

进行了一个形式的变换

我们首先把(0,0)点到(n,n)

这样一条对角线

也就是x等于y

这条对角线进行了下移

因为题目中要求是不穿过

但是可以接触

那么问题太复杂

我们希望只是解决不接触

所以我们直接把线段进行下移之后

变成了x减y等于这条线

只要我们这些格路都不与

x减y等于1进行接触的话

我们就可以找到所有的合理的格路

而这个问题大家仔细

去看一下相关的解答

就会发现

实际上我们经过的一个变换

做它的对应的点之后

就会直接转化成两个组合数的差

也就是我们从(0,0)点到(n,n)点

所有可行格路数

减去它的对称点

也就是(1,-1)点

到(n,n)点所有的格路数

那么写成组合数的

它的答案就是C(2n,n)减去C(2n,n-1)

这时候我们如果进一步的化简的话

会发现这实际上

可以整理成一个非常整洁的数字

也就是等于n分之1乘以C(2n,n)

这个式子就是我们说的

所谓的Dyck Path相应的格路数目

而这个格路数目又和我们

一开始说到的栈的问题

是完全一一对应的

这就意味着我们实际上已经给出了

所有的卡特兰数的一个直接表达式

那么除了刚才这样巧妙地用格路

来证明卡特兰数的话

我们有没有其他方法呢

我们同样也可以用传统的

母函数方法给予相应的证明

说起母函数的话

我们肯定首先要按照序列来

构造一个母函数

这里面对于卡特兰数Cn来说

我们就直接来写它的母函数

是小c(x)等于Cnxn次方

其中累加n从0到无穷大

(那对应于)我们知道对应于卡特兰数

它有这样一个两个卡特兰数

进行相乘的递推关系

那我们就会想

怎么能通过母函数

去构造一个这样相乘的系数呢

我们用c(x)的平方来看一下

那么两个小c(x)相乘以后

我们就会得到它就是C0乘以C0

加上C1 C0加上C0 C1x

加上C2 C0

加上C1 C1 C0 C2x平方

这个式子似乎我们看到了

构造出来了两两卡特兰数

相乘进行累加的这样的系数

而这个系数和原来的c(x)

有什么关系呢

我们来分析一下

实际上C1就相当于C0 C0

所以在c(x)平方项

这里就是C1

而C1 C0加上C0 C1对应的就是C2

正好它的x次方

前面的对应的系数刚好是C2

依次C平方项前面对应的是C3

所以我们可以整理出来

对于小c(x)的平方

就等于C1加C2x

加C3x平方

这个式子和原来的c(x)有什么区别呢

我们把c(x)整理出来可能看到

小c(x)是常数项是C0

加上C1x

加上C2x平方

和c(x)平方对应的我们会发现

实际上就差了一个x

那么我们就可以写出式子

假如说C0就等于1的话

我们就可以直接写c(x)就等于C0

也就是1加上c(x)平方乘以一个x

这时候我们似乎得到了

母函数一个关系

当然我们的目标是想求小c(x)

而这里x作为了一个变量

那我们怎么进一步的

去求出来这个c(x)呢

我们可以看作这个c(x)

是对应于x作为常数的时候

我想求c(x)的变量的取值的话

仍然可以用2a分之负b

加减根号下b平方减4ac来求解呀

所以我们来进一步求解这样一个

对于c(x)的一元二次方程

这个方程求解以后

自然会有两个根

那么我们要求对于小c(x)

当x趋近于0的时候

它应该得1

因此在两个根中

我们选择了2x分之1减

根号下1减4x

这时候我们得到了一个母函数

我们要求它们的序列

要求它的序列

我们实际上会发现

这里面首先这里有一个2x

而这里有一个1减4x的2分之1次方

2分之1次方的话

我们可以用对应的1

加x的α次方这样二项式定理

进行展开

那么具体的细节我就在这里省略了

大家可以回去练习一下

我们经过整理之后

就会发现c(x)实际上可以转化成

x的n次方

前面的系数是C(2n,n)

除以(n+1)

因此通过母函数的方法

我们照样也可以得到对应的

卡特兰数的一个直接表达式

也就是Cn等于(n+1)分之1(貌似口误说成了1/n)

乘以C(2n,n)

组合数学课程列表:

漫谈组合数学

-什么是组合数学

--什么是组合数学

--讨论题

-最精巧的排列——幻方

--幻方

-漫谈组合数学--最精巧的排列——幻方

-苦难的羊皮纸卷

--羊皮纸卷

-苦难的羊皮纸卷--作业

-你的手机密码安全吗

--你的手机密码安全吗

-漫谈组合数学--你的手机密码安全吗

-暴力枚举和抽象转换

--世界杯引出的问题

--世界杯引出的问题--练习

--一一对应

--七桥问题

--小结

--讨论题

-大家谈组合数学(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

-知识点串串烧

--知识点串串烧

期末测验

-期末测验--期末测验

Catalan数的直接表达式笔记与讨论

也许你还感兴趣的课程:

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