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