小学数学竞赛7-6-计数方法与技巧综合

1、计数方法与技巧综合7-6.计数方法与技巧综合.题库教师版page 18 of 16知识框架图7计数综合7-6计数方法与技 巧综合7- 6-1归纳法7- 6- 2整体法7- 6- 3对应法7- 6- 3-1图形中的对应关系7- 6- 3- 2数字问题中的对应关系7- 6- 3- 3对应与阶梯型标数法7- 6- 3- 4不完全对应关系7- 6- 4递推法教学目标前面在讲加法原理、乘法原理、排列组合时已经穿插讲解了计数中的一些常用的方法，比如枚举法、树 形图法、标数法、捆绑法、排除法、插板法等等，这里再集中学习一下计数中其他常见的方法，主要有归纳 法、整体法、对应法、递推法.对这些计数方法与技巧要做

2、到灵活运用.例题精讲模块一、归纳法从条件值较小的数开始，找出其中规律，或找出其中的递推数量关系，归纳出一般情况下的数量关系.【例1】（难度等级）一条直线分一个平面为两部分.两条直线最多分这个平面为四部分.问5条直线最多分这个平面为多少部分 ？【解析】方法一：我们可以在纸上试着画出1条直线，2条直线，3条直线，时的情形，于是得到下表：直线条数123456最多可分成的部分政247n1622后一项与前一项的基23456由上表已知5条直线最多可将这个平面分成16个部分，并且不又t知晓，当有n条直线时，最多可将平面分成 2+2+3+4+n=n（n.1）+1个部分2方法二：如果已有 k条直线，再增加一条直

3、线，这条直线与前k条直线的交点至多 k个，因而至多被分成k+1段，每一段将原有的部分分成两个部分，所以至多增加k+1个部分.于是3条直线至多将平面分为4+3=7个部分，4条直线至多将平面分为7+4=11个部分，5条直线至多将平面分为 11+5=16个部分.一般的有k条直线最多将平面分成：1+1+2+k=k（k +1 %个部分，所以五条直线可以分平面为162个部分.【巩固】(难度等级)平面上5条直线最多能把圆的内部分成几部分？平面上100条直线最多能把圆的内部分成几部分？【解析】 假设用ak表示k条直线最多能把圆的内部分成的部分数，这里 k= 0, 1, 2,ao= 1ai=ao+1 =2a2=

4、ai + 2=4a3=a2 + 3=7a4=a3+4 = 11故5条直线可以把圆分成 16部分，100条直线可以把圆分成 5051部分【例2】(难度等级 派)平面上10个两两相交的圆最多能将平面分割成多少个区域？【解析】先考虑最简单的情形.为了叙述方便，设平面上k个圆最多能将平面分割成 akj部分.从图中可以看出,a1=2, a2=4=2+2M1, a3=8=4+2M2, a4=14=8+2M3,可以发现ak满足下列关系式：ak =ak+2(k -1 ).实际上，当平面上的(k-1)个圆把平面分成ak二个区域时，如果再在平面上出现第k个圆，为了保证划分平面的区域尽可能多，新添的第k个圆不能通过

5、平面上前(k-1)个圆之间的交点.这样，第k个圆与前面(k-1)个圆共产生2M(k-1)个交点，如下图：而这2 M (k-1)段圆弧中的每一段都将所在的这2M(k1)个交点把第k个圆分成了 2M(k1)段圆弧,区域一分为二，所以也就是整个平面的区域数增加了2M(k-1)个部分.所以，ak=ak+ 2(k-1).那么，aw=ag 2 9=% 2 8 2 9= a7 2 7 2 8 2 9二& 2 1 2 2 . 2 7 2 8 2 9 =2 +2父(1 +2 +7 +8+9 )=92 .故10个圆最多能将平面分成 92部分.【例3】【解析】例410个三角形最多将平面分成几个部分？设n个三

6、角形最多将平面分成 an个部分.n =1 时，ai =2 ；n=2时，第二个三角形的每一条边与第一个三角形最多有2个交点，三条边与第一个三角形最多有2x3=6 （个）交点.这6个交点将第二个三角形的周边分成了6段，这6段中的每一段都将原来的每一个部分分成 2个部分，从而平面也增加了6个部分，即a2=2+2x3.n=3时，第三个三角形与前面两个三角形最多有4父3=12 （个）交点，从而平面也增加了 12个部分，即：a3 =2 2 3 4 3 . 一般地，第n个三角形与前面（n1 ）个三角形最多有2（n _1产3个交点，从而平面也增加2（n_1y（3个 部分，故 an =2+2M3+4M3 + |

7、+2（n 1 产3=2 +2+4 训+2（n 1 ）M3 = 3n23n+2 ;特别地，当n =10时，a10 =3父102 +3M10 +2=272 ,即10个三角形最多把平面分成 272个部分.（难度等级）一个长方形把平面分成两部分，那么3个长方形最多把平面分成多少部分?【解析】一个长方形把平面分成两部分.第二个长方形的每一条边至多把第一个长方形的内部分成2部分,这样第一个长方形的内部至多被第二个长方形分成五部分.同理，第二个长方形的内部至少被第一个长方形分成五部分.这两个长方形有公共部分（如下图，标有数字9的部分）.还有一个区域位于两个长方形外面，所以两个长方形至多把平面分成10部分.【

8、小结】例5【解析】第三个长方形的每一条边至多与前两个长方形中的每一个的两条边相交，故第一条边被隔成五条小线段，其中间的三条小线段中的每一条线段都把前两个长方形内部的某一部分一分为二，所以至多增加3M=12个部分.而第三个长方形的4个顶点都在前两个长方形的外面，至多能增加4个部分.所以三个长方形最多能将平面分成10+12+4=26.n个图形最多可把平面分成部分数：直线：1+nrim)；2圆：2+nM(n1);三角形：2+3MnM(n1);长方形：2+4MnM(n1).（难度等级派）在平面上画5个圆和1条直线，最多可把平面分成多少部分？先考虑圆.1个圆将平面分成2个部分.这时增加1个圆，这个圆与原

9、有的 1个圆最多有两个交点，成为2条弧，每条弧将平面的一部分一分为二，增加了2个部分，所以2个圆最多将平面分成 4个部分.当有3个圆时，第3个圆与原有的2个产生4个交点而增加4个部分，所以3个圆最多将平面分成8个部分.同样的道理，5个圆最多将平面分成 22个部分.再考虑直线.直线与每个圆最多有 2个交点，这样与5个圆最多有10个交点.它们将直线分成 11 条线段或射线，而每条线段又将平面的一部分一分为二，2条射线增加了一部分，因此 5个圆和1条直线最多可将平面分成 32个部分.【例6】 在一个西瓜上切6刀，最多能将瓜皮切成多少片？【解析】将西瓜看做一个球体，球体上任意一个切割面都是圆形，所以球

10、面上的切割线是封闭的圆周，考虑 每一次切割能增加多少瓜皮片.当切1刀时，瓜皮被切成两份，当切第 2刀时，由于切割线相交，所以瓜皮被切成4分，切第n次时，新增加的切割线与原来的切割线最多有2(n1)个交点.这些交点将第n条切割线分成2 (n1)段，也就是说新增加的切割线使瓜皮数量增加了2(n_1),所以在西瓜上切6刀，最多能将瓜皮切成 1+1+2父1 +2M2+2父3 + 2父4+2父5 = 32片.【例7】 在一大块面包上切 6刀最多能将面包切成多少块.(注：面包是一个立体几何图形，切面可以是任何方向)【解析】题目相当于6个平面能将空间划分为多少个部分.通过找规律来寻找递推关系，显然的 1个平

11、面能将空间划分成 2块，2个平面能将空间划分成 4块, 3个平面能将空间划分成 8个平面，当增加到第四个平面时，第四个平面这能将原来空间中的8个部分中的其中几个划分.如图：注意到第四个平面与其他三个平面相交形成3条直线，这三条直线将第四个平面分割成7个部分，而每一部分将原来三个平面划分的8个空间中的7个划分成两份，所以 4个平面能将空间划分成8+7 =15个部分.同样的第五个平面与前四个平面分别相交成4条直线，这四条直线能将第5个平面分割成1 1 2 3 4 =1小部分，每一部分都划分原空间中的某一区域，所以第五个平面能使空间中的区 域增加到15+11 =26个部分.当增加到6个平面时，第六个

12、平面共被划分成1+1+2+3+4+5 =16个部分，所以第6个平面能将空间中的区块数增加到 26+16 = 42个部分.所以6刀能将面包切成 42块.模块二、整体法解决计数问题时，有时要“化整为零”，使问题变得简单；有时反而要从整体上来考虑，从全局、从整体来研 究问题，反而有利于发现其中的数量关系.【例8（难度等级 ）一个正方形的内部有1996个点，以正方形的 4个顶点和内部的1996个点为顶点，将它剪成一些三角形.问：一共可以剪成多少个三角形？如果沿上述这些点中某两点之间所连的线段剪开算作一刀，那么共需剪多少刀？【解析】方法一：归纳法如下图，采用归纳法，列出 1个点、2个点、3个点一时可剪出

13、的三角形个数，需剪的刀数.内部I个点2个点3个点-9个点他个点三儡形个数468F i 20需典的刀数472®31L不难看出，当正方形内部有n个点时，可以剪成 2n+2个三角形，需剪 3n+l刀，现在内部有1996个点，所以可以剪成 2M996+2=3994个三角形，需剪 3M996+1=5989刀.方法二：整体法.我们知道内部一个点贡献 360度角，原正方形的四个顶点共贡献了 360度角，所以当内部有 n个点 时，共有360n+360度角，而每个三角形的内角和为 180度角，所以可剪成（360n+360） T80=2n+2个 三角形.2n+2个三角形共有3X2n+2）=6n+6条边，

14、但是其中有 4条是原有的正方形的边，所以正方形内部的 三角形边有6n+64=6n+2条边，又知道每条边被 2个三角形共用，即每 2条边是重合的，所以只用剪（6n+2） -2=3n+1 刀.本题中n=1996,所以可剪成 3994个三角形，需剪 5989刀.【巩固】在三角形 ABC内有100个点，以三角形的顶点和这 100点为顶点，可把三角形剖分成多少个小三角 形？【解析】整体法.100个点每个点周围有360度，三角形本身内角和为180度，所以可以分成 （360区100 +180广180 =201个小三角形.【例9】 在一个六边形纸片内有 60个点，以这60个点和六变形的 6个顶点为顶点的三角形

15、，最多能剪出 个.【解析】设正六边形内有n个点，当n=1时有6个三角形，每增加一个点，就增加2个三角形，n个点最多能剪出6+2（n+1）=2（n+2）个三角形.n=60时，可剪出124个三角形.注：设最多能剪出x个小三角形，则这些小三角形的内角和为180"x.换一个角度看，汇聚到正六边形六个顶点 处各角之和为 4M180",故这些 小三角形的内 角总和为60M360口+4父180，于是 180rx = 60父 360 + 4 180解得 x =124.模块三、对应法将难以计数的数量与某种可计量的事物联系起来，只要能建立一一对应的关系，那么这两种事物在数量上是相同的.事实上插

16、入法和插板法都是对应法的一种表现形式.一、图形中的对应关系【例10】（难度等级 派）在8X8的方格棋盘中，取出一个由三个小方格组成的“噂（如图），一共有多少种不同的方法？【解析】注意：数 不规则几何图形”的个数时，常用对应法.第1步：找对应图形 每一种取法，有一个点与之对应，这就是图中的A点，它是棋盘上横线与竖线的交点，且不在棋盘边上.第2步：明确对应关系从下图可以看出，棋盘内的每一个点对应着4个不同的取法（“形的 角在2>2正方形的不同角”上）.第3步：计算对应图形个数由于在8>8的棋盘上，内部有 7X7=49 （个）交叉点，第4步：按照对应关系，给出答案故不同的取法共有49&g

17、t;4=196 （种）.评注:通过上面两个范例我们知道 ，当直接去求一个集合元素的个数较为困难的时候，可考虑采用相等的原则，把问题转化成求另一个集合的元素个数.【例11】（难度等级 派）在8>8的黑白相间染色的国际象棋棋盘中，以网格线为边的、恰包含两个白 色小方格与一个黑色小方格的长方形共有多少个？【解析】首先可以知道题中所讲的1父3长方形中间的那个小主格为黑色，这是因为两个白格不相邻，所以不能在中间.显然，位于棋盘角上的黑色方格不可能被包含在这样的长方形中.下面分两种情况来分析：第一种情况，一个位于棋盘内部的黑色方格对应着两个这样的1M 3长方形（一横一竖）；第二种情况，位于边上的黑色

18、方格只能对应一个1黑3长方形.由于在棋盘上的32个黑色方格中，位于棋盘内部的18个，位于边上的有12个，位于角上的有2个， 所以共有18M2+12=48个这样的长方形.本题也可以这样来考虑：事实上，每一行都有6个1父3长方形，所以棋盘上横、竖共有 1父3长方形6X8X2=96个.由于棋盘上的染色具有对称性，因此包含两个白色小方格与一个黑色小方格的长方形正好与包含两个黑色小方格与一个白色小方格的长方形具有一一对应关系，这说明它们各占一半，因此所求的长方形个数为 96+2 =48个.【巩固】（难度等级 派）用一张如图所示的纸片盖住置方法？6 M6方格表中的四个小方格，共有多少种不同的放【解析】如图

19、，将纸片中的一个特殊方格染为黑色，下面考虑此格在6父6方格表中的位置.易见它不能位于四个角上；若黑格位于方格表中间如图浅色阴影所示的4父4正方形内的某格时，纸片有 4种不同的放法，共计4x4x4=64种；若黑格位于方格表边上如图深色阴影所示的方格中时，纸片的位置随之 确定，即只有1种放法，此类放法有 4x4=16种.所以，纸片共有64 +16 =80种不同的放置方法.【例12（难度等级 ”）图中可数出的三角形的个数为 .【解析】这个图不像我们以前数三角形那样规则，粗看似乎看不出其中的规律，不妨我们取出其中的一个三 角形，发现它的三条边必然落在这个图形中的三条大线段上，而每三条大线段也正好能构成

20、一个三 角形，因此三角形的个数和三条大线段的取法是一一对应的关系，图中一共有8条大线段，因此有C83 =56个三角形.【例13如图所示，在直线 AB上有7个点，直线CD上有9个点.以AB上的点为一个端点、CD上的点为另一个端点的所有线段中，任意 的交点数.3条线段都不相交于同一个点，求所有这些线段在AB与CD之间C【解析】常规的思路是这样的：直线 AB上的7个点，每个点可以与直线 CD上的9个点连9根线段，然后再 分析这些线段相交的情况.如右图所示，如果注意到下面这个事实：对于直线AB上的任意两点 M、N与直线CD上的任意两点P、Q都可以构成一个四边形 MNQP ,而这个四边形的两条对角线 M

21、Q、NP的交点恰好是我们 要计数的点，同时，对于任意四点 （AB与CD上任意两点）都可以产生一个这样的交点，所以图中两 条线段的交点与四边形有一一对应的关系.这说明，为了计数出有多少个交点，我们只需要求出在直线AB与CD中有多少个满足条件的四边形MNQP就可以了！从而把问题转化为：在直线AB上有7个点，直线CD上有9个点.四边形MNQP有多少个？其中点 M、N位于直线AB 上，点P、Q位于直线CD上.这是一个常规的组合计数问题，可以用乘法原理进行计算：由于线段MN有C72=21种选择方式，线2段PQ有C9 =36种选择方式，根据乘法原理，共可产生21M36 =756个四边形.因此在直线 AB与

22、CD 之间共有756个交点.、数字问题中的对应关系【例14】有多少个四位数，满足个位上的数字比千位数字大，千位数字比百位大， 百位数字比十位数字大？【解析】由于四位数的四个数位上的数的大小关系已经非常明确，而对于从09中任意选取的4个数字，它们的大小关系也是明确的，那么由这4个数字只能组成1个符合条件的四位数（题目中要求千位比百位大，所以千位不能为 0,本身已符合四位数的首位不能为0的要求，所以进行选择时可以把0包含在内），也就是说满足条件的四位数的个数与从09中选取4个数字的选法是一一对应的关系，那么满足条件的四位数有 C140 =10父9父8父7 =210个. 4 3 2 1【巩固】（难度

23、等级 派）三位数中，百位数比十位数大，十位数比个位数大的数有多少个？【解析】相当于在10个数字中选出3个数字，然后按从大到小排列.共有10X9X8+ （3X2X 1） =120种.实 际上，前铺中每一种划法都对应着一个数.【例15】数3可以用4种方法表示为一个或几个正整数的和，如 3, 1+2, 2+1, 1+1+1 .问：1999表示 为一个或几个正整数的和的方法有多少种？【解析】我们将1999个1写成一行，它们之间留有 1998个空隙，在这些空隙处，或者什么都不填，或者填 上“ 十 ”号.例如对于数3,上述4种和的表达方法对应：1 1 1, 1+1 1, 1 1+1, 1十1十1.可见，将

24、1999表示成和的形式与填写 1998个空隙处的方式之间是一一对应的关系，而每一个空隙 处都有填“ 十 ”号和不填“ 十 ”号 2种可能，因此 1999可以表示为正整数之和的不同方法有 2 M2 研| 乂二2 1998种.1998个2相乘【例16】（2008年国际小学数学竞赛）请问至少出现一个数码3,并且是3的倍数的五位数共有多少个？【解析】五位数共有90000个，其中3的倍数有30000个.可以采用排除法，首先考虑有多少个五位数是3的倍数但不含有数码 3. 首位数码有8种选择，第二、三、四位数码都有9种选择.当前四位的数码确定后，如果它们的和除以余数为0,则第五位数码可以为 0、6、9;如果

25、余数为1,则第五位数码可以为 2、5、8;如果 余数为2,则第五位数码可以为 1、4、7.可见只要前四位数码确定了，第五位数码都有3种选择，所以五位数中是 3的倍数但不含有数码 3的数共有8M9乂9父9黑3=17496个. 所以满足条件的五位数共有 30000 -17496 =12504个.三、对应与阶梯型标数法【例17】游乐园的门票1元1张，每人限购1张.现在有10个小朋友排队购票，其中 5个小朋友只有1元 的钞票，另外5个小朋友只有2元的钞票，售票员没有准备零钱.问有多少种排队方法，使售票 员总能找得开零钱？【解析】与类似题目找对应关系.要保证售票员总能找得开零钱，必须保证每一位拿2元钱的

26、小朋友前面的若干小朋友中，拿1元的要比拿2元的人数多，先将拿 1元钱的小朋友看成是相同的，将拿2元钱的小朋友看成是相同的，可以利用斜直角三角模型.在下图中，每条小横线段代表1元钱的小朋友，每条小竖线段代表 2元钱的小朋友，因为从 A点沿格线走到B点，每次只能向右或向上走，无论到途中哪一点，只要不超 过斜线，那么经过的小横线段都不少于小竖线段，所以本题相当于求下图中从A到B有多少种不同走法.使用标数法，可求出从 A到B有42种走法.但是由于10个小朋友互不相同，必须将他们排队，可以分成两步，第一步排拿2元的小朋友，5个人共有5! =120种排法；第二步排拿到1元的小朋友，也有120种排法，所以共

27、有3父3 =14400种排 队方法.这样，使售票员能找得开零钱的排队方法共有42x14400=604800（种）.【例18【解析】（ 2008年第一届“学而思杯”五年级试题）学学和思思一起洗5个互不相同的碗，思思洗好的碗一个一个往上摞，学学再从最上面一个一个地拿走放入碗柜摞成一摞，思思一边洗，学学一边拿， 那么学学摞好的碗一共有种不同的摞法.我们把学学洗的 5个碗过程看成从起点向右走5步（即洗几个碗就代表向右走几步），思思拿5个碗的过程看成是向上走5步（即拿几个碗就代表向上走几步），摞好碗的摞法，就代表向右、向上走5步到达终点最短路线的方法.由于洗的碗要多余拿的碗，所以向右走的路线要多余向上走

28、的路线，所以我们用下面的斜三角形进行标数，共有42种走法，即代表 42种摞法.【例19【解析】（第七届走美试题）一个正在行进的 8人队列，每人身高各不相同，按从低到高的次序排列，现在他们要变成并列的 2列纵队，每列仍然是按从低到高的次序排列，同时要求并排的每两人中左边的人比右边的人要矮，那么，2列纵队有 种不同排法.首先，将8人的身高从低到高依次编号为 1、2、3、4、5、6、7、8,现在就相当于要将这 8个数填到一个4M 2 的方格中，要求每一行的数依次增大，每一列上面的要比下面的大.下面我们将1、2、3、4、5、6、7、8依次往方格中填，按照题目规则，很容易就发现：第二行填的的数字的 个数

29、永远都小于或等于第一行数字填的个数.也就是说，不能出现下图这样的情况.而这个正好是“阶梯型标数”12345在这个阶梯型方格中，横格代表在第一行的四列，纵格代表第二行的四列，那么此题所有标数的方法就相当于从 A走到B的最短路线有多少条. 例如，我们选择一条路线：14 B【巩固】将112这12个数填入到2行6列的方格表中，使得每行右边比左边的大，每一列上面比下面的大,共有多少种填法？【解析】根据对应关系，再运用阶梯型标数法画图如下：共有132种填法.四、不完全对应关系【例20圆周上有12个点，其中一个点涂红，还有一个点涂了蓝色，其余10个点没有涂色，以这些点为顶点的凸多边形中，其顶点包含了红点及蓝

30、点的多边形称为双色多边形；只包含红点（蓝点）的多边形称为红色（蓝色）多边形.不包含红点及蓝点的称无色多边形.试问，以这12个点为顶点的所有凸多边形（边数可以从三角形到 12边形）中，双色多边形的个数与无色多边形的个数，哪一种较 多？多多少个？【解析】从任意一个双色的 N边形出发（N之5时），在去掉这个双色多边形中的红色顶点与蓝色顶点后，将 得到一个无色的 N -2边形；另一方面，对于一个任意的无色的M边形，如果加上红色顶点和蓝色顶点，就得到一个双色的 M +2边形，所以无色多边形与双色多边形中的五边形以上的图形是一一 对应的关系，所以双色多边形的个数比较多，多的是双色三角形和双色四边形的个数.

31、而双色三角 形有10个，双色四边形有 G2）=45个，所以双色多边形比无色多边形多10 + 45=55个.【例21】有一类各位数字各不相同的五位数M ,它的千位数字比左右两个数字大，十位数字也比左右两位数字大.另有一类各位数字各不相同的五位数W ,它的千位数字比左右两个数字小，十位数字也比左右两位数字小.请问符合要求的数M与W,哪一类的个数多？多多少？【解析】M与W都是五位数，都有千位和十位与其它数位的大小关系，所以两类数有一定的对应关系.比如有一个符合要求的五位数M =ABCDE （A不为0）,那么就有一个与之相反并对应的五位数（9 A）（9 B）（9 C）（9 D）（9 E）必属于 W类,

32、比如13254为M类，则与之对应的 86754为W类. 所以对于M类的每一个数， W类都有一个数与之对应.但是两类数的个数不是一样多，因为 M类 中0不能做首位，而 W类中9可以做首位.所以 W类的数比M类的数要多，多的就是就是首位为9的符合要求的数.计算首位为9的W类的数的个数，首先要确定另外四个数， 因为要求各不相同，从除9外的其它9个 数字中选出4个，有C4 =126种选法.对于每一种选法选出来的4个数，假设其大小关系为 A4AA3AA2 > A,由于其中最小的数只能在千位和十位上，最大的数只能在百位和个位上，所以符合要求的数有2类：千位、十位排 A、A2,有两种方法，百位、十位排

33、A3、A4,也有两种方法，故此时共有4种；千位、十位排 A、A3,只能是千位A3,百位A4,十位A,个位A2,只有1种方法.根据乘法原理，首位为 9的W类的数有126乂（4+1 ）=630个.故W类的数比M类的数多630个.【例22 用1元，2元，5元，10元四种面值的纸币若干张（不一定要求每种都有）,组成99元有P种方法， 组成101元有Q种方法，则Q -P =.【解析】由于101-99=2,所以对于组成99元的每一种方法，只要再加上一张2元的，即可组成101元；而对于组成101元的方法，如果其中包含有一张2元的，那么去掉这张 2元的，即可得到一种组成 99元的方法.可见组成99元的方法与组

34、成101元的某些方法之间存在对应的关系，组成101元的所有方法中，除去这些与组成99元的方法对应的方法，剩下的都是不包含有 2元纸币的组成方法.所 以Q比P多的就是用1元，5元，10元这三种面值的纸币组成 101元的方法的总数.假设用x张1元的，y张5元的，z张10元的可以组成101元，则x + 5y+10z = 101 .由于10zE101,所以z<10 .即10元的可以有010张.如果10元的张数确定了， 那么有x+5y=10110z=10（10z）+1=5（202z）+1 ,那么y的值可以为 0至1J（202z）,也就是对每一个 z的值，y都可以有202z+1=212z种可能，相应

35、地5元纸币的 张数也有21-2z种取法.而当10元和5元的张数都确定了以后，1元纸币的张数也就确定了，这样也就确定了组成101元的方法.所以只需要看取 10元和5元的共有多少种取法.如果10元的取0张，即z = 0 ,则21 -2z=21 ,即5元的有21种取法； 如果10元的取1张，即z=1 ,则212z=19 ,即5元的有19种取法； 如果10元的取2张，即z=2 ,则21 -2z=17 ,即5元的有17种取法；如果10元的取10张，即z=10,则212z=1,即5元的有1种取法;所以总数为 21+19+17+川+1=112=121.那么 Q _P =121 .模块四、递推法对于某些难以发

36、现其一般情形的计数问题，可以找出其相邻数之间的递归关系，有了这一递归关系就可以利 用前面的数求出后面未知的数，这种方法称为递推法.【例23（难度等级 ）有一堆火柴共 12根，如果规定每次取 13根，那么取完这堆火柴共有多少 种不同取法？【解析】取1根火柴有1种方法，取2根火柴有2种方法，取3根火柴有4种取法，以后取任意根火柴的种 数等于取到前三根火柴所有情况之和，以此类推，参照上题列表如下：1根2根3根4根5根6根7根8根9根10根11根12根124713244481149274504927取完这堆火柴一共有 927种方法.【巩固】 （难度等级 派）一堆苹果共有 8个，如果规定每次取 13个，

37、那么取完这堆苹果共有多少种 不同取法？【解析】取1个苹果有1种方法，取2个苹果有2种方法，取3个苹果有4种取法，以后取任意个苹果的种 数等于取到前三个苹果所有情况之和，以此类推，参照上题列表如下：1个2个3个4个5个6个7个8个124713244481取完这堆苹果一共有 81种方法.【例24】有10枚棋子，每次拿出 2枚或3枚，要想将10枚棋子全部拿完，共有多少种不同的拿法？【解析】本题可以采用递推法，也可以进行分类讨论，当然也可以直接进行枚举.（法1）递推法.假设有n枚棋子，每次拿出2枚或3枚，将n枚棋子全部拿完的拿法总数为 小种.贝 U a? =1 , a3 =1 ,=1 .由于每次拿出2

38、枚或3枚，所以an =an+an/（ n之5）.所以，a5 a2 "*"a3 2 j a6=a3+a4=2； a7=a4+a5=3； a8=a5+a6=4； a9 - a6 "*"a7 - 5 j a10 =a7 +a8 =7 .即当有10枚棋子时，共有7种不同的拿法.（法2）分类讨论.由于棋子总数为10枚，是个偶数，而每次拿 2枚或3枚，所以其中拿3枚的次数也应该是偶数.由 于拿3枚的次数不超过3次，所以只能为0次或2次.若为0次，则相当于2枚拿了 5次，此时有1种拿法；若为2次，则2枚也拿了 2次，共拿了 4次，所以此时有C：=6种拿法.根据加法原理

39、，共有1+6=7种不同的拿法.【例25（难度等级 派）用1M3的小长方形覆盖3M8的方格网，共有多少种不同的盖法？【解析】如果用1父3的长方形盖3。的长方形，设种数为 小，则a1=1, a2=1,%=2,对于n24,左边可能竖放1个1父3的，也可能横放 3个1父3的，前者有an-1种，后者有an-3种，所以an=an-1+an-3,依照 这条递推公式列表：3父13M23M33M43M53M63M73M8112346913所以用1 m3的小长方形形覆盖 3父8的方格网，共有13种不同的盖法.【例26（难度等级 派）如下图，一只蜜蜂从 A处出发，回到家里 B处，每次只能从一个蜂房爬向右 侧邻近的蜂

40、房而不准逆行，共有多少种回家的方法？【解析】按照蜜蜂只能从小号码的蜂房爬近相邻大号码的蜂房的原则，运用标号法进行计算.如右图所示,小蜜蜂从A出发到B处共有296种不同的回家方法.【例27】有20个石子，一个人分若干次取，每次可以取1个，2个或3个，但是每次取完之后不能留下质数个，有多少种方法取完石子？（石子之间不作区分，只考虑石子个数）【解析】如果没有剩下的不能使质数这个条件，那么递推方法与前面学过的递推法相似，只不过每次都是前面3个数相加.现在剩下的不能是质数个，可以看作是质数个的取法总数都是0,然后再进行递推.剩 下 的 石 子 数20191817161514131211109876543

41、210取101012305051015025025002525法总 数【巩固】有20个相同的棋子，一个人分若干次取，每次可取1个，2个，3个或4个，但要求每次取之后留下的棋子数不是 3或4的倍数，有 种不同的方法取完这堆棋子 .【解析】把20、0和20以内不是3或4的倍数的数写成一串，用递推法把所有的方法数写出来：2019171413111075210112246121818183654【例28】4个人进行篮球训练，互相传球接球，要求每个人接球后马上传给别人，开始由甲发球，并作为第一次传球，第五次传球后，球又回到甲手中，问有多少种传球方法？【解析】设第n次传球后，球又回到甲手中的传球方法有an

42、种.可以想象前n-1次传球，如果每一次传球都任选其他三人中的一人进行传球，即每次传球都有3种可能，由乘法原理，共有3M3M3-、.3 = 3力种）（n 1）个 3传球方法.这些传球方法并不是都符合要求的，它们可以分为两类，一类是第n-1次恰好传到甲手中，这有an二种传法，它们不符合要求，因为这样第n次无法再把球传给甲； 另一类是第n-1次传球，球不在甲手中，第n次持球人再将球传给甲，有an种传法.根据加法原理，有Wn+an三3M3M'Q =3（n 1）个 3由于甲是发球者，一次传球后球又回到甲手中的传球方法是不存在的，所以a=0 .利 用递推 关系可 以得到：a2=30=3 , a3

43、=3x3-3=6 , a4 =3x3x3-6 =21 a5 =3x3x3x3-21 =60 .这说明经过5次传球后，球仍回到甲手中的传球方法有60种.本题也可以列表求解.由于第n次传球后，球不在甲手中的传球方法，第n+1次传球后球就可能回到甲手中，所以只需求出第四次传球后，球不在甲手中的传法共有多少种.第n次传球传球的方法球在甲手中的传球方法球小在甲手中的传球方法130329363276214812160524360183从表中可以看出经过五次传球后，球仍回到甲手中的传球方法共有60种.【巩固】五个人互相传球，由甲开始发球，并作为第一次传球，经过4次传球后，球仍回到甲手中.问：共有多少种传球方

44、式？【解析】递推法.设第n次传球后球传到甲的手中的方法有an种.由于每次传球有 4种选择，传n次有4n次可能.其中有的球在甲的手中， 有的球不在甲的手中，球在甲的手中的有an种，球不在甲的手中的，下一次传球都可以将球传到甲的手中，故有an出种.所以an +an书=4n .由于ai =0 ,所以a2 =41 -ai =4 , a3 =42 -a? =12 , a4=43 -a? =52 .即经过4次传球后，球仍回 到甲手中的传球方法有 52种.【例29】（2009年清华附中考题）设八、E为正八边形 ABCDEFGH的相对顶点，顶点 A处有一只青蛙，除 顶点E外青蛙可以从正八边形的任一顶点跳到其相

45、邻两个顶点中任意一个，落到顶点E时青蛙就停止跳动，则青蛙从顶点 A出发恰好跳10次后落到E的方法总数为 种.【解析】可以使用递推法.回到A跳到B或H跳到C或G跳到D或FW E1步12步213步314步6425步1046步201487步34148步6848289步11648其中，A列的每个数都等于它的上一行的第二列的数的2倍，第二列的每一个数都等于它的上一行的第一列和第三列的两个数的和，第三列的每一个数都等于它的上一行的第二列和第四列的两 个数的和，第四列的每一个数都等于它的上一行的第三列的数，第五列的每一个数都等于都等于它 的上一行的第四列的数的 2倍.这一规律很容易根据青蛙的跳动规则分析得来.所以，青蛙第10步跳到E有48M 2 =96种方法.【巩固】在正五边形 ABCDE上，一只青蛙从 A点开始跳动，它每次可以随意跳到相邻两个顶点中的一个上, 一旦跳到D点上就停止跳动.青蛙在 6次之内（含6次）跳到D点有 种不同跳法.【解析】采用递推的方法.列表如下:跳到A跳到B跳到CW D跳到E1步112步2113步3124步5325步8356步1385其中，根据规则，每次可以随意跳到相邻两个顶点中的一个上，一旦跳到D点上就停止跳动.所以，每一步跳到 A的跳法数等于上一步跳到