【正文】 教學(xué)目標(biāo)前面在講加法原理、乘法原理、排列組合時(shí)已經(jīng)穿插講解了計(jì)數(shù)中的一些常用的方法，比如枚舉法、樹形圖法、標(biāo)數(shù)法、捆綁法、排除法、插板法等等，這里再集中學(xué)習(xí)一下計(jì)數(shù)中其他常見(jiàn)的方法，主要有歸納法、整體法、對(duì)應(yīng)法、遞推法．對(duì)這些計(jì)數(shù)方法與技巧要做到靈活運(yùn)用．例題精講對(duì)于某些難以發(fā)現(xiàn)其一般情形的計(jì)數(shù)問(wèn)題，可以找出其相鄰數(shù)之間的遞歸關(guān)系，有了這一遞歸關(guān)系就可以利用前面的數(shù)求出后面未知的數(shù)，這種方法稱為遞推法．【例 1】 每對(duì)小兔子在出生后一個(gè)月就長(zhǎng)成大兔子，而每對(duì)大兔子每個(gè)月能生出一對(duì)小兔子來(lái)．如果一個(gè)人在一月份買了一對(duì)小兔子，那么十二月份的時(shí)候他共有多少對(duì)兔子？【考點(diǎn)】計(jì)數(shù)之遞推法 【難度】3星 【題型】解答【解析】 第一個(gè)月，有1對(duì)小兔子；第二個(gè)月，長(zhǎng)成大兔子，所以還是1對(duì)；第三個(gè)月，大兔子生下一對(duì)小兔子，所以共有2對(duì)；第四個(gè)月，剛生下的小兔子長(zhǎng)成大兔子，而原來(lái)的大兔子又生下一對(duì)小兔子，共有3對(duì)；第五個(gè)月，兩對(duì)大兔子生下2對(duì)小兔子，共有5對(duì)；……這個(gè)特點(diǎn)的說(shuō)明每月的大兔子數(shù)為上月的兔子數(shù)，每月的小兔子數(shù)為上月的大兔子數(shù)，即上上月的兔子數(shù)，所以每月的兔子數(shù)為上月的兔子數(shù)與上上月的兔子數(shù)相加． 依次類推可以列出下表： 經(jīng)過(guò)月數(shù)：123456789101112兔子對(duì)數(shù)：1123581321345589—144，所以十二月份的時(shí)候總共有144對(duì)兔子．【答案】【例 2】 樹木生長(zhǎng)的過(guò)程中，新生的枝條往往需要一段“休息”時(shí)間供自身生長(zhǎng)，而后才能萌發(fā)新枝．一棵樹苗在一年后長(zhǎng)出一條新枝，第二年新枝“休息”，老枝依舊萌發(fā)新枝；此后，老枝與“休息”過(guò)一年的枝同時(shí)萌發(fā)，當(dāng)年生的新枝則依次“休息”．這在生物學(xué)上稱為“魯?shù)戮S格定律”．那么十年后這棵樹上有多少條樹枝？【考點(diǎn)】計(jì)數(shù)之遞推法 【難度】3星 【題型】解答【解析】 一株樹木各個(gè)年份的枝椏數(shù)，構(gòu)成斐波那契數(shù)列：1，2，3，5，8，13，21，34，55，89，……所以十年后樹上有89條樹枝．【答案】【例 3】 一樓梯共10級(jí)，規(guī)定每步只能跨上一級(jí)或兩級(jí)，要登上第10級(jí)，共有多少種不同走法？【考點(diǎn)】計(jì)數(shù)之遞推法 【難度】4星 【題型】解答【解析】 登 1級(jí) 2級(jí) 3級(jí) 4級(jí) ...... 10級(jí)1種方法2種 3種 5種 ...... ？我們觀察每級(jí)的種數(shù)，發(fā)現(xiàn)這么一個(gè)規(guī)律：從第三個(gè)數(shù)開始，每個(gè)數(shù)是前面兩個(gè)數(shù)的和；：假如我們把這個(gè)人開始登樓梯的位置看做A0，那么登了1級(jí)的位置是在A1，2級(jí)在A2... A10級(jí)就在A10．到A3的前一步有兩個(gè)位置；分別是A2 和A1 ．在這里要強(qiáng)調(diào)一點(diǎn)，那么A2 到A3 既然是一步到了，那么A2 、A3之間就是一種選擇了；同理A1 到A3 也是一種選擇了．同時(shí)我們假設(shè)到n級(jí)的選擇數(shù)就是An ．那么從A0 到A3 就可以分成兩類了：第一類：A0 A1 A3 ，那么就可以分成兩步．有A11種，也就是A1 種；(A1 A3 是一種選擇)第二類：A0 A2 A3， 同樣道理 有A2 ．類類相加原理：A3 = A1 ＋A2，依次類推An = An1 + An2．【答案】【鞏固】一樓梯共10級(jí)，規(guī)定每步只能跨上一級(jí)或三級(jí)，要登上第10級(jí)，共有多少種不同走法？【考點(diǎn)】計(jì)數(shù)之遞推法 【難度】4星 【題型】解答【解析】 登 1級(jí) 2級(jí) 3級(jí) 4級(jí) 5級(jí) ...... 10級(jí)1種方法1種 2種 3種 4種...... ？我們觀察每級(jí)的種數(shù)，發(fā)現(xiàn)這么一個(gè)規(guī)律：從第三個(gè)數(shù)開始，每個(gè)數(shù)是前面相隔的兩個(gè)數(shù)的和；依此規(guī)律我們就可以知道了第10級(jí)的種數(shù)是28.【答案】【例 4】 12的小長(zhǎng)方形(橫的豎的都行)覆蓋210的方格網(wǎng)，共有多少種不同的蓋法．【考點(diǎn)】計(jì)數(shù)之遞推法 【難度】4星 【題型】解答【解析】 如果用的長(zhǎng)方形蓋的長(zhǎng)方形，設(shè)種數(shù)為,則，,對(duì)于，左邊可能豎放1個(gè)的，也可能橫放2個(gè)的，前者有種，后者有種，所以,所以根據(jù)遞推，覆蓋的長(zhǎng)方形一共有89種．【答案】【例 5】 用的小長(zhǎng)方形覆蓋的方格網(wǎng)，共有多少種不同的蓋法？【考點(diǎn)】計(jì)數(shù)之遞推法 【難度】5星 【題型】解答【解析】 如果用的長(zhǎng)方形蓋的長(zhǎng)方形，設(shè)種數(shù)為,則，,對(duì)于，左邊可能豎放1個(gè)的，也可能橫放3個(gè)的，前者有種，后者有種，所以,依照這條遞推公式列表：112346913所以用的小長(zhǎng)方形形覆蓋的方格網(wǎng)，共有13種不同的蓋法．【答案】【例 6】 有一堆火柴共12根，如果規(guī)定每次取1～3根，那么取完這堆火柴共有多少種不同取法？【考點(diǎn)】計(jì)數(shù)之遞推法 【難度】4星 【題型】解答【解析】 取1根火柴有1種方法，取2根火柴有2種方法，取3根火柴有4種取法，以后取任意根火柴的種數(shù)等于取到前三根火柴所有情況之和，以此類推，參照上題列表如下：1根2根3根4根5根6根7根8根9根10根11根12根124713244481149274504927取完這堆火柴一共有927種方法．【答案】【鞏固】 一堆蘋果共有8個(gè)，如果規(guī)定每次取1～3個(gè)，那么取完這堆蘋果共有多少種不同取法？【考點(diǎn)】計(jì)數(shù)之遞推法 【難度】4星 【題型】解答【解析】 取1個(gè)蘋果有1種方法，取2個(gè)蘋果有2種方法，取3個(gè)蘋果有4種取法，以后取任意個(gè)蘋果的種數(shù)等于取到前三個(gè)蘋果所有情況之和，以此類推，參照上題列表如下：1個(gè)2個(gè)3個(gè)4個(gè)5個(gè)6個(gè)7個(gè)8個(gè)124713244481取完這堆蘋果一共有81種方法．【答案】【例 7】 有10枚棋子，每次拿出2枚或3枚，要想將10枚棋子全部拿完，共有多少種不同的拿法？【考點(diǎn)】計(jì)數(shù)之遞推法 【難度】4星 【題型】解答【解析】 本題可以采用遞推法，也可以進(jìn)行分類討論，當(dāng)然也可以直接進(jìn)行枚舉．(法1)遞推法．假設(shè)有枚棋子，每次拿出2枚或3枚，將枚棋子全部拿完的拿法總數(shù)為種．則，．由于每次拿出2枚或3枚，所以()．所以，；；；；；．即當(dāng)有10枚棋子時(shí)，共有7種不同的拿法．(法2)分類討論．由于棋子總數(shù)為10枚，是個(gè)偶數(shù)，而每次拿2枚或3枚，所以其中拿3枚的次數(shù)也應(yīng)該是偶數(shù)．由于拿3枚的次數(shù)不超過(guò)3次，所以只能為0次或2次．若為0次，則相當(dāng)于2枚拿了5次，此時(shí)有1種拿法；若為2次，則2枚也拿了2次，共拿了4次，所以此時(shí)有種拿法．根據(jù)加法原理，共有種不同的拿法．【答案】【例 8】 如下圖，一只蜜蜂從處出發(fā)，回到家里處，每次只能從一個(gè)蜂房爬向右側(cè)鄰近的蜂房而不準(zhǔn)逆行，共有多少種回家的方法？【考點(diǎn)】計(jì)數(shù)之遞推法 【難度】4星 【題型】解答 【解析】 蜜蜂“每次只能從一個(gè)蜂房爬向右側(cè)鄰近的蜂房而不準(zhǔn)逆行”這意味著它只能從小號(hào)碼的蜂房爬近相鄰大號(hào)碼的蜂房．明確了行走路徑的方向，就可以運(yùn)用標(biāo)數(shù)法進(jìn)行計(jì)算．如右圖所示，小蜜蜂從A出發(fā)到B處共有89種不同的回家方法．【答案】【鞏固】小蜜蜂通過(guò)蜂巢房間，規(guī)定只能由小號(hào)房間進(jìn)入大號(hào)房間問(wèn)小蜜蜂由房間到達(dá) 房間有多少種方法？【考點(diǎn)】計(jì)數(shù)之遞推法 【難度】4星 【題型】解答【解析】 斐波那契數(shù)列第八項(xiàng)．21種．【答案】【例 9】 如下圖，一只蜜蜂從A處出發(fā)，回到家里B處，每次只能從一個(gè)蜂房爬向右側(cè)鄰近的蜂房而不準(zhǔn)逆行，共有多少種回家的方法？【考點(diǎn)】計(jì)數(shù)之遞推法 【難度】4星 【題型】解答 【解析】 按照蜜蜂只能從小號(hào)碼的蜂房爬近相鄰大號(hào)碼的蜂房的原則，運(yùn)用標(biāo)號(hào)法進(jìn)行計(jì)算．如右圖所示，小蜜蜂從A出發(fā)到B處共有296種不同的回家方法．【答案】【例 10】 對(duì)一個(gè)自然數(shù)作如下操作：如果是偶數(shù)則除以2，如果是奇數(shù)則加1，如此進(jìn)行直到得數(shù)為1操作停止．問(wèn)經(jīng)過(guò)9次操作變?yōu)?的數(shù)有多少個(gè)？【考點(diǎn)】計(jì)數(shù)之遞推法 【難度】4星 【題型】解答【解析】 可以先嘗試一下，倒推得出下面的圖：其中經(jīng)1次操作變?yōu)?的1個(gè)，即2，經(jīng)2次操作變?yōu)?的1個(gè)，即4，經(jīng)3次操作變?yōu)?的2個(gè)，是一奇一偶，以后發(fā)現(xiàn)，每個(gè)偶數(shù)可以變成兩個(gè)數(shù)，分別是一奇一偶，每個(gè)奇數(shù)變?yōu)橐粋€(gè)偶數(shù)，于是，經(jīng)…次操作變?yōu)?的數(shù)的個(gè)數(shù)依次為：1，1，2，3，5，8，… 這一串?dāng)?shù)中有個(gè)特點(diǎn)：自第三個(gè)開始，每一個(gè)等于前兩個(gè)的和，即即經(jīng)過(guò)9次操作變?yōu)?的數(shù)有34個(gè).為什么上面的規(guī)律是正確的呢？道理也很簡(jiǎn)單. 設(shè)經(jīng)過(guò)次操作變?yōu)?的數(shù)的個(gè)數(shù)為,則1，1，2，…從上面的圖看出，比大. 一方面，每個(gè)經(jīng)過(guò)次操作變?yōu)?的數(shù)，乘以2，就得出一個(gè)偶數(shù)，經(jīng)過(guò)次操作變?yōu)?；反過(guò)來(lái)，每個(gè)經(jīng)過(guò)次操作變?yōu)?的偶數(shù)，除以2，就得出一個(gè)經(jīng)過(guò)次操作變?yōu)?的數(shù). ,因此后者也是個(gè).另一方面，每個(gè)經(jīng)過(guò)次操作變?yōu)?的偶數(shù)，減去1，就得出一個(gè)奇數(shù)，它經(jīng)過(guò)次操作變?yōu)?，加上1，就得出一個(gè)偶數(shù)，它經(jīng)過(guò)次操作變?yōu)?. 所以經(jīng)過(guò)次操作變?yōu)?的偶數(shù)經(jīng)過(guò)次操作變?yōu)?的奇數(shù)恰好一樣多.而由上面所說(shuō)，前者的個(gè)數(shù)就是,因此后者也是.經(jīng)過(guò)1次操作變?yōu)?的數(shù)，分為偶數(shù)、奇數(shù)兩類，所以，即上面所說(shuō)的規(guī)律的確成立.【答案】【例 11】 有20個(gè)石子，一個(gè)人分若干次取，每次可以取1個(gè)，2個(gè)或3個(gè)，但是每次取完之后不能留下質(zhì)數(shù)個(gè)，有多少種方法取完石子？（石子之間不作區(qū)分，只考慮石子個(gè)數(shù)）【考點(diǎn)】計(jì)數(shù)之遞推法 【難度】5星 【題型】解答【解析】 如果沒(méi)有剩下的不能使質(zhì)數(shù)這個(gè)條件，那么遞推方法與前面學(xué)過(guò)的遞推法相似，只不過(guò)每次都是前面3個(gè)數(shù)相加．現(xiàn)在剩下的不能是質(zhì)數(shù)個(gè)，可以看作是質(zhì)數(shù)個(gè)的取法總數(shù)都是0，然后再進(jìn)行遞推．【答案】【鞏固】有20個(gè)相同的棋子，一個(gè)人分若干次取，每次可取1個(gè)，2個(gè)，3個(gè)或4個(gè)，但要求每次取之后留下的棋子數(shù)不是3或4的倍數(shù)，有 種不同的方法取完這堆棋子. 【考點(diǎn)】計(jì)數(shù)之遞推法 【難度】5星 【題型】填空【解析】 把0和20以內(nèi)不是3或4的倍數(shù)的數(shù)寫成一串，用遞推法把所有的方法數(shù)寫出來(lái)：【答案】【例 12】 個(gè)人進(jìn)行籃球訓(xùn)練，互相傳球接球，要求每個(gè)人接球后馬上傳給別人，開始由甲發(fā)球，并作為第一次傳球，第五次傳球后，球又回到甲手中，問(wèn)有多少種傳球方法？【考點(diǎn)】計(jì)數(shù)之遞推法 【難度】5星 【題型】解答【解析】 設(shè)第次傳球后，球又回到甲手中的傳球方法有種．可以想象前次傳球，如果每一次傳球都任選其他三人中的一人進(jìn)行傳球，即每次傳球都有種可能，由乘法原理，共有(種)傳球方法．這些傳球方法并不是都符合要求的，它們可以分為兩類，一類是第次恰好傳到甲手中，這有種傳法，它們不符合要求，因?yàn)檫@樣第次無(wú)法再把球傳給甲；另一類是第次傳球，球不在甲手中，第次持球人再將球傳給甲，有種傳法．根據(jù)加法原理，有．由于甲是發(fā)球者，一次傳球后球又回到甲手中的傳球方法是不存在的，所以．利用遞推關(guān)系可以得到：，，．這說(shuō)明經(jīng)過(guò)次傳球后，球仍回到甲手中的傳球方法有種．本題也可以列表求解．由于第次傳球后，球不在甲手中的傳球方法，第次傳球后球就可能回到甲手中，所以只需求出第四次傳球后，球不在甲手中的傳法共有多少種．從表中可以看出經(jīng)過(guò)五次傳球后，球仍回到甲手中的傳球方法共有種．【答案】【鞏固】五個(gè)人互相傳球，由甲開始發(fā)球，并作為第一次傳球，經(jīng)過(guò)次傳球后，球仍回到甲手中．問(wèn)：共有多少種傳球方式？【考點(diǎn)】計(jì)數(shù)之遞推法 【難度】5星 【題型】解答【解析】 遞推法．設(shè)第次傳球后球傳到甲的手中的方法有種．由于每次傳球有4種選擇，傳次有次可能．其中有的球在甲的手中，有的球不在甲的手中，球在甲的手中的有種，球不在甲的手中的，下一次傳球都可以將球傳到甲的手中，故有種．所以．由于，所以，．即經(jīng)過(guò)次傳球后，球仍回到甲手中的傳球方法有52種．【答案】【例 13】 設(shè)、為正八邊形的相對(duì)頂點(diǎn)，頂點(diǎn)處有一只青蛙，除頂點(diǎn)外青蛙可以從正八邊形的任一頂點(diǎn)跳到其相鄰兩個(gè)頂點(diǎn)中任意一個(gè)，落到頂點(diǎn)時(shí)青蛙就停止跳動(dòng)，則青蛙從頂點(diǎn)出發(fā)恰好跳次后落到的方法總數(shù)為 種．【考點(diǎn)】計(jì)數(shù)之遞推法 【難度】5星 【題型】填空【關(guān)鍵詞】清華附中【解析】 可以使用遞推法． 回到 跳到或 跳到或 跳到或 停在1步 12步 2 13步 3 14步 6 4 25步 10 46步 20 14 87步 34 148步 68 48 289步 116 48其