附录37递推法解几类计数问题一、染色问题：三、错排问题：二、传球(踢毽子)问题：四、走楼梯问题：五、汉诺塔问题：六、概
率问题：1.条型域：2.环型域：①无心环型域②有心环型域3.其他型：一、染色问题：1.条型域：,相邻…32
n1注1：染色基础是条型方法多多随爱好从头到尾逐个染乘法原理显神功练习1.条型域：区域不能同色,
则共有种染法注2：隐含了颜色有剩余(1)如图，用5种不同的颜色给图中的4个格子涂色，每个格
子涂一种颜色，相邻格子颜色不同则不同的涂色方法共有种解：如图,用k种颜色染n块区域，如图，用k种不同的颜色,涂圆
中n块区域要求每个区域染一种颜色，相邻的区域不同色，则不同的染色方法有多少种？析：记n块区域染法为易得易得易得2.环
型域：①无心环型域:如图，用k种不同的颜色,涂圆中n块区域要求每个区域染一种颜色，相邻的区域不同色，则不同的染色方法有多少
种？法2：化环型域为条型域：注：思路显然，但操作量过大2.环型域：①无心环型域:法1：通项公式：如图，用k种不同的颜色
,涂圆中n块区域要求每个区域染一种颜色，相邻的区域不同色，则不同的染色方法有多少种？法3：环型域递推法：2.环型域：①无
心环型域:注：二三环型点算法四块以上递推法异色插入第一类同色剪开第二类练习2.无心环型域:(2)如
图,用4种不同的颜色,涂圆中4块区域,要求每个区域染一种颜色，相邻的区域不同色，则不同的染色方法有多少种？析：练习2.无心
环型域:(3)如图,用5种不同的颜色,涂圆中4块区域,要求每个区域染一种颜色，相邻的区域不同色，则不同的染色方法有多少种
？析：练习2.无心环型域:(4)如图,用5种不同的颜色,涂圆中5块区域,要求每个区域染一种颜色，相邻的区域不同色，则不
同的染色方法有多少种？析：②有心环型域无心环型域先染心练习3.有心环型域：(5)如图,用5种不同的颜色,涂圆中5块区域
,要求每个区域染一种颜色，相邻的区域不同色则不同的染色方法有多少种？析1：A5有5种染色方法析2：剩余4块区域，4色染之
综上，N=5×84=420练习4.其他型：(6)课本P：28B组Ex2解：N=5×4×3×3=180(7)用5种
不同的颜色给四棱锥P-ABCD的5个面涂色,要求每个面染一种颜色，相邻的两面不同色，则不同的染色方法有多少种？PDCB
A……N=5×84=420二、传球(踢毽子)问题：析：此类问题解法甚多.现只研究递推法(8)k个人进行传球游戏，由甲
先传，经过n次传球后,球仍回到甲手中的传球方法有多少种？法1：设不同的传球方法共有an种，则：第一次传球：甲传给其他人
，有k-1种传球方法；第二次传球：拿球者把球传给他人，有k-1种传球方法；第n-1次传球：拿球者把球传给他人，有k-1种传球方
法…………………………………………………………第n次传球：由于只能传给甲，故只有一次传球方法由乘法原理得有种传球方法注意
：第n-1次传球不能传给甲，否则就不存在第n次传球故需去掉第n-1次传球中，综上，有递推关系：（易得a1=0）传给甲的传球
方法数an-1二、传球(踢毽子)问题：(8)k个人进行传球游戏，由甲先传，经过n次传球后,球仍回到甲手中的传球方法
有多少种？法1：设不同的传球方法共有an种，则……（易得a1=0）法2：可以转换成于k种颜色n块区域的无心环型
域的染色问题三、错排问题：1.背诵法：a1=0；a2=1；a3=2；a4=9；a5=44……2.递推法：①
②3.通项公式：ABCDbacd假定元素为A、B、C、D；对应的位置为a、b、c、d对于元素
A，我们可将其放在b、c、d三个位置下面先探讨的特例易得这三个位置是等价的
故不妨设A放在了b位置此时，元素B有两种选择：之后的情形与a2等价①放在a位置；②不放在a位置；情况与a3等价AB
CDabcd因此，我们得到一个递推公式：不妨设A放在了b位置；ABCDbac
dABCDbacdi：第n位上不是第k元，①显然在错排中，第n元必不在第n位上,则第n
位上有两种可能：ii：第n位上是第k元，则问题转化成：除去第n元以外的其他n－1个元素的错排③所以第n元在第k位上的错排数共
有an-1＋an-2④由于k可以是1,2,3,……,n-1等n-1种取法综上，②不妨设第n元在第k位上那么把第n位看作第k
位除去n和k以外的其他n-2个元素的错排,其错排数是an-1则问题转化成：其错排数是an-2四、走楼梯问题：(10)欲
登上第10级楼梯，如果规定每步只能跨上一级或两级，则不同的走法共有A.34种 B.55种 C.89种 D.144种析：
设走n级有an种走法，则所以an=an-1+an-2i：当第一步是一步一级时，ii：当第一步是一步两级时，则余下的n
-1级有an-1种走法则余下的n-2级有an-2种走法由递推可得a10=89易得，a1=1，a2=2五、汉诺
塔问题：记n个金片重新摞好需要移动次数为②易得①可得递推关系：③由不动点法可得六、概率问题：(11)(2012年全国数
学联赛)某情报站有A、B、C、D四种互不相同的密码，每周使用其中的一种密码，且每周都是从上周未使用的三种密码中等可能地随机选用
一种．设第一周使用A种密码，那么第7周也使用A种密码的概率是（用最简分数表示）附加作业：1.(20
07年天津)如图，用6种不同的颜色给图中的4个格子涂色，每个格子涂一种颜色,要求最多使用3种颜色且相邻的两个格子颜
色不同，则不同的涂色方法共有__________种2.(2003年天津)如图,某城市在中心广场建造一个花圃花圃分成6个部分,现要栽种4种不同颜色的花，每部分栽种一种,且相邻部分不能栽种同样颜色的花,则不同的栽种方法共有种 |
|
