关于“小贩找零”的问题-卡特兰数

关于“小贩找零”的问题-卡特兰数 关于“小贩找零”的问题——解卡特兰数 题目:小贩早上未带零钱出去卖煎饼，煎饼定价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均匀站位只有一可能，即后面4个空各一个。B还可以分组成1-1-2，1-2-1，2-1-1，2-2，1-3，3-1，4。如果是1-1-2，除了2个B要求在最后的空位，前面的1可以任意站位，则方式有3种。其它各种站位的对应分配数量如下。 分组方式 1-1-1-1 1-1-2 1-2-1 2-1-1 2-2 1-3 3-1 4 对应可能 1 3 2 1 2 3 1 1 合计:14种。 那么总计排队方式为4～*4～*14=8064。 至此题目已经找到，但是这种枚举的方式无法推广，如果是更多的人来买煎饼，又如何解答呢,必须需找一种一般性的方法。设买煎饼的人数为2n，排队方法总数为s(n)，AB相互穿插的方法数为f(n)。s(n)= f(n)*n!*n!。 我们换一个思路，如下左图 因为每一个B之前都必须有一个A，那么我们画一个路线图。向右一格表示一个A的行为，向上一格表示一个B的行为，只允许向上和向右。这样就保证了每一个B发生时，前面有足够的A，那么从起点到达终点的路线数量即排队的方式数f(4)。下面我们来逐步计算各路段到达的方式数量，寻找规律。 当从起点到达a点时，路线仅有一条，之后分为2条路段，但是到达各路段的路线都是1条，标记1。到达b点时，也是一条路线分成两条，到达各路段的路线也都是1，标记1。到达c点时，1条路线依然1条，标记1。到达d点后，有2条路线汇入，那么之后的路段也就有两条前置路线，到达方式就有了2种 可能，则之后的路段标记为2。以这种方式将所有的路线标记完成，如上右图。最终到达终点的路线方式为14条。 那么这组数字有什么规律呢，我们单看竖线。很明显:每一条竖线上的数字都等于下一行左方的所有竖线上数字之和如14=5+9，9=2+3+4，因为他们都是在“向上向右”的规则下能到达该路段的。我们扩展这个数列，翻转一下，如下图。 第一列表示行数，斜线上的数字为我们要求得的结果。那么这个数字塔有什么规律呢,第一行都是1，第二行是缺少1的顺序数，第三行是自然数的求和减1，因为上一行少了1，第四行无法直接看出。那么我们注意到二三行发生影响， 补齐，再察看一下规律，如下图。 我们将左方的空位 n-1这列数字规律可以推导获得，也能猜想获得，那就是g(n)=C，2n-2g(4)=6*5*4/1*2*3=20。那么可以猜想，我们要求的数字的规律也有可能是这样一 y种结构:f(n)=kC。 x 下面我们来做分解因式，看看各个数值是由哪些数值相乘得到的。将我们要求的各个数值做简单的因式分解，为便于查看4不再分解，如下图。 按照上面的猜想，我们将f(12)=208012的因子补齐成连续的形式，因为包含23和17两个较大的质数，34太大不考虑。那么至少要补上22，21，20，18。此时我们发现，f(12)=(23连乘到17)/(11*10*9*6)，分子已经连续了，分母还未连续，如下图:上面为分子的因子，下面为分母的因子，商为f(12)=208012。 对于组合C的算法，分子是从1开始连乘的，那么我们尝试将分子从1补齐到11，发现分子补上16*15*14后，分子比分母多一个因子2。再观察发现，分母可以增加一个24，分子可以增加一个12，则商恰好等于208012，此时分子分母都连续了。同样的方式，我们再分析f(9) 、f(10)和f(11)，得到图表如下， 同样上面为分子的因子，下面为分母的因子。 n很容易可以看出，f(n)= = C/(n+1)=2n!/[(n!*n!)*(n+1)]，这与开始的猜想也2n 是吻合的。 那么原题的答案s(4)=4!*4!*C84/5=8!/5=8064。到此，这个问题算是解答完成。从答案的形式看，应该有更简单的算法，确切的说，是更简单的理解方法，欢迎大家讨论。 :卡塔兰数是组合中一个常出现在各种计数问题中出现的数例。由比利时的数学家欧仁?查理?卡塔兰(1814-1894)命名。