卡特兰数
卡特兰（Catalan）数来源于卡特兰解决凸n+2边形的剖分时得到的数列，在数学竞赛、信息学竞赛、组合数学、计算机编程等方面都会有其不同侧面的介绍．卡特兰问题的解决过程应用了大量的映射方法，堪称计数的映射方法的典范．为了便于读者理解，我们先介绍一些卡特兰问题的简单变形，再介绍卡特兰问题及其解法．
问题一 进出栈
栈是一种先进后出（FILO，First In Last Out）的数据结构．
如上图所示，一个足够大的栈的进栈序列为时有多少个不同的出栈序列？
首先，每一种进出栈的顺序都与出栈序列一一对应,如果我们用push,用pop表示进栈，表示出栈，那么出栈序列231对应的进出栈顺序
（push,push,pop,push,pop,pop)
那么对个n数的序列，总的进出栈序列有c(n,2n)种。是这样吗？
答案是否定的，这是因为出栈的前提是有进栈动作，于是要求每个排列中的前若干项和均不为负数，也就是说排列
是无效的．
那么无效的排列到底有多少呢？
考虑是所有无效的排列构成的集合，考虑其中第一次发现排列无效的时候，也就是第一次发现其前若干项和为的时候，此时我们将包含使得前若干项和为的这一项开始的之前的所有项全都取相反数，那么就会得到一个新的排列，这个排列包含个，以及个，设所有这样的排列构成集合．
显然，这个的映射是一一映射（中的每一个排列从第一项往后累积求和的时候必然会出现和为的情形，此时将排列中使得和为的这一项连同之前的所有项全部取相反数，那么就会得到中的一个排列）．
因此无效的排列共有个．
综上，所有不同的出栈序列总数为，即．
进出栈问题的一个简单变形就是二叉树问题：
求个叶子的满二叉树的个数，如图8．
QQ20151105-6
图8 n+1个叶子的满二叉树的个数问题
事实上，向左记为，向右记为，按照向左优先的原则，从根节点开始遍历．例如第一个图记为
于是由卡特兰数的含义可得满二叉树的个数为．