建立遞推關(guān)系求通項(xiàng)公式

王正勇

(如皋市搬經(jīng)中學(xué),江蘇 如皋 226561)

組合數(shù)學(xué)的考題一般都以計(jì)數(shù)問(wèn)題為主,而有些計(jì)數(shù)問(wèn)題直接去求解并不是那么容易,因?yàn)樗鼈兪且浴敖⑦f推關(guān)系”為背景的,也就是說(shuō),要先建立遞推關(guān)系,再去求解通項(xiàng)公式,才能順利完成計(jì)數(shù)問(wèn)題.

1 知識(shí)與方法

1.1 遞推關(guān)系

對(duì)于數(shù)列{an}(n∈N*),若當(dāng)n≥k+1時(shí),an與an-1,an-2,…,an-k之間滿足函數(shù)關(guān)系

F(an,an-1,an-2,…,an-k)=0,

①

或an=f(an-1,an-2,…,an-k),

②

則稱①或②為k階遞推關(guān)系或k階遞歸關(guān)系.由此遞推關(guān)系及初值條件a1,a2,…,ak所確定的數(shù)列稱為k階遞推數(shù)列[1].

在k階遞推關(guān)系①中,若各項(xiàng)的系數(shù)均是與n無(wú)關(guān)的常數(shù),則稱這個(gè)遞推關(guān)系為常系數(shù)遞推關(guān)系;若遞推關(guān)系中各項(xiàng)的次數(shù)相同,則稱這個(gè)遞推關(guān)系為齊次遞推關(guān)系;若遞推關(guān)系中各項(xiàng)的次數(shù)均不超過(guò)一次,則稱這個(gè)遞推關(guān)系為線性遞推關(guān)系.

本文主要介紹計(jì)數(shù)問(wèn)題的重要方法——建立線性遞推關(guān)系.

1.2 建立線性遞推關(guān)系的方法

(1)通過(guò)求數(shù)列{an}的第1項(xiàng)以及前幾項(xiàng),去尋找任一項(xiàng)an與它的前一項(xiàng)an-1或前幾項(xiàng)間的關(guān)系式.

(2)分析要計(jì)算第n項(xiàng)an的值需要計(jì)算哪些項(xiàng)的值,從而得到an與它的前幾項(xiàng)間的關(guān)系.

建立遞推關(guān)系進(jìn)而解遞推關(guān)系是解決組合計(jì)數(shù)問(wèn)題的一種常用而重要的方法.

2 應(yīng)用

例1(強(qiáng)基計(jì)劃模擬題)空間有n個(gè)平面,最多能把空間分割成____個(gè)部分[2].

解析為了將空間分割成最多的部分,n個(gè)平面中的任意兩個(gè)平面都不應(yīng)平行,任意三個(gè)平面都不應(yīng)共線,其所得交線中任意兩條交線都不應(yīng)平行.

現(xiàn)設(shè)n個(gè)平面最多能把空間分割成an個(gè)部分,易知a1=2,a2=2+2=4.增添第三個(gè)平面時(shí),和原來(lái)兩個(gè)平面有兩條交線,兩條交線把第三個(gè)平面分成4個(gè)部分,所以使空間增多4個(gè)部分,即a3=a2+4=8.增添第四個(gè)平面時(shí),和原來(lái)三個(gè)平面有三條交線,三條交線把第四個(gè)平面分成7個(gè)部分,所以空間增多7個(gè)部分,即a4=a3+7=15,按此規(guī)律可得到a5=a4+11=26,并發(fā)現(xiàn)

a1=2,

a2=a1+2=a1+(1+1),

a3=a2+4=a2+(1+2+1),

a4=a3+7=a3+(1+2+3+1),

a5=a4+11=a4+(1+2+3+4+1),

……

an=an-1+[(1+2+3+…+n-1)+1].

所以得到下列遞推公式

評(píng)價(jià)本題是通過(guò)建立數(shù)列的遞推關(guān)系來(lái)求解,對(duì)于較為復(fù)雜的計(jì)數(shù)問(wèn)題,這個(gè)方法值得借鑒.

例2(高考模擬題)如圖1所示,有標(biāo)號(hào)為1,2,3的三根柱子,在1號(hào)柱子上套有n個(gè)金屬圓片,從下到上圓片依次減小.按下列規(guī)則,把金屬圓片從1號(hào)柱子全部移到3號(hào)柱子,要求:①每次只能移動(dòng)一個(gè)金屬圓片;②較大的金屬圓片不能在較小的金屬圓片上面[3].

(1)若n=3,則至少需要移動(dòng)____次;

(2)將n個(gè)金屬圓片從1號(hào)柱子全部移到3號(hào)柱子,至少需要移動(dòng)____次.

圖1 金屬圓片

解析(1)當(dāng)n=1時(shí),只需要把金屬圓片從1號(hào)柱子移到3號(hào)柱子,用符號(hào)(13)表示,共移動(dòng)了1次.

當(dāng)n=2時(shí),移動(dòng)的順序?yàn)?(12)(13)(23),共移動(dòng)3次.

當(dāng)n=3時(shí),把上面的兩個(gè)金屬圓片作為一個(gè)整體,則歸結(jié)為n=2的情形,移動(dòng)的順序是:

(13)(12)(32);(13);(21)(23)(13)

共移動(dòng)了7次.

(2)記把n個(gè)金屬圓片從1號(hào)柱子移到3號(hào)柱子,最少需要移動(dòng)an次,則由(1)知

a1=1,a2=3,a3=7.

當(dāng)移動(dòng)n個(gè)金屬圓片時(shí),可分別進(jìn)行下列3個(gè)步驟:

①將上面(n-1)個(gè)金屬圓片從1號(hào)柱子移到2號(hào)柱子;②將第n個(gè)金屬圓片從1號(hào)柱子移到3號(hào)柱子;③將上面(n-1)個(gè)金屬圓片從2號(hào)柱子移到3號(hào)柱子.

這樣就把移動(dòng)n個(gè)金屬圓片的任務(wù),轉(zhuǎn)為移動(dòng)兩次(n-1)個(gè)金屬圓片和移動(dòng)1次第n個(gè)金屬圓片的任務(wù).而移動(dòng)(n-1)個(gè)金屬圓片需要移動(dòng)兩次(n-2)個(gè)金屬圓片和移動(dòng)1次第(n-1)個(gè)金屬圓片;移動(dòng)(n-2)個(gè)金屬圓片需要移動(dòng)兩次(n-3)個(gè)金屬圓片和移動(dòng)1次第(n-2)個(gè)金屬圓片……如此繼續(xù),直到轉(zhuǎn)化為移動(dòng)1個(gè)金屬圓片的情形.根據(jù)這個(gè)過(guò)程,可得遞推公式:

從而當(dāng)n≥2時(shí),有an+1=2(an-1+1).

所以{an+1}是以2為公比,2為首項(xiàng)的等比數(shù)列.

所以an+1=2n,即an=2n-1.

例3(強(qiáng)基計(jì)劃模擬題)將一個(gè)2021邊形的每個(gè)頂點(diǎn)染為紅、藍(lán)、綠三種顏色之一,使得相鄰頂點(diǎn)的顏色互不相同.問(wèn):有多少種滿足條件的染色方法?

解析記將一個(gè)n邊形的每個(gè)頂點(diǎn)染為紅、藍(lán)、綠三種顏色之一,使得相鄰頂點(diǎn)的顏色互不相同的方法數(shù)為Tn. 易知,T3=6,T4=18.

對(duì)于任意一個(gè)n(n≥5),記A1,A2,…,An順次為這個(gè)n邊形的頂點(diǎn),則對(duì)它按題設(shè)要求染色,有兩種情況:

①A1,An-1異色,共有Tn-1種;

②A1,An-1同色,共有2Tn-2種.

因此Tn=Tn-1+2Tn-2(n≥5).

該遞推公式的特征方程為x2=x+2,解得x1=-1,x2=2.

所以Tn=c1(-1)n+c2·2n.

又因?yàn)門3=6,T4=18,解得c1=2,c2=1.

因此Tn=2(-1)n+2n,所以T2021=22021-2.

例4(1995年全國(guó)高中數(shù)學(xué)聯(lián)賽)將一個(gè)四棱錐的每個(gè)頂點(diǎn)染上一種顏色,并使同一條棱的兩個(gè)端點(diǎn)異色. 如果只有5種顏色可供使用,那么不同的染色方法總數(shù)是多少?

當(dāng)S,A,B已染好時(shí),不妨設(shè)其顏色分別為1,2,3.下面分C與A同色與異色兩種情況討論:

若C染顏色2,則D可染顏色3,4,5之一,有3種染法;若C染顏色4,則D可染顏色3或5,有2種染法;若C染顏色5,則D可染顏色3或4,有2種染法.

可見(jiàn),當(dāng)S,A,B已染好時(shí),C與D還有7種染法. 從而總的染色方法數(shù)為60×7=420.

評(píng)析我們可把四棱錐推廣為n棱錐,顏色數(shù)推廣為m種(n≥3,m≥4).

事實(shí)上,頂點(diǎn)S可用m種顏色中的任一種,并且S上的顏色不能再出現(xiàn)在多邊形A1A2…An的頂點(diǎn)上. 問(wèn)題轉(zhuǎn)化為用m-1種顏色給多邊形A1A2…An的頂點(diǎn)染色,相鄰的頂點(diǎn)不同色. 設(shè)有an種染法,則a3=(m-1)(m-2)(m-3).

對(duì)n>3,考慮an的遞推公式. 若從頂點(diǎn)A1開(kāi)始,則A1有m-1種染法,繼而A2,A3,…,An-1均有m-2種染法. 最后到An,如果只要求An與An-1不同色,則仍有m-2種染法,于是總共有(m-1)·(m-2)n-1種染法.

在這個(gè)計(jì)算過(guò)程中可以分為兩類:一類是An與A1不同色,這符合要求,正是染法數(shù)an;另一類是An與A1同色,這不符合要求,但可將An與A1合并成一點(diǎn),得出染法數(shù)an-1.于是

即an=(m-2)n+(-1)n(m-2).

從而n棱錐的染法總數(shù)為

N=(m-2)n+(-1)n(m-2).

許多組合計(jì)數(shù)問(wèn)題都?xì)w結(jié)為求某個(gè)數(shù)列的通項(xiàng)公式,而直接去求數(shù)列的通項(xiàng)公式往往比較困難,此時(shí)我們可以考慮先求關(guān)于該數(shù)列的遞推關(guān)系,然后去解這個(gè)遞推關(guān)系.如果能順利完成這兩個(gè)步驟,則問(wèn)題就得到了解決.