算法

http://blog.csdn.net/linhuanmars/article/details/24761459

https://zh.wikipedia.org/wiki/%E5%8D%A1%E5%A1%94%E5%85%B0%E6%95%B0

C_n表示长度2n的dyck word的个数。Dyck word是一个有n个X和n个Y组成的字串，且所有的前缀字串皆满足X的个数大于等于Y的个数。

C_n的另一个表达形式为 $C_n = {2nchoose n} - {2nchoose n+1} quadmbox{ for }nge 1$

$所以， C n 是一个自然数；这一点在先前的通项公式中并不显而易见。这个表达形式也是André对前一公式证明的基础。（见下文的第二个证明。）$

$C_0 = 1 quad mbox{and} quad C_{n+1}=sum_{i=0}^{n}C_i\,C_{n-i}quadmbox{for }nge 0.$

它也满足

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

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

卡塔兰数的渐近增长为

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

它的含义是当n → ∞时，左式除以右式的商趋向于1。（这可以用n!的斯特灵公式来证明。）

所有的奇卡塔兰数C_n都满足 $n=2^k-1$

$example:$

$https://leetcode.com/problems/unique-binary-search-trees/description/$