顶 顶
顶顶 顶顶
顶顶顶 顶顶顶
顶顶顶顶 顶顶顶顶
顶顶顶顶顶 顶顶顶顶顶
顶顶顶顶顶顶 顶顶顶顶顶顶
顶顶顶顶顶顶顶 顶顶顶顶顶顶顶
顶顶顶顶顶顶 顶顶顶顶顶顶
顶顶顶顶顶 顶顶顶顶顶
顶顶顶顶 顶顶顶顶
顶顶顶 顶顶顶
顶顶 顶顶
顶 顶
所谓三阶的卡特兰数列是怎么回事？（我对这方面的数学知识了解的太少了）。这个数列的通项是如何推出的？它的各个因式的实际意义是什么？如果说有三阶的话，那么更高阶的呢？这东西的本质是什么......
实在抱歉，细查之下，我打的公式少了一个括号。应该是（C(2n,n)/(n+1)）*（C(3n,n)/(n^2/2+3n/2+1)），前一项是大家熟悉的卡特兰数，
C(N,M)就是组合数的意思，(n^2/2+3n/2+1)就是一个二次函数：a=1/2,b=3/2,c=1。应该很清楚了。
二阶的：（C(2n,n)/C(n+1,1)）
三阶的：（C(3n,n)/C(n+2,2)）*二阶的
四阶的：（C(4n,n)/C(n+3,3)）*三阶的
五阶的：（C(5n,n)/C(n+4,4)）*四阶的
以此类推至N阶。
qingxilzq 帐号设置退出初级编辑 三级|我的百科我的贡献草稿箱我的任务为我推荐|百度首页 新闻网页贴吧知道MP3图片视频地图百科文库
帮助 首页 自然 文化 地理 历史 生活 社会 艺术 人物 经济 科技 体育 图片 数字博物馆 核心用户 百科商城
卡特兰数
求助编辑百科名片卡特兰数又称卡塔兰数，是组合数学中一个常出现在各种计数问题中出现的数列。由以比利时的数学家欧仁·查理·卡塔兰 (1814–1894)命名。
查看精彩图册
目录
卡特兰数
英文名
原理
卡特兰数的应用 括号化
出栈次序
凸多边形三角划分
给定节点组成二叉树
卡特兰数的扩展
展开 卡特兰数
英文名
原理
卡特兰数的应用 括号化
出栈次序
凸多边形三角划分
给定节点组成二叉树
卡特兰数的扩展
展开 编辑本段卡特兰数 卡特兰数前几项为 : 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, ...编辑本段英文名 Catalan number编辑本段原理 令h(0)=1,h(1)=1，catalan数满足递推式[1]： h(n)= h(0)*h(n-1)+h(1)*h(n-2) + ... + h(n-1)h(0) (n>=2) 例如：h(2)=h(0)*h(1)+h(1)*h(0)=1*1+1*1=2 h(3)=h(0)*h(2)+h(1)*h(1)+h(2)*h(0)=1*2+1*1+2*1=5 另类递推式[2]： h(n)=h(n-1)*(4*n-2)/(n+1); 递推关系的解为： h(n)=C(2n,n)/(n+1) (n=1,2,3,...) 递推关系的另类解为： h(n)=c(2n,n)-c(2n,n+1)(n=1,2,3,...)编辑本段卡特兰数的应用 实质上都是递推等式的应用
括号化
矩阵链乘： P=a1×a2×a3×……×an，依据乘法结合律，不改变其顺序，只用括号表示成对的乘积，试问有几种括号化的方案？(h(n)种)[3]
出栈次序
一个栈(无穷大)的进栈序列为1，2，3，…，n，有多少个不同的出栈序列?[4-5]
常规分析 首先，我们设f（n）=序列个数为n的出栈序列种数。同时，我们假定第一个出栈的序数是k。 第一个出栈的序数k将1~n的序列分成两个序列，其中一个是1~k-1，序列个数为k-1，另外一个是k+1~n，序列个数是n-k。 此时，我们若把k视为确定一个序数，那么根据乘法原理，f（n）的问题就等价于——序列个数为k-1的出栈序列种数乘以序列个数为n - k的出栈序列种数，即选择k这个序数的f（n）=f（k-1）×f（n-k）。而k可以选1到n，所以再根据加法原理，将k取不同值的序列种数相加，得到的总序列种数为：f（n）=f（0）f（n-1）+f（1）f（n-2）+……+f（n-1）f（0）。 看到此处，再看看卡特兰数的递推式，答案不言而喻，即为f（n）=h（n+1）= C（2n,n）/（n+1）= c（2n,n）-c（2n,n+1）（n=1，2，3，……）。 最后，令f（0）=1，f（1）=1。 非常规分析 对于每一个数来说，必须进栈一次、出栈一次。我们把进栈设为状态‘1’，出栈设为状态‘0’。n个数的所有状态对应n个1和n个0组成的2n位二进制数。由于等待入栈的操作数按照1‥n的顺序排列、入栈的操作数b大于等于出栈的操作数a(a≤b)，因此输出序列的总数目=由左而右扫描由n个1和n个0组成的2n位二进制数，1的累计数不小于0的累计数的方案种数。 在2n位二进制数中填入n个1的方案数为c(2n,n),不填1的其余n位自动填0。从中减去不符合要求（由左而右扫描，0的累计数大于1的累计数）的方案数即为所求。 不符合要求的数的特征是由左而右扫描时，必然在某一奇数位2m+1位上首先出现m+1个0的累计数和m个1的累计数，此后的2(n-m)-1位上有n-m个 1和n-m-1个0。如若把后面这2(n-m)-1位上的0和1互换，使之成为n-m个0和n-m-1个1，结果得1个由n+1个0和n-1个1组成的2n位数，即一个不合要求的数对应于一个由n+1个0和n-1个1组成的排列。 反过来，任何一个由n+1个0和n-1个1组成的2n位二进制数，由于0的个数多2个，2n为偶数，故必在某一个奇数位上出现0的累计数超过1的累计数。同样在后面部分0和1互换，使之成为由n个0和n个1组成的2n位数，即n+1个0和n-1个1组成的2n位数必对应一个不符合要求的数。 因而不合要求的2n位数与n+1个0，n－1个1组成的排列一一对应。 显然，不符合要求的方案数为c(2n,n+1)。由此得出输出序列的总数目=c(2n,n)-c(2n,n+1)=c(2n,n)/(n+1)=h(n+1)。 类似问题 买票找零 有2n个人排成一行进入剧场。入场费5元。其中只有n个人有一张5元钞票，另外n人只有10元钞票，剧院无其它钞票，问有多少中方法使得只要有10元的人买票，售票处就有5元的钞票找零？(将持5元者到达视作将5元入栈，持10元者到达视作使栈中某5元出栈)
凸多边形三角划分
在一个凸多边形中，通过若干条互不相交的对角线，把这个多边形划分成了若干个三角形。现在的任务是键盘上输入凸多边形的边数n，求不同划分的方案数f（n）。比如当n=6时，f（6）=14。[6]
分析 如果纯粹从f（4）=2，f（5）=5，f（6）=14，……，f（n）=n慢慢去归纳，恐怕很难找到问题的递推式，我们必须从一般情况出发去找规律。 因为凸多边形的任意一条边必定属于某一个三角形，所以我们以某一条边为基准，以这条边的两个顶点为起点P1和终点Pn（P即Point），将该凸多边形的顶点依序标记为P1、P2、……、Pn，再在该凸多边形中找任意一个不属于这两个点的顶点Pk（2<=k<=n-1），来构成一个三角形，用这个三角形把一个凸多边形划分成两个凸多边形，其中一个凸多边形，是由P1，P2，……，Pk构成的凸k边形（顶点数即是边数），另一个凸多边形，是由Pk，Pk+1，……，Pn构成的凸n-k+1边形。 此时，我们若把Pk视为确定一点，那么根据乘法原理，f（n）的问题就等价于——凸k多边形的划分方案数乘以凸n-k+1多边形的划分方案数，即选择Pk这个顶点的f（n）=f（k）×f（n-k+1）。而k可以选2到n-1，所以再根据加法原理，将k取不同值的划分方案相加，得到的总方案数为：f（n）=f（2）f（n-2+1）+f（3）f（n-3+1）+……+f（n-1）f（2）。看到此处，再看看卡特兰数的递推式，答案不言而喻，即为f（n）=h（n-1） （n=2，3，4，……）。 最后，令f（2）=1，f（3）=1。 此处f（2）=1和f（3）=1的具体缘由须参考详尽的“卡特兰数”，也许可从凸四边形f（4）=f（2）f（3）+ f（3）f（2）=2×f（2）f（3）倒推，四边形的划分方案不用规律推导都可以知道是2，那么2×f（2）f（3）=2，则f（2）f（3）=1，又f（2）和f（3）若存在的话一定是整数，则f（2）=1，f（3）=1。（因为我没研究过卡特兰数的由来，此处仅作刘抟羽的臆测）。 类似问题 一位大城市的律师在她住所以北n个街区和以东n个街区处工作。每天她走2n个街区去上班。如果她从不穿越（但可以碰到）从家到办公室的对角线，那么有多少条可能的道路？ 在圆上选择2n个点,将这些点成对连接起来使得所得到的n条线段不相交的方法数？
给定节点组成二叉树
给定N个节点，能构成多少种不同的二叉树？[7] （能构成h（N）个） （这个公式的下标是从h(0)=1开始的）编辑本段卡特兰数的扩展 对于在n位的2进制中，有m个0，其余为1的catalan数为：C（n,m）-C(n,m-1)。证明可以参考标准catalan数的证明。[8] 问题1的描述：有n个1和m个-1（n>=m），共n+m个数排成一列，满足对所有0<=k<=n+m的前k个数的部分和Sk > 0的排列数。 问题等价为在一个格点阵列中，从（0，0）点走到（n，m）点且不经过对角线x==y的方法数（x > y）。 考虑情况I：第一步走到（0，1），这样从（0，1）走到（n，m）无论如何也要经过x==y的点，这样的方法数为(( n+m-1,m-1 )); 考虑情况II：第一步走到（1，0），又有两种可能： a . 不经过x==y的点；（所要求的情况） b . 经过x==y的点，我们构造情况II.b和情况I的一一映射，说明II.b和I的方法数是一样的。设第一次经过x==y的点是（x1，y1），将（0，0）到（x1，y1）的路径沿对角线翻折，于是唯一对应情况I的一种路径；对于情况I的一条路径，假设其与对角线的第一个焦点是（x2，y2），将（0，0）和（x2，y2）之间的路径沿对角线翻折，唯一对应情况II.b的一条路径。 问题的解就是总的路径数 ((n+m, m)) - 情况I的路径数 - 情况II.b的路径数。 ((n+m , m)) - 2*((n+m-1, m-1)) 或： ((n+m-1 , m)) - ((n+m-1 , m-1)) 问题2的描述：有n个1和m个-1（n>=m），共n+m个数排成一列，满足对所有0<=k<=n+m的前k个数的部分和Sk >= 0的排列数。（和问题1不同之处在于此处部分和可以为0，这也是更常见的情况） 问题等价为在一个格点阵列中，从（0，0）点走到（n，m）点且不穿过对角线x==y的方法数（可以走到x==y的点）。 把（n，m）点变换到（n+1，m）点，问题变成了问题1。 方法数为： ((n+m+1, m)) - 2*((n+m+1-1, m-1)) 或： ((n+m+1-1, m)) - ((n+m+1-1, m-1))
参考资料
1． 卡特兰数 ．网易博客[引用日期 2012-06-16]．
2． 卡塔兰数 ．维基百科[引用日期 2012-06-16]．
3． 2012腾讯实习笔试中看到的Catalan数 ．CSDN博客[引用日期 2012-06-16]．
4． 给定一个入栈序列，求所有可能的出栈序列 ．CSDN博客[引用日期 2012-06-16]．
5． Catalan数（卡特兰数） ．51CTO博客[引用日期 2012-06-16]．
6． 解题笔记（37）——Catalan数计算及应用 ．CSDN博客[引用日期 2012-06-16]．
7． 卡特兰数 ．CSDN博客-幽兰止水[引用日期 2012-06-16]．
8． 卡特兰数 ．CSDN博客[引用日期 2012-06-16]．
开放分类：
编程，数学，公式，算法，ACM
我来完善 “卡特兰数”相关词条：
组合数学
百度百科中的词条正文与判断内容均由用户提供，不代表百度百科立场。如果您需要解决具体问题（如法律、医学等领域），建议您咨询相关领域专业人士。
本词条对我有帮助添加到搜藏 分享到:
更多
合作编辑者
5季末不寂寞 ，防撒旦机 ，trj217 ，为醒而歌 ，yushuai007008 ，liuhaodiyi ，cnresonant 更多
如果您认为本词条还需进一步完善，百科欢迎您也来参与编辑词条在开始编辑前，您还可以先学习如何编辑词条
如想投诉，请到百度百科投诉中心；如想提出意见、建议，请到百度百科吧。
qingxilzq
00
去兑换>>您尚无道具可使用
成长任务快乐起航学习词条基础编辑 +30
现在去完成>>完成0%日常任务本月累计点亮0天。今日笑脸还没点亮哦。
大展宏图：参加任务，拿点亮任务日历获得额外财富值热词推送编辑热词可获得额外经验值
词条动态进入我的百科您目前的等级是3级
您目前的经验值是594点
您还需606点经验值即可升为4级
词条统计
浏览次数：约 29440次
编辑次数：38次 历史版本
最近更新：2012-08-23
创建者：t466307446
更多贡献光荣榜
辛勤贡献者：
liuhaodiyi 展开
版本
版本
版本
trj217 版本
千黎迢迢 版本
t466307446 版本
最新动态
解析中国航母：
百科消息：
百科android客户端升级1.1版
贴吧搞笑专题：刺瞎双眼自带墨镜
求知：太空里的糖或有生命价值
百度文库：2013考研必备材料
百度校园 看见你的光芒
百科航海日志-船长分享成长点滴
? 2012 Baidu 使用百度前必读 | 百科协议 | 百度百科合作平台
卡特兰数卡特兰数英文名原理卡特兰数的应用括号化出栈次序凸多边形三角划分给定节点组成二叉树卡特兰数的扩展
退出
若有错误，请划词选中错误内容并按提示质疑，为词条的质量提升做出贡献。
展开收起
若您对这些内容有可信的参考资料，并掌握百科编辑技巧，欢迎你直接编辑词条。
参与质疑×全方位解读中国首艘航母中国首艘航母辽宁号正式服役，它虽不具备作战能力但却是国力象征。《求知》带你走近辽宁号，了解航母知识。关闭