遞推思想在排列組合中的應用

■河北南宮中學 韓文娟 霍忠林

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

題型一、爬樓梯問題

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

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

設小明走n個臺階有an種走法,則a1=1,a2=2。

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

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

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

所以an=an-1+an-2(n≥3)。

當n=10時,易得a10=89。

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

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

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

所以an=an-1+an-2(n≥3)。

當n=10時,易得a10=89。

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

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

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

題型二、平面劃分問題

例23 條直線最多能將平面分成幾部分?4條直線最多能將平面分成幾部分呢?

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

設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)型遞推公式的應用,通過累加法可以得到

題型三、錯排問題

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

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

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

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

第二步,不妨設第一個人站在第二個人的原來位置,則第二個人的站法又可以分為兩類:

第一類是第二個人站在第一個人原來的位置,此時余下的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,即為本題所求的答案。

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

變式2:甲、乙、丙、丁、戊排成一排,重新站隊時,甲不能站原來乙的位置,乙不能站原來丙的位置,丙不能站原來丁的位置,丁不能站原來戊的位置,戊不能站原來甲的位置,則不同的站隊方式有多少種? (答案略。)

題型四、傳球問題

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

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

設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)次傳球后,球仍回到甲手中,則遞推關系為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),每個頂點染一種顏色,相鄰的頂點染不同的顏色,則有多少種不同的染色方法?

設用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ù)。當A1與An同色時,此時可將A1與An合并看成一個點,則此時有an-1種方法,故an=m(m-1)n-1-an-1(其中m≥3,n≥3),其中a3=A3m。

容易得到當m=4,n=6時a6=732,即為本題所求的答案。

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

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

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

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

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

圖1

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

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

評析:結草成環(huán)問題是一個古老的游戲問題,是典型的an=f(n)·an-1型遞推公式的應用,通過累乘法可以得到an=2n-1(n-1)!。

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