catalan卡塔兰数是组合数学中一个常出现在各种计数问题中出现的数例。由比利时的数学家欧仁·查理·卡塔兰（1814-1894）命名。 www.wkfxw.com，免费收集整理

方法/步骤

题目：小贩早上未带零钱出去卖煎饼，煎饼定价5元一个。8个人来买煎饼，其中4人只有5元钞票各一张，另4人只有10元钞票，每人要买一个煎饼。问：有多少种排队购买方式才能保证小贩顺利完成交易？

分析：10元买主（设为B）买煎饼时需要找零，那么前面必须有5元买主（设为A）买过煎饼。

下面开始解答：

首先我们假设一种最简单的情况，4个5元买主先买，4个10元买主后买。那么4个A排队方式有4！，总共排队方式有4！*4！。但是A和B可以穿插，这种穿插方式有多少呢？

4个A排队有5个空位，其中队首空站位数小于等于0，第二个空站位数小于等于1……最后一个空站位数小于等于4。4个B以1-1-1-1均匀站位是一种，B还可以分组成1-1-2，1-2-1，2-1-1，2-2，1-3，3-1，4。如果是1-1-2，除了2个B要求在最后，前面的1可以任意站位，方式有3种。其它各种站位的对应分配数量如下表。

合计：14种。

那么总计排队方式为4！*4！*14=8064。

至此题目已经找到答案，但是这种枚举的方式无法推广，如果是更多的人来买煎饼，又如何解答呢？必须寻找一种一般性的方法。

我们换一个思路，如下图

相右一格表示一个A的行为，向上一格表示一个B的行为，只允许向上和向右，保证每一个B行为前有足够的A,从起点到达终点的路线数量即排队的方式。下面我们来逐步计算各路段到达的方式数量，寻找规律。

当从起点到达a点时，路线仅有一条，之后分为2条路段，但是到达各路段的路线都是1条，标记1。到达b点时，也是一条路线分成两条，各路段的路线也都是1，标记1。到达c点时，1条路线继续变成1条，标记1。到达d点后，有2条路线汇入，那么之后的路段也就有两条前置路线，之后的路段标记为2。以这种方式将所有的路线标记完成，如上图。最终到达终点的路线方式为14条。

那么这组数字有什么规律呢，我们先单看竖线。很明显：每一条竖线上的数字都等于下一行左方的所有数字之和如14=5+9，9=2+3+4，因为加数路段都是在“向上向右”的规则下能到达和数路段的。我们扩展这个数列到12，翻转一下，如下图。

第一列表示行数，即n，斜线上的数字为我们要求得的结果，即f(n)。那么这个数字塔有什么规律呢？除了每个数字等于上一行左方所有数字之和；第一行都是1，第二行是缺少1的顺序数，第三行是自然数的求和减1，因为上一行少了1，第4行就看不出来了。那么他们将左方的补齐，察看一下规律，如下图。

这列数字规律可以推导获得，也能猜想获得，那就是f(n)=C2n-2n-1，f(4)=6*5*4/1*2*3=20。那么可以猜想，我们要求的数字的规律也有可能是这样一种结构kCxy。

下面我们来做分解因式。将我们要求解的各个数值（第二列）做简单的因式分解。

按照上面的猜想，我们将f(12)=208012的因子补齐成连续的形式，因为包含23和17两个较大的质数，34太大不考虑，那么至少要补上22，21，20，18。此时我们发现，f(12)=23连乘到17除以11*10*9*6，分母已经连续，分子未连续。如下图

很容易可以看出，f(n)= C2nn-1/n=C2nn/(n+1)=2n!/[(n!*n!)*(n+1)]，这与开始的猜想也是吻合的。f(4)=C83/4=8*7*6/(4*3*2)=14。

原题的答案可以写成s(n)=2n!/(n+1)，s(4)=8!/5=8*7*6*4*3*2=8064。到此，这个问题算是解答完成。不过，从答案的构成看，应该有更简单的算法，确切的说，是更简单的理解方法：如全排列后，只有n+1分之一的排列有效，n+1为n个单位产生的空位数。