卡塔兰数简介

卡塔兰数（Catalan）

一、简介：

　　卡塔兰数是一个特殊的数列，在ACM程序设计、组合数学中会经常见到。

二、性质

（1）卡塔兰数的前几项

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, ……

（2）公式

（a）通项公式： 1) $C_n = frac{1}{n+1}{2n choose n} = frac{(2n)!}{(n+1)!n!}$

2） $C_n = {2nchoose n} - {2nchoose n-1} quadmbox{ for }nge 1$

（b）递归公式： C(n) = ((4*n-2)/(n+1)) * C(n-1)

（c）递推公式： 1） $C_0 = 1 quad mbox{and} quad C_{n+1}=sum_{i=0}^{n}C_i\,C_{n-i}quadmbox{for }nge 0.$

2） $C_0 = 1 quad mbox{and} quad C_{n+1}=frac{2(2n+1)}{n+2}C_n,$

（3）渐进时间增长函数

$C_n sim frac{4^n}{n^{3/2}sqrt{pi}}$

三、应用

　　（1）完成N个矩阵连续相乘的运算时，任意顺序组合的个数。

　　eg：

　　n = 1：（A）;

　　n = 2：（AB）；

　　 n = 3：（A（BC）），（（AB），C）；

　　n = 4：（（A（BC））D），（（AB）（CD）），（（（AB）C）D），（A（（BC）D）），（A（（BC）D））；

　　 ……

　　（2）当二叉树有n+1个叶子结点时，其所有二叉树种类为Cn。

　　（3）将有n+2条边的凸多边形通过连接其对角线可分成n个三角形的连线方案数为Cn。

　　（4）将1、2、3，……n这几个自然数依次入栈，其出栈序列有Cn中情况。

更多关于卡塔兰数的内容请参考维基百科。