遞歸數(shù)列在計(jì)數(shù)中的應(yīng)用

周天明

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

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

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

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

設(shè)遞推數(shù)列可化成an-λan-1=μ(an-1-λan-2)，即an=(μ+λ)an-1-λμan-2，比較對(duì)應(yīng)的系數(shù)，

①

②

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

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

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

解析記第n次傳球時(shí)球仍傳回到甲的傳法種數(shù)為an，易得a1=0,a2=m-1，要第n次傳球時(shí)球正好又傳回到甲,必需第n-1次傳球時(shí)球正好不傳到甲. 因?yà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次傳球時(shí)球正好傳回到甲即可,故得遞推數(shù)列an=(m-1)n-1-an-1.

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

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

n個(gè)不同元素的一個(gè)全錯(cuò)位排列可分成二個(gè)步驟:

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

章建躍先生提出以課本為本才是好的數(shù)學(xué)教學(xué).我們?cè)谄綍r(shí)的教學(xué)中，要以教材為本，要重視教材中的例題和閱讀材料的教學(xué)，教材的每一個(gè)角落都可能成為拓展的落腳點(diǎn)和生成點(diǎn)，也是命題的切入點(diǎn)，基于教材進(jìn)行適度拓展，不但可以提高學(xué)生的學(xué)習(xí)興趣，也可以提高提高學(xué)生提出問題和解決問題的能力，一舉兩得，何樂而不為.