refernce:http://zh.wikipedia.org/wiki/%E5%8D%A1%E5%A1%94%E5%85%B0%E6%95%B0
卡塔兰数是组合数学中一个常在各种计数问题中出现的数列。以比利时的数学家欧仁·查理·卡塔兰(1814–1894)命名。
卡塔兰数的一般项公式为
前几项为 (OEIS中的数列A000108):
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, ...
Cn的另一个表达形式为所以,Cn是一个自然数;这一点在先前的通项公式中并不显而易见。这个表达形式也是André对前一公式证明的基础。(见下文的第二个证明。)
递推关系
它也满足
这提供了一个更快速的方法来计算卡塔兰数。
卡塔兰数的渐近增长为
它的含义是左式除以右式的商趋向于1当n→∞。(这可以用n!的斯特灵公式来证明。)
所有的奇卡塔兰数Cn都满足。所有其他的卡塔兰数都是偶数。
组合数学中有非常多.的组合结构可以用卡塔兰数来计数。在Richard P. Stanley的Enumerative Combinatorics: Volume 2一书的习题中包括了66个相异的可由卡塔兰数表达的组合结构。以下用Cn=3和Cn=4举若干例:
-
Cn表示长度2n的dyck word的个数。Dyck word是一个有n个X和n个Y组成的字串,且所有的前缀字串皆满足X的个数大于等于Y的个数。以下为长度为6的dyck words:
XXXYYY XYXXYY XYXYXY XXYYXY XXYXYY
- 将上例的X换成左括号,Y换成右括号,Cn表示所有包含n组括号的合法运算式的个数:
((())) ()(()) ()()() (())() (()())
-
Cn表示有n个节点组成不同构二叉树的方案数。下图中,n等于3,圆形表示节点,月牙形表示什么都没有。
-
Cn表示有2n+1个节点组成不同构满二叉树(full binary tree)的方案数。下图中,n等于3,圆形表示内部节点,月牙形表示外部节点。本质同上。
证明:
令1表示进栈,0表示出栈,则可转化为求一个2n位、含n个1、n个0的二进制数,满足从左往右扫描到任意一位时,经过的0数不多于1数。显然含n个1、n个0的2n位二进制数共有个,下面考虑不满足要求的数目。
考虑一个含n个1、n个0的2n位二进制数,扫描到第2m+1位上时有m+1个0和m个1(容易证明一定存在这样的情况),则后面的0-1排列中必有n-m个1和n-m-1个0。将2m+2及其以后的部分0变成1、1变成0,则对应一个n+1个0和n-1个1的二进制数。反之亦然(相似的思路证明两者一一对应)。
从而。证毕。
-
Cn表示所有在n×n格点中不越过对角线的单调路径的个数。一个单调路径从格点左下角出发,在格点右上角结束,每一步均为向上或向右。计算这种路径的个数等价于计算Dyck word的个数: X代表“向右”,Y代表“向上”。下图为n= 4的情况:
-
Cn表示通过连结顶点而将n+2边的凸多边形分成三角形的方法个数。下图中为n=
4的情况:
-
Cn表示对{1, ...,n}依序进出栈的置换个数。一个置换w是依序进出栈的当S(w)
= (1, ...,n), 其中S(w)递归定义如下:令w=unv,其中n为w的最大元素,u和v为更短的数列;再令S(w) =S(u)S(v)n,其中S为所有含一个元素的数列的单位元。
-
Cn表示用n个长方形填充一个高度为n的阶梯状图形的方法个数。下图为n=4的情况:
分享到:
相关推荐
之前玩ACM了解的一点信息,共享一下,东西不多,希望能帮到需要的人。
介绍了卡塔兰数的定义及使用场景,针对杭电hdu上的题目给出相关解析。
卡特兰数 catalan number 卡特兰数前几项为 : 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440,
组合数学中有非常多的组合结构可以用卡塔兰数来计数。在Richard P. Stanley的Enumerative Combinatorics: Volume 2一书的习题中包括了66个相异的可由卡塔兰数表达的组合结构。
3.2.1 卡塔兰数的第一种表示法 第63-71页 3.2.2 卡塔兰数的第二种表示法 第71-76页 3.2.3 卡塔兰数的第三种表示法 第76-81页 3.3 无穷级数求反函数的两种表示法 第81-96页 3.3.1 “通弦求弧背法解”中无穷级数...
求出栈序列个数。卡塔兰数是组合数学中一个常出现在各种计数问题中出现的数列。
卡特兰数(Catalan Number)是组合数学中应用广泛的重要计数函数,以比利时的数学家欧仁·查理·卡塔兰(1814–1894)的名字来命名,其前几项为(从第零项开始):1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012,...
卡塔兰猜想:从一道普特南竞赛试题谈起 出版时间:2013年版 丛编项: 数学中的小问题大定理丛书 内容简介 《数学中的小问题大定理丛书·卡塔兰猜想:从一道普特南竞赛试题谈起》从一道普特南数学竞赛试题谈起,洋...
卡特兰数(英语:Catalan number),又称卡塔兰数、明安图数,是组合数学中一种常出现于各种计数问题中的数列。以比利时的数学家欧仁·查理·卡特兰的名字来命名。1730年左右被蒙古族数学家明安图使用于对三角函数幂...
Catalan number,卡特兰数又称卡塔兰数,是组合数学中一个常出现在各种计数问题中出现的数列。以比利时的数学家欧仁·查理·卡塔兰 (1814–1894)命名。 令h(0)=1,h(1)=1,catalan数满足递推式:h(n)= h(0)*h(n-1)+h...
二进制指数运算2,二进制指数运算3,二项式系数,二项分布,二分法,卡迈克尔数,卡塔兰数,上取整,检查多边形,楚德诺夫斯基算法,考拉兹序列,组合,十进制分离,十进制转分数,十二面体,双阶乘迭代,双阶乘递归...
卡塔兰数 组合序列 整点三角形 BFS最长路径 树状数组 背包 凸包面积 高精度除法取模 完全匹配KM 字符串KMP 凸包graham算法 输出最短路径 子集 拓扑排序 欧拉函数&素数筛选 Pick定理 高精度浮点数比较 日历 15数码...
参加acm程序设计的同志请注意收藏,组合论的详细内容都在里面