它对应的填法就是：．
最后，用“标数法”得出从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次，共拿了4次，所以此时有C42?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 13 所以用1?3的小长方形形覆盖3?8的方格网，共有13种不同的盖法．
【例 26】 （难度等级 ※※※）如下图，一只蜜蜂从A处出发，回到家里B处，每次只能从一个蜂房爬向右
侧邻近的蜂房而不准逆行，共有多少种回家的方法？
AB
【解析】 按照蜜蜂只能从小号码的蜂房爬近相邻大号码的蜂房的原则，运用标号法进行计算．如右图所示，
小蜜蜂从A出发到B处共有296种不同的回家方法．
【例 27】 有20个石子，一个人分若干次取，每次可以取1个，2个或3个，但是每次取完之后不能留下质
数个，有多少种方法取完石子？（石子之间不作区分，只考虑石子个数）
【解析】 如果没有剩下的不能使质数这个条件，那么递推方法与前面学过的递推法相似，只不过每次都是前
面3个数相加．现在剩下的不能是质数个，可以看作是质数个的取法总数都是0，然后再进行递推． 剩下的石7-6.计数方法与技巧综合.题库 教师版 page 14 of 17 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 子数 取法总数 【巩固】有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 1 0 1 0 1 2 3 0 5 0 5 10 15 0 25 0 25 0 0 25 25
【例 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?3???????????(n?1)个3n?1．
由于甲是发球者，一次传球后球又回到甲手中的传球方法是不存在的，所以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次传球 1 2传球的方法 3 9球在甲手中的传球方法 0球不在甲手中的传球方法 36 3 63 27 81 243 21601834521 60从表中可以看出经过五次传球后，球仍回到甲手中的传球方法共有60种．
【巩固】五个人互相传球，由甲开始发球，并作为第一次传球，经过4次传球后，球仍回到甲手中．问：共
有多少种传球方式？
【解析】 递推法．设第n次传球后球传到甲的手中的方法有an种．由于每次传球有4种选择，传n次有4n次
可能．其中有的球在甲的手中，有的球不在甲的手中，球在甲的手中的有an种，球不在甲的手中的，
7-6.计数方法与技巧综合.题库 教师版 page 15 of 17