在排列组合计算问题中，有一组有趣的数列，叫做“卡塔兰数(Catalan Numbers)”。卡特兰数的前10项分别为：1、1、2、5、14、42、132、429、1430、4862。
与斐波那契数列(Fibonacci Sequence)一样，卡塔兰数也是离散数学和编程算法中相当重要的数列，它以比利时的数学家欧仁·查理·卡塔兰(Eugene Charles Catalan，1814年~1894年)命名。
那么到底什么是卡塔兰数呢?让我们从简单的问题出发：有一只小蜗牛，要从森林的西南角(A点)爬到森林的东北角(B点)，它只能往东或者往北爬。请问：小蜗牛一共有多少种到达目的的走法?
学习过排列组合计算的同学对这个问题肯定不陌生，我们可以通过两种方式得到答案。
第一种，标数法。因为这里的走法恰好是一个帕斯卡三角形。
第二种，我们经过观察可以发现：小蜗牛从森林的西南角(A点)爬到森林的东北角(B点)，无论怎么走，都要走过10格;其中5次向东，5次向北。
于是，这个问题就变成了10选5的排列组合计算问题了，答案就是：
现在，我们再来看另外一个问题：儿童节时，游乐园搞促销活动，每个小朋友可以1元购买一张门票。现在10个小朋友排队购买，其中5个小朋友只有1元的纸币，另外5个小朋友只有2元的纸币，售票员没有准备零钱。请问：有多少种排法，可以使售票员总能找开零钱?
这个问题其实和前面的问题很类似。可以把这里横向的格子看成是只有1元纸币的小朋友，纵向的格子看成是只有2元纸币的小朋友，假如没有售票员找零的限制，这个问题和前面的小蜗牛爬格子的方法极为相似。只是由于这10个小朋友是不同的个体，所以还有一个排列的顺序问题，很容易处理，不是这里的重点。
然而，有了售票员找零的限制条件，这个问题就变得不同了。排在第1位的必须是持有1元纸币的小朋友，第2位可以是持有1元纸币的小朋友也可以是持有2元纸币的小朋友;如果第2位是持有1元纸币的小朋友，第3位可以是持有1元纸币的小朋友，也可以是持有2元纸币的小朋友;但如果第2位是持有2元纸币的小朋友，则第3位必须是持有1元纸币的小朋友;……;以此类推。最后出现了如下图所示的情况：
也就是说，无论怎么排列顺序，都不可能越过这条红色的对角线。细心的小朋友可能已经发现，这条对角线上的标数，正好就是我们在一开始提到的卡塔兰数。
那么我们如何用排列组合计算的原理，得到这些卡塔兰数呢?卡塔兰数又与普通的排列组合计算问题有什么内在的逻辑关系呢?让我们依旧回到小蜗牛的问题上来。
假如连接森林A、B两地有一条河流，并且A、B两地都位于这条河流的东侧，小蜗牛不会游泳，那么它只能在河流的一边行走，于是范围只限于河流东边的二分之一森林。
如果我们用字母E表示往东走，用字母N表示往东走，那么三条路径可以分别表示如下：
路径一，紫色路径：
ENENEENENN
路径二，蓝色路径：
EENENNENEN
路径三，绿色路径：
EEENENENNN
不难发现，这些路径的第一步都是往东走(E)，到达终点时的最后一步都是往北走(N)。我们知道，假如没有河流的限制，全部的走法就是C(10,5)=252种。这些走法中包含了没有跨过河流的(符合条件的)和跨过河流的(不符合条件的)。如果我们从全部的走法可能性中，减去跨过河流的走法，那么剩下的就是没有跨过河流的走法。
我们能否直接从路径的字母序列中判断出这个路径是否符合题目条件的要求呢?答案是肯定的。如果小蜗牛没有跨过河流，那么从起点出发，无论在整个路径的任何时候，往东走过的格子数都不会少于往北走的格子数，最多是两者相等。
现在，问题的核心就归结到如何找到不符合条件的路径数。这里，不符合条件的路径就是从左往右看，N的个数会在某个时候大于E的个数的字母序列，比如：
ENENNEENEN
EENNENNEEN
当我们看ENENNEENEN这串字母序列时，第5个字母就已经代表小蜗牛跨过了河流。现在让我们把第5个字母后面的E全部用N来替换，N全部用E来替换，可以得到：ENENNNNENE。在这串字母序列里，有4个字母E和6个字母N。这个结果很好理解。因为第5个字母时，字母N已经比字母E多了1个，第5个字母后面的字母N自然比字母E少1个;经过互相转变后，第5个字母后面的字母N又会比字母E多1个;综合起来，最后的序列里字母N会比字母E多2个。
再看第二个例子EENNENNEEN。从第7个字母N开始，小蜗牛就跨过了河流。再次用上面的方法进行转换，得到EENNENNNNE。我们发现，转换后的字母序列中，依旧有4个字母E和6个字母N。
同学们可以继续尝试，最后我们会发现，对于任何一个由5个E和5个N组成不符合题目条件的字母序列，经过上述的转换，都能得到一个包含4个字母E和6个字母N的字母序列。并且任意两个不同的不符合题目条件的字母序列经过转换之后所得到的，一定是两个不相同的各自包含4个字母E和6个字母N的字母序列。换句话说，这种转换是“一对一(one-to-one)”的。
另一方面，我们还需要确定的问题是：任意一个包含4个字母E和6个字母N的字母序列，是否都是由某个包含5个字母E和5个字母N组成的不符合题目条件的字母序列所转换而来的?答案也是肯定的。对于任意一个由4个字母E和6个字母N所组成的字母序列，从左往右看，字母N的个数一定会在某个时候第一次超过字母E的个数。我们将这个字母N之后所有的字母E以字母N替代，所有的字母N以字母E替代，所得到的结果一定是由5个字母E和5个字母N组成的不符合题目条件的字母序列。
因此，这种转换不仅是“一对一”的，而且还是“满射(onto)”的，即：所有包含4个字母E和6个字母N的字母序列与所有包含5个字母E和5个字母N的字母序列之间存在着某种“映射(bijection)”关系。也就是说，由5个字母E和5个字母N组成的不符合题目条件的字母序列数等于由4个字母E和6个字母N所组成的字母序列。
于是，我们可以得到小蜗牛不跨过河流的走法一共有：
我们还可以从几何图形的角度来理解这个问题。
为了图形处理方便，我现在假设小蜗牛只能在河流的左边部分爬行。如下图所示：
我把小蜗牛跨过河流的路径进行翻转，如下图所示。
情形一：
情形二：
情形三：
那么，现在的问题就转换为：从A点到B点的全部线路可能性，剔除从A点到C点的线路可能性后的走法一共有多少种?
从A点到C点可能的走法为C(2n，n-1)可以用下面的图来表示：
因此，我们可以最终得到卡塔兰数的计算方法为：
读者朋友们可以自行验证一下最后的结果是否就是卡塔兰数。
卡塔兰数在排列组合计算问题中有着非常广泛的应用，尤其是在计算机编程的算法上更有其重要的地位。
比如：P=A1×A2×A3×……×An，依据乘法结合律，不改变其顺序，只用括号表示成对的乘积，试问有几种括号化的方案?
( ( ( ) ) ) ( )
( ( ( ( ) ) ) )
( ( ( ) ) ( ) )
……
又比如：甲乙两人比赛乒乓球，最后结果为20∶20，问比赛过程中甲始终领先乙的计分情形的数。即甲在得到1分到19分的过程中始终领先乙，其情形数就是卡特兰数。
又比如：将一个凸多边形区域分成三角形区域(划分线不交叉)的方法数有多少?
类似的问题如：在圆上选择2n个点,将这些点成对连接起来使得所得到的n条线段不相交的方法数?
这个问题可以应用在这样的场景中：有2n个人围着圆桌而坐，有几种方式可以让每个人同时伸出一只手与另一个人握手，同时不会发生手臂互相重叠的情形?当n=3时，总共有如下五种握手的可能性：
据说目前已经有50多种数学模型都是建立在卡塔兰数之上。在很多关于排列组合计算和离散数学的书中，都有卡塔兰数的介绍。有兴趣的读者朋友可以看美国著名的排列组合计算专家Richard P. Stanley所写的书，比如下面这本书：
历史上，全世界有很多数学家都研究过卡塔兰数，这其中也包括大数学家欧拉。
清代数学家明安图(1692年~1763年)在其《割圜密率捷法》中最先发明这种计数方式，远远早于比利时数学家卡塔兰。有中国学者建议将此数命名为“明安图数”或“明安图-卡塔兰数”。
明安图，字静庵，亦那木都鲁氏，蒙古正白旗常舒保佐领(今内蒙古锡林郭勒盟正白旗)人。清朝天文学家、数学家。
青年时期被选入钦天监为官学生，学习天文、历法和数学,又从法国人杜德美学习艾萨克·牛顿的三个无穷级数展开式。康熙五十一年(1712年)，随康熙皇帝往承德避暑山庄，回答科学问题。又参加了《律在渊源》的编撰工作，两次赴新疆测绘地图。康熙六十年，任钦天监五官正。乾隆二年(1737年)参加编修《历象考成后编》。乾隆十六年(1751年)辛未翻译科进士。乾隆二十四年(1759年)，升任钦天监监正。卒于乾隆二十八(1763年)年。有一本数学名著《割圜密率捷法》四卷，是研究三角函数的重要书籍。明安图在书中最早发现了卡塔兰数。
