卡塔兰数是组合数学中一个常在各种计数问题中出现的数列。以比利时的数学家欧仁·查理·卡特兰（1814–1894）命名。
原理证明
先假设这样一个场景，有 n 个 1，n 个 -1，那么这 2n 个数字以 任意顺序 相加，结果肯定是等于 0 的。但是现在加一个限制，就是在所给的任意顺序的表达式，前 i 项(0<=i<=2n)的和也要>=0,问有多少种组合方式?
首先，如果不加所给的限制，任意排列，那么产生的序列为：C(n,2n)
接下来，就要从所有的序列中，排除掉不合法的序列，那么结果就是合法序列数量。
不合法的序列：
想象一下，产生不合法的序列的情形，一定是在前 2i 项相加为 0 后，2i+1 项出现了一个 -1，此序列就是不合法的。同时，2i+2 到 2n 的和为 1。那么我们做一个变换，就是将第 1 项到第 2i+1 项的 -1 全部变为 1,1 全部变为 -1。因为前 2i 项相加为 0，变换后相加依然为 0，但是第 2i+1 变为了 1，这导致前 2i+1 项的和为 1。同时 2i+2 到 2n 的数字没有改变。导致此时整个序列的和变为了 2。
以下是上述的一个例子，第一个式子是不合法的，我们进行一步转换，得到第二个式子。
1 | 1 -1 -1 1 = 0 |
注意，这种转换后和为 2 的式子和为转换前的不合法的式子是一一对应的。也就是说如果出现了不合法的式子，一定能转换成一个唯一的相加为 2 的式子。同理这一步也是可逆的，也就是说如果出现了一个相加为 2 的式子，那么一定有一个不合法的序列和其对应。
前面我们直接找不合法的序列的种类并不好找，但是经过这一步转换后，现在的问题转换为 n+1 个 1，n-1 个 -1 组成相加为 2 的序列种类有多少，那么结果就是：C(n-1,2n)
也就是说，错排种类为：C(n-1,2n)
所以合法的种类为：C(n,2n) - C(n-1,2n) = C(n,2n)/(n+1)
该结果就是著名的卡特兰公式：f(n) = C(2n, n)/(n+1)
递推公式：f(n) = f(0)*f(n-1) + f(1)*f(n-2) + f(2)*f(n-3) + … + f(n-1)*f(0)
f(0)=1，f(1)=1，
使用场景
出栈顺序/括号匹配
假设有一个无穷大的栈，现在有 n 个数字按顺序依次进栈，那么合法的进出栈的序列是多少？
合法的进出栈，把入栈想象为 1，出栈想象为 -1，那么合法的进出栈序列为：C(n,2n)/(n+1)
排队买票
假设现在有 2n 个人排队买票，n 个人有 5 块，n 个人有十块，票价正好为 5 块，同时售票员手上没有零钱，那么合法的排队顺序有多少种?
这个和之前不一样的是：每个人都是不同的，所以在之前的结果前提下，还要对 n 个人进行排列，结果为：
C(n,2n)/(n+1) * n! * n!
二叉查找树种类
n 个节点(节点序号为 1 ~ n)，将其组成二叉查找树，有几种可能的结果；
n = 0，f(0) = 1,认为是空结构；
n = 1，f(1) = 1,只有一种可能
n = 2, f(2) = 2,分别是 1 作为根节点，2 只能是右子节点；或者 2 作为根节点，1 只能是左子节点；
n = 3，f(3) = 5;
n = 4, f(4) =
……
接下来，讨论 n 个节点的情况，每个节点都有可能作为头结点；
那么 f(n) = f(0)*f(n-1) + f(1)*f(n-2) + f(2)*f(n-3) + … + f(n-1)*f(0)
结果其实就是卡特兰数，为 C(n,2n)/(n+1)
排队问题
12 个高矮不同的人，站成两排，每排 6 人，从左到右，从矮到高；同时第二排的人比第一排的对应的人要高，有几种排列方式；
隐藏的卡特兰问题：
将 12 个人编号，1~12；站在第一排的为（，站在第二排的人为）；如果出现了不匹配的括号，那么说明不合法；
现在问题变成：任意前缀不能出现）比（多的情况；
结果依然是例题 1 的结果；