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

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

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

題型一、爬樓梯問題

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

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

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

思路一 按第一步走的臺階數分類

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

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

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

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

思路二 按最后一步走的臺階數分類

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

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

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

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

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

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

解析:該問題等價于:已知數列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種站法。

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

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

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

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

題型四、傳球問題

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

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

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

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

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

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

題型五、環形區域染色問題

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

解析:問題一般化:用m種不同顏色給n邊形A1A2…An的n個頂點染色(其中m≥3,n≥3),每個頂點染一種顏色,相鄰的頂點染不同的顏色,則有多少種不同的染色方法?

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

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

第二步,染A2共有m-1種方法,同理染A3,…,An均有m-1種方法,根據分步乘法計數原理得共有m(m-1)n-1種方法,但是要去掉A1與An同色的種類數。當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,即為本題所求的答案。

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

題型六、結草成環問題

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

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

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

圖1

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

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

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

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