Catalan数的应用：
http://www.cppblog.com/abilitytao/archive/2010/04/12/112371.html卡特兰数真是一个神奇的数字，很多组合问题的数量都和它有关系，例如：
一.Cn= 长度为 2n的 Dyck words的数量。 Dyck words是由 n个 X和 n个 Y组成的字符串，并且从左往右数， Y的数量不超过 X，例如长度为 6的 Dyck words为：
XXXYYY XYXXYY XYXYXY XXYYXY XXYXYY
二.Cn= n对括号正确匹配组成的字符串数，例如 3对括号能够组成：
((())) ()(()) ()()() (())() (()())
三.Cn= n+1个数相乘，所有的括号方案数。例如， 4个数相乘的括号方案为：
((ab)c)d (a(bc))d (ab)(cd) a((bc)d) a(b(cd))
\四.Cn= 拥有 n+1 个叶子节点的二叉树的数量。例如 4个叶子节点的所有二叉树形态：
五.Cn=n*n的方格地图中，从一个角到另外一个角，不跨越对角线的路径数，例如， 4×4方格地图中的路径有：
六.Cn= n+2条边的多边形，能被分割成三角形的方案数，例如 6边型的分割方案有：
七.Cn= 圆桌周围有 2n个人，他们两两握手，但没有交叉的方案数。
在《Enumerative Combinatorics》一书中，竟然提到了多达 66种组合问题和卡特兰数有关。
算法分析中Catalan数的应用研究一、catalan计数序列及其递推公式
（一）catalan数
catalan数即序列c0,c1,c2,…,cn,…。其中cn= (n=0,1,2,…)。前几个catalan数为c0=1,c1=1,c2=2,c3=5,c4=14,c5=42,c6=132,c7=429,c8=1430,c9=4862。
（二）递推公式
公式1：cn=c0cn-1+c1cn-2+…+cn-1c0= (1)
此公式为catalan数最常见递推公式。由公式可得出cn= (n=0,1,2,…),其证明过程主要是求此非线性递推公式的生成函数, 具体证明可参见参考文献中的组合数学。
公式2：cn= cn-1 (n≥1) c0=1,c1=1 (2)
此公式也为catalan数常见递推公式之一。由公式也可得出cn= (n=0,1,2,…),其证明过程较为简单。只要不断地递归到c0=1即可。
定理1：n个+1和n个-1构成的2n项a1,a2,…,a2n,其部分和满足a1+a2+…+ak≥0 (k=1,2,…,2n)的数列个数等于第n个catalan数，即cn= 。
证明：此定理的可以直接利用排列组合来证明，具体的证明可参见参考文献中的组合数学。这里给出另一种证明方式。
设满足部分和非负的数列个数为cn，此数列中的每一个都可看成是由i个+1和i个-1以及n-i个+1和n-i个-1这样两个数列构成。 由i个+1和i个-1构成的数列个数为ci, 由n-i个+1和n-i个-1构成的数列个数为cn-i，由乘法和加法原理可知cn= 且c0=1即满足公式1,所以cn= 。