1、附录附录37 37 递推法解几类计数问题递推法解几类计数问题 一、染色问题：一、染色问题：三、错排问题：三、错排问题：二、二、传球传球(踢毽子踢毽子)问题：问题：四、四、走楼梯问题：走楼梯问题：五、汉诺塔五、汉诺塔问题：问题：六、六、概率问题：概率问题：1.1.条型域：条型域：2.2.环环型型域：域：无心环型域无心环型域有心环型域有心环型域3.3.其他其他型型：一、染色问题：一、染色问题：1.1.条型域：条型域：,相邻相邻3 32 2n n1 11)1(nnkkt注注1 1：染：染色基础是色基础是条型条型 方法多多随爱好方法多多随爱好 从头到尾逐个染从头到尾逐个染 乘法原理显神功乘法原理显神功
2、练习练习1.1.条型域：条型域：区域不能同色区域不能同色,则共有则共有 种染法种染法注注2 2：隐含了颜色有剩余：隐含了颜色有剩余(1)(1)如图，用如图，用5 5种不同的颜色给图中的种不同的颜色给图中的4 4个格子涂色，个格子涂色，每个格子涂一种颜色，相邻格子颜色不同每个格子涂一种颜色，相邻格子颜色不同则不同的涂色方法共有则不同的涂色方法共有种种解：解：3204445N如图如图,用用k k种颜色染种颜色染n n块区域，块区域，如图，用如图，用k k种不同的颜色种不同的颜色,涂圆中涂圆中n n块区域块区域要求每个区域染一种颜色，相邻的区域不同色，要求每个区域染一种颜色，相邻的区域不同色，则不同
3、的染色方法有多少种？则不同的染色方法有多少种？1A2A3AnA1nA4A析：记析：记n n块区域染法为块区域染法为nh易得易得kh 1易得易得)1(2kkh易得易得)2)(1(3kkkh?4h2.2.环环型型域：域：无心环型域无心环型域:如图，用如图，用k k种不同的颜色种不同的颜色,涂圆中涂圆中n n块区域块区域要求每个区域染一种颜色，相邻的区域不同色，要求每个区域染一种颜色，相邻的区域不同色，则不同的染色方法有多少种？则不同的染色方法有多少种？法法2 2：化环型域为条型域：化环型域为条型域：注：思路显然，但操作量过大注：思路显然，但操作量过大kh 123(1),(1)(2)hk khk k
4、k(4)n 2.2.环环型型域：域：无心环型域无心环型域:1nnnthh1A2A3AnA1nA4A法法1 1：通项公式：通项公式：)1()1()1(kkhnnn如图，用如图，用k k种不同的颜色种不同的颜色,涂圆中涂圆中n n块区域块区域要求每个区域染一种颜色，相邻的区域不同色，要求每个区域染一种颜色，相邻的区域不同色，则不同的染色方法有多少种？则不同的染色方法有多少种？法法3 3：环型域递推法：环型域递推法：kh 1)1(2kkh)4(n2.2.环环型型域：域：无心环型域无心环型域:1A2A3AnA1nA4A21)1()2(nnnhkhkh注：二三环型点算法注：二三环型点算法 四块以上递推法
5、四块以上递推法 异色插入第一类异色插入第一类 同色剪开第二类同色剪开第二类)2)(1(3kkkh练习练习2.2.无心环型域无心环型域:1A2A3A4A(2)(2)如图如图,用用4 4种不同的颜色种不同的颜色,涂圆中涂圆中4 4块区域块区域,要求每个区域要求每个区域染一种颜色，相邻的区域不同色，染一种颜色，相邻的区域不同色，则不同的染色方法有多少种？则不同的染色方法有多少种？41h12342h析：析：242343h84)14()24(234hhh练习练习2.2.无心环型域无心环型域:1A2A3A4A(3)(3)如图如图,用用5 5种不同的颜色种不同的颜色,涂圆中涂圆中4 4块区域块区域,要求每个
6、区域要求每个区域染一种颜色，相邻的区域不同色，染一种颜色，相邻的区域不同色，则不同的染色方法有多少种？则不同的染色方法有多少种？51h20452h析：析：603453h260)15()25(234hhh练习练习2.2.无心环型域无心环型域:1A2A3A5A(4)(4)如图如图,用用5 5种不同的颜色种不同的颜色,涂圆中涂圆中5 5块区域块区域,要求每个区域要求每个区域染一种颜色，相邻的区域不同色，染一种颜色，相邻的区域不同色，则不同的染色方法有多少种？则不同的染色方法有多少种？51h20452h析：析：603453h260)15()25(234hhh4A1020)15()25(345hhh有心
7、环型域有心环型域无心环型域无心环型域先染心先染心练习练习3.3.有心环型域：有心环型域：1A2A3A4A(5)(5)如图如图,用用5 5种不同的颜色种不同的颜色,涂圆中涂圆中5 5块区域块区域,要求每个区域要求每个区域染一种颜色，相邻的区域不同色染一种颜色，相邻的区域不同色 则不同的染色方法有多少种？则不同的染色方法有多少种？5A析析1 1：A A5 5有有5 5种染色方法种染色方法析析2 2：剩余剩余4 4块区域，块区域，4 4色染之色染之41h1234,2h24234,3h84)14()24(234hhh综上，综上，N=5N=584=420 84=420 练习练习4.4.其他其他型型：(6
8、)(6)课本课本P P：28 B28 B组组 Ex2Ex2解：解：N=5N=54 43 33=1803=1801A2A3A4A(7)(7)用用5 5种不同的颜色给四棱锥种不同的颜色给四棱锥P-ABCDP-ABCD的的5 5个面涂个面涂色色,要求要求每个面每个面染一种颜色，相邻的两面不同色，染一种颜色，相邻的两面不同色，则不同的染色方法有多少种？则不同的染色方法有多少种？5AP PD DC CB BA A N=5 N=584=42084=420二、二、传球传球(踢毽子踢毽子)问题：问题：析：此类问题解法甚多析：此类问题解法甚多.现只研究递推法现只研究递推法(8)k(8)k个人进行传球游戏，由甲先
9、传，经过个人进行传球游戏，由甲先传，经过n n次传球后次传球后,球仍回到甲手中的传球方法有多少种？球仍回到甲手中的传球方法有多少种？法法1 1：设不同的传球方法共有：设不同的传球方法共有an n种，则：种，则：第一次传球：甲传给其他人，有第一次传球：甲传给其他人，有k-1k-1种传球方法；种传球方法；第二次传球：拿球者把球传给他人，有第二次传球：拿球者把球传给他人，有k-1k-1种传球方法；种传球方法；第第n-1n-1次传球：拿球者把球传给他人，有次传球：拿球者把球传给他人，有k-1k-1种传球方法种传球方法第第n n次传球：由于只能传给甲，故只有一次传球方法次传球：由于只能传给甲，故只有一次
10、传球方法由乘法原理得有由乘法原理得有1(1)nk种传球方法种传球方法注意：第注意：第n-1n-1次传球不能传给甲，否则就不存在第次传球不能传给甲，否则就不存在第n n次传球次传球故需去掉第故需去掉第n-1n-1次传球中，次传球中，综上，有递推关系：综上，有递推关系：11(1)nnnaka（易得（易得a1 1=0=0）传给甲的传球方法数传给甲的传球方法数an-1 n-1 二、二、传球传球(踢毽子踢毽子)问题：问题：(8)k(8)k个人进行传球游戏，由甲先传，经过个人进行传球游戏，由甲先传，经过n n次传球后次传球后,球仍回到甲手中的传球方法有多少种？球仍回到甲手中的传球方法有多少种？法法1 1：
11、设不同的传球方法共有：设不同的传球方法共有an n种，则种，则 11(1)nnnaka（易得（易得a1 1=0=0）法法2 2：可以转换成于可以转换成于k k种颜色种颜色n n块区域的块区域的 无心环型无心环型域的域的染色问题染色问题 nnhak三三、错排问题：、错排问题：1.1.背诵法：背诵法：a1 1=0=0；a2 2=1=1；a3 3=2=2；a4 4=9=9；a5 5=44=44 2.2.递推法：递推法：nnnnnnnnaCaCaCaCA221100)(1(21nnnaana3.3.通项公式：通项公式：!)1(!4!3!2!1!0!nnnnnnnannABCD ba c d假定元素为假
12、定元素为A A、B B、C C、D D；对应的位置为；对应的位置为a、b、c、d对于元素对于元素A A，我们可将其放在，我们可将其放在b、c、d三个位置三个位置)(1(21nnnaana)(3234aaa下面先探讨下面先探讨 的特例的特例 易得这三个位置是等价的易得这三个位置是等价的故不妨设故不妨设A A放在了放在了b b位置位置此时，元素此时，元素B B有两种选择：有两种选择：之后的情形与之后的情形与a2 2等价等价放在放在a位置；位置；不放在不放在a位置；位置；情况与情况与a3 3等价等价ABCD ab c d因此，我们得到一个递推公式：因此，我们得到一个递推公式：不妨设不妨设A A放在了
13、放在了b b位置；位置；ABCD ba c dABCD ba c d)(234aaa 3i i：第第n位上不是位上不是第第k元元，显然在错排中，第显然在错排中，第n元元必不在第必不在第n位上位上,则第则第n位上有两种可能：位上有两种可能：iiii：第第n位上是位上是第第k元元，则问题转化成：则问题转化成：除去第除去第n元元以外的其他以外的其他n1个元素的错排个元素的错排所以所以第第n元元在第在第k位上的错排数共有位上的错排数共有an-1an-2由于由于k可以是可以是1,2,3,n-1等等n-1种取法种取法综上，综上，)(1(21nnnaana不妨设不妨设第第n元元在第在第k位上位上那么把第那么
14、把第n位看作第位看作第k位位除去除去n和和k以外的以外的其他其他n-2-2个个元素元素的错排的错排,其错排数是其错排数是an-1则问题转化成：则问题转化成：其错排数是其错排数是an-2四、四、走楼梯问题：走楼梯问题：(10)(10)欲登上第欲登上第1010级楼梯，如果规定每步只能跨上一级级楼梯，如果规定每步只能跨上一级或两级，则不同的走法共有或两级，则不同的走法共有A.34A.34种种 B.55B.55种种C.89C.89种种D.144D.144种种析：设走析：设走n n级有级有an n种走法，则种走法，则所以所以 an n=an-1n-1+an-2n-2i i：当第一步是一步一级时，：当第一
15、步是一步一级时，iiii：当第一步是一步两级时，：当第一步是一步两级时，则余下的则余下的n-1n-1级有级有an-1n-1种走法种走法则余下的则余下的n-2n-2级有级有an-2n-2种走法种走法由递推可得由递推可得 a10 10=89=89易得，易得，a1 1=1=1，a2 2=2=2五、汉诺塔五、汉诺塔问题：问题：记记n n个金片重新摞好个金片重新摞好需要移动次数为需要移动次数为na11a易得易得121nnaa12 nna可得递推关系：可得递推关系：由不动点法可得由不动点法可得六、六、概率问题：概率问题：(11)(2012(11)(2012年全国数学联赛年全国数学联赛)某情报站有某情报站有
16、A A、B B、C C、D D四种四种互不相同的密码，每周使用其中的一种密码，且每周都互不相同的密码，每周使用其中的一种密码，且每周都是从上周未使用的三种密码中等可能地随机选用一种是从上周未使用的三种密码中等可能地随机选用一种设第一周使用设第一周使用A A种密码，那么第种密码，那么第7 7周也使用周也使用A A种密码的概率种密码的概率是是 （用最简分数表示（用最简分数表示 ）附加作业：附加作业：1.(20071.(2007年天津年天津)如图，用如图，用6 6种不同的颜色给图中的种不同的颜色给图中的 4 4个格子涂色，每个格子涂一种颜色个格子涂色，每个格子涂一种颜色,要求最多要求最多 使用使用3 3种颜色且相邻的两个格子颜色不同，则种颜色且相邻的两个格子颜色不同，则 不同的涂色方法共有不同的涂色方法共有_种种2.(20032.(2003年天津年天津)如图如图,某城市在中心广场建造一个某城市在中心广场建造一个 花圃花圃分成花圃花圃分成6 6个部分个部分,现要栽种现要栽种4 4种不同颜色的种不同颜色的 花，每部分栽种一种花，每部分栽种一种,且相邻且相邻 部分不能栽种同样颜色的花部分不能栽种同样颜色的花,则不同的栽种方法共有则不同的栽种方法共有 种种
