Catalan数，即卡特兰数（英语：Catalan number），又称明安图数，是组合数学中一种常出现于各种级数问题中的数列。以比利时的数学家欧仁·查理·卡特兰的名字来命名。
它是指满足以下递推关系的数列：
$$ C_{n+1}=C_0C_n+C_1C_{n-1} + \cdots + C_{n-1}C_1 + C_nC_0 $$Catalan数的递推关系很简单，乍看之下没什么特别的，但是Catalan数却是许多计数问题的最终形式。Stanley的Enumerative Combinatorics一书中就囊括了上百个最后可以归结为Catalan数的问题，所以它的重要性不言而喻。接下来我们从上述递推关系的解开始，一步步探讨Catalan数的一些经典应用。
求解 Catalan 数
由于 Catalan 数的递推关系并不是线性的，所以它的求解方法比较复杂。这里我们通过生成函数（母函数）来求解 Catalan 数的递推关系。
根据Catalan数的递推关系，我们设$C_0=C_1=1$。
$$ C_1 = C_0C_0=C_0^2 $$设函数$C_n$的生成函数为$G(x)$：
$$ G(x) = C_0 + C_1x+C_2x^2 + \cdots $$根据递推关系，有
$$ \begin{array}{cc} x^2:& C_2=C_0C_1 + C_1C_0 \\ x^3:& C_3=C_0C_2 + C_1C_1 + C_2C_0 \\ x^4:& C_4=C_0C_3 + C_1C_2 + C_2C_1 + C_3C_0 \\ &\vdots\\ x^n:&C_n=C_0C_{n-1}+C_1C_{n-2} + \cdots + C_{n-1}C_0\\ &\vdots\\ \end{array} $$对上式求和，有
$$ \begin{aligned} C_2x^2+C_3x^3+\cdots=& \;C_0(C_1x^2+C_2x^2+\cdots) \\ &+C_1(C_0x^2+C_2x^3+\cdots)\\ &+C_2(C_0x^3+C_1x^4+\cdots)\\ &+\cdots \\ G(x)-x-1=&\; C_{0}x\left(C_{1} x+C_{2} x^{2}+\cdots\right) \\ &+C_{1} x^2\left(C_{0} +C_{1} x+\cdots\right) \\ &+C_{2} x^{e}\left(C_{0} +C_{1} x+\cdots\right)+\cdots \\ =& -x+ C_{0}x\left(C_0 +C_{1} x+C_{2} x^{2}+\cdots\right) \\ &+C_{1} x^2\left(C_{0} +C_{1} x+\cdots\right) \\ &+C_{2} x^{e}\left(C_{0} +C_{1} x+\cdots\right)+\cdots \\ =& -x+ (C_{0}x + C_1x^2+\cdots)\left(C_0 +C_{1} x+C_{2} x^{2}+\cdots\right) \\ =& -x +xG^2(x) \end{aligned} $$于是得到一个关于$G(x)$的二次方程：
$$ xG^2(x)-G(x)+1=0 $$解之即得：
$$ G(x)=\frac{1\pm\sqrt{1-4x}}{2x} $$考虑到牛顿二项式定理：
$$ (1+x)^{\frac12} = 1 + x+\frac{\frac12(\frac12 -1)}{2!}x^2+\frac{\frac12(\frac12 -1) (\frac12 -2)}{3!}x^3 + \cdots $$则$\sqrt{1-4x}$可以表示为：
$$ \sqrt{1-4x} = 1 + (-4x)+\frac{\frac12(\frac12 -1)}{2!}(-4x)^2+\frac{\frac12(\frac12 -1) (\frac12 -2)}{3!}(-4x)^3 + \cdots $$其中$x^{n+1}$的系数为：
$$ \begin{align} \frac{\frac12 (\frac12 -1)\cdots(\frac12 -n)}{(n+1)!}(-4)^{n+1} =& \;(-1)^{n+1}\frac{\frac12 (\frac12 -1)\cdots(\frac12 -n)}{(n+1)!}4^{n+1}\\ =& \;(-1)^{n+1}\frac{(1 -2)\cdots(1 -2n)}{(n+1)!}2^{n+1}\\ =& -\frac{(2-1)\cdots(2n-1)}{(n+1)!}2^{n+1}\\ =& -2\frac{1\cdot 3\cdot 5\cdots (2n-1)\cdot n!}{(n+1)!n!}2^{n+1}\\ =& -2\frac{1\cdot 3\cdot 5\cdots (2n-1)\cdot 1\cdot2 \cdot4\cdots 2n}{(n+1)!n!}\\ =& -2\frac{2n!}{(n+1)!n!}\\ =& -2\frac{2n!}{(n+1)(n!)^2}\\ =& -2\frac{1}{n+1}\binom{2n}{n} \end{align} $$注意到$G(x)$的系数应当为正，所以
$$ G(x)=\frac{-1 - \sqrt{1-4x}}{2x} $$其中$x^n$的系数为：
$$ C_n=\frac{1}{n+1}\binom{2n}{n} $$这便是卡特兰数的计算公式。
应用
括号匹配问题
$n$对括号有多少种匹配方式？
$n$对括号相当于有$2n$个符号，$n$个左括号、$n$个右括号，可以设问题的解为$f(2n)$。第$0$个符号肯定为左括号，与之匹配的右括号必须为第$2i+1$个字符。因为如果是第$2i$个字符，那么第$0$个字符与第$2i$个字符间包含奇数个字符，而奇数个字符是无法构成匹配的。
通过简单分析，$f(2n)$可以转化如下的递推式
$$ f(2n)=f(0)f(2n-2)+f(2)f(2n-4)+\cdots+f(2n-4)f(2)+f(2n-2)f(0) $$简单解释一下，$f(0)f(2n-2)$表示第$0$个字符与第$1$个字符匹配，同时剩余字符分成两个部分，一部分为$0$个字符，另一部分为$2n-2$个字符，然后对这两部分求解。$f(2)f(2n-4)$表示第$0$个字符与第$3$个字符匹配，同时剩余字符分成两个部分，一部分为$2$个字符，另一部分为$2n-4$个字符。依次类推。
结合Catalan数的递归式，不难发现$f(2n)$等于$C_n$。
除次之外，我们还可以从另一个角度考虑这个问题。我们假设括号串是和法的，则$n$对括号，除了最外层的一对，剩下的$n-1$对括号可以分为$0$和$n$对，$1$和$n-1$对，依次类推。设$T(n)$为$n$对括号的匹配数。则根据乘法原理，有
$$ T(n) = T(0)T(n-1) + T(1)T(n-2) + \cdots + T(n-1)T(0) $$$T(n)$的解同样是Catalan数。
进栈出栈问题
一个栈（无穷大）的进栈序列为
1，2，3，...，n，有多少个不同的出栈序列?
这个与加括号的很相似，进栈操作相当于是左括号，而出栈操作相当于右括号。$n$个数的进栈次序和出栈次序构成了一个含$2n$个数字的序列。第$0$个数字肯定是进栈的数，这个数相应的出栈的数一定是第$2i+1$个数。因为如果是$2i$，那么中间包含了奇数个数，这奇数个肯定无法构成进栈出栈序列。
设问题的解为$f(2n)$，那么
$$ f(2n)=f(0)f(2n-2)+f(2)f(2n-4)+\cdots+f(2n-4)f(2)+f(2n-2)f(0) $$$f(0)f(2n-2)$表示第$0$个数字进栈后立即出栈，此时这个数字的进栈与出栈间包含的数字个数为$0$，剩余为$2n-2$个数。$f(2)f(2n-4)$表示第$0$个数字进栈与出栈间包含了$2$个数字，相当于$1221$，剩余为$2n-4$个数字。依次类推。
结合Catalan数的递归式，不难发现$f(2n)$等于$C_n$。
二叉树的种类问题
$n$个节点构成的二叉树，共有多少种情形？
可以这样考虑，根肯定会占用一个结点，那么剩余的$n-1$个结点可以有如下的分配方式，$T(0,n-1),T(1,n-2),\cdots T(n-1,0)$，设$T(i,j)$表示根的左子树含$i$个结点，右子树含$j$个结点。
设问题的解为$f(n)$，那么
$$ f(n)=f(0)f(n-1)+f(1)f(n-2)+\cdots+f(n-2)f(1)+f(n-1)f(0) $$结合Catalan数的递归式，不难发现$f(n)$等于$C_n$。
网格路径问题
对于一个$n\times n$的正方形网格，每次我们能向右或者向上移动一格，那么从左下角到右上角的所有在副对角线右下方的路径总数为多少？
首先尝试转化问题为我们熟悉的类型。我们将一条水平边记为进栈，垂直边记为出栈，那么我们所要保证的就是前$k$步中水平边的个数不小于垂直边的个数，换句话说出栈的时候栈内一直有元素，所以从根本上说又回归到Catalan数了。对比进栈出栈问题，只需将含有$f(0)$的两项去掉，此时我们得到的递推关系为：
$$ f(2n)=f(2)f(2n-4)+\cdots+f(2n-4)f(2) $$解出后即可得
$$ T(n)=f(2n)=C_{n-1} $$接下来介绍该问题的另一种思路。我们知道，对于$n\times n$网格，从左下角到右上角的路径数$T(n)$为：
$$ T(n) = \binom{2n}{n} $$但题目所求的是所有位于对角线之下的路径数。
首先注意到，所有终点为$(n,n)$的路径，若仅位于对角线下方，则它必来自$(n,n-1)$，所以我们只需考虑点$(0,0)$到点$(n,n-1)$的路径数。
接下来我们可以考虑建立一个一一对应关系，注意到所有从$(0,0)$点出发的路径的下一个点要么是$(0,1)$，要么是$(1,0)$。而所有自$(1,0)$出发的路径，倘若与对角线有交点，则一定有唯一的一条自$(0,1)$出发的路径与之对应；反之，所有从$(0,1)$到$(n,n-1)$的路径，一定有一条$(1,0)$到$(n,n-1)$的路径与之对应。
如下图所示，图中的橙色路径与黑色路径关于$y=x$对称，他们之间构成一个一一对应关系。因此，所有从$(1,0)$到$(n,n-1)$且位于对角线下方的路径数等于所有从$(1,0)$到$(n,n-1)$的路径数减去所有从$(0,1)$到$(n,n-1)$的路径数。
根据上图的思想，我们设$T(n)$为题目要求的路径数，可列式如下：
$$ \begin{align} T(n)&=\binom{2n-2}{n-1}-\binom{2n-2}{n}\\[2ex] &= \frac{(2n-2)(2n-1)\cdots(n)}{(n-1)!} -\frac{(2n-2)(2n-1)\cdots(n-1)}{n!}\\[2ex] &= \frac{(2n-2)(2n-1)\cdots(n)}{(n-1)!} \left(1-\frac{n-1}n \right)\\[2ex] &= \binom{2n-2}{n-1}\frac1n\\[2ex] &= C_{n-1} \end{align} $$于是我们又回到了Catalan数。我们可以稍加验证一下，$n=1$及$n=2$时，只有一条路径，正确。$n=3$时，有两条路径，同样正确。
总而言之，进栈出栈且要求栈内始终不为空的问题的解为$T(n)=C_{n-1}$
凸多边形分割问题
求一个凸多边形区域划分成三角形区域的方法数？
以凸多边形的一边为基，设这条边的$2$个顶点为$A$和$B$。从剩余顶点中选$1$个，可以将凸多边形分成三个部分，中间是一个三角形，左右两边分别是两个凸多边形，然后求解左右两个凸多边形。
设问题的解$f(n)$，其中$n$表示顶点数，那么
$$ f(n)=f(2)f(n-1)+f(3)f(n-2)+......f(n-2)f(3)+f(n-1)f(2) $$$f(2)f(n-1)$表示三个相邻的顶点构成一个三角形，那么另外两个部分的顶点数分别为$2$和$n-1$。
注意上述的递推式中，$n$是从$2$开始的，回忆我们求解Catalan数的过程，不难发现$f(n)$等于$C_{n-2}$。
集合划分问题
对于集合$\{1,2,3\cdots2n\}$的不交叉划分的数目为多少？
这里解释一下不交叉划分，我们对于集合{a,b}和{c,d}，假设他们组成了两个区间$[a,b]$和$[c,d]$，我们假设两个区间不重合，那么以下四种情况当做是不交叉的：$a 对于集合$\{1,2,3\cdots2n\}$，将里面元素两两分为一子集，共$n$个，若任意两个子集都是不交叉的，那么我们称此时的这个划分为一个不交叉划分。此时不交叉的划分数就是我们的Catalan数了，证明也很容易，我们将每个子集中较小的数用左括号代替，较大的用右括号代替，那么带入原来的$1$至$2n$的序列中就形成了合法括号问题，就是我们之前得到过的结论。例如我们的集合$\{1,2,3,4,5,6\}$的不交叉划分有五个： $\{\{1,2\},\{3,4\},\{5,6\}\}$ $\{\{1,2\},\{3,6\},\{4,5\}\}$ $\{\{1,4\},\{2,3\},\{5,6\}\}$ $\{\{1,6\},\{2,3\},\{4,5\}\}$ $\{\{1,6\},\{2,5\},\{3,4\}\}$ 求$n$层的阶梯切割为$n$个矩形的切法数 这个证明是怎么进行的呢？我们先绘制如下的一张图片，即n为5的时候的阶梯： 我们注意到每个切割出来的矩形都必需包括一块标示为#的小正方形，那么我们此时枚举每个与#标示的两角作为矩形，剩下的两个小阶梯就是我们的两个更小的子问题了，于是
注意到这里的式子就是我们前面的性质3,因此这就是我们所求的结果了。 矩阵链乘：$P=a_1\cdot a_2\cdot a_3\cdots a_n$，依据乘法结合律，不改变其顺序，只用括号表示成对的乘积，试问有几种括号化的方案？ 我们这样考虑，首先通过括号化，将$P$分成两个部分，然后分别对两个部分进行括号化。比如分成$(a_1)×(a_2×a_3\cdots an)$，然后再对$(a1)$和$(a_2×a_3\cdots a_n)$分别括号化；又如分成$(a_1×a_2)×(a_3\cdots a_n)$，然后再对$(a_1×a_2)$和$(a_3\cdots a_n)$括号化。 设$n$个矩阵的括号化方案的种数为$f(n)$，那么问题的解为
表示分成$(a_1)×(a_2×a_3\cdots a_n)$两部分，然后分别括号化。 计算开始几项，$f(1)=1$，$f(2)=1$，$f(3)=2$，$f(4)=5$。结合递归式，不难发现$f(n)$等于$C_{n-1}$。 在圆上有$2n$个点，将这些点成对连接起来使得所得到的$n$条线段不相交的方法数？ 我们这样考虑，以其中一个点为基点，编号为$0$，然后按顺时针方向将其他点依次编号。那么与编号为$0$相连点的编号一定是奇数，否则，这两个编号间含有奇数个点，势必会有个点被孤立，即在一条线段的两侧分别有一个孤立点，从而导致两线段相交。设选中的基点为$A$，与它连接的点为$B$，那么$A$和$B$将所有点分成两个部分，一部分位于$A$、$B$的左边，另一部分位于$A$、$B$的右边。然后分别对这两部分求解即可。 设问题的解$f(2n)$，那么
$f(0)f(2n-2)$表示编号0的点与编号$1$的点相连，此时位于它们右边的点的个数为$0$，而位于它们左边的点为$2n-2$。依次类推。 $f(0)=1$,$f(2)=1$,$f(4)=2$。结合递归式，不难发现$f(2n)$等于$C_n$。 $2n$个高矮不同的人,排成两排,每排必须是从矮到高排列,而且第二排比对应的第一排的人高,问排列方式有多少种? 先将$2n$个人从低到高排列，然后用$0$表示对应的人在第一排，用$1$表示对应的人在第二排，那么含有$n$个$0$，$n$个$1$的序列，就对应一种方案。
比如$00\cdots011\cdots1$就对应着
第一排：$1,2,3,\cdots, n$
第二排：$n+1,n+2,n+3,\cdots,2n$ 而$010101\cdots01$对应着 第一排:$1,3,5,\cdots,2n-1$
第二排:$2,4,6,\cdots,2n$ 问题转换为，这样的满足条件的$01$序列有多少个.
观察$1$的出现,我们考虑它能不能放在第二排,显然,在这个$1$之前出现的那些$0$和$1$对应的人要么是在这个$1$左边,要么是在这个$1$前面。而即使前面$0$和$1$刚好配对，也一定要留出一个$0$在这个$1$前面，也就是要求之前的$0$的个数大于$1$的个数。
如果把$0$看成入栈操作，$1$看成出栈操作,就是说给定$2n$个元素，合法的入栈出栈且栈不为空的序列有多少个。 参考网格路径问题，它的解是Catalan数$C_{n-1}$。 在一个$2\times n$的格子中填入$1$到$2n$这些数值使得每个格子内的数值都比其右边和上边的所有数值都小的情况数。 这一题和上一题排队是一样的思路。 有$2n$个人排成一行进入剧场。入场费$5$元。其中只有$n$个人有一张$5$元钞票，另外$n$人只有$10$元钞票，剧院无其它钞票，问有多少中方法使得只要有$10$元的人买票，售票处就有$5$元的钞票找零？ 可以将持$5$元买票视为进栈，那么持10元买票视为$5$元的出栈。这个问题就转化成了栈的出栈次序数。由应用三的分析直接得到结果，$f(2n)$等于$C_n$。阶梯切分问题
乘积重组问题
连线不相交问题
高矮排队问题
格子填数问题
门票找钱问题