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

王正勇

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

組合數(shù)學(xué)的考題一般都以計數(shù)問題為主,而有些計數(shù)問題直接去求解并不是那么容易,因為它們是以“建立遞推關(guān)系”為背景的,也就是說,要先建立遞推關(guān)系,再去求解通項公式,才能順利完成計數(shù)問題.

1 知識與方法

1.1 遞推關(guān)系

對于數(shù)列{an}(n∈N*),若當(dāng)n≥k+1時,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)系①中,若各項的系數(shù)均是與n無關(guān)的常數(shù),則稱這個遞推關(guān)系為常系數(shù)遞推關(guān)系;若遞推關(guān)系中各項的次數(shù)相同,則稱這個遞推關(guān)系為齊次遞推關(guān)系;若遞推關(guān)系中各項的次數(shù)均不超過一次,則稱這個遞推關(guān)系為線性遞推關(guān)系.

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

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

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

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

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

2 應(yīng)用

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

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

現(xiàn)設(shè)n個平面最多能把空間分割成an個部分,易知a1=2,a2=2+2=4.增添第三個平面時,和原來兩個平面有兩條交線,兩條交線把第三個平面分成4個部分,所以使空間增多4個部分,即a3=a2+4=8.增添第四個平面時,和原來三個平面有三條交線,三條交線把第四個平面分成7個部分,所以空間增多7個部分,即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].

所以得到下列遞推公式

評價本題是通過建立數(shù)列的遞推關(guān)系來求解,對于較為復(fù)雜的計數(shù)問題,這個方法值得借鑒.

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

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

(2)將n個金屬圓片從1號柱子全部移到3號柱子,至少需要移動____次.

圖1 金屬圓片

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

當(dāng)n=2時,移動的順序為:(12)(13)(23),共移動3次.

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

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

共移動了7次.

(2)記把n個金屬圓片從1號柱子移到3號柱子,最少需要移動an次,則由(1)知

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

當(dāng)移動n個金屬圓片時,可分別進行下列3個步驟:

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

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

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

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

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

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

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

對于任意一個n(n≥5),記A1,A2,…,An順次為這個n邊形的頂點,則對它按題設(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.

又因為T3=6,T4=18,解得c1=2,c2=1.

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

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

當(dāng)S,A,B已染好時,不妨設(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種染法.

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

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

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

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

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

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

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

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

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