由于卡特兰(Catalan)数经常会在算法题或面试题中出现，在这里做一下小小的总结。

卡特兰数是组合数据中一个常在各种计数问题中出现的数列，由比利时的数学家欧仁.查理.卡特兰（1814-1894）命名。

Catalan数的定义：令h(0)=1，Catalan数满足递归式：h(n)= h(0)*h(n-1) + h(1)*h(n-2) + ... + h(n-1)h(0) (其中n>=0)。该递推关系的解为：h(n) = C(2n-2,n-1)/n，n=1,2,3,...（其中C(2n-2,n-1)表示2n-2个中取n-1个的组合数）。

卡特兰数：规定h(0)＝1，而h(1)＝1，h(2)＝2，h(3)＝5，h(4)＝14，h(5)＝42，h(6)＝132，h(7)＝429，h(8)＝1430，h(9)＝4862，h(10)＝16796，h(11)＝58786，h(12)＝208012，h(13)＝742900，h(14)＝2674440，h(15)＝9694845。

• 1 h(0)＝1
• 1 h(1)＝h(0)*h(0) = 1
• 2 h(2)= h(0)*h(1) + h(1)*h(0) = 1 + 1 = 2
• 5 h(3)= h(0)*h(2) + h(1)*h(1) + h(2)*h(0) = 2 + 1 + 2 = 5
• 14 h(4)= h(0)*h(3) + h(1)*h(2) + h(2)*h(1) + h(3)*h(0) = 5 + 2 + 2 + 5 = 14
• 42 h(5)= h(0)*h(4) + h(1)*h(3) + h(2)*h(2) + h(3)*h(1) + h(4)*h(0) = 14 + 5 + 4 + 5 + 14 = 42
• ……

卡塔兰数的一般项公式为：

另一个表达形式：

满足递推关系：

也满足：

这提供了一个更快速的方法来计算卡塔兰数。

关于卡特兰数的概念就介绍到这里，后面再补充其它方面的知识。