遞推計(jì)數(shù)有許多計(jì)數(shù)問(wèn)題很復(fù)雜，直接處理比較困難，此時(shí)硬碰硬是不行的．一個(gè)比較有效的策略是退而求其次：先考慮該問(wèn)題的簡(jiǎn)單情形，看看簡(jiǎn)單情形如何處理；在解決了簡(jiǎn)單情形后，再考慮如何利用簡(jiǎn)單情形的結(jié)論來(lái)解決更復(fù)雜的問(wèn)題……這個(gè)由簡(jiǎn)單到復(fù)雜的推導(dǎo)過(guò)程就叫“遞推”．那如何利用“遞推法”來(lái)解決計(jì)數(shù)問(wèn)題呢？下面我們就來(lái)看幾個(gè)例子．老師給小高布置了12篇作文，規(guī)定他每天至少寫(xiě)1篇．如果小高每天最多能寫(xiě)3篇，那么共有多少種不同的完成方法？（小高每天只能寫(xiě)整數(shù)篇）

「分析」從簡(jiǎn)單情況入手，看看能否找到合適的突破口．如果老師只布置1篇作文，小高有多少種不同的完成方法？如果老師布置2篇作文，小高有多少種不同的完成方法？如果老師布置3篇、4篇、……小高又分別有多少種不同的完成方法？篇數(shù)由少到多，完成方法數(shù)也會(huì)逐漸變多，這其中有什么規(guī)律呢？

練習(xí)1、一個(gè)樓梯共有12級(jí)臺(tái)階，規(guī)定每步可以邁二級(jí)臺(tái)階或三級(jí)臺(tái)階．走完這12級(jí)臺(tái)階，共有多少種不同的走法？

用10個(gè)的長(zhǎng)方形紙片覆蓋一個(gè)的方格表，共有多少種覆蓋方法？「分析」與例1的類似，我們還是從簡(jiǎn)單情形入手找遞推關(guān)系．可具體從什么樣的情形入手呢？

練習(xí)2、用7個(gè)的長(zhǎng)方形紙片覆蓋一個(gè)的方格表，共有多少種覆蓋方法？

在一個(gè)平面上畫(huà)出100條直線，最多可以把平面分成幾個(gè)部分？

「分析」當(dāng)直線數(shù)量不多時(shí)，畫(huà)圖數(shù)一數(shù)即可．但現(xiàn)在有100條，畫(huà)圖數(shù)并不現(xiàn)實(shí)．我們不妨在紙上將直線逐一畫(huà)出，并在畫(huà)的過(guò)程中仔細(xì)觀察：每增加一條直線，平面被分成的部分會(huì)增加多少？這個(gè)增量有什么變化規(guī)律？

練習(xí)3、如果在一個(gè)圓內(nèi)畫(huà)出50條直線，最多可以把圓分成多少部分？

下面我們來(lái)學(xué)習(xí)一類很經(jīng)典的遞推計(jì)數(shù)問(wèn)題——傳球問(wèn)題．

四個(gè)人分別穿著紅、黃、綠、藍(lán)四種顏色的球衣練習(xí)傳球，每人都可以把球傳給另外三個(gè)人中的任意一個(gè)．先由紅衣人發(fā)球，并作為第1次傳球，經(jīng)過(guò)8次傳球后球仍然回到紅衣人手中．請(qǐng)問(wèn)：整個(gè)傳球過(guò)程共有多少種不同的可能？

「分析」看到這個(gè)問(wèn)題，很多同學(xué)可能想通過(guò)樹(shù)形圖來(lái)求解，我們不妨來(lái)試一試．設(shè)穿著紅、黃、綠、藍(lán)四種顏色球衣的人分別是A、B、C、D．如下圖，最開(kāi)始時(shí)，球在A手上，第一次傳球由A傳給B、C、D，也就是第一層有三個(gè)字母就夠了．然后B、C、D都會(huì)繼續(xù)往下傳球，各有3種傳法，傳到第二層需要9個(gè)字母．再傳到第三層，需要27個(gè)字母……每一層需要的字母增加迅猛！如果傳8次球，到最后一層會(huì)用到個(gè)字母，這要多大的一個(gè)樹(shù)形圖??！

BCBCDACDABDABCABCDABDABCBCDACDABCBCDACDABD可見(jiàn)畫(huà)樹(shù)形圖的方案不可行．但樹(shù)形圖對(duì)這道題就沒(méi)有用了嗎？并非如此．它可以幫助我們找出傳球過(guò)程中所隱藏的遞推關(guān)系．事實(shí)上，我們并不關(guān)心樹(shù)形圖長(zhǎng)啥樣，我們關(guān)心的是數(shù)量——樹(shù)形圖每一層分支的數(shù)量．因此，只要知道每一層各字母出現(xiàn)的次數(shù)就可以了，我們不妨制作一個(gè)表格來(lái)統(tǒng)計(jì)這個(gè)次數(shù)．如下表，我們用第一列來(lái)表示層數(shù)，第一行來(lái)表示每個(gè)人，其余空格用于填寫(xiě)字母在該層中出現(xiàn)的次數(shù)．請(qǐng)你從上方的樹(shù)形圖中數(shù)一數(shù)，填出表格中的前幾行．然后思考一下：這其中隱藏著什么樣的遞推關(guān)系？ABCD01ABCD012345678解傳球問(wèn)題的方法稱為“傳球法”．“傳球法”是遞推法的一種特殊形式，是一種極其實(shí)用的數(shù)表累加計(jì)數(shù)法．

一個(gè)七位數(shù)，每一位都是1、2或者3，而且沒(méi)有連續(xù)的兩個(gè)1，這樣的七位數(shù)一共有多少個(gè)？

「分析」這道題與前面兩道題有何異同？應(yīng)該如何求解呢？

前面的計(jì)數(shù)問(wèn)題，遞推關(guān)系都表現(xiàn)為數(shù)列、數(shù)表的簡(jiǎn)單累加，但這不是遞推的全部．簡(jiǎn)單累加只是遞推的一種表現(xiàn)形式，遞推還有很多其它形式．下面我們就來(lái)看一道無(wú)法通過(guò)簡(jiǎn)單累加求解的計(jì)數(shù)問(wèn)題．

圓周上有10個(gè)點(diǎn)A1、A2、、A10，以這些點(diǎn)為端點(diǎn)連接5條線段，要求線段之間沒(méi)有公共點(diǎn)，共有多少種連接方式？

「分析」圓周上10個(gè)點(diǎn)，連5條線段，連法很多，很難直接畫(huà)出來(lái)枚舉．像這類問(wèn)題，我們同樣還是從簡(jiǎn)單的情況入手．那么是應(yīng)該按1個(gè)點(diǎn)、2個(gè)點(diǎn)、3個(gè)點(diǎn)、……這樣依次計(jì)數(shù)，來(lái)找遞推關(guān)系嗎？作業(yè)有10個(gè)蛋黃派，萱萱每天吃1個(gè)或2個(gè)，那么共有多少種不同的吃法？

甲、乙兩人玩抓石子游戲，共有12個(gè)石子，甲先乙后輪流抓取．每次可以抓取其中的2個(gè)、3個(gè)或4個(gè)，直到最后抓取完畢為止．那么共有多少種抓取石子的方案？

用直線把一個(gè)平面分成100部分，至少要在平面上畫(huà)幾條直線？

一個(gè)七位數(shù)，它由數(shù)字0、1、2、3、4組成，相鄰位置上的數(shù)字不相同，并且個(gè)位數(shù)字是2．這樣的七位數(shù)有多少個(gè)？

用8個(gè)的長(zhǎng)方形紙片覆蓋下面的方格表，共有多少種覆蓋方法？

作業(yè)：答案：89

簡(jiǎn)答：

蛋黃派數(shù)蛋黃派數(shù)12345678910吃的方法數(shù)123581321345589答案：36

簡(jiǎn)答：

石子數(shù)石子數(shù)123456789101112抓取方法數(shù)0112245811172436012301234001111143333212131313133525151515142042052052052055820819819819819632763277327732773277答案：3277

簡(jiǎn)答：如右表所示，用傳球法列表解決．傳球規(guī)則是：0不能發(fā)球，其它都可以發(fā)球；傳球不能傳給自己，只能傳給別人；總共傳球傳6次．答案：29

簡(jiǎn)答：如下方左圖所示，和例題2類似，找到某個(gè)方格，依據(jù)這個(gè)方格是橫著覆蓋還是豎著覆蓋分兩種情況討論．情況一，橫著覆蓋：這類情況其實(shí)就是的覆蓋方法，利用練習(xí)2的分析方法和相關(guān)結(jié)