遞推法解幾類計(jì)數(shù)問題課件

附錄37遞推法解幾類計(jì)數(shù)問題一、染色問題：三、錯排問題：二、傳球(踢毽子)問題：四、走樓梯問題：五、漢諾塔問題：六、概率問題：1.條型域：2.環(huán)型域：①無心環(huán)型域②有心環(huán)型域3.其他型：附錄37遞推法解幾類計(jì)數(shù)問題一、染色問題：三、錯排問題1一、染色問題：1.條型域：,相鄰…32n1注1：染色基礎(chǔ)是條型方法多多隨愛好從頭到尾逐個染乘法原理顯神功練習(xí)1.條型域：區(qū)域不能同色,則共有種染法注2：隱含了顏色有剩余(1)如圖，用5種不同的顏色給圖中的4個格子涂色，每個格子涂一種顏色，相鄰格子顏色不同則不同的涂色方法共有

種解：如圖,用k種顏色染n塊區(qū)域，一、染色問題：1.條型域：,相鄰…32n1注1：染色基礎(chǔ)是2如圖，用k種不同的顏色,涂圓中n塊區(qū)域要求每個區(qū)域染一種顏色，相鄰的區(qū)域不同色，則不同的染色方法有多少種？析：記n塊區(qū)域染法為易得易得易得2.環(huán)型域：①無心環(huán)型域:如圖，用k種不同的顏色,涂圓中n塊區(qū)域要求每個區(qū)域染一種顏色3如圖，用k種不同的顏色,涂圓中n塊區(qū)域要求每個區(qū)域染一種顏色，相鄰的區(qū)域不同色，則不同的染色方法有多少種？法2：化環(huán)型域?yàn)闂l型域：注：思路顯然，但操作量過大2.環(huán)型域：①無心環(huán)型域:法1：通項(xiàng)公式：如圖，用k種不同的顏色,涂圓中n塊區(qū)域要求每個區(qū)域染一種顏色4如圖，用k種不同的顏色,涂圓中n塊區(qū)域要求每個區(qū)域染一種顏色，相鄰的區(qū)域不同色，則不同的染色方法有多少種？法3：環(huán)型域遞推法：2.環(huán)型域：①無心環(huán)型域:注：二三環(huán)型點(diǎn)算法四塊以上遞推法異色插入第一類同色剪開第二類如圖，用k種不同的顏色,涂圓中n塊區(qū)域要求每個區(qū)域染一種顏色5練習(xí)2.無心環(huán)型域:(2)如圖,用4種不同的顏色,涂圓中4塊區(qū)域,要求每個區(qū)域染一種顏色，相鄰的區(qū)域不同色，則不同的染色方法有多少種？析：練習(xí)2.無心環(huán)型域:(2)如圖,用4種不同的顏色,涂圓中6練習(xí)2.無心環(huán)型域:(3)如圖,用5種不同的顏色,涂圓中4塊區(qū)域,要求每個區(qū)域染一種顏色，相鄰的區(qū)域不同色，則不同的染色方法有多少種？析：練習(xí)2.無心環(huán)型域:(3)如圖,用5種不同的顏色,涂圓中7練習(xí)2.無心環(huán)型域:(4)如圖,用5種不同的顏色,涂圓中5塊區(qū)域,要求每個區(qū)域染一種顏色，相鄰的區(qū)域不同色，則不同的染色方法有多少種？析：練習(xí)2.無心環(huán)型域:(4)如圖,用5種不同的顏色,涂圓中58②有心環(huán)型域無心環(huán)型域先染心練習(xí)3.有心環(huán)型域：(5)如圖,用5種不同的顏色,涂圓中5塊區(qū)域,要求每個區(qū)域染一種顏色，相鄰的區(qū)域不同色則不同的染色方法有多少種？析1：A5有5種染色方法析2：剩余4塊區(qū)域，4色染之綜上，N=5×84=420②有心環(huán)型域無心環(huán)型域先染心練習(xí)3.有心環(huán)型域：(5)如圖,9練習(xí)4.其他型：(6)課本P：28B組Ex2解：N=5×4×3×3=180(7)用5種不同的顏色給四棱錐P-ABCD的5個面涂色,要求每個面染一種顏色，相鄰的兩面不同色，則不同的染色方法有多少種？PDCBA……N=5×84=420練習(xí)4.其他型：(6)課本P：28B組Ex2解：N=510二、傳球(踢毽子)問題：析：此類問題解法甚多.現(xiàn)只研究遞推法(8)k個人進(jìn)行傳球游戲，由甲先傳，經(jīng)過n次傳球后,球仍回到甲手中的傳球方法有多少種？法1：設(shè)不同的傳球方法共有an種，則：第一次傳球：甲傳給其他人，有k-1種傳球方法；第二次傳球：拿球者把球傳給他人，有k-1種傳球方法；第n-1次傳球：拿球者把球傳給他人，有k-1種傳球方法…………第n次傳球：由于只能傳給甲，故只有一次傳球方法由乘法原理得有種傳球方法注意：第n-1次傳球不能傳給甲，否則就不存在第n次傳球故需去掉第n-1次傳球中，綜上，有遞推關(guān)系：（易得a1=0）傳給甲的傳球方法數(shù)an-1二、傳球(踢毽子)問題：析：此類問題解法甚多.現(xiàn)只研究遞推11二、傳球(踢毽子)問題：(8)k個人進(jìn)行傳球游戲，由甲先傳，經(jīng)過n次傳球后,球仍回到甲手中的傳球方法有多少種？法1：設(shè)不同的傳球方法共有an種，則……（易得a1=0）法2：可以轉(zhuǎn)換成于k種顏色n塊區(qū)域的無心環(huán)型域的染色問題二、傳球(踢毽子)問題：(8)k個人進(jìn)行傳球游戲，由甲先傳，12三、錯排問題：1.背誦法：a1=0；

a2=1；a3=2；a4=9；a5=44……2.遞推法：①②3.通項(xiàng)公式：三、錯排問題：1.背誦法：a1=0；a2=1；a3=2；13ABCDbacd假定元素為A、B、C、D；對應(yīng)的位置為a、b、c、d對于元素A，我們可將其放在b、c、d三個位置下面先探討的特例易得這三個位置是等價的故不妨設(shè)A放在了b位置ABCDbacd假定元素為A、B、C、D；對應(yīng)的位置為14此時，元素B有兩種選擇：之后的情形與a2等價①放在a位置；②不放在a位置；情況與a3等價ABCDabcd因此，我們得到一個遞推公式：不妨設(shè)A放在了b位置；ABCDbacdABCDbacd此時，元素B有兩種選擇：之后的情形與a2等價①放在a位置；②15i：第n位上不是第k元，①顯然在錯排中，第n元必不在第n位上,則第n位上有兩種可能：ii：第n位上是第k元，則問題轉(zhuǎn)化成：除去第n元以外的其他n－1個元素的錯排③所以第n元在第k位上的錯排數(shù)共有an-1＋an-2④由于k可以是1,2,3,……,n-1等n-1種取法綜上，②不妨設(shè)第n元在第k位上那么把第n位看作第k位除去n和k以外的其他n-2個元素的錯排,其錯排數(shù)是an-1則問題轉(zhuǎn)化成：其錯排數(shù)是an-2i：第n位上不是第k元，①顯然在錯排中，第n元必不在第n位上16四、走樓梯問題：(10)欲登上第10級樓梯，如果規(guī)定每步只能跨上一級或兩級，則不同的走法共有A.34種 B.55種 C.89種 D.144種析：設(shè)走n級有an種走法，則所以an=an-1+an-2i：當(dāng)?shù)谝徊绞且徊揭患墪r，ii：當(dāng)?shù)谝徊绞且徊絻杉墪r，則余下的n-1級有an-1種走法則余下的n-2級有an-2種走法由遞推可得a10=89易得，a1=1，a2=2四、走樓梯問題：(10)欲登上第10級樓梯，如果規(guī)定每步只能17五、漢諾塔問題：記n個金片重新摞好需要移動次數(shù)為②易得①可得遞推關(guān)系：③由不動點(diǎn)法可得五、漢諾塔問題：記n個金片重新摞好需要移動次數(shù)為②易得①可得18六、概率問題：(11)(2012年全國數(shù)學(xué)聯(lián)賽)某情報站有A、B、C、D四種互不相同的密碼，每周使用其中的一種密碼，且每周都是從上周未使用的三種密碼中等可能地隨機(jī)選用一種．設(shè)第一周使用A種密碼，那么第7周也使用A種密碼的概率是

（用最簡分?jǐn)?shù)表示）六、概率問題：(11)(2012年全國數(shù)學(xué)聯(lián)賽)某情報站有A19附加作業(yè)：1.(2007年天津)如圖，用6種不同的顏色給圖中的4個格子涂色，每個格子涂一種顏色,要求最多使用3種顏