递推与计数

引例：在介绍“递推方法”的时候，我们接触过以下计数问题： （1）n条直线最多有几个交点？

（2）n条直线最多将平面分成几块？

（3）平面上n个圆最多将平面划分成多少块？ （4）平面上n个椭圆最多将平面划分成多少块？ 解析：（1）anan1n1,a10

（2）第n条直线与前面n1条直线最多有n1个交点，这n1个交点将直线分成了n段（n2段线段，2段射线），每段使得平面区域多了一块，故增加了n块，所以anan1n,a12

（3）第n个圆与前n1个圆最多2(n1)个交点，产生2(n1)条弧，即增加了

2(n1)个区域，所以anan12(n1),a12

（4）第n个圆与前n1个圆最多4(n1)个交点，产生4(n1)条弧，即增加了

2(n1)个区域，所以anan14(n1),a12

例1：欲登上第10级楼梯，如果规定每步只能跨上一级或两级，则不同的走法共有多少种？

解：方法一

第一类：没有一步两级，则只有一种走法；

第二类：恰有一步是一步两级，则走完10级要走9步，9步中选一步是一步两级的，有C91种走法。

第三类：恰有两步是一步两级，则走完10级要走8步，8步中选两步是一步两级的，有C92种可能走法；

„„

12345C8C7C6C589种走法。 依此类推，共有1C9方法二

设走n级台阶有an种走法，则这些走法可按第一步分类： 第一类：第一步是一步一级，则余下的n1级有an1种走法； 第二类：第一步是一步两级，则余下的n2级有an2种走法；

所以anan1an2，又a11,a22，anFn1115[25n2152n2]

例2：（2008年全国I高考） 如图所示，一环形花坛分成1、2、3、4四块。现有4种不同的花供选择，要求在每块里种一种花，且相邻的2块不能种同一种花，则不同的种法总数为？ 解：方法一

第一类：1,3同色：有4×3×1×3=36种

第二类：1,3异色：有4×3×2×2=48种，共有36+48=84种.

方法二 递推法，看下面的推广

推广（染色问题）：一个圆形区域分成n个不全等的扇形区域，用m种颜色涂这些扇形，使相邻的扇形没有相同的颜色，问共有多少种染法？ 解：令an表示n个扇形的所有满足条件的染法数目，顺时针用R1,R2,,Rn表示这n个扇形

思路一：扇形Rn的涂色方法，至多有两种情况：

第一种情况：Rn1和R1同色，这时Rn有m1种颜色可供选择，并且扇形R1至

Rn2有an2种涂色方法，所以共有(m1)an2种染法。

第二种情况：Rn1和R1异色，这时Rn有m2种颜色可供选择，并且扇形R1至Rn1有an1种涂色方法。所以共有(m2)an1种染法，故知涂色方法总数的递推方程为：

anm1an2m2an1a2mm1,a3mm1m2

解得an(1)n(m1)(m1)n

思路二： 第一步：染R1，有m种染法；

第二步：染R2，有m1种染法；（避免与R1重复） „„

同理，染R3,,Rn1均有m1种染法，最后染Rn，如果仅考虑Rn与Rn1不同色（此时没考虑Rn与R1是否同色），则仍有m1种染法，相乘得m(m1)n1种染法。但要排除Rn与R1同色的染法数，此时可将Rn与R1合并看成一个点，故需要排除的染法数为an1，所以anm(m1)n1an1，解得an(1)n(m1)(m1)n。

于是在本题中，mn4所以a4=84，即84种种法。

（思考：如果经过一个小变化，就是中间那个圆里也要种花，其他要求不变，问现在共有多少种方法？）（这仍然是一道全国高考试题）

练习：（1）如图1，一个地区分为5个行政区域，现给地图着色，要求相邻区域不得使用同一颜色，现有四种颜色可供选择，则不同的着色方法共有 种。（以数字作答）(2003年全国高考试题)

（2）某城市在中心广场建造一个花圃，花圃分成6个部分(如图2)，现要栽种4种不同颜色的花，每部分栽种一种且相邻部分不能栽种同样颜色的花，不同的栽种方法共有 种。（以数字作答）(2003年天津理科高考试题) （3）在一个正六边形的六个区域栽种观赏植物(如图)，要求同一块种种植一种植物，相邻的两块种植不同的植物.现有4种不同的植物可供选择，则有________种栽种方案.（2001全国高中数学联赛）

2 5

5 1 1 6 4 3

3 2 4

图2

图1

(1)第一步：中间一块有5种涂法，第二步：其他4块，就是m3,n4的染色问题，即a418，得出共有41872种涂法。 （2）同（1）4a5120（m3） （3）n6,m4,a6732

例3：（错位问题）有n封信装进n个信封里，结果发现这n封信全部装错了那么装错的情况总共有多少种？ 解法一：设满足这样的装信方式有an种，

第一步：第一封信不装在原来的第一个位置，有n1种装法。

第二步：假设第一封信装在第2个位置，则第二封信的装法又可以分为两类： 第一类，第二封信恰好装在第一个位置，则余下的n2封信有an2种装信方式；第二类，第二封信不装在第一个位置，则就是第二封信不装在第一个位置，第三封信不装在第三个位置，„„，第n封信不装在第n个位置，所以有an1种装信方式。得递推关系：an(n1)(an2an1),a10,a21。 annan1[an1(n1)an2](1)n1(a2a1)(1)n 得

解法二：（容斥原理）设I{(a1,,an)|ai{1,2,,n}},Ai{(a1,,an)I|aii}

n。

ann!an1(n1)!(1)n，累加得ann!(1)n

n!n!2!3!4!1111则an|I||Ai|，注意到|Ai|(n1)!,|AiAj|(n2)!|A1A2An|1i1n由容斥原理，|Ai|n(n1)!Cn2(n2)!Cn3(n3)!(1)n1Cnn0!

i111111n11n1，n!1(1)an!(1)n2!3!n!n!2!3!4!

练习：(1993年全国高考试题)同室4人各写一张贺年卡，先集中起来，然后每

人从中拿一张别人送出的贺年卡，则4张贺年卡不同的分配方式共有( )

（A）6种 （B）9种 （C）11种 （D）23种

例4：（Hanoi塔问题）N个圆盘按从小到大的顺序依次套在柱A上，如图所示。规定每次只能从一根柱子上搬动一个圆盘到另一根柱子上，且要求在搬动过程中不允许大盘放在小盘上，而且只有A,B,C三根柱子可供使用，求将n个盘从柱A移到柱C上所需搬动圆盘的最少次数.

例5：（信号传输问题）在信道上传输a,b,c构成的字符串(长度为n)，两个a相连的串不能传，求允许传输的串的个数。

解：用an表示该信道允许传的长度为n的串的个数，显然，

a13,a2318，当n3时，将符合要求的串分为两类：

2第一类： 第一字母不是a的串有2an1个；

第二类： 首字母为a，次字母必为b或c，这样的串有2an2个。 综合以上情况有：an2(an1an2),a13,a28

例6：甲、乙、丙、丁四人相互传球，第一次甲传给乙、丙、丁中的任一人，第二次由拿球者再传给其他人中任一人，这样共传了四次，则第四次球仍传回到甲的方法共有( )

（A）21种 （B）42 （C）24 （D）27

推广：（传球问题）m(mN)个人相互进行n(nN)次传球，由甲先传，第一次甲传给其他m1个人中的任一人，第二次由拿球者再传给其他人中任一人，这样经过n次传球，最后球仍回到甲手中的传球方法有多少种？

解：设不同的传球方法共有an种， 第一步进行第一次传球：甲传给其他人，有m1种传球方法；

第二步进行第二次传球：拿球者把球传给其他人，仍有m1种传球方法； 同理，第三次、第四次、„„、第n1次传球都有m1种传球方法，最后进行第n次传球，由于只能传给甲，故只有一次传球方法，相乘得(m1)n1种传球方法，但要注意第n1次传球不能传给甲，否则就不存在第n次传球，因此要去掉第n1次传球，球恰好传给甲的传球方法数，而这恰好就是由甲先传，经过n1次传球后球又回到甲手中的传球方法，显然，这里有an1种传球方法，所以有递推关系：an(m1)n1an1，a10，易得an而在本题中，m4，a4

1441m[(m1)(1)(m1)]

nn(33)21，故本题应选（A）

练习：

（1）A,B二人拿两颗骰子做抛掷游戏，规则如下：若掷出的点数之和为3的倍数时，原掷骰子的人再继续掷；若掷出的点数不是3的倍数时就由对方接着掷，第一次由A开始掷，求第n次仍由A掷的概率Pn. （2）袋子里有10个相同的小球，现在把这些球全部摸出来，一次可以摸一个球，也可以摸两个球，则不同的摸法共有多少种？恰好7次摸完的概率为多少？ （3）五本不同的书分给五个同学，而每个同学都看过其中的一本书，但没有两个同学看过同一本书，则每个同学分到恰好是他没有看过的书概率为多少？恰有一个同学分到他看过的书的概论为多少？

（4）有一堆大小相同的小球，里面有红色、黄色、白色，并且每种颜色的球至少都有3个，现从中任取6个球排成一圈，要求任意相邻的两个小球不得同色，则不同的排法有多少种？

（5）从集合{1，2，3，4}中任取5个数（可重复）排成一个五位数，要求首位只能排1且任意相邻两个位置不能排同一数，则末位恰好也是1的五位数有多少个？末位不是1的五位数有多少个？末位是2的概率为多少？

解：（1）连续掷两次骰子，点数之和为3的倍数的概率为倍数的概率为11323123613，不是3的

，又第n次由A掷这一事件，包括第n1次由A掷且第n次继续由A掷这一事件以及第n1次由B掷，第n次由A掷这一事件，并且这两个事件是互斥的，而第n1次由A掷的概率为Pn1，由B掷的概率为1Pn1，所以Pn13Pn123(1Pn1)(13)13(Pn123Pn123,(n2,nN)„„①，又显然P11，

12(P112)(13)n1由①有Pn即Pn12121212)，所以Pn，

n1(n1,nN)。

（2）即为走楼梯的89种.恰好7次摸完说明4次1个球，3次2个球，故有C7335种，概率为

3589

11621241120)44（3）5个元素的全错位数为120(C591201，故概率为

1130；

38

（4）即染色问题，a666，但是圆排列，故有11种

（5）末位是1的即上述m4的传球问题，a421种；总共有3481种，末位不是1的有342160种；末位是2的占，有20种，概率为

312081.