遞推法解幾類(lèi)計(jì)數(shù)問(wèn)題課件

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

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

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

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