卡特兰数

卡特兰数是一个具有多种实际意义的数列。定义为

$$C_n:=\frac{1}{n+1}\left(\genfrac{}{}{0ex}{}{2n}{n}\right).$$

递推式：

$$C_n=\sum _{i=0}^{n-1}{C}_i{C}_{n-i}.$$

实际意义

括号序列的个数

$2n$ 个括号可以构成的合法括号序列的个数为 $C_n$。

本质不同满二叉树个数

$2n+1$ 个节点的本质不同满二叉树个数为 $C_n$。