卡特兰数（catalan numbers）

首先我们给出卡特兰序列：

卡特兰数定理

考虑由n个+1和n个-1构成的2n项序列

其部分和总满足

这样的序列的个数为：

证明过程就不说了，大致思路为从不可接受序列入手，再用总序列减去不可接受序列（不可接受序列的数目求解仍然很tricky，没时间看~）。

看上面的定理是不是还觉得有些不直观，看看下面的例子应该理解起来就比较简单了。

参考文献：

[1] 组合数学（Richard A. Brualdi）