卡特兰数又称卡塔兰数，是组合数学中一个常出现在各种计数问题中出现的数列。以比利时的数学家欧仁·查理·卡塔兰 (1814–1894)命名。
前20项为（OEIS中的数列A000108）：1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190
用几个在OJ中经常遇到的问题来说下具体应用。
一个栈(无穷大)的进栈序列为1,2,3,..n,有多少个不同的出栈序列
2n人进剧院。入场费1元。n人有1元钞票，n人有2元钞票，剧院无钞票，有多少方式进场
以上面第二个为例，该题求的是左端点为首元素的任意区间内，1的个数大于等于2的个数。
可以认为问题是，任意两种操作，持1元者买票是操作一，持2元买票者是操作二。要求每种操作的总次数一样，且进行第k次操作2前必须先进行至少k次操作1。我们假设一个人在原点，操作1是此人沿右上角45°走一个单位（一个单位设为根号2，这样他第一次进行操作1就刚好走到（1,1）点），操作2是此人沿右下角45°走一个单位。第k次操作2前必须先进行至少k次操作1，就是说明所走出来的折线不能跨越x轴走到y=-1这条线上！在进行n次操作1和n此操作2后，此人必将到到达（2n，0）！若无跨越x轴的限制，折线的种数将为$C\tbinom{n}{2n}$，即在2n次操作中选出n次作为操作1的方法数。
只要减去跨越了x轴的情况数。对于任意跨越x轴的情况，必有将与y=-1相交。找出第一个与y=-1相交的点k，将k点以右的折线根据y=-1对称（即操作1与操作2互换了）。可以发现终点最终都会从（2n，0）对称到（2n，-2）。由于对称总是能进行的，且是可逆的。我们可以得出所有跨越了x轴的折线总数是与从（0,0）到（2n,-2）的折线总数。而后者的操作2比操作1要多0-（-2）=2次。即操作1为n-1,操作2为n+1。总数为$C\tbinom{n-1}{2n}$
这个证明的关键就是最终一定会到达（2n,0)这个点。
对于不满足情况的方案，它一定会越过y=-1，捉住这个特点，我们可将求不合法的方案数这个问题换个说法来：从（0，0）到（2n,-2)一共有多少种走法？这个走法数就是C(2n,n-1)因为走右下角的要多走2步，同时一共只走2n步，那就右下角走n+1步，为$C\tbinom{n-1}{2n}$
最终结果为$C\tbinom{n}{2n}-C\tbinom{n-1}{2n}$
