建立遞推關系求通項公式

2023-10-26 11:04:34王正勇

數理化解題研究 2023年28期

王正勇

(如皋市搬經中學,江蘇如皋 226561)

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

1 知識與方法

1.1 遞推關系

對于數列{an}(n∈N*),若當n≥k+1時,an與an-1,an-2,…,an-k之間滿足函數關系

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

①

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

②

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

在k階遞推關系①中,若各項的系數均是與n無關的常數,則稱這個遞推關系為常系數遞推關系;若遞推關系中各項的次數相同,則稱這個遞推關系為齊次遞推關系;若遞推關系中各項的次數均不超過一次,則稱這個遞推關系為線性遞推關系.

本文主要介紹計數問題的重要方法——建立線性遞推關系.

1.2 建立線性遞推關系的方法

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

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

建立遞推關系進而解遞推關系是解決組合計數問題的一種常用而重要的方法.

2 應用

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

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

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

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].

所以得到下列遞推公式

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

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

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

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

圖1 金屬圓片

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

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

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

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

共移動了7次.

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

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

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

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

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

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

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

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

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

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

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

①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.