7-6计数方法与技巧综合.题库版

计数方法与技巧综合

知识框架图 7-6-1归纳法 7-6-2整体法 7-6 计数方法与技7 计数综合 巧综合 7-6-3对应法 7-6-3-1图形中的对应关系 7-6-3-2数字问题中的对应关系 7-6-3-3对应与阶梯型标数法 7-6-3-4不完全对应关系 7-6-4递推法

前面在讲加法原理、乘法原理、排列组合时已经穿插讲解了计数中的一些常用的方法，比如枚举法、树形图法、标数法、捆绑法、排除法、插板法等等，这里再集中学习一下计数中其他常见的方法，主要有归纳法、整体法、对应法、递推法．对这些计数方法与技巧要做到灵活运用．

教学目标

例题精讲

模块一、归纳法

从条件值较小的数开始，找出其中规律，或找出其中的递推数量关系，归纳出一般情况下的数量关系． 【例 1】 （难度等级※※）一条直线分一个平面为两部分．两条直线最多分这个平面为四部分．问5条直

线最多分这个平面为多少部分?

【解析】 方法一：我们可以在纸上试着画出1条直线，2条直线，3条直线，……时的情形，于是得到下表：

由上表已知5条直线最多可将这个平面分成16个部分，并且不难知晓，当有n条直线时，最多可将

n?n?1?平面分成2+2+3+4+…+n=+1个部分． 2方法二：如果已有k条直线，再增加一条直线，这条直线与前k条直线的交点至多k个，因而至多被分成k+1段，每一段将原有的部分分成两个部分，所以至多增加k+1个部分．于是3条直线至多将平面分为4+3=7个部分，4条直线至多将平面分为7+4=11个部分，5条直线至多将平面分为11+5=16个部分．

7-6.计数方法与技巧综合.题库 教师版 page 1 of 17

一般的有k条直线最多将平面分成：1+1+2+…+k=个部分．

k?k?1?+1个部分，所以五条直线可以分平面为162

【巩固】（难度等级※※）平面上5条直线最多能把圆的内部分成几部分？平面上100条直线最多能把圆的内

部分成几部分？

【解析】 假设用ak表示k条直线最多能把圆的内部分成的部分数，这里k＝0，1，2，……

a0＝1

a1=a0+1＝2 a2=a1＋2=4 a3=a2＋3=7 a4=a3+4＝11 ……

故5条直线可以把圆分成16部分，100条直线可以把圆分成5051部分

【例 2】 （难度等级 ※※）平面上10个两两相交的圆最多能将平面分割成多少个区域？ 【解析】 先考虑最简单的情形．为了叙述方便，设平面上k个圆最多能将平面分割成ak个部分．

12124361234785

从图中可以看出，a1?2，a2?4?2?2?1，a3?8?4?2?2，a4?14?8?2?3，…… 可以发现ak满足下列关系式：ak?ak?1?2?k?1?．

实际上，当平面上的(k?1)个圆把平面分成ak?1个区域时，如果再在平面上出现第k个圆，为了保证划分平面的区域尽可能多，新添的第k个圆不能通过平面上前?k?1?个圆之间的交点．这样，第k个圆与前面?k?1?个圆共产生2?(k?1)个交点，如下图：

6879451231112131410

这2?(k?1)个交点把第k个圆分成了2?(k?1)段圆弧，而这2?(k?1)段圆弧中的每一段都将所在的

7-6.计数方法与技巧综合.题库 教师版 page 2 of 17

区域一分为二，所以也就是整个平面的区域数增加了2?(k?1)个部分．所以，ak?ak?1?2?k?1?． 那么，a10?a9?2?9?a8?2?8?2?9?a7?2?7?2?8?2?9 ???

?a1?2?1?2?2?...?2?7?2?8?2?9

?2?2??1?2?...?7?8?9??92．

故10个圆最多能将平面分成92部分．

【例 3】 10个三角形最多将平面分成几个部分？ 【解析】 设n个三角形最多将平面分成an个部分．

n?1时，a1?2；

n?2时，第二个三角形的每一条边与第一个三角形最多有2个交点，三条边与第一个三角形最多有

2?3?6（个）交点．这6个交点将第二个三角形的周边分成了6段，这6段中的每一段都将原来的每一个部分分成2个部分，从而平面也增加了6个部分，即a2?2?2?3．

n?3时，第三个三角形与前面两个三角形最多有4?3?12（个）交点，从而平面也增加了12个部分，即：a3?2?2?3?4?3．

…… 一般地，第n个三角形与前面?n?1?个三角形最多有2?n?1??3个交点，从而平面也增加2?n?1??3个

2部分，故an?2?2?3?4?3???2?n?1??3?2???2?4???2?n?1????3?3n?3n?2；

特别地，当n?10时，a10?3?102?3?10?2?272，即10个三角形最多把平面分成272个部分．

【例 4】 （难度等级※※）一个长方形把平面分成两部分，那么3个长方形最多把平面分成多少部分？

【解析】 一个长方形把平面分成两部分．第二个长方形的每一条边至多把第一个长方形的内部分成2部分，

这样第一个长方形的内部至多被第二个长方形分成五部分．

同理，第二个长方形的内部至少被第一个长方形分成五部分．这两个长方形有公共部分(如下图，标

有数字9的部分)．还有一个区域位于两个长方形外面，所以两个长方形至多把平面分成10部分．

第三个长方形的每一条边至多与前两个长方形中的每一个的两条边相交，故第一条边被隔成五条小

线段，其中间的三条小线段中的每一条线段都把前两个长方形内部的某一部分一分为二，所以至多增加3×4=12个部分．而第三个长方形的4个顶点都在前两个长方形的外面，至多能增加4个部分． 所以三个长方形最多能将平面分成10+12+4=26．

【小结】n个图形最多可把平面分成部分数：

7-6.计数方法与技巧综合.题库 教师版 page 3 of 17

直线：1?； 2圆：2?n??n?1?； 三角形：2?3?n??n?1? ； 长方形：2?4?n??n?1?．

【例 5】 （难度等级※※）在平面上画5个圆和1条直线，最多可把平面分成多少部分? 【解析】 先考虑圆．1个圆将平面分成2个部分．这时增加1个圆，这个圆与原有的1个圆最多有两个交点，

成为2条弧，每条弧将平面的一部分一分为二，增加了2个部分，所以2个圆最多将平面分成4个部分．当有3个圆时，第3个圆与原有的2个产生4个交点而增加4个部分，所以3个圆最多将平面分成8个部分．

同样的道理，5个圆最多将平面分成22个部分．

再考虑直线．直线与每个圆最多有2个交点，这样与5个圆最多有10个交点．它们将直线分成11条线段或射线，而每条线段又将平面的一部分一分为二，2条射线增加了一部分，因此5个圆和1条直线最多可将平面分成32个部分．

【例 6】 在一个西瓜上切6刀，最多能将瓜皮切成多少片？

【解析】 将西瓜看做一个球体，球体上任意一个切割面都是圆形，所以球面上的切割线是封闭的圆周，考虑

每一次切割能增加多少瓜皮片．当切1刀时，瓜皮被切成两份，当切第2刀时，由于切割线相交，所以瓜皮被切成4分，……，切第n次时，新增加的切割线与原来的切割线最多有2?n?1?个交点．这

些交点将第n条切割线分成2?n?1?段，也就是说新增加的切割线使瓜皮数量增加了2?n?1?，所以在西瓜上切6刀，最多能将瓜皮切成1?1?2?1?2?2?2?3?2?4?2?5?32片．

【例 7】 在一大块面包上切6刀最多能将面包切成多少块．（注：面包是一个立体几何图形，切面可以是任

何方向） 【解析】 题目相当于6个平面能将空间划分为多少个部分．

通过找规律来寻找递推关系，显然的1个平面能将空间划分成2块，2个平面能将空间划分成4 块，

3个平面能将空间划分成8个平面，当增加到第四个平面时，第四个平面这能将原来空间中的8个部

n??n?1? 分中的其中几个划分．如图：

7-6.计数方法与技巧综合.题库 教师版 page 4 of 17

注意到第四个平面与其他三个平面相交形成3条直线，这三条直线将第四个平面分割成7个部分，而每一部分将原来三个平面划分的8个空间中的7个划分成两份，所以4个平面能将空间划分成8?7?15个部分．

同样的第五个平面与前四个平面分别相交成4条直线，这四条直线能将第5个平面分割成1?1?2?3?4?1个部分，每一部分都划分原空间中的某一区域，所以第五个平面能使空间中的区1域增加到15?11??26个部分．

当增加到6个平面时，第六个平面共被划分成1?1?2?3?4?5?16个部分，所以第6个平面能将空间中的区块数增加到26?16?42个部分． 所以6刀能将面包切成42块．

模块二、整体法

解决计数问题时，有时要“化整为零”，使问题变得简单；有时反而要从整体上来考虑，从全局、从整体来研究问题，反而有利于发现其中的数量关系．

【例 8】 （难度等级 ※※※）一个正方形的内部有1996个点，以正方形的4个顶点和内部的1996个点为

顶点，将它剪成一些三角形．问：一共可以剪成多少个三角形?如果沿上述这些点中某两点之间所连的线段剪开算作一刀，那么共需剪多少刀?

【解析】 方法一：归纳法

如下图，采用归纳法，列出1个点、2个点、3个点…时可剪出的三角形个数，需剪的刀数．

不难看出，当正方形内部有n个点时，可以剪成2n＋2个三角形，需剪3n+l刀，现在内部有1996

个点，所以可以剪成2×1996+2=3994个三角形，需剪3×1996+1=5989刀．

方法二：整体法．

我们知道内部一个点贡献360度角，原正方形的四个顶点共贡献了360度角，所以当内部有n个点时，共有360n+360度角，而每个三角形的内角和为180度角，所以可剪成(360n+360)÷180=2n+2个三角形．

2n+2个三角形共有3×(2n+2)=6n+6条边，但是其中有4条是原有的正方形的边，所以正方形内部的

三角形边有6n+6—4=6n+2条边，又知道每条边被2个三角形共用，即每2条边是重合的，所以只用剪(6n+2)÷2＝3n+1刀．

本题中n=1996，所以可剪成3994个三角形，需剪5989刀．

【巩固】在三角形ABC内有100个点，以三角形的顶点和这100点为顶点，可把三角形剖分成多少个小三角

形？

【解析】 整体法．100个点每个点周围有360度，三角形本身内角和为180度，所以可以分成

?360?100?180??180?201个小三角形．

7-6.计数方法与技巧综合.题库 教师版 page 5 of 17

【例 9】 在一个六边形纸片内有60个点，以这60个点和六变形的6个顶点为顶点的三角形，最多能剪出

_______个．

【解析】 设正六边形内有n个点，当n?1时有6个三角形，每增加一个点，就增加2个三角形，

n个点最多能剪出6?2?n?1??2?n?2?个三角形．

n?60时，可剪出124个三角形．

注：设最多能剪出x个小三角形，则这些小三角形的内角和为180?x．换一个角度看，汇聚到正六边形六个顶点处各角之和为4?180?，故这些小三角形的内角总和为60?360??4?180?．于是180?x?60?360??4?18?0x?124． ，解得

模块三、对应法

将难以计数的数量与某种可计量的事物联系起来，只要能建立一一对应的关系，那么这两种事物在数量上是

相同的．事实上插入法和插板法都是对应法的一种表现形式．

一、图形中的对应关系

【例 10】 （难度等级 ※※※）在8×8的方格棋盘中，取出一个由三个小方格组成的“L”形（如图），一共有

多少种不同的方法？

【解析】 注意：数“不规则几何图形”的个数时，常用对应法．

第1步：找对应图形 每一种取法，有一个点与之对应，这就是图中的A点，它是棋盘上横线与竖线的交点，且不在棋盘边上．

第2步：明确对应关系 从下图可以看出，棋盘内的每一个点对应着4个不同的取法（“L”形的“角”在2×2正方形的不同“角”上）．

第3步：计算对应图形个数 由于在 8×8的棋盘上，内部有7×7=49（个）交叉点， 第4步：按照对应关系，给出答案故不同的取法共有49×4=196（种）．

评注:通过上面两个范例我们知道,当直接去求一个集合元素的个数较为困难的时候,可考虑采用相等的原则,把问题转化成求另一个集合的元素个数．

【例 11】 （难度等级 ※※※）在8×8的黑白相间染色的国际象棋棋盘中，以网格线为边的、恰包含两个白

色小方格与一个黑色小方格的长方形共有多少个？

【解析】 首先可以知道题中所讲的1?3长方形中间的那个小主格为黑色，这是因为两个白格不相邻，所以不

7-6.计数方法与技巧综合.题库 教师版 page 6 of 17

能在中间．显然，位于棋盘角上的黑色方格不可能被包含在这样的长方形中． 下面分两种情况来分析：第一种情况，一个位于棋盘内部的黑色方格对应着两个这样的1?3长方形(一横一竖)；第二种情况，位于边上的黑色方格只能对应一个1?3长方形． 由于在棋盘上的32个黑色方格中，位于棋盘内部的18个，位于边上的有12个，位于角上的有2个，所以共有18?2?12?48个这样的长方形．

本题也可以这样来考虑：事实上，每一行都有6个1?3长方形，所以棋盘上横、竖共有1?3长方形6?8?2?96个．由于棋盘上的染色具有对称性，因此包含两个白色小方格与一个黑色小方格的长方形正好与包含两个黑色小方格与一个白色小方格的长方形具有一一对应关系，这说明它们各占一半，因此所求的长方形个数为96?2?48个．

【巩固】 （难度等级 ※※）用一张如图所示的纸片盖住6?6方格表中的四个小方格，共有多少种不同的放

置方法？

【解析】如图，将纸片中的一个特殊方格染为黑色，下面考虑此格在6?6方格表中的位置．易见它不能位于

四个角上；若黑格位于方格表中间如图浅色阴影所示的4?4正方形内的某格时，纸片有4种不同的放法，共计4?4?4?64种；若黑格位于方格表边上如图深色阴影所示的方格中时，纸片的位置随之确定，即只有1种放法，此类放法有4?4?16种． 所以，纸片共有64?16?80种不同的放置方法．

【例 12】 （难度等级 ※※）图中可数出的三角形的个数为 ． 【解析】 这个图不像我们以前数三角形那样规则，粗看似乎看不出其中的规律，不妨我们取出其中的一个三

角形，发现它的三条边必然落在这个图形中的三条大线段上，而每三条大线段也正好能构成一个三角形，因此三角形的个数和三条大线段的取法是一一对应的关系，图中一共有8条大线段，因此有

C83?56个三角形．

【例 13】 如图所示，在直线AB上有7个点，直线CD上有9个点．以AB上的点为一个端点、CD上的点为

7-6.计数方法与技巧综合.题库 教师版 page 7 of 17

另一个端点的所有线段中，任意3条线段都不相交于同一个点，求所有这些线段在AB与CD之间的交点数．

ABCD

【解析】 常规的思路是这样的：直线AB上的7个点，每个点可以与直线CD上的9个点连9根线段，然后再

分析这些线段相交的情况．

如右图所示，如果注意到下面这个事实：对于直线AB上的任意两点M、N与直线CD上的任意两点P、Q都可以构成一个四边形MNQP，而这个四边形的两条对角线MQ、NP的交点恰好是我们要计数的点，同时，对于任意四点(AB与CD上任意两点)都可以产生一个这样的交点，所以图中两条线段的交点与四边形有一一对应的关系．

这说明，为了计数出有多少个交点，我们只需要求出在直线AB与CD中有多少个满足条件的四边形MNQP就可以了！从而把问题转化为： 在直线AB上有7个点，直线CD上有9个点．四边形MNQP有多少个？其中点M、N位于直线AB上，点P、Q位于直线CD上．

这是一个常规的组合计数问题，可以用乘法原理进行计算：由于线段MN有C72?21种选择方式，线段PQ有C92?36种选择方式，根据乘法原理，共可产生21?36?756个四边形．因此在直线AB与CD之间共有756个交点．

二、数字问题中的对应关系

【例 14】 有多少个四位数，满足个位上的数字比千位数字大，千位数字比百位大，百位数字比十位数字大？ 【解析】 由于四位数的四个数位上的数的大小关系已经非常明确，而对于从0～9中任意选取的4个数字，它

们的大小关系也是明确的，那么由这4个数字只能组成1个符合条件的四位数(题目中要求千位比百位大，所以千位不能为0，本身已符合四位数的首位不能为0的要求，所以进行选择时可以把0包含在内)，也就是说满足条件的四位数的个数与从0～9中选取4个数字的选法是一一对应的关系，

10?9?8?74那么满足条件的四位数有C10??210个．

4?3?2?1

【巩固】 （难度等级 ※※※）三位数中，百位数比十位数大，十位数比个位数大的数有多少个？ 【解析】 相当于在10个数字中选出3个数字，然后按从大到小排列.共有10×9×8÷（3×2×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． 可见，将1999表示成和的形式与填写1998个空隙处的方式之间是一一对应的关系，而每一个空隙处都有填“＋”号和不填“＋”号2种可能，因此1999可以表示为正整数之和的不同方法有2?2???2?21998种． ?????1998个2相乘

【例 16】 （2008年国际小学数学竞赛）请问至少出现一个数码3，并且是3的倍数的五位数共有多少个？ 【解析】 五位数共有90000个，其中3的倍数有30000个．可以采用排除法，首先考虑有多少个五位数是3

的倍数但不含有数码3.

7-6.计数方法与技巧综合.题库 教师版 page 8 of 17

首位数码有8种选择，第二、三、四位数码都有9种选择．当前四位的数码确定后，如果它们的和除以余数为0，则第五位数码可以为0、6、9；如果余数为1，则第五位数码可以为2、5、8；如果余数为2，则第五位数码可以为1、4、7.可见只要前四位数码确定了，第五位数码都有3种选择，所以五位数中是3的倍数但不含有数码3的数共有8?9?9?9?3?17496个． 所以满足条件的五位数共有30000?17496?12504个．

三、对应与阶梯型标数法

【例 17】 游乐园的门票1元1张，每人限购1张．现在有10个小朋友排队购票，其中5个小朋友只有1元

的钞票，另外5个小朋友只有2元的钞票，售票员没有准备零钱．问有多少种排队方法，使售票员总能找得开零钱？

【解析】 与类似题目找对应关系．

要保证售票员总能找得开零钱，必须保证每一位拿2元钱的小朋友前面的若干小朋友中，拿1元的要比拿2元的人数多，先将拿1元钱的小朋友看成是相同的，将拿2元钱的小朋友看成是相同的，可以利用斜直角三角模型．在下图中，每条小横线段代表1元钱的小朋友，每条小竖线段代表2元钱的小朋友，因为从A点沿格线走到B点，每次只能向右或向上走，无论到途中哪一点，只要不超过斜线，那么经过的小横线段都不少于小竖线段，所以本题相当于求下图中从A到B有多少种不同走法．使用标数法，可求出从A到B有42种走法．

B145212534242142891445111111

但是由于10个小朋友互不相同，必须将他们排队，可以分成两步，第一步排拿2元的小朋友，5个

?120种排法；第二步排拿到1元的小朋友，也有120种排法，所以共有5！?5！?14400种排人共有5！队方法．

这样，使售票员能找得开零钱的排队方法共有42?14400?604800(种)．

【例 18】 （2008年第一届“学而思杯”五年级试题）学学和思思一起洗5个互不相同的碗，思思洗好的碗

一个一个往上摞，学学再从最上面一个一个地拿走放入碗柜摞成一摞，思思一边洗，学学一边拿，那么学学摞好的碗一共有 种不同的摞法．

【解析】 我们把学学洗的5个碗过程看成从起点向右走5步（即洗几个碗就代表向右走几步），思思

拿5个碗的过程看成是向上走5步（即拿几个碗就代表向上走几步），摞好碗的摞法，就代表向右、向上走5步到达终点最短路线的方法.由于洗的碗要多余拿的碗，所以向右走的路线要多余向上走的路线，所以我们用下面的斜三角形进行标数，共有42种走法，即代表42种摞法.

A7-6.计数方法与技巧综合.题库 教师版 page 9 of 17

B421414941422814515212A11315

【例 19】 (第七届走美试题)一个正在行进的8人队列，每人身高各不相同，按从低到高的次序排列，现在

他们要变成并列的2列纵队，每列仍然是按从低到高的次序排列，同时要求并排的每两人中左边的人比右边的人要矮，那么，2列纵队有 种不同排法．

2、3、4、5、6、7、8，【解析】 首先，将8人的身高从低到高依次编号为1、现在就相当于要将这8个数填到一个4?2的方格中，要求每一行的数依次增大，每一列上面的要比下面的大．

2、3、4、5、6、7、8依次往方格中填，按照题目规则，很容易就发现：第二行填的的数字的下面我们将1、个数永远都小于或等于第一行数字填的个数．也就是说，不能出现下图这样的情况．

而这个正好是“阶梯型标数”题型的基本原则．于是，我们可以把原题转化成：

在这个阶梯型方格中，横格代表在第一行的四列，纵格代表第二行的四列，那么此题所有标数的方法就相当于从A走到B的最短路线有多少条． 例如，我们选择一条路线：

7-6.计数方法与技巧综合.题库 教师版 page 10 of 17

它对应的填法就是：．

最后，用“标数法”得出从A到B的最短路径有14种，如下图：

【巩固】将1~12这12个数填入到2行6列的方格表中，使得每行右边比左边的大，每一列上面比下面的大，

共有多少种填法？

【解析】 根据对应关系，再运用阶梯型标数法画图如下：

7-6.计数方法与技巧综合.题库 教师版 page 11 of 17

13242145211121531132429014284891420415161

共有132种填法．

四、不完全对应关系

【例 20】 圆周上有12个点，其中一个点涂红，还有一个点涂了蓝色，其余10个点没有涂色，以这些点为

顶点的凸多边形中，其顶点包含了红点及蓝点的多边形称为双色多边形；只包含红点(蓝点)的多边形称为红色(蓝色)多边形．不包含红点及蓝点的称无色多边形．试问，以这12个点为顶点的所有凸多边形(边数可以从三角形到12边形)中，双色多边形的个数与无色多边形的个数，哪一种较多？多多少个？

【解析】 从任意一个双色的N边形出发(N?5时)，在去掉这个双色多边形中的红色顶点与蓝色顶点后，将

得到一个无色的N?2边形；另一方面，对于一个任意的无色的M边形，如果加上红色顶点和蓝色顶点，就得到一个双色的M?2边形，所以无色多边形与双色多边形中的五边形以上的图形是一一对应的关系，所以双色多边形的个数比较多，多的是双色三角形和双色四边形的个数．而双色三角

2形有10个，双色四边形有C10?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类，比如13254为M类，则与之对应的86754为W类． 所以对于M类的每一个数，W类都有一个数与之对应．但是两类数的个数不是一样多，因为M类中0不能做首位，而W类中9可以做首位．所以W类的数比M类的数要多，多的就是就是首位为9的符合要求的数．

计算首位为9的W类的数的个数，首先要确定另外四个数，因为要求各不相同，从除9外的其它9个数字中选出4个，有C94?126种选法．

对于每一种选法选出来的4个数，假设其大小关系为A4?A3?A2?A1，由于其中最小的数只能在千位和十位上，最大的数只能在百位和个位上，所以符合要求的数有2类：①千位、十位排A1、A2，有两种方法，百位、十位排A3、A4，也有两种方法，故此时共有4种；②千位、十位排A1、A3，只能是千位A3，百位A4，十位A1，个位A2，只有1种方法．

根据乘法原理，首位为9的W类的数有126??4?1??630个．故W类的数比M类的数多630个．

【例 22】 用1元，2元，5元，10元四种面值的纸币若干张(不一定要求每种都有)，组成99元有P 种方法，

组成101元有Q种方法，则Q?P? ．

7-6.计数方法与技巧综合.题库 教师版 page 12 of 17

【解析】 由于101?99?2，所以对于组成99元的每一种方法，只要再加上一张2元的，即可组成101元；而

对于组成101元的方法，如果其中包含有一张2元的，那么去掉这张2元的，即可得到一种组成99元的方法．可见组成99元的方法与组成101元的某些方法之间存在一一对应的关系，组成101元的所有方法中，除去这些与组成99元的方法对应的方法，剩下的都是不包含有2元纸币的组成方法．所以Q比P多的就是用1元，5元，10元这三种面值的纸币组成101元的方法的总数． 假设用x张1元的，y张5元的，z张10元的可以组成101元，则x?5y?10z?101． 由于10z?101，所以z?10．即10元的可以有0～10张． 如果10元的张数确定了，那么有x?5y?101?10z?10?10?z??1?5?20?2z??1，那么y的值可以为

0到?20?2z?，也就是对每一个z的值，y都可以有20?2z?1?21?2z种可能，相应地5元纸币的张数也有21?2z种取法．

而当10元和5元的张数都确定了以后，1元纸币的张数也就确定了，这样也就确定了组成101元的方法．所以只需要看取10元和5元的共有多少种取法．

如果10元的取0张，即z?0，则21?2z?21，即5元的有21种取法； 如果10元的取1张，即z?1，则21?2z?19，即5元的有19种取法； 如果10元的取2张，即z?2，则21?2z?17，即5元的有17种取法； ……

如果10元的取10张，即z?10，则21?2z?1，即5元的有1种取法； 所以总数为21?19?17???1?112?121． 那么Q?P?121．

模块四、递推法

对于某些难以发现其一般情形的计数问题，可以找出其相邻数之间的递归关系，有了这一递归关系就可以利用前面的数求出后面未知的数，这种方法称为递推法．

【例 23】 （难度等级 ※※※）有一堆火柴共12根，如果规定每次取1～3根，那么取完这堆火柴共有多少

种不同取法？

【解析】 取1根火柴有1种方法，取2根火柴有2种方法，取3根火柴有4种取法，以后取任意根火柴的种

数等于取到前三根火柴所有情况之和，以此类推，参照上题列表如下： 1根 2根 3根 4根 5根 6根 7根 8根 9根 10根 11根 12根 1 2 4 7 13 24 44 81 149 274 504 927 取完这堆火柴一共有927种方法．

【巩固】 （难度等级 ※※※）一堆苹果共有8个，如果规定每次取1～3个，那么取完这堆苹果共有多少种

不同取法？

【解析】 取1个苹果有1种方法，取2个苹果有2种方法，取3个苹果有4种取法，以后取任意个苹果的种

数等于取到前三个苹果所有情况之和，以此类推，参照上题列表如下： 1个 1 2个 2 3个 4 4个 7 5个 13 6个 24 7个 44 8个 81 取完这堆苹果一共有81种方法．

【例 24】 有10枚棋子，每次拿出2枚或3枚，要想将10枚棋子全部拿完，共有多少种不同的拿法？ 【解析】 本题可以采用递推法，也可以进行分类讨论，当然也可以直接进行枚举．

(法1)递推法．假设有n枚棋子，每次拿出2枚或3枚，将n枚棋子全部拿完的拿法总数为an种．

7-6.计数方法与技巧综合.题库 教师版 page 13 of 17

则a2?1，a3?1，a4?1．

由于每次拿出2枚或3枚，所以an?an?3?an?2(n?5)．

所以，a5?a2?a3?2；a6?a3?a4?2；a7?a4?a5?3；a8?a5?a6?4；a9?a6?a7?5；a10?a7?a8?7．

即当有10枚棋子时，共有7种不同的拿法． (法2)分类讨论．

由于棋子总数为10枚，是个偶数，而每次拿2枚或3枚，所以其中拿3枚的次数也应该是偶数．由于拿3枚的次数不超过3次，所以只能为0次或2次． 若为0次，则相当于2枚拿了5次，此时有1种拿法；

2若为2次，则2枚也拿了2次，共拿了4次，所以此时有C4?6种拿法． 根据加法原理，共有1?6?7种不同的拿法．

【例 25】 （难度等级 ※※※）用1?3的小长方形覆盖3?8的方格网，共有多少种不同的盖法？

【解析】 如果用1?3的长方形盖3?n的长方形，设种数为an,则a1?1，a2?1,a3?2,对于n?4，左边可能

竖放1个1?3的，也可能横放3个1?3的，前者有an-1种，后者有an-3种，所以an?an-1?an-3,依照这条递推公式列表： 3?1 3?2 3?3 3?4 3?5 3?6 3?7 3?8 1 1 2 3 4 6 9 所以用1?3的小长方形形覆盖3?8的方格网，共有13种不同的盖法． 13

【例 26】 （难度等级 ※※※）如下图，一只蜜蜂从A处出发，回到家里B处，每次只能从一个蜂房爬向右

侧邻近的蜂房而不准逆行，共有多少种回家的方法？

AB

【解析】 按照蜜蜂只能从小号码的蜂房爬近相邻大号码的蜂房的原则，运用标号法进行计算．如右图所示，

小蜜蜂从A出发到B处共有296种不同的回家方法．

【例 27】 有20个石子，一个人分若干次取，每次可以取1个，2个或3个，但是每次取完之后不能留下质

数个，有多少种方法取完石子？（石子之间不作区分，只考虑石子个数）

【解析】 如果没有剩下的不能使质数这个条件，那么递推方法与前面学过的递推法相似，只不过每次都是前

面3个数相加．现在剩下的不能是质数个，可以看作是质数个的取法总数都是0，然后再进行递推．

剩下的石20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 7-6.计数方法与技巧综合.题库 教师版 page 14 of 17

子数 取1 法总数

0 1 0 1 2 3 0 5 0 5 10 15 0 25 0 25 0 0 25 25 【巩固】有20个相同的棋子，一个人分若干次取，每次可取1个，2个，3个或4个，但要求每次取之后留

下的棋子数不是3或4的倍数，有 种不同的方法取完这堆棋子.

【解析】 把20、0和20以内不是3或4的倍数的数写成一串，用递推法把所有的方法数写出来： 20 1 19 1 17 2 14 2 13 4 11 6 10 12 7 18 5 18 2 18 1 36 0 54

【例 28】 4个人进行篮球训练，互相传球接球，要求每个人接球后马上传给别人，开始由甲发球，并作为第

一次传球，第五次传球后，球又回到甲手中，问有多少种传球方法？

【解析】 设第n次传球后，球又回到甲手中的传球方法有an种．可以想象前n?1次传球，如果每一次传球都

n?1任选其他三人中的一人进行传球，即每次传球都有3种可能，由乘法原理，共有3(种)?3?3…?3?3?????????(n?1)个3传球方法．这些传球方法并不是都符合要求的，它们可以分为两类，一类是第n?1次恰好传到甲手中，这有an?1种传法，它们不符合要求，因为这样第n次无法再把球传给甲；另一类是第n?1次传球，球不在甲手中，第n次持球人再将球传给甲，有an种传法．根据加法原理，有

an?1?an?3?3?…?3?3n?1． ???????????(n?1)个3由于甲是发球者，一次传球后球又回到甲手中的传球方法是不存在的，所以a1?0．

利用递推关系可以得到：a2?3?0?3，a3?3?3?3?6，a4?3?3?3?6?21，a5?3?3?3?3?21?60．

这说明经过5次传球后，球仍回到甲手中的传球方法有60种． 本题也可以列表求解．

由于第n次传球后，球不在甲手中的传球方法，第n?1次传球后球就可能回到甲手中，所以只需求出第四次传球后，球不在甲手中的传法共有多少种． 第n次传球 传球的方法 3 球在甲手中的传球方法 0 3 球不在甲手中的传球方法 3 1 2 3 9 6 27 81 243 6 21 60 183 4 5 21 60 从表中可以看出经过五次传球后，球仍回到甲手中的传球方法共有60种．

【巩固】五个人互相传球，由甲开始发球，并作为第一次传球，经过4次传球后，球仍回到甲手中．问：共

有多少种传球方式？

【解析】 递推法．设第n次传球后球传到甲的手中的方法有an种．由于每次传球有4种选择，传n次有4n次

可能．其中有的球在甲的手中，有的球不在甲的手中，球在甲的手中的有an种，球不在甲的手中的，

7-6.计数方法与技巧综合.题库 教师版 page 15 of 17

下一次传球都可以将球传到甲的手中，故有an?1种．所以an?an?1?4n．

由于a1?0，所以a2?41?a1?4，a3?42?a2?12，a4?43?a3?52．即经过4次传球后，球仍回到甲手中的传球方法有52种．

【例 29】 (2009年清华附中考题)设A、E为正八边形ABCDEFGH的相对顶点，顶点A处有一只青蛙，除

顶点E外青蛙可以从正八边形的任一顶点跳到其相邻两个顶点中任意一个，落到顶点E时青蛙就停止跳动，则青蛙从顶点A出发恰好跳10次后落到E的方法总数为 种．

【解析】 可以使用递推法．

回到A 跳到B或H 跳到C或G 跳到D或F 停在E 1步 1 2步 2 1 3步 3 1 4步 6 4 2 5步 10 4 6步 20 14 8 7步 34 14 8步 68 48 28 9步 116 48

其中，第一列的每一个数都等于它的上一行的第二列的数的2倍，第二列的每一个数都等于它的上一行的第一列和第三列的两个数的和，第三列的每一个数都等于它的上一行的第二列和第四列的两个数的和，第四列的每一个数都等于它的上一行的第三列的数，第五列的每一个数都等于都等于它的上一行的第四列的数的2倍．这一规律很容易根据青蛙的跳动规则分析得来． 所以，青蛙第10步跳到E有48?2?96种方法．

【巩固】在正五边形ABCDE上，一只青蛙从A点开始跳动，它每次可以随意跳到相邻两个顶点中的一个上，

一旦跳到D点上就停止跳动．青蛙在6次之内(含6次)跳到D点有 种不同跳法．

ABE

【解析】 采用递推的方法．列表如下：

跳到A 跳到B 跳到C 停在D 跳到E 1步 1 1 2步 2 1 1 3步 3 1 2 4步 5 3 2 5步 8 3 5 6步 13 8 5

其中，根据规则，每次可以随意跳到相邻两个顶点中的一个上，一旦跳到D点上就停止跳动．所以，每一步跳到A的跳法数等于上一步跳到B和E的跳法数之和，每一步跳到B的跳法数等于上一步跳到A和C的跳法数之和，每一步跳到C的跳法数等于上一步跳到B的跳法数，每一步跳到E的跳法数等于上一步跳到A的跳法数，每一步跳到D的跳法数等于上一步跳到C或跳到E的跳法数． 观察可知，上面的递推结果与前面的枚举也相吻合，所以青蛙在6次之内(含6次)跳到D点共有1?1?2?3?5?12种不同的跳法．

7-6.计数方法与技巧综合.题库 教师版 page 16 of 17

CD 【例 30】 (2006年“迎春杯”中年级组决赛)有6个木箱，编号为1，2，3，??，6，每个箱子有一把钥匙，

6把钥匙各不相同，每个箱子放进一把钥匙锁好．先挖开1，2号箱子，可以取出钥匙去开箱子上的锁，如果最终能把6把锁都打开，则说这是一种放钥匙的“好”的方法，那么“好”的方法共有 种．

【解析】 (法1)分类讨论．如果1，2号箱中恰好放的就是1，2号箱的钥匙，显然不是“好”的方法，所以

“好”的方法有两种情况：

⑴1，2号箱的钥匙恰有1把在1，2号箱中，另一箱装的是3～6箱的钥匙． ⑵1，2号箱的钥匙都不在1，2号箱中．

对于⑴，从1，2号箱的钥匙中选1把，从3～6号箱的钥匙中选1把，共有2?4?8(种)选法，每一种选法放入1，2号箱各有2种放法，共有8?2?16(种)放法．

不妨设1，3号箱的钥匙放入了1，2号箱，此时3号箱不能装2号箱的钥匙，有3种选法，依次类推，可知此时不同的放法有3?2?1?6(种)．

所以，第⑴种情况有“好”的方法16?6?96(种)．

对于⑵，从3～6号箱的钥匙中选2把放入1，2号箱，有4?3?12(种)放法．不妨设3，4号箱的钥匙放入了1，2号箱．

此时1，2号箱的钥匙不可能都放在3，4号箱中，也就是说3，4号箱中至少有1把5，6号箱的钥匙．

如果3，4号箱中有2把5，6号箱的钥匙，也就是说3，4号箱中放的恰好是5，6号箱的钥匙，那么1，2号箱的钥匙放在5，6号箱中，有2?2?4种放法；

如果3，4号箱中有1把5，6号箱的钥匙，比如3，4号箱中放的是5，1号箱的钥匙，则只能是5号箱放6号箱的钥匙，6号箱放2号箱的钥匙，有2?1?2种放法；

同理，3，4号箱放5，2号箱或6，1号箱或6，2号箱的钥匙，也各有2种放法． 所以，第⑵种情况有“好”的放法12??4?2?2?2?2??144(种)．

所以“好”的方法共有96?144?240(种)．

(法2)递推法．设第1，2，3，…，6号箱子中所放的钥匙号码依次为k1，k2，k3，…，k6．当箱子数为n(n?2)时，好的放法的总数为an．

当n?2时，显然a2?2(k1?1，k2?2或k1?2，k2?1)．

当n?3时，显然k3?3，否则第3个箱子打不开，从而k1?3或k2?3，如果k1?3，则把1号箱子和3号箱子看作一个整体，这样还是锁着1，2两号钥匙，撬开1，2两号箱子，那么方法有a2种；当k2?3也是如此．于是n?2时的每一种情况对应k1?3或k2?3时的一种情况，这样就有a3?2a2?4．

当n?4时，也一定有kn?n，否则第n个箱子打不开，从而k1、k2、……、kn?1中有一个为n，不论其中哪一个是n，由于必须要把该箱子打开才能打开n号箱子，所以可以将锁着这把钥匙的箱子与第n号箱子看作1个箱子，于是还是锁着k1、k2、……、kn?1这?n?1?把钥匙，需要撬开1，2两号箱子，所以每种情况都有an?1种．所以an??n?1?an?1．

所以，a6?5a5?5?4a4???5?4?3?2a2?2?5!?240，即好的方法总数为240种．

7-6.计数方法与技巧综合.题库 教师版 page 17 of 17

本文来源：https://www.bwwdw.com/article/so7g.html