卡特兰数
简介
数列的前几项为：1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862，...
以比利时的数学家欧仁·查理·卡特兰（1814–1894）命名。历史上，清朝数学家明安图（1692年－1763年）在其《割圜密率捷法》中最先发明这种计数方式，远远早于卡塔兰[1][2][3]。有中国学者建议将此数命名为“明安图数”或“明安图-卡塔兰数”[4]。
卡塔兰数的一般项公式为：
$$
C _ { n } = \frac { 1 } { n + 1 } \left( \begin{array} { c } 2 n \ n \end{array} \right) = \frac { ( 2 n ) ! } { ( n + 1 ) ! n ! }
$$
经典问题
进出栈系列
题目描述：
n 个元素进栈序列为：1，2，3，4，...，n，则有多少种出栈序列
我们将进栈表示为 +1，出栈表示为 -1，则 1 3 2 的出栈序列可以表示为：+1 -1 +1 +1 -1 -1。
根据栈本身的特点，每次出栈的时候，必定之前有元素入栈，即对于每个 -1 前面都有一个 +1 相对应。因此，出栈序列的所有前缀和必然大于等于 0，并且 +1 的数量等于 -1 的数量。
接下来让我们观察一下 n = 3 的一种出栈序列：+1 -1 -1 +1 -1 +1。序列前三项和小于 0，显然这是个非法的序列。
如果将第一个前缀和小于 0 的前缀，即前三项元素都进行取反，就会得到：-1 +1 +1 +1 -1 +1。此时有 3 + 1 个 +1 以及 3 - 1 个 -1。
因为这个小于 0 的前缀和必然是 -1，且 -1 比 +1 多一个，取反后，-1 比 +1 少一个，则 +1 变为 n + 1 个，且 -1 变为 n - 1 个。
进一步推广，对于 n 元素的每种非法出栈序列，都会对应一个含有 n + 1 个 +1 以及 n - 1 个 -1 的序列。
如何证明这两种序列是一一对应的？
假设非法序列为 A，对应的序列为 B。
每个 A 只有一个”第一个前缀和小于 0 的前缀”，所以每个 A 只能产生一个 B。
而每个 B 想要还原到 A，就需要找到”第一个前缀和大于 0 的前缀”，显然 B 也只能产生一个 A。
每个 B 都有 n + 1 个 +1 以及 n - 1 个 -1，因此 B 的数量为$C _ { 2 n } ^ { n + 1 }$，相当于在长度为 2n 的序列中找到 n + 1 个位置存放 +1。相应的，非法序列的数量也就等于$C _ { 2 n } ^ { n + 1 }$。
出栈序列的总数量共有$C _ { 2 n } ^ { n }$，因此，合法的出栈序列数量也就等于$C _ { 2 n } ^ { n } - C _ { 2 n } ^ { n + 1 } = \frac { C _ {2 n } ^ { n } } { n + 1 }$。
此时我们就得到了卡特兰数的通项$ \frac{C_{2n}^n}{n + 1}$。
