卡特兰数与数的表示法

注：摘自《奥数标准教程+习题精选+能力测试三合一》（六年级分册第12讲）北大出版社，陈拓著。第72讲图形标数法与卡特兰数1.图形标数法如图1.在4x5的方格表中，从左下角儿到右上角B的最短路线有多少条?图］ 图2 图3这是基本的最短路线问题，可以采用标数法.从4到S需要横着走5条线段，竖着走4条线段，对于每个基本的方格的右上角顶点，可以从左边再走一步，因此包括左边的“种走法；也可以从下边向上再走一步，也包括下边的/，种走法.根据加法原理，到每个右上角有（u+6）种最短路线，如图2.具体如图3标出.所以,从4到E的最短路线有126条.本题还有一种组合的解法.1）从4到E的最短路线共有9步，其中5横4竖.它们构成的任 ——F意一种排法，都对应一条最短路线.如“横横纵横纵纵横横纵”，即图4中的粗线. 2）根据相同对象排列，共有C；=126种. 月图42.卡特兰数卡特个数又称为卡塔丝数，是组合数学中一个经常出现的计数问题，用比利时数学家欧仁•查理•卡特子的名字加以命名.对于一个数列与吗，的，…%T,把它逆序排列成4_i ，…，4，然后对应项相乘得到n个乘积的和叫作逆序乘积之和，简称逆序和.记作：%=«o +«iXan_2+a2Xan_3+••+a„,2X%+an_iXa0.设q=1时，则第12讲图形标数法与卡特兰数%=a0Xa0 =1 X1=1,a2=xa\ +% xa0=1x1+1x 1=2,=a0xa2 + xai+a2 xa0=\ x2+ 1 x 1 +2x1 =5,a4=a0xa3 + x+a-, xaA+a3xa0 = 1 x 5 +1 x 2+2x1+5x1=14,如此，得到卡特兰数列为1,1,2,5,14,42,132,…卡特兰数的另一种表示方法为4=一二加,（〃20）.卡特兰数与阶梯最短路线标数法一一对应，如图1所示.卬二5卬二5为什么阶梯标数法与卡特兰数的结果相同呢？下面以5个1和5个。组成的十位数中，符合从左到右1的个数始终不少于。的个数的十位数共有多少个？推导过程如下.把1用一横表示，把0用一竖表示.则符合条件的十位数就是图2中从4到B的最短路线条数.1）我们想从图3中的最短路线的条数中排除一部分，从而就得到所求的结果.符合条件的就是图4中线段加以下的从4到8的最短路线的条数.图3的最短路线有C：o=252条，排除图5中的穿过线段A8的最短路线条数.2）对图5中的穿过AB的路线做出以下调整.当最短路线第一次越过线段AB后（保留这次），把后面横线变竖线，同时把竖线变横线，如图5中的粗线对应图6中的粗线.这样就会发现，穿过的最短路线与从4到"的最短路线一一对应.也就是说，图3中的最短路线条奥数六年级标准教程+习题精选+能力测试三合一数中不符合的最短路线(穿过，仍的路线)对应图6中4x6的方格表中从4到"的最短路线条数，共有C；。=210条.所以，图2中的最短路线有C：。-C：。==21。条.o一般地，〃个〃与〃个排成的2〃个字母串中，从左至右。的个数不少于/)的个数的字母另外，〃个Q、〃个以〃个C排成的3〃个字母串中，从左至右。的个数不少于〃的个数,且b的个数不少于c的个数的字母串个数为--(29M—―.n!x(n+l)!x(n+2)j〃个a、〃个〃、〃个c、〃个“排成的4〃个字母串中，从左至右a的个数不少于〃的个数,且的个数不少于。的个数，c的个数不少于d的个数的字母串个数为12x(4〃)！n!x(n+1)!x(〃+2)!x(n+3)!3如右图，按照向右或向上的方向，沿着方格线从4点走到3 |||||一点，其中C点不能通过，共有 种不同的走法. Q——【分析】行走方向确定，相当于求从4到8的最短路线.采用标数4III-A法，C点不能通过，可以在此处先标记0.【解答】如下图，先在c处标记0,然后从左下角到右上角标数，得到不同的走法共66种.15 252611另解：本题可以先考虑从4到8的最短路线条数，然后减去经过点。的最短路线条数,得到不同走法《-C；x=126-10x6=66条.【评注】本题给出的是行走的方向，并没有向下和向左的可能，不能走“I可头路”，所以所求是从4到8的最短路线条数.第12讲图形标数法与卡特兰数@）如右图，从4到8的最短路线共有@）如右图，从4到8的最短路线共有【分析】此题图形非不完整的矩形，就采用图形标数法吧.【解答】如下图标数，得到从4到3的最短路线共有42条.【评注】本题采用标数法求得最短路线条数.想一想，此题还可以再用组合法吗?【解答】如右图，从/1到N的最短路线有髭条.从N到M的最短路线有C；条.从M到B的最短路线有C；条.根据乘法原理，得到符合条件的走法共有C；xC：xC；=150种.【评注】小河上只有MN一座独木桥，如果从4到N标数，就是在2x4的长方形中标数，同时在从时到3标数，就是在2x3的长方形标数.可以试一试在下图的虚线中标数，得到正确答案.扫我听课扫我听课按右图中箭头所示的方向行走，从4点走到8点的不同路线共有条，港奥数六年级标准教程+习题精选+能力测试三合一【分析】按箭头方向进行标数，分析每个点上的标数是哪些数之和.【解答】如图标数，得到从人点走到3点的不同路线共有55条.【评注】本题按箭头方向行走，得到每个点处的标数.这些标数是不是很熟悉，排成一排看看.1,1,2,3,5,8,13,21,34,55.它是斐波那契数列的前几项吗？扫我听课扫我听课。如图是中国象棋棋盘的一部分.象棋中的“车”必须走直线（走几个边长都可以，就是不能拐弯）.如果一个“车”从4出发到&且路线最短，那么共有――—―种不同的走法.（“车”行两个边长，可以两步，每步一个边 长.也可以一步，一下子走两个边长，算不同的走法.） 力1~~~~【分析】“车”走直线.对于每个格点，这个格点左边的每个点都可以是“车”倒数第二步的位置，然后一下子到达该点.同样，这个点下边的每个点也是如此.因此，到达每个格点的走法包括其左边和下边所有点的走法，是它们所有走法的和.【解答】如下图，根据分析，采用图形标数法，得到“车”从4到3的走法有94种.2512【评注】本题采用图形标数法，根据实际情况，调整原来两个之和的一般标数法.这里是每个点前面和下面所有点的标数之和.除了掌握基本的标数法以外，要学会根据实际情况修改调整标数方法.,其中一个盒子放有4个相同的红球，另个盒子放有,其中一个盒子放有4个相同的红球，另个盒子放有3个相同的黄球.现在从两个盒子中把球全部取走.取球方法如下：①每次从一个盒子里取球，所取球数目不限；②每次从一个盒子里取球，每次最多取两个球;

第12讲图形标数法与卡特兰数③每次从两个盒子里各取一个球.那么，如果按要求①把球取完，共有种不同的取球顺序；如果按要求②③把球取完，共有 种不同的取球顺序.【分析】可以把红球看作一段“横线”，把黄球看作一段“竖线”.这样构造一个3x4的方格表.根据条件进行标数.【解答】画出3x4的方格表，满足条件①，每个格点处的标数是其左边和下边所有点上所标数之和.如图1所示，从4到8的不同走法有289条，对应289种不同的取球顺序.画出3x4的方格表，并画出每个小正方形从左下到右上的对角线.根据条件②，每个点所标数包括其左边最近的两个点和下边最近的两个点上的标数.根据条件③，可以从单位小正方形的左下角到该点，表示每次从两个盒子里各取一个球.所以，每个点上的标数来自其左边两个点、下边两个点，左下角一个点处的标数之和（最多是5个标数之和）.如图2所示，共计有417种不同的取球顺序.4 12 37 106 289图14 12 37 106 289图1【评注】对应法是计数问题中常用的技巧.把看似麻烦的问题，做出一个合理的对应，使所求问题的每种情况，对应新问题的每种情况.同时每种新问题的一种情况也一定对应着原来问题的已知情况，这样就是一一对应了.所求问题的计数情况，就可以转化为新问题的计数情况.这种具有附加条件的标数法，需要灵活掌握.如果题目要求满足条件①③，可以采用标数法来解答吗？扫我听课扫我听课⑪在一次巴西和英格兰的足球比赛中，巴西始终至少领先1个球，最多领先5个球,且曾经出现领先5个球的情况.最后以7：5结束比赛，那么共有种不同的进球情况.【分析】根据题意，可以采用对应法.巴西进一个球，记作“一”，英格兰进一个球，记作

场❷奥数六年级标准教程+习题精选+能力测试三合一“I”，构造一个图形，进行最短路线标数.【解答】根据分析，如图1构图，注意前3个球必须是巴西进的球，这样就找到阶梯的标数法.但是又有领先最多5个球的限制，还要排除没有领先的情况，如图2所示.共计有122-89=33种进球情况.@有一天,【评注】在图1和图2的标数中，对右下角处不可能出现的情况，采取了两种不同的构图标数方法.图1是把不可能得到的情况先标数0,图2是在构图中，就把不可能得到的情况直接删除，两种方法都可行.@有一天,张经理有5封文件交给打字员打印.每次他都将要打印的文件放在打字员的文件堆的上面，打字员有时间就将文件堆最上面的文件取来打印.当要打印的文件有3封时，打字员必须停下手中的其他工作来打印.假定5封文件按经理放在文件堆上的时间顺序依次编号为1、2、3、4、5.则张经理放文件与打字员打印文件的顺序共有种.（如12345、21435是可能打印的顺序，但54321不可能）【分析】我们把张经理交给一封信记作一段横线，打字员打印一封信记作一段竖线.由于有最多积压3封信的要求，不是标准的阶梯标数法.【解答】根据分析，构造下图并标数，得到打印顺序有34种.。3434218【评注】如果本题没有“当要打印的文件有3封时，打字员必须停下手中的其他T.作来打E|T这个条件，就会是标准的阶梯标数法.第12讲图形标数法与卡特兰数扫我听课回扫我听课回3游乐园门票5元一张，每人限购一张.现在有8个小朋友排队购票，其中4个小朋友每人只有10元的钞票一张，另外4个小朋友每人只有5元的钞票一张，售票员没有准备零钱.那么共有种排队方法，使售票员总能找得开零钱.【分析】排队时，售票员总能找开零钱，需要队头到队尾的排队中，有10元的小朋友始终不多于有5元的小朋友.可以把有5元的小朋友看作一段横线，有10元的小朋友看作一段竖线，利用阶梯标数法，得到排队的所有情况.同时不要忘了，小朋友是不同的对象，需要再考虑4名有10元的小朋友的排列和4名有5元的小朋友的排列.【解答】根据分析，对图1进行阶梯标数，得到排队的情况共有14种.图1中的粗线代表一种排队顺序，转化为图2.那么4个有10元的小朋友，如何排列这其中4个10元的位置呢?有5元的4个小朋友也同样分析.所以，共有14xA：xA：=8064种排队方法，使售票员总能找得开零钱.图1 图2【评注】此题的找得开零钱的排列顺序，就是从队头到队尾的累计过程中，5元的个数不®姐妹两人一起配合洗6少于10元的个数.也就是〃=4时的卡特兰数，即®姐妹两人一起配合洗6个大小不同的盘子.姐姐按从大到小的顺序洗盘子，然后把洗好的盘子一个一个摞起来.妹妹从最上面一个一个地把盘子拿走放到碗柜中，按照自己所拿的顺序摞在一起.那么姐姐与妹妹洗盘子和摞盘子共有种不同的顺序.【分析】妹妹摞的盘子一定在姐姐洗好的盘子之后.也就是说，对于姐妹洗放盘子的顺序,是姐姐的洗盘子数不少于妹妹的摞盘子数，就是〃=6时的卡特兰数.【解答】根据分析，得/C；2=132种顺序.【评注】两个对象都有〃个，且一种对象从一个方向的累计数不少于另一个对象的累计数,

卷；奥数六年级标准教程+习题精选+能力测试三合一就是〃个对象的卡特兰数.）14个高矮不同的人，排成两排七列，每排必须是从矮到高排列，而且第二排比对应的第一排的人高.那么共有种不同排法.【分析】把14个人先从矮到高的顺序排列，然后每个人被选到第一排或第二排.每挑完一次后，第二排中的人数不多于第一排中的人数.符合卡特兰数特征.【解答】当〃=7时，JcZ=429（种）.O【评注】符合卡特兰数条件或特征就可以直接运用公式.扫我听课扫我听课法国队和巴西队进行世界杯比赛，最终法国队以7：5获胜.已知整个比赛过程中，巴西队始终没有领先过.那么符合要求的进球顺序共有种.【分析】上面都是（〃+〃）型的卡特兰数，这里是（〃+根）型的卡特兰数.同样可以进行阶梯型标数或使用公式.【解答】法国队进一球画一段横线，巴西队进一球画一段竖线.得到阶梯型图形进行标数.共有297种不同的进球顺序.（请在图1中标数）口，口，图1 图2【评注】图2中的右下角的阶梯型从4到8的最短路线是符合条件的，把穿过虚线后的第一段线段保留，以后每段横线变竖线，每段竖线变横线.这些不符合的最短路线就是从4到所的最短路线.所以也可以得到进球顺序是C；2-Cl=297种.一般地，〃:形成的卡特、/一捌r-1〃—IJ1+1为C/i.m—C/a.m— 〃+]C/i.m*

第12讲图形标数法与卡特兰数4、8两人竞选部门经理，一共14票，结果4得9票，3得5票.在唱票的过程中,A始终领先B的得票记录.那么唱票过程共有种.【分析】没有得票持平的情况，必须让4先得1票，然后出现阶梯型卡特兰数.［解答］根据分析，让/I先得1票，共有C：3-Cf3=1287-715=572种唱票顺序.1〜9填入3x3的右图方格中,使每一行左边的数大于右边的数.1〜9填入3x3的右图方格中,使每一行左边的数大于右边的数.每一列上面的数都大于下面的数.那么共有种不同填法.【分析】把第一行、第二行、第三行所填的数排成一行时，从左到右的累计中，第一行中的数的个数不少于第二行中数的个数，第二行中的数的个数不少于第三行中数的个数.可以考虑三维图形标数法.【解答】构造三维立体图形标数.第一行每写一个数画一横；第二行每写一个数画一斜杠;第三行每写一个数画一竖.如图1所示，从4到B的最短路线有42条，对应方格表的填法有42种.42种.图1 图2【评注】1）立体图形标数，其正视图、右视图、俯视图都是图2.三维图形对应的卡特兰数也是有公式的，当n=3时，Mx；：；；?：—!=IfvMW=42.2）对于本讲的阶梯标数法和卡特兰数，有些同学认为掌握一种就可以了.其实两者各有优越性.如果图形出现变形，阶梯标数较为直观和简单；如果维度较高，还是卡特兰数快速和简洁.若把本题的表格换成4x4的方格表，所填数字是1〜16,其他条件不变，共有多少种不同填法？显然四维图形是无法画出的，而公式就可以发挥其威力了.根据公式，得到二24024种.12x(4二24024种.4!x5!x6!x7!嘴奥数六年级标准教程+习题精选+能力测试三合一1.(1)如右图，从1.(1)如右图，从4到3的最短路线共有条.(2)如右图，按照向右或向上沿着方格线从4点走到8点，其中C点不能通过.共有种不同的走法.点不能通过.共有种不同的走法.3.如右图, 条.沿圆周上的弧线从A3.如右图, 条.沿圆周上的弧线从A到B的最短路线共有(3)右图中，从4到8的最短路线共有种不同的走法. 一2.按照右图中的箭头方向，从4到8的路线共有条..(1)甲、乙足球队进行一场比赛，结果甲5：3获胜，且甲一直保持领先.那么进球的情第12讲图形标数法与卡特兰数(2)甲、乙两个足球队进行一场比赛，结果甲以5：3获得胜利，又知道乙始终没有领先过.那么比赛中进球情况共有种..巴西和英格兰两个足球队进行一场比赛，结果巴西以6：4获得胜利，且英格兰始终落后，但是巴西最多比英格兰多进4个球(且多4个球的情况出现过).那么比赛进球情况共有 种..一天，经理有5封信交给打字员打字，每次他都将信放在打字员的信堆上面，打字员有时间就将信堆最上面的那封信取来打印.假定5封信按经理放在信堆的先后顺序依次编号为1、2、3、4、5.那么经理放信与打字员打字共有种顺序..某班竞选班长，甲共得6票，乙共得7票.在唱票的过程中，甲始终没有超过乙的得票记录.那么唱票顺序共有种..3个1、3个2、3个3排成一个九位数，从左往右看，1出现的次数始终不多于2出现的次数，2出现的次数不多于3出现的次数.如332132211、321323211都是符合条件的,332221311、321322131都是不符合条件的.那么共有种符合条件的排法.内容摘要本教程是针对六年级学生的智力发展特点和教学认知能力而编写的奥数教程、习题精选和能力测试综合教材。全书共设几何、计数、构造论语、能力测试和参考答案五部分，共30讲。每一讲设置知识点综述、例题详解和习题精选三个环节。本教程内容丰富.深入浅出，知识点梳理详细，便于阅读理解和记忆。为方便学生进行自学，每道例题均附有配套的详解视频，通过扫描二维码可以在线访问播放。在知识点的讲解中穿插顺口溜形式的总结,简单明了、诙谐幽