卡塔兰数是组合数学中一个常在各种计数问题中出现的数列。

$Catalan(0) = 1，Catalan(n) = C^n_{2n}-C^{n+1}_{2n} = \frac{C^n_{2n}}{n+1}$

为了更快地计算，又得到：

$Catalan(0) = 1，Catalan(n+1) = \frac{4n+2}{n+2}Catalan(n)$

public int catalan(int n) {
    long c = 1;
    for (int i = 0; i < n; i++) {
        c = c * (4 * i + 2) / (i + 2);
    }
    return (int)c;
}

1、1、2、5、14、42、132、429……

理解应用

出栈次序问题

一个无穷大栈的进栈序列为1,2,3,…n，有多少个不同的出栈序列?
找零钱（找一半）

有 2n 个人排成一行进入剧场。入场费 5 元。其中只有 n 个人有一张 5 元钞票，另外 n 人只有 10 元钞票，剧院无其它钞票，问有多少中方法使得只要有 10 元的人买票，售票处就有 5 元的钞票找零？
三角网格

形如这样的直角三角形网格，从左上角开始，只能向右走和向下走，问总共有多少种走法？
括号排列

矩阵连乘，共有（n+1）项，依据乘法结合律，不改变其顺序，只用括号表示成对的乘积，试问有几种括号化的方案？或者说：有n对括号，可以并列或嵌套排列，共有多少种情况？
球盒问题

球分两种颜色，黑色和白色分别各有n只，盒子数量和球的个数相同，每个盒子里面只能放一只球，并且必须满足如下限制,即每一个白球必须和一只黑球配对（白球在黑球前，允许嵌套）。

例.用0表示白球，1表示黑球，则：

0011，010101，001011合法。

1100，101010，010110不合法。
最适合理解的模型

n个0和n个1组成一个2n位的2进制数，要求从左到右扫描时，1的累计数始终都小于等于0的累计数，求满足条件的数有多少？

理解方式

模型	事件1	事件2
(1)	入栈	出栈
(2)	用5元支付	用10元支付
(3)	向下走	向右走
(4)	左括号	右括号
(5)	0	1
(6)	0	1

同列事件可视为等价，且在题目要求中事件1的次数/大小需要始终大于事件2。

观察模型 6：在2n位上填入n个0的方案数为 $C^n_{2n}$ 。而从 $C^n_{2n}$ 中减去不符合要求的方案数即为所求答案。

在从左往右扫时，必然会在某一个奇数位 $2p+1$ 上首先出现 $p+1$ 个 1，和 $p$ 个 0

此后的 $[2p+2, 2n]$ 上的 $2n−(2p+1)$ 位有 $n−p$ 个 $0$ ， $n−p−1$ 个1。如若把后面这部分 $2n−(2p+1)$ 位的 1 与 0 互换，使之成为 $n−p$ 个 1， $n−p−1$ 个 0，结果得 1 个由 $n+1$ 个 1 和 $n−1$ 个 0 组成的 $2n$ 位数，即一个不合法的方案必定对应着一个由 $n+1$ 个 1 和 $n-1$ 个 0 组成的一个排列。

于是，不合法的方案数就可以写作： $C^{n+1}_{2n}$

所以

$Catalan(n) = C^n_{2n}-C^{n+1}_{2n} = \frac{C^n_{2n}}{n+1}$

类似题目

将多边行划分为三角形问题。将一个凸多边形区域分成三角形区域的方法数?
有 N 个节点的二叉树共有多少种情形？
- 有 N 个结点且不同的 BST
一位大城市的律师在她住所以北n个街区和以东n个街区处工作。每天她走2n个街区去上班。如果他

从不穿越（但可以碰到）从家到办公室的对角线，那么有多少条可能的道路？