遞推思想在排列組合中的應(yīng)用

韓文娟 霍忠林

利用遞推思想求解排列組合問題是一種解題思路，但對同學(xué)們的數(shù)學(xué)素養(yǎng)要求較高，是排列組合中的難點。如何借助分類加法計數(shù)原理和分步乘法計數(shù)原理找到遞推關(guān)系這是解題的關(guān)鍵點，下面通過六種題型來分析遞推思想在排列組合中的應(yīng)用。

題型一、爬樓梯問題

例1 一段樓梯，有10個臺階，小明每次走一個或兩個臺階，則他有多少種不同的走法？

解析：問題一般化：一段樓梯，有n 個臺階，小明每次走一個或兩個臺階，則他有多少種不同的走法？

設(shè)小明走n 個臺階有an 種走法，則a1=1，a2=2。

思路一 按第一步走的臺階數(shù)分類

若第一步走一個臺階，則余下的n-1個臺階共有an-1 種走法。

若第一步走兩個臺階，則余下的n-2個臺階共有an-2 種走法。

所以an =an-1+an-2（n≥3）。

當(dāng)n=10時，易得a10=89。

思路二 按最后一步走的臺階數(shù)分類

若最后一步走一個臺階，則前n-1個臺階共有an-1 種走法。

若最后一步走兩個臺階，則前n-2個臺階共有an-2 種走法。

所以an =an-1+an-2（n≥3）。

當(dāng)n=10時，易得a10=89。

評析：“爬樓梯問題”本質(zhì)上就是“斐波那契數(shù)列”，該數(shù)列是普通高中教材人教A 版《數(shù)學(xué)選擇性必修第二冊》第11頁、第12頁的內(nèi)容。采用類似方法還可以處理下面變式。

變式1：一段樓梯，有5個臺階，小明每次走一個或兩個或三個臺階，則他有多少種不同的走法？

解析：該問題等價于：已知數(shù)列an =an-1+an-2+an-3（n≥4），其中a1=1，a2=2，a3=4，求a5 的值。過程略。

題型二、平面劃分問題

例2 3條直線最多能將平面分成幾部分？ 4條直線最多能將平面分成幾部分呢？

解析：問題一般化：n 條直線最多能將平面分成幾部分？

設(shè)n 條直線最多將平面分成an 部分，則前n-1條直線最多將平面分成an-1 部分。要使第n 條直線將平面分成的部分最多，則第n 條直線必須與前n-1條直線均相交，此時共有n-1 個交點，增加n 部分，從而有an =an-1+n（n≥2），其中a1=2。容易得到a3=7，a4=11，即為本題所求的答案。

評析：平面劃分問題是典型的an =an-1+f（n）型遞推公式的應(yīng)用，通過累加法可以得到an =n2+n+2／2 。

題型三、錯排問題

例3 甲、乙、丙、丁、戊5個人排成一排，重新站隊，各人都不站在原來的位置，共有多少種不同的站隊方式？

解析：問題一般化：n 個人排成一排，重新站隊，各人都不站在原來的位置，共有多少種不同的站隊方式？

設(shè)n 個人排成一排，重新站隊，各人都不站在原來的位置共有an 種方法。

第一步，第一個人不站在原來的位置共有n-1種方法。

第二步，不妨設(shè)第一個人站在第二個人的原來位置，則第二個人的站法又可以分為兩類：

第一類是第二個人站在第一個人原來的位置，此時余下的n-2人共有an-2 種站法;

第二類是第二個人不站在第一個人原來的位置，此時第三個人不站在第三個人原來的位置，第四個人不站在第四個人原來的位置，……，第n 個人不站在第n 個人原來的位置，所以有an-1 種站法。

由分類加法計數(shù)原理和分步乘法計數(shù)原理得an =（n-1）·（an-1+an-2）（n≥3），其中a1=0，a2=1。

容易得到a5=44，即為本題所求的答案。

評析：錯排問題的本質(zhì)是先把n 個不同元素排成一排，再重新排列，所有元素各有一個指定位置不能站，且不同元素不能站的指定位置也不同。上述解題過程中第二步的第二類：從第二個人到第n 個人，每個人均有一個指定位置不能站，且不同的人不能站的指定位置也不同，因此是n-1個人的錯排問題。比如例3與下面變式本質(zhì)是一樣的。

變式2：甲、乙、丙、丁、戊排成一排，重新站隊時，甲不能站原來乙的位置，乙不能站原來丙的位置，丙不能站原來丁的位置，丁不能站原來戊的位置，戊不能站原來甲的位置，則不同的站隊方式有多少種？ （答案略。）

題型四、傳球問題

例4 甲、乙、丙三人傳球，由甲開始發(fā)球，并作為第一次傳球，經(jīng)過5次傳球后，球仍回到甲手中，則不同的傳球方式有多少種？

解析：問題一般化：甲、乙、丙三人傳球，由甲開始發(fā)球，并作為第一次傳球，經(jīng)過n 次傳球后，球仍回到甲手中，則不同的傳球方式有多少種？

設(shè)n 次傳球后，球仍回到甲手中有an 種方法，要使第n 次傳球后，球在甲手中，則第n-1次傳球后球一定在乙或丙手中，而n-1次傳球一共有2n-1 種方法，所以第n-1次傳球后球在乙或丙手中的種類數(shù)為2n-1-an-1。

接著乙或丙再向甲傳最后一次球，所以an =2n-1-an-1（n≥2），其中a1=0。

容易得到a5=10，即為本題所求的答案。

評析：傳球問題是排列組合中最經(jīng)典的問題。實際上例4還可以推廣為“m （m ≥2）個人傳球，由甲開始發(fā)球，并作為第一次傳球，經(jīng)過n（n≥2）次傳球后，球仍回到甲手中，則遞推關(guān)系為an = （m -1）n-1 -an-1（m ≥2，n≥2），其中a1=0”。

題型五、環(huán)形區(qū)域染色問題

例5 用4 種不同顏色給六邊形A1A2A3A4A5A6 的6個頂點染色，每個頂點染一種顏色，相鄰的頂點染不同的顏色，則有多少種不同的染色方法？

解析：問題一般化：用m 種不同顏色給n邊形A1A2…An 的n 個頂點染色（其中m ≥3，n≥3），每個頂點染一種顏色，相鄰的頂點染不同的顏色，則有多少種不同的染色方法？

設(shè)用m 種不同顏色給n 邊形A1A2…An的n 個頂點染色（其中m≥3，n≥3），每個頂點染一種顏色，相鄰的頂點染不同的顏色的染色方法有an 種，現(xiàn)在從A1 到An 依次染色。

第一步，染A1 共有m 種方法。

第二步，染A2 共有m-1種方法，同理染A3，…，An 均有m -1種方法，根據(jù)分步乘法計數(shù)原理得共有m（m-1）n-1 種方法，但是要去掉A1 與An 同色的種類數(shù)。當(dāng)A1 與An 同色時，此時可將A1 與An 合并看成一個點，則此時有an-1 種方法，故an =m （m -1）n-1 -an-1（其中m≥3，n≥3），其中a3=A3m 。

容易得到當(dāng)m =4，n=6時a6=732，即為本題所求的答案。

評析：環(huán)形區(qū)域染色問題與傳球問題的求解思路類似，不同點是傳球問題第一個發(fā)球者是固定的，而環(huán)形區(qū)域染色問題第一個染色點不固定。若將例4 改為“甲、乙、丙三人傳球，第一次發(fā)球者傳給其他任意一人，第二次由拿球者再傳給其他任意一人，經(jīng)過5次傳球后，球仍回到最初發(fā)球者手中，則不同的傳球方式有多少種”，這樣就是環(huán)形區(qū)域染色問題。

題型六、結(jié)草成環(huán)問題

例6 現(xiàn)有3根草，共有6個草頭，現(xiàn)將6個草頭平均分成3組，每兩個草頭打結(jié)，則打結(jié)后所有草構(gòu)成一個圓環(huán)的打結(jié)方法有多少種？

解析：問題一般化：現(xiàn)有n 根草，共有2n個草頭，現(xiàn)將2n 個草頭平均分成n 組，每兩個草頭打結(jié)，則打結(jié)后所有草構(gòu)成一個圓環(huán)的打結(jié)方法有多少種？

設(shè)n 根草構(gòu)成一個圓環(huán)的打結(jié)方法共有an種，現(xiàn)將草頭如圖1 編號為1，2，3，…，2n-1，2n。

草頭1可以與草頭3，4，…，2n-1，2n 打結(jié)，共2n-2種方法;不妨設(shè)草頭1與草頭3打結(jié)，此時可將問題轉(zhuǎn)化為“n-1 根草打結(jié)后所有草構(gòu)成一個圓環(huán)的問題”，故共有an-1種方法，根據(jù)分步乘法計數(shù)原理得an =（2n-2）·an-1（n≥2），其中a1=1。

容易得到a3=8，即為本題所求的答案。

評析：結(jié)草成環(huán)問題是一個古老的游戲問題，是典型的an =f（n）·an-1 型遞推公式的應(yīng)用，通過累乘法可以得到an=2n-1（n-1）！。

通過對上述六種題型的研究可以發(fā)現(xiàn)，有些排列組合問題通過合理分步、恰當(dāng)分類，巧妙地運用遞推數(shù)列的思想方法，不僅可以化繁為簡，輕松破解，還能將問題拓展和推廣，從而達(dá)到“做一題、會一類、通一片”的效果。

（責(zé)任編輯 徐利杰）