第三讲 递推计数

例题

1. 答案：927
   详解：将作文数量与完成作文的方法数列成一张表格，如下所示：
   

下面解释一下这张数表是如何累加得到的．写1、2、3篇作文的方法数可以枚举得到．写4篇作文的完成方法数可以分三类去数：如果第一天写1篇，那么参考数表可得，剩下3篇有4种完成方法；如果第一天写2篇，同样参考数表可得，剩下2篇有2种完成方法；如果第一天写3篇，那么剩下1篇还有1种完成方法——因此4篇作文的完成方法总数为 ，如上表箭头所示．接着分析5篇作文的完成方法数，仍然分三类：第一天写1篇，那么参考数表可得，剩下4篇还有7种完成方法；第一天写2篇，那么剩下3篇还有4种完成方法；第一天写3篇，那么剩下2篇还有2种完成方法——因此5篇作文的完成方法数等于 ……以此类推便可填满整张表格．

2. 答案：28
   详解：我们同样可以列出一个递推数列，将其表示如下：
   
   下面详细说明该问题的递推规律．覆盖1×3、2×3和3×3方格表的方法数可以枚举得到．接着分析覆盖4×3的表格有几种覆盖方法．如下图所示，左上角的阴影方格在覆盖的时候有两种方法：竖着覆盖或横着覆盖．当竖着覆盖时，余下部分恰好是一个3×3的方格表，覆盖方法数为2；当横着覆盖时，其下方的方格只能被横放的纸片盖住，因此只剩下一个1×3的方格表需要覆盖，方法数为1．由此可得4×3表格的方法数为2+1=3．用同样的方法分析5×3的
   方格表，可得其覆盖方法数等于 的方法数加上 的方法数，因此等于 ．接着以此类推即可．
   
   

3. 答案：5051
   详解：我们同样可以列出一个递推数列，将其写为如下的一张数表：
   
   下面详细说明该递推过程．平面上有1、2、3条直线的情形画图即可解决，我们从第4条直线开始分析．如右图所示，当画上第4条直线时，会把原有的区域一分为二（如编号为I、II、III、IV的4个区域），因此会增加4个新区域．而之所以能产生4个新区域，就是由于第4条直线会与原有的3条直线产生3个交点，而这3个交点会把第4条直线分为4部分，每一部分都会位于一个原有的区域中，因此每一部分都就会把原有的某个区域一分为二，因此直线被分为几部分，区域数量自然也就增加几部分．上述逻辑关系在下方右侧有明确的表示．由此可得，增加到第n条直线就会增加n个新区域，因此答案是 ．
   

4. 答案：1641
   详解：本题的方法称为“传球法”．传球法在很多问题中有着广泛的应用．如右侧表格所示，除了第“0”行外，其余每一行的数量都是由上一行的数量通过某种规则累加得到的．比如第“1”行A下方的0，就是通过第“0”行B、C、D的数量相加得到的；第“3”行B下方的7，就是通过第“2”行A、C、D的数量相加得到的；第“4”行C下方的20，就是通过第“5”行A、B、D的数量相加得到的；第“6”行D下方的182，就是通过第“5”行A、B、C的数量相加得到的．之所以有这样的累加规则，就是因为A想拿球，必须由B、C、D传球给他，所以他下方的数也必须由B、C、D累加给他——这就是传球规则决定累加规则．依据这一累加规则，我们不停地将数表向下累加，每传一次球就多累加一行，最后得到第“8”行．这一行的四个数分别为1641、1640、1640和1640．他们分别表示8次传球后，由A、B、C、D拿球的传球方法数．由于题目要求最后球回到A手中，因此答案为1641种．
   
   

5. 答案：1224
   详解：我们把这个七位数看作是1、2、3三个人之间传6次球的一个传球顺序，具体的传球规则是：1能传球给2、3，但不能给自己；2、3都能传球给1、2、3．依据“传球规则决定累加规则”，我们可以列出如右表所示的一张递推表格．表格的第“0”行是发球行，对应的是这个七位数的首位数字．由于1、2、3都能作首位，因此第“0”行写的都是1．接着按照传球规则累加即可．表格中第“6”行（最后一行）中的三个数分别表示第六次传球后，球在1、2、3手中的方法数，对于七位数而言，就是表示分别以1、2、3结尾的符合题意的七位数有多少个．所以最后答案应该把它们全加起来，等于328+448+448=1224．

6. 答案：42
   详解：我们依照连续偶数的次序进行递推累加．（1）圆周上有2个点，只有1种连法．（2）圆周上有4个点，只有2种连法．（3）圆周上有6个点A₁、A₂、A₃、A₄、A₅、A₆（如下左图），那么与A₁相连的点只能是A₂、A₄或A₆．依次分三类情况讨论：第一，A₁连A₂，剩下4个点连法数为2；第二，A₁连A₄，剩下4个点连法数为1；第三，A₁连A₄，剩下4个点连法数也为2．由此可得，6个点共有5种不同的连法．（4）如果圆周上有8个点A₁、A₂、A₃、A₄、A₅、A₆、A₇、A₈（如下右图），那么与A₁相连的点有四种可能，分别是A₂、A₄、A₆或A₈．以此分四类讨论，共14种方法．
   （5）如果圆周上有10个点，同样考虑能与A₁相连的点，分五类讨论，如下图所示．共42种方法．
   
   评析：本题虽然不像之前那样，只遵循一个简单的累加规则，但也仍然是一个由小求大的递推过程：在求解6个点的方法数时，会用到2个、4个点的方法数；在求解8个点的方法数时，也会用到2个、4个、6个点的方法数；而在求解10个点的方法数时，则会用到2个、4个、6个、8个点的方法数……由此可见“由小求大”应该说是递推法真正的内涵．我们再处理问题时，要有能力将数目较大的情形通过变形，化归为数目较小的情形来解决．
   另外，请大家观察右图．从A处出发，每次只能向右或向上走一步，那么从A到B、C、D、E、F的最短路径分别有多少？大家不妨用标数法（参考四年级上册第16讲《加法原理与乘法原理》）自己做一做，在把相应的结果与本题的结果对照一下，你能发现其中的奥妙吗？

练习：

练习1、

答案：12

简答：仿照例题1进行分类讨论，列出如下数表进行累加即可，注意累加规则．

练习2、
答案：21

简答：仿照例题2，找到左上角的方格，按照该方格是横着覆盖还是竖着覆盖分两类讨论即可得递推规则．

练习3、

答案：1276

简答：本题与直线分平面的问题本质相同，因此与例题3类似进行递推即可．如下表所示

练习4、

答案：43

简答：本题的传球规则和例题4相同，都只能把球传给别人，因此累加规则也相同．但最后的拿球人不是发球人这一点要注意！

作业：

1. 答案：89
   简答：
   
   

2. 答案：36
   简答：
   
   

3. 答案：14
   简答：略．

4. 答案：3277
   简答：如右表所示，用传球法列表解决．传球规则是：0不能发球，其它都可以发球；传球不能传给自己，只能传给别人；总共传球传6次．

5. 答案：29
   简答：如下方左图所示，和例题2类似，找到某个方格，依据这个方格是横着覆盖还是竖着覆盖分两种情况讨论．情况一，横着覆盖：这类情况其实就是 的覆盖方法，利用练习2的分析方法和相关结论，可得答案为21．情况二，竖着覆盖：在这类情况下，有另外四个格子的覆盖方法唯一确定，如下方右图中的虚线所示，剩下需要覆盖的是一个 的方格表，其方法数量也可参考练习2的分析方法和相关结论来取得，答案为8．上述两种情况相加，可得答案为 ．