遞歸數列在計數中的應用

周天明

(安徽省合肥市第六中學 230001)

人教A版數學教材,必修5第二章的閱讀與思考,是關于我國古老智力游戲九連環的相關內容,書中利用數列的有關知識,解決了解開九連環最少需要移動圓環次數問題,在選修2-2中,又以例題的形式提出了漢諾塔問題,同樣也利用數列的有關知識,解決了鐵片最少需要移動次數問題.在排列組合問題中也存在類似的解決問題的方法.這兩個問題都是計數問題,都使用了所謂的遞歸數列法,按照某種標準找出遞推關系式，并求出取第一個值(或前幾個值)時的各項，然后代入遞推關系式，得出所要求的結果.將計數問題化歸為數列問題,通過遞推關系式求出數列的通項公式或數列中的某一項.這類問題需要對題設中所給出的遞推關系式進行分析、推理、變形等處理，發現規律才能達到所要解決問題的目的.實際上很多計數問題都可以用遞歸數列法,以下介紹其在幾種典型問題中的應用.

問題1 (上樓梯問題)有一樓梯共n級,如果規定每次只能跨上一級或兩級,問要登上第n級樓梯,共有多少種不同的走法？

解析設登上第n級樓梯有an種走法，而登上第n級走法可以分為兩類,第一類是第n-1級跨一級，第二類是從第n-2級跨兩級，根據加法原理有an=an-1+an-2，又a1=1,a2=2.

設遞推數列可化成an-λan-1=μ(an-1-λan-2)，即an=(μ+λ)an-1-λμan-2，比較對應的系數，

①

②

問題2 (圓形染色問題)如圖所示，將圓n等分得到n塊區域M1,M2,M3,…,Mn(n≥2)，現取k(k≥2)種顏色對這n塊區域染色，要求每相鄰的兩個區域染不同色，共有多少種不同染色方案？

解析設k種顏色對n塊區域染色，要求每相鄰的兩個區域染不同色，共有an種不同染色方案．區域M1有k種染色方案，區域M2有k-1種染色方案，區域M3也有k-1種染色方案，…，區域Mn也有k-1種染色方案，共有k·(k-1)n-1種染色方案．顯然上述計數中包含區域M1和區域Mn同色的情況，故要排除這種情況．若區域M1和區域Mn同色，則可以把區域M1和區域Mn看成是同一個區域，根據假設知此時，有an-1種染色方案，故an=k·(k-1)n-1-an-1，又a2=k(k-1),a3=k(k-1)(k-2)，設遞推式可化為an-t(k-1)n=-[an-1-t(k-1)n-1],即an=-an-1+tk(k-1)n-1，與原遞推式比較對應系數，得t=1.所以有an-(k-1)n=-[an-1-(k-1)n-1]，可見數列{an-(k-1)n}從第2項k-1起成公比為-1的等比數列，所以an-(k-1)n=(k-1)·(-1)n-2，故an=(k-1)n+(k-1)·(-1)n(n≥2).

問題3 (傳球問題)有m個人做相互傳球練習，第一次甲先傳球給其余m-1人中一人,第二次由拿球者再傳給其余m-1人中的一人,這樣共傳了n次球,則第n次傳球仍傳回到甲的傳法種數共有多少種?

解析記第n次傳球時球仍傳回到甲的傳法種數為an，易得a1=0,a2=m-1，要第n次傳球時球正好又傳回到甲,必需第n-1次傳球時球正好不傳到甲. 因為前n-1次傳球共有(m-1)n-1種不同傳法，其中第n-1次傳球傳回到甲的傳法有an-1種，所以第n-1次傳球沒有傳回到甲的傳法有(m-1)n-1-an-1種，在這(m-1)n-1-an-1種情況中，只要第n次傳球時球正好傳回到甲即可,故得遞推數列an=(m-1)n-1-an-1.

問題4 (全錯位排列問題)有n個不同的元素,它們一一對應于n個位置，如果這n個元素都不排在自身對應的位置上,這種排列的方法稱為n個元素的一個全錯位排列.n個元素都不排在自身對應的位置上的全錯位排列共有多少種？

解析設這n個不同的元素分別為b1,b2,…,bn，并設元素bi對應的位置為i(i=1,2,…,n)，并記n個元素都不排在自身對應的位置上的不同排列有an種.

n個不同元素的一個全錯位排列可分成二個步驟:

第一步，先決定元素b1的排法,可以排在位置2,3,…,n，共有n-1種不同排法；

章建躍先生提出以課本為本才是好的數學教學.我們在平時的教學中，要以教材為本，要重視教材中的例題和閱讀材料的教學，教材的每一個角落都可能成為拓展的落腳點和生成點，也是命題的切入點，基于教材進行適度拓展，不但可以提高學生的學習興趣，也可以提高提高學生提出問題和解決問題的能力，一舉兩得，何樂而不為.