遞推法解排列、組合及概率問題

1、1遞推法解排列、組合及概率問題遞推法解排列、組合及概率問題劉東林（廣東省普寧市第二中學(xué)數(shù)學(xué)組515300）排列組合在高中數(shù)學(xué)舊教材中是相對獨(dú)立的內(nèi)容，而在高中數(shù)學(xué)新教材中排列組合是概率及統(tǒng)計(jì)的基礎(chǔ)，因此，排列組合內(nèi)容在高中數(shù)學(xué)新教材中的位置也變得相對重要起來了。而概率是新教材中新增加的內(nèi)容，也是初等概率論中最基本的內(nèi)容。在歷年的高考中，排列組合知識多是選擇題或填空題，概率一般是一個解答題，這些題的題型繁多，解法獨(dú)特，因此得分率普遍較低。

2、本文試圖用遞推法來解決幾類常見的排列組合及概率問題。1走樓梯問題例1：欲登上第10級樓梯，如果規(guī)定每步只能跨上一級或兩級，則不同的走法共有()（A）34種（B）55種（C）89種（D）144種解法1：分類法：第一類：沒有一步兩級，則只有一種走法；第二類：恰有一步是一步兩級，則走完10級要走9步，9步中選一步是一步兩級的，有種可能走法；919?C第三類：恰有兩步是一步兩級，則走完10級要走8步，8步中選兩步是一步兩級的，有種可能走法；28

3、28?C依此類推，共有=89，故選(C)。55463728191CCCCC?????解法2：遞推法：設(shè)走級有種走法，這些走法可按第一步來分類，nna第一類：第一步是一步一級，則余下的級有種走法；1?n1?na第二類：第一步是一步兩級，則余下的級有種走法，2?n2?na所以，又易得，由遞推可得，故選21????nnnaaa2121??aa8910?a(C)。顯然，遞推法的關(guān)鍵是按照某種標(biāo)準(zhǔn)找出遞推關(guān)系式，并求出取第一個值n(或前幾個值)時

4、的各項(xiàng)，然后代入遞推關(guān)系式，求出題中要求的值。當(dāng)然，我們也可以由找出的遞推關(guān)系，求出通項(xiàng)，但對于選擇填空題，我們不必大動na干戈的去求通項(xiàng)，因?yàn)檫@樣太浪費(fèi)時間與精力。2更列問題把個元素排成一列，所有元素各有一個不能占據(jù)的指定位置，且)(??Nnn不同元素不能占據(jù)的指定位置也不同，我們把滿足這種條件的一個排列叫做這些元素的一個更列。例2：五個人排成一列，重新站隊(duì)時，各人都不站在原來的位置上，那么不同的站隊(duì)方式共有()（A）60種（B）44

5、種（C）36種（D）24種解：首先我們把人數(shù)推廣到個人，即個人排成一列，重新站隊(duì)時，各人nn都不站在原來的位置上。設(shè)滿足這樣的站隊(duì)方式有種，現(xiàn)在我們來通過合理na分步，恰當(dāng)分類找出遞推關(guān)系：第一步：第一個人不站在原來的第一個位置，有種站法。1?n第二步：假設(shè)第一個人站在第2個位置，則第二個人的站法又可以分為兩3我們來看例5，其中2、3、4、5四個區(qū)域圍成一個四邊形，因此可以把它們看成是一個四邊形的4個頂點(diǎn)，而區(qū)域1就是這個四邊形對角線的

6、交點(diǎn)。第一步，先涂區(qū)域1，有4種涂法，由于區(qū)域1跟其余四個區(qū)域都相鄰，因此涂1的顏色不能用來涂其余的四個區(qū)域，因此第二步相當(dāng)于用3種顏色來涂一個四邊形的四個頂點(diǎn)，由例4不難得出，，所以，1123?????nnnaa6333??Aa33423aa???，由分步計(jì)數(shù)原理，得出共有種涂法。18?72184??同理，不難得出例6的答案為120種。4傳球問題例7：甲、乙、丙、丁四人相互傳球，第一次甲傳給乙、丙、丁中的任一人，第二次由拿球者再傳給其

7、他人中任一人，這樣共傳了四次，則第四次球仍傳回到甲的方法共有()（A）21種（B）42（C）24（D）27解：先把這個題目進(jìn)行推廣：個人相互進(jìn)行次傳球，)(??Nmm)(??Nnn由甲先傳，第一次甲傳給其他個人中的任一人，第二次由拿球者再傳給其1?m他人中任一人，這樣經(jīng)過次傳球，最后球仍回到甲手中的傳球方法有多少n種？(這里為常數(shù))m設(shè)不同的傳球方法共有種，現(xiàn)在我們來通過合理分步，恰當(dāng)分類找出遞na推關(guān)系：第一步進(jìn)行第一次傳球：甲傳給其

8、他人，有種傳球方法；1?m第二步進(jìn)行第二次傳球：拿球者把球傳給其他人，仍有種傳球方法；1?m同理，第三次、第四次、……、第次傳球都有種傳球方法，最后1?n1?m進(jìn)行第次傳球，由于只能傳給甲，故只有一次傳球方法，相乘得種n1)1(??nm傳球方法，但要注意第次傳球不能傳給甲，否則就不存在第次傳球，因1?nn此要去掉第次傳球，球恰好傳給甲的傳球方法數(shù)，這就是由甲先傳，經(jīng)過1?n次傳球后球又回到甲手中的傳球方法，顯然，這里有種傳球方法，所1?

9、n1?na以有遞推關(guān)系：，又易得，。11)1(?????nnnama01?a而在本題中，，所以，所以由遞推可得，4?m113????nnnaa，3312???aa，故本題應(yīng)選（A）21363334223??????aaaa最后，我們來用遞推法求解一個概率問題。5概率問題例8：A、B二人拿兩顆骰子做拋擲游戲，規(guī)則如下：若擲出的點(diǎn)數(shù)之和為3的倍數(shù)時，原擲骰子的人再繼續(xù)擲；若擲出的點(diǎn)數(shù)不是3的倍數(shù)時就由對方接著擲，第一次由A開始擲，求第次仍由