遞推法解排列組合問題

《遞推法解排列組合問題》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在學術論文-天天文庫。

1、遞推法解排列、組合及概率問題排列組合在高中數(shù)學舊教材中是相對獨立的內(nèi)容，而在高中數(shù)學新教材中排列組合是概率及統(tǒng)計的基礎，因此，排列組合內(nèi)容在高中數(shù)學新教材中的位置也變得相對重要起來了。而概率是新教材中新增加的內(nèi)容，也是初等概率論中最基本的內(nèi)容。在歷年的高考中，排列組合知識多是選擇題或填空題，概率一般是一個解答題，這些題的題型繁多，解法獨特，因此得分率普遍較低。本文試圖用遞推法來解決幾類常見的排列組合及概率問題。1走樓梯問題例1：欲登上第10級樓梯，如果規(guī)定每步只能跨上一級或兩級，則不同的走法共有()（A）34種（B）55種（C）89種（

2、D）144種解法1：分類法：第一類：沒有一步兩級，則只有一種走法；第二類：恰有一步是一步兩級，則走完10級要走9步，9步中選一步是一步兩級的，有種可能走法；第三類：恰有兩步是一步兩級，則走完10級要走8步，8步中選兩步是一步兩級的，有種可能走法；依此類推，共有=89，故選(C)。解法2：遞推法：設走級有種走法，這些走法可按第一步來分類，第一類：第一步是一步一級，則余下的級有種走法；第二類：第一步是一步兩級，則余下的級有種走法，所以，又易得，由遞推可得，故選(C)。顯然，遞推法的關鍵是按照某種標準找出遞推關系式，并求出取第一個值(或前幾個

3、值)時的各項，然后代入遞推關系式，求出題中要求的值。當然，我們也可以由找出的遞推關系，求出通項，但對于選擇填空題，我們不必大動干戈的去求通項，因為這樣太浪費時間與精力。2更列問題把個元素排成一列，所有元素各有一個不能占據(jù)的指定位置，且不同元素不能占據(jù)的指定位置也不同，我們把滿足這種條件的一個排列叫做這些元素的一個更列。例2：五個人排成一列，重新站隊時，各人都不站在原來的位置上，那么不同的站隊方式共有()（A）60種（B）44種（C）36種（D）24種解：首先我們把人數(shù)推廣到個人，即個人排成一列，重新站隊時，各人都不站在原來的位置上。設滿

4、足這樣的站隊方式有種，現(xiàn)在我們來通過合理分步，恰當分類找出遞推關系：第一步：第一個人不站在原來的第一個位置，有種站法。第二步：假設第一個人站在第2個位置，則第二個人的站法又可以分為兩類：第一類，第二個人恰好站在第一個位置，則余下的個人有4種站隊方式；第二類，第二個人不站在第一個位置，則就是第二個人不站在第一個位置，第三個人不站在第三個位置，第四個人不站在第四個位置，……，第個人不站在第個位置，所以有種站隊方式。由分步計數(shù)原理和分類計數(shù)原理，我們便得到了數(shù)列的遞推關系式：，顯然，，再由遞推關系有，，故應選(B)我們再來看一道全國高考題：例

5、3：同室4人各寫一張賀年卡，先集中起來，然后每人從中拿一張別人送出的賀年卡，則4張賀年卡不同的分配方式共有()(1993年全國高考試題)（A）6種（B）9種（C）11種（D）23種此題就是更列問題，即為例2中的，故選（B）3染色問題例4：用4種不同顏色涂四邊形的4個頂點，要求每點染一種顏色，相鄰的頂點染不同的顏色，則不同的染色方法有()（A）84種（B）72種（C）48種（D）24種解：我們先把這個題目推廣：用種不同顏色給邊形的個頂點染色(其中，且為常數(shù))，每點染一種顏色，相鄰的頂點染不同的顏色，不同的染色方法有多少種？設不同的染色方法

6、有種，現(xiàn)在我們來通過合理分布，恰當分類找出遞推關系：第一步：染，有種染法；第二步：染，有種染法；同理，染均有種染法，最后染，如果僅考慮與不同色，則仍有種染法，相乘得種染法，但要去掉與同色的染法數(shù)，此時可將與合并看成一個點，得出需要排除的染法數(shù)為，所以有，顯然，。又本題中，顏色數(shù)，所以遞推關系為：，又，所以（種），故選（A）。用這種方法，不難求出下面兩道2003年的高考題：例5：如圖1，一個地區(qū)分為5個行政區(qū)域，現(xiàn)給地圖著色，要求相鄰區(qū)域不得使用同一顏色，現(xiàn)有四種顏色可供選擇，則不同的著色方法共有種。（以數(shù)字作答）(2003年全國高考試題

7、)例6：某城市在中心廣場建造一個花圃，花圃分成6個部分(如圖2)，現(xiàn)要栽種4種不同顏色的花，每部分栽種一種且相鄰部分不能栽種同樣顏色的花，不同的栽種方法共有種。（以數(shù)字作答）(2003年天津理科高考試題)1345圖12123456圖24我們來看例5，其中2、3、4、5四個區(qū)域圍成一個四邊形，因此可以把它們看成是一個四邊形的4個頂點，而區(qū)域1就是這個四邊形對角線的交點。第一步，先涂區(qū)域1，有4種涂法，由于區(qū)域1跟其余四個區(qū)域都相鄰，因此涂1的顏色不能用來涂其余的四個區(qū)域，因此第二步相當于用3種顏色來涂一個四邊形的四個頂點，由例4不難得出，

8、，所以，，由分步計數(shù)原理，得出共有種涂法。同理，不難得出例6的答案為120種。4傳球問題例7：甲、乙、丙、丁四人相互傳球，第一次甲傳給乙、丙、丁中的任一人，第二次由拿球者再傳給其他人中任一人，這樣共傳了四次