7-6-4.计数之递推法
前面在讲加法原理、乘法原理、排列组合时已经穿插讲解了计数中的一些常用的方法，比如枚举法、树形图法、标数法、捆绑法、排除法、插板法等等，这里再集中学习一下计数中其他常见的方法，主要有归纳法、整体法、对应法、递推法．对这些计数方法与技巧要做到灵活运用．
教学目标
对于某些难以发现其一般情形的计数问题，可以找出其相邻数之间的递归关系，有了这一递归关系就可以利用前面的数求出后面未知的数，这种方法称为递推法． 【例 1】 每对小兔子在出生后一个月就长成大兔子，而每对大兔子每个月能生出一对小兔子来．如果一个人
在一月份买了一对小兔子，那么十二月份的时候他共有多少对兔子？ 【考点】计数之递推法 【难度】3星 【题型】解答
【解析】 第一个月，有1对小兔子；第二个月，长成大兔子，所以还是1对；第三个月，大兔子生下一对小
兔子，所以共有2对；第四个月，刚生下的小兔子长成大兔子，而原来的大兔子又生下一对小兔子，共有3对；第五个月，两对大兔子生下2对小兔子，共有5对；……这个特点的说明每月的大兔子数为上月的兔子数，每月的小兔子数为上月的大兔子数，即上上月的兔子数，所以每月的兔子数为上月的兔子数与上上月的兔子数相加． 依次类推可以列出下表： 经过月数：---1---2---3---4---5---6---7---8---9---10---11---12
兔子对数：---1---1---2---3---5---8--13--21--34--55--89—144，所以十二月份的时候总共有144对兔子．
【答案】144
【例 2】 树木生长的过程中，新生的枝条往往需要一段“休息”时间供自身生长，而后才能萌发新枝．一棵树
苗在一年后长出一条新枝，第二年新枝“休息”，老枝依旧萌发新枝；此后，老枝与“休息”过一年的枝同时萌发，当年生的新枝则依次“休息”．这在生物学上称为“鲁德维格定律”．那么十年后这棵树上有多少条树枝？ 【考点】计数之递推法 【难度】3星 【题型】解答
【解析】 一株树木各个年份的枝桠数，构成斐波那契数列：1，2，3，5，8，13，21，34，55，89，……所以
十年后树上有89条树枝．
【答案】89
【例 3】 一楼梯共10级，规定每步只能跨上一级或两级，要登上第10级，共有多少种不同走法？ 【考点】计数之递推法 【难度】4星 【题型】解答
例题精讲
【解析】 登 1级 2级 3级 4级 ...... 10级
1种方法 2种 3种 5种 ...... ？
我们观察每级的种数，发现这么一个规律：从第三个数开始，每个数是前面两个数的和；依此规律我们就可以知道了第10级的种数是89.其实这也是加法的运用：假如我们把这个人开始登楼梯的位置看做A0，那么登了1级的位置是在A1，2级在A2... A10级就在A10．到A3的前一步有两个位置；分别是A2 和A1 ．在这里要强调一点，那么A2 到A3 既然是一步到了，那么A2 、A3之间就是一种选择了；同理A1 到A3 也是一种选择了．同时我们假设到n级的选择数就是An ．那么从A0 到A3 就可以分成两类了：第一类：A0 ---- A1 ------ A3 ，那么就可以分成两步．有A1×1种，也就是A1 种；(A1 ------ A3 是一种选择)第二类：A0 ---- A2 ------ A3， 同样道理 有A2 ．类类相加原理：A3 = A1 ＋A2，依次类推An = An-1 + An-2．
【答案】89
【巩固】一楼梯共10级，规定每步只能跨上一级或三级，要登上第10级，共有多少种不同走法？ 【考点】计数之递推法 【难度】4星 【题型】解答
【解析】 登 1级 2级 3级 4级 5级 ...... 10级
1种方法 1种 2种 3种 4种...... ？
我们观察每级的种数，发现这么一个规律：从第三个数开始，每个数是前面相隔的两个数的和；依此规律我们就可以知道了第10级的种数是28.
【答案】28
【例 4】 1×2的小长方形(横的竖的都行)覆盖2×10的方格网，共有多少种不同的盖法． 【考点】计数之递推法 【难度】4星 【题型】解答
【解析】 如果用1?2的长方形盖2?n的长方形，设种数为an,则a1?1，a2?2,对于n?3，左边可能竖放1个
1?2的，也可能横放2个1?2的，前者有an-1种，后者有an-2种，所以an?an-1?an-2,所以根据递推，
覆盖2?10的长方形一共有89种．
【答案】89
【例 5】 用1?3的小长方形覆盖3?8的方格网，共有多少种不同的盖法？ 【考点】计数之递推法 【难度】5星 【题型】解答
【解析】 如果用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 1 1 3?3 2 3?4 3 3?5 4 3?6 6 3?7 9 3?8 13 所以用1?3的小长方形形覆盖3?8的方格网，共有13种不同的盖法． 【答案】13
【例 6】 有一堆火柴共12根，如果规定每次取1～3根，那么取完这堆火柴共有多少种不同取法？ 【考点】计数之递推法 【难度】4星 【题型】解答
【解析】 取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种方法． 【答案】927
【巩固】 一堆苹果共有8个，如果规定每次取1～3个，那么取完这堆苹果共有多少种不同取法？ 【考点】计数之递推法 【难度】4星 【题型】解答
【解析】 取1个苹果有1种方法，取2个苹果有2种方法，取3个苹果有4种取法，以后取任意个苹果的种
数等于取到前三个苹果所有情况之和，以此类推，参照上题列表如下： 1个 1 2个 2 3个 4 4个 7 5个 13 6个 24 7个 44 8个 81 取完这堆苹果一共有81种方法． 【答案】81
【例 7】 有10枚棋子，每次拿出2枚或3枚，要想将10枚棋子全部拿完，共有多少种不同的拿法？ 【考点】计数之递推法 【难度】4星 【题型】解答
【解析】 本题可以采用递推法，也可以进行分类讨论，当然也可以直接进行枚举．
(法1)递推法．假设有n枚棋子，每次拿出2枚或3枚，将n枚棋子全部拿完的拿法总数为an种． 则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?6种拿法． 若为2次，则2枚也拿了2次，共拿了4次，所以此时有C4根据加法原理，共有1?6?7种不同的拿法．
【答案】7
【例 8】 如下图，一只蜜蜂从A处出发，回到家里B处，每次只能从一个蜂房爬向右侧邻近的蜂房而不准逆
行，共有多少种回家的方法？ 【考点】计数之递推法 【难度】4星 【题型】解答
11323558721955B89ABA124613834
【解析】 蜜蜂“每次只能从一个蜂房爬向右侧邻近的蜂房而不准逆行”这意味着它只能从小号码的蜂房爬近相
邻大号码的蜂房．明确了行走路径的方向，就可以运用标数法进行计算．如右图所示，小蜜蜂从A出发到B处共有89种不同的回家方法．
【答案】89
【巩固】小蜜蜂通过蜂巢房间，规定只能由小号房间进入大号房间问小蜜蜂由A房间到达B 房间有多少种
方法？ 【考点】计数之递推法 【难度】4星 【题型】解答 【解析】 斐波那契数列第八项．21种．
12357846【答案】21
【例 9】 如下图，一只蜜蜂从A处出发，回到家里B处，每次只能从一个蜂房爬向右侧邻近的蜂房而不准逆
行，共有多少种回家的方法？ 【考点】计数之递推法 【难度】4星 【题型】解答
AB
【解析】 按照蜜蜂只能从小号码的蜂房爬近相邻大号码的蜂房的原则，运用标号法进行计算．如右图所示，
小蜜蜂从A出发到B处共有296种不同的回家方法．
【答案】296
【例 10】 对一个自然数作如下操作：如果是偶数则除以2，如果是奇数则加1，如此进行直到得数为1
操作停止．问经过9次操作变为1的数有多少个？ 【考点】计数之递推法 【难度】4星 【题型】解答 【解析】 可以先尝试一下，倒推得出下面的图：
5312487161415326121011241328303164其中经1次操作变为1的1个，即2， 经2次操作变为1的1个，即4， 经3次操作变为1的2个，是一奇一偶，
以后发现，每个偶数可以变成两个数，分别是一奇一偶，每个奇数变为一个偶数，于是，经1、2、…次操作变为1的数的个数依次为：1，1，2，3，5，8，…
这一串数中有个特点：自第三个开始，每一个等于前两个的和，即即经过9次操作变为1的数有34个.
为什么上面的规律是正确的呢？
道理也很简单. 设经过n次操作变为1的数的个数为an,则a1?1，a2?1，a3?2，… 从上面的图看出，an?1比an大.
一方面，每个经过n次操作变为1的数，乘以2，就得出一个偶数，经过n?1次操作变为1；反过来，每个经过n?1次操作变为1的偶数，除以2，就得出一个经过n次操作变为1的数. 所以经过n次操作变为1的数与经过n?1次操作变为1的偶数恰好一样多.前者的个数是an,因此后者也是an个. 另一方面，每个经过n次操作变为1的偶数，减去1，就得出一个奇数，它经过n?1次操作变为1，反过来.每个经过n?1次操作变为1的奇数，加上1，就得出一个偶数，它经过n次操作变为1. 所以经过n次操作变为1的偶数经过n?1次操作变为1的奇数恰好一样多. 而由上面所说，前者的个数就是an?1,因此后者也是an?1.
经过n?1次操作变为1的数，分为偶数、奇数两类，所以an?1?an?an?1，即上面所说的规律的确成立.
【答案】34
【例 11】 有20个石子，一个人分若干次取，每次可以取1个，2个或3个，但是每次取完之后不能留下
质数个，有多少种方法取完石子？（石子之间不作区分，只考虑石子个数） 【考点】计数之递推法 【难度】5星 【题型】解答
【解析】 如果没有剩下的不能使质数这个条件，那么递推方法与前面学过的递推法相似，只不过每次都是前
面3个数相加．现在剩下的不能是质数个，可以看作是质数个的取法总数都是0，然后再进行递推．
【答案】25
【巩固】有20个相同的棋子，一个人分若干次取，每次可取1个，2个，3个或4个，但要求每次取之后留
下的棋子数不是3或4的倍数，有 种不同的方法取完这堆棋子.
【考点】计数之递推法 【难度】5星 【题型】填空
【解析】 把20、0和20以内不是3或4的倍数的数写成一串，用递推法把所有的方法数写出来：
【答案】54
【例 12】 4个人进行篮球训练，互相传球接球，要求每个人接球后马上传给别人，开始由甲发球，并作
为第一次传球，第五次传球后，球又回到甲手中，问有多少种传球方法？ 【考点】计数之递推法 【难度】5星 【题型】解答
【解析】 设第n次传球后，球又回到甲手中的传球方法有an种．可以想象前n?1次传球，如果每一次传球都
任选其他三人中的一人进行传球，即每次传球都有3种可能，由乘法原理，共有3?3?3…?3?3n?1(种)
(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次传球后球就可能回到甲手中，所以只需求出第四次传球后，球不在甲手中的传法共有多少种．
从表中可以看出经过五次传球后，球仍回到甲手中的传球方法共有60种．
【答案】60
【巩固】五个人互相传球，由甲开始发球，并作为第一次传球，经过4次传球后，球仍回到甲手中．问：共
有多少种传球方式？ 【考点】计数之递推法 【难度】5星 【题型】解答
【解析】 递推法．设第n次传球后球传到甲的手中的方法有an种．由于每次传球有4种选择，传n次有4n次
可能．其中有的球在甲的手中，有的球不在甲的手中，球在甲的手中的有an种，球不在甲的手中的，下一次传球都可以将球传到甲的手中，故有an?1种．所以an?an?1?4n．
由于a1?0，所以a2?41?a1?4，a3?42?a2?12，a4?43?a3?52．即经过4次传球后，球仍回到甲手中的传球方法有52种．
【答案】52
【例 13】 设A、E为正八边形ABCDEFGH的相对顶点，顶点A处有一只青蛙，除顶点E外青蛙可以从
正八边形的任一顶点跳到其相邻两个顶点中任意一个，落到顶点E时青蛙就停止跳动，则青蛙从顶
点A出发恰好跳10次后落到E的方法总数为 种．
【考点】计数之递推法 【难度】5星 【题型】填空 【关键词】清华附中 【解析】 可以使用递推法．
回到A 2 6
跳到B或H 1 3
1 4
1 4 14 48
28
8
2
跳到C或G
跳到D或F
停在E
1步 2步 3步 4步 5步 6步 7步 8步 9步
10 34 116
20 68
14 48
其中，第一列的每一个数都等于它的上一行的第二列的数的2倍，第二列的每一个数都等于它的上一行的第一列和第三列的两个数的和，第三列的每一个数都等于它的上一行的第二列和第四列的两个数的和，第四列的每一个数都等于它的上一行的第三列的数，第五列的每一个数都等于都等于它的上一行的第四列的数的2倍．这一规律很容易根据青蛙的跳动规则分析得来． 所以，青蛙第10步跳到E有48?2?96种方法．
【答案】96
【巩固】在正五边形ABCDE上，一只青蛙从A点开始跳动，它每次可以随意跳到相邻两个顶点中的一个上，
一旦跳到D点上就停止跳动．青蛙在6次之内(含6次)跳到D点有 种不同跳法． 【考点】计数之递推法 【难度】5星 【题型】填空
ABECD【解析】 采用递推的方法．列表如下：
跳到A
2 5 13
跳到B
跳到C
1步 2步 3步 4步 5步 6步
跳到E
停在D
1 1
1 1
1 2 2
3 5 5
3 8
3 8
其中，根据规则，每次可以随意跳到相邻两个顶点中的一个上，一旦跳到D点上就停止跳动．所以，每一步跳到A的跳法数等于上一步跳到B和E的跳法数之和，每一步跳到B的跳法数等于上一步跳到A和C的跳法数之和，每一步跳到C的跳法数等于上一步跳到B的跳法数，每一步跳到E的跳法数等于上一步跳到A的跳法数，每一步跳到D的跳法数等于上一步跳到C或跳到E的跳法数． 观察可知，上面的递推结果与前面的枚举也相吻合，所以青蛙在6次之内(含6次)跳到D点共有
1?1?2?3?5?12种不同的跳法．
【答案】12
【例 14】 有6个木箱，编号为1，2，3，……，6，每个箱子有一把钥匙，6把钥匙各不相同，每个箱子
放进一把钥匙锁好．先挖开1，2号箱子，可以取出钥匙去开箱子上的锁，如果最终能把6把锁都打开，则说这是一种放钥匙的“好”的方法，那么“好”的方法共有 种． 【考点】计数之递推法 【难度】5星 【题型】填空 【关键词】迎春杯，中年级组，决赛
【解析】 (法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种．
【答案】240
【巩固】有10个木箱，编号为1，2，3，……，10，每个箱子有一把钥匙，10把钥匙各不相同，每个箱子放
进一把钥匙锁好．先挖开1，2号箱子，可以取出钥匙去开箱子上的锁，如果最终能把10把锁都打
开，则说这是一种放钥匙的“好”的方法，那么“好”的方法共有 种．
【考点】计数之递推法 【难度】5星 【题型】填空
【解析】 递推法．设第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． 所以，a10?9a9?9?8a8?种．
【答案】725760
?9?8?7?6?5?4?3?2a2?2?9!=725760，即好的方法总数为725760
小学奥数 计数之递推法 精选练习例题 含答案解析（附知识点拨及考点）
