通过本文主要向大家介绍了卡特兰数,卡特兰数公式,卡特兰数公式推导,什么是卡特兰数,卡特兰数程序等相关知识,希望对您有所帮助,也希望大家支持linkedu.com www.linkedu.com
</div>
</div>
</div>
1、一个栈(无穷大)的进栈序列为1,2,3,..n,有多少个不同的出栈序列?
2、有2n个人排成一行进入剧场。入场费5元。其中只有n个人有一张5元钞票，另外n人只有10元钞票，剧院无其它钞票，问有多少中方法使得只要有10元的人买票，售票处就有5元的钞票找零？(将持5元者到达视作将5元入栈，持10元者到达视作使栈中某5元出栈)。
将多边行划分为三角形问题
1、将一个凸多边形区域分成三角形区域的方法数?
2、一位大城市的律师在她住所以北n个街区和以东n个街区处工作。每天她走2n个街区去上班。如果她从不穿越（但可以碰到）从家到办公室的对角线，那么有多少条可能的道路？
3、在圆上选择2n个点,将这些点成对连接起来使得所得到的n条线段不相交的方法数? 给顶节点组成二叉树的问题 给定N个节点，能构成多少种不同的二叉树？</div> </div> </div> </div>
递推关系：
它也满足
这提供了一个更快速的方法来计算卡塔兰数。
卡特兰数的应用n个元素顺序入栈，出栈顺序有多少种？此问题是一个卡特兰数问题，证明过程如下：
令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的二进制数。
反过来，任何一个由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)。
从而
。证毕。
1、一个栈(无穷大)的进栈序列为1,2,3,..n,有多少个不同的出栈序列?
2、有2n个人排成一行进入剧场。入场费5元。其中只有n个人有一张5元钞票，另外n人只有10元钞票，剧院无其它钞票，问有多少中方法使得只要有10元的人买票，售票处就有5元的钞票找零？(将持5元者到达视作将5元入栈，持10元者到达视作使栈中某5元出栈)。
将多边行划分为三角形问题
1、将一个凸多边形区域分成三角形区域的方法数?
2、一位大城市的律师在她住所以北n个街区和以东n个街区处工作。每天她走2n个街区去上班。如果她从不穿越（但可以碰到）从家到办公室的对角线，那么有多少条可能的道路？
3、在圆上选择2n个点,将这些点成对连接起来使得所得到的n条线段不相交的方法数? 给顶节点组成二叉树的问题 给定N个节点，能构成多少种不同的二叉树？</div> </div> </div> </div>