談構(gòu)造遞推關(guān)系式法在計(jì)數(shù)問題中的應(yīng)用

劉海濤

(安徽省蕪湖市第一中學(xué))

《中國高考評(píng)價(jià)體系》指出:高考要從“知識(shí)立意”轉(zhuǎn)向“能力立意”，考查學(xué)生的“關(guān)鍵能力”和“核心素養(yǎng)”.這就要求學(xué)生在學(xué)習(xí)中學(xué)會(huì)靈活運(yùn)用所學(xué)知識(shí)分析、解決問題，達(dá)到從“解題”向“解決問題”的轉(zhuǎn)變.解答一些看似與數(shù)列無關(guān)的計(jì)數(shù)問題時(shí)，若我們深入剖析問題，利用類比聯(lián)想、抽象轉(zhuǎn)化，通過建立數(shù)列的遞推關(guān)系模型表示計(jì)數(shù)規(guī)則，則可將問題轉(zhuǎn)化為數(shù)列問題，避免繁雜的分類討論，簡化解題過程，同時(shí)可將問題拓展到一般化模型.

1 涂色問題

例1如圖1所示，用四種不同的顏色給六邊形ABCDEF的六個(gè)頂點(diǎn)涂色，若相鄰頂點(diǎn)不同色，則不同的涂色方案共有_________種.

圖1

解析

用四種顏色給n邊形A1A2…An的頂點(diǎn)涂色，相鄰頂點(diǎn)不同色，不同的涂色方案數(shù)記作an(n≥2).從n－1邊 形A1A2…An－1到n邊 形A1A2…An，我們考慮增加的頂點(diǎn)An的涂色問題.

若A1與An－1同色(n≥4)，則An有三種顏色可供選擇，而前n－2個(gè)頂點(diǎn)滿足相鄰不同色，所以此時(shí)有3an－2種方案.

若A1與An－1不同色，則An有兩種顏色可供選擇，而前n－1個(gè)頂點(diǎn)滿足相鄰不同色，所以此時(shí)有2an－1種方案.

綜上，得到遞推關(guān)系式an＝2an－1＋3an－2(n≥4)，易知a2＝A24＝12，a3＝A34＝24，經(jīng)計(jì)算得a6＝732，所以有732種涂色方案.點(diǎn)評(píng)

本題只有六個(gè)頂點(diǎn)，利用分類討論的思想逐一分析可以快速解題，但是若點(diǎn)數(shù)較多，則分類情況太多，難以求解.從n－1邊形到n邊形增加的頂點(diǎn)的涂色情況分析，可以建立遞推關(guān)系式順利解題，同時(shí)可將問題拓展為一般化模型.

模型1用m(n≥m≥3)種不同的顏色給n(n≥3)邊形A1A2…An的n個(gè)頂點(diǎn)涂色，若相鄰頂點(diǎn)不同色，則不同的涂色方案共有(m－1)n＋(－1)n(m－1)種.

證明n邊形A1A2…An不同的涂色方案數(shù)記作an(n≥3).若A1與An－1同色(n≥4)，則An有m－1種顏色可供選擇，而前n－2個(gè)頂點(diǎn)滿足相鄰不同色，所以此時(shí)有(m－1)an－2種方案.若A1與An－1不同色，則An有兩種顏色可供選擇，而前n－1個(gè)頂點(diǎn)滿足相鄰不同色，所以此時(shí)有(m－2)an－1種方案.

綜上，得到遞推關(guān)系式an＝(m－2)an－1＋(m－1)an－2(n≥4)，易知a2＝A2m，a3＝A3m.解特征方程x2＝(m－2)x＋m－1，得特征根為m－1和－1，設(shè)an＝λ·(m－1)n－1＋μ·(－1)n－1，則于是an＝(m－1)n＋(－1)n(m－1)，不同的涂色方案共有(m－1)n＋(－1)n(m－1)種.

2 登臺(tái)階問題

例2現(xiàn)要登一個(gè)十級(jí)的臺(tái)階，每一次可登一級(jí)或兩級(jí)，則有多少種不同的登法?

解析

不妨將n級(jí)臺(tái)階的登法數(shù)記作an，因?yàn)榈堑降趎級(jí)臺(tái)階的方式有兩種:一種方式是從第n－2級(jí)臺(tái)階直接登上第n級(jí)臺(tái)階，另一種方式是從第n－1級(jí)臺(tái)階登上第n級(jí)臺(tái)階，所以得到遞推關(guān)系式an＝an－2＋an－1(n≥3)，易知a1＝1，a2＝2，經(jīng)計(jì)算得a10＝89，所以共有89種登法.

點(diǎn)評(píng)

模型2登上一個(gè)n級(jí)的臺(tái)階，若每一次可登一級(jí)或兩級(jí)，則有種登法.

證明登上n級(jí)臺(tái)階的登法數(shù)實(shí)為數(shù)列{an}的通項(xiàng)，而 數(shù)列{an}滿 足:a1＝1，a2＝2，an＝an－2＋an－1(n≥3).解 特 征 方 程x2＝x＋1，得 特 征 根 為

3 全錯(cuò)位排列問題

例3現(xiàn)有分別標(biāo)號(hào)為1，2，3，4，5的五個(gè)球與五個(gè)盒子，將五個(gè)球分別放入五個(gè)盒子中，每個(gè)盒子僅一個(gè)球，若要求球的編號(hào)與所在盒子的編號(hào)均不同，則有多少種不同的放球方法?

解析

不妨把編號(hào)為1，2，…，n的球放入編號(hào)為1，2，…，n的盒子，符合題設(shè)條件的放法數(shù)記作an.我們分兩步來完成放球:第一步，將標(biāo)號(hào)為n的球放到標(biāo)號(hào)為m的盒子里，有n－1種放法.第二步，考慮編號(hào)為m的球，有兩種放法，即放到編號(hào)為n的盒子里，則余下n－2個(gè)球放到n－2個(gè)盒子，有an－2種放法;不放到編號(hào)為n的盒子里，這時(shí)對(duì)于這n－1個(gè)球，共有an－1種放法.

綜上，得到遞推關(guān)系式an＝(n－1)(an－2＋an－1)(n≥3)，易得a1＝0，a2＝1，經(jīng)計(jì)算a5＝44，所以共有44種放法.

點(diǎn)評(píng)

由滁州市統(tǒng)計(jì)局網(wǎng)站公布的信息可知，2018年上半年全市地區(qū)生產(chǎn)總值增長9.7%，高于全省增速1.4個(gè)百分點(diǎn)，高于預(yù)期增速2.1個(gè)百分點(diǎn)，高于同期增速0.5個(gè)百分點(diǎn)。市場消費(fèi)增長，網(wǎng)上零售發(fā)展較快，城鄉(xiāng)協(xié)調(diào)發(fā)展，商品零售和餐飲消費(fèi)協(xié)調(diào)發(fā)展。就業(yè)形勢良好，物價(jià)保持穩(wěn)定，居民收入穩(wěn)步增長。從企業(yè)的經(jīng)營情況和財(cái)政收入結(jié)構(gòu)看，經(jīng)濟(jì)發(fā)展的質(zhì)量效益不斷提高。工業(yè)增速回升，在全省的位次較高，國有企業(yè)、園區(qū)工業(yè)增長加快，部分行業(yè)貢獻(xiàn)較大，億元企業(yè)的拉動(dòng)力較強(qiáng)。高新、戰(zhàn)略新興產(chǎn)業(yè)取得較快增長，創(chuàng)新創(chuàng)業(yè)成效明顯，產(chǎn)業(yè)轉(zhuǎn)型升級(jí)穩(wěn)步推進(jìn)。

本題實(shí)際上是組合數(shù)學(xué)中的錯(cuò)排問題，就是將n個(gè)元素進(jìn)行排列，若每一個(gè)元素均不在原來的位置，則稱之為這n個(gè)元素的一個(gè)錯(cuò)排.根據(jù)解答不難發(fā)現(xiàn)，可建立數(shù)列模型求解錯(cuò)排問題.

模型3若將n個(gè)元素進(jìn)行排列，使得每一元素均不在原來位置，則共有n!種排列方法.

證明n個(gè)元素的錯(cuò)排方法數(shù)為數(shù)列{an}的通項(xiàng)，而 數(shù) 列{an}滿 足:a1＝0，a2＝1，an＝(n－1)·(an－2＋an－1)(n≥3).

由an＝(n－1)(an－2＋an－1)，得an－nan－1＝－[an－1－(n－1)an－2]，則{an＋1－(n＋1)an}是以a2－2a1＝1為首項(xiàng)，－1為公比的等比數(shù)列，則

4 有序子集對(duì)問題

例4已知集合M＝{1，2，…，5}，P，Q為M的兩個(gè)非空子集，若子集P的最小元素大于子集Q的最大元素，則有多少對(duì)有序子集對(duì)(P，Q)?

解析

設(shè)集合Mn＝{1，2，…，n}，對(duì)應(yīng)符合題設(shè)條件的有序子集對(duì)個(gè)數(shù)記作an，從集合Mn－1到Mn，我們只需要考慮多出的元素n，顯然元素n只能屬于子集P.

若元素n放入或不放入集合Mn－1對(duì)應(yīng)的子集P，都能保證集合Mn－1對(duì)應(yīng)的有序子集對(duì)(P，Q)滿足集合Mn，則有2an－1對(duì).

若元素n單獨(dú)構(gòu)成集合P＝{n}，則Mn－1的任一非空子集都可作為子集Q，構(gòu)成滿足集合Mn的有序子集對(duì)，有2n－1－1對(duì).

綜上，得到遞推關(guān)系式an＝2an－1＋2n－1－1(n≥2).易知a1＝0，a2＝1，經(jīng)計(jì)算得a5＝49，所以共有49對(duì)有序子集對(duì)(P，Q).

點(diǎn)評(píng)

若直接討論求解本題，情況較多，容易遺漏，且過程復(fù)雜，不易得到正確結(jié)果，而從子集元素個(gè)數(shù)的角度入手，抓住從集合Mn－1到Mn的變化情況，建立起相應(yīng)的遞推關(guān)系式，就可輕松解題.另外，由解答過程我們不難將問題拓展為一般模型.

模型4已知集合M＝{1，2，…，n}，P，Q為M的兩個(gè)非空子集，若子集P的最小元素大于子集Q的最 大 元 素，則 有(n－2)2n－1＋1對(duì) 有 序 子 集對(duì)(P，Q).

證明有序子集對(duì)(P，Q)的個(gè)數(shù)實(shí)為數(shù)列{an}的通項(xiàng)，而數(shù)列{an}滿足:a1＝0，an＝2an－1＋2n－1－1(n≥2).由an＝2an－1＋2n－1－1，得

5 傳球問題

例5三個(gè)人互相傳球，由甲開始發(fā)球，并作為第一次傳球，經(jīng)過5次傳球后，球仍回到甲手中，則有多少種不同的傳球方式?

解析

設(shè)第n次將球傳給甲的方式有an種，傳n次球共有2n種不同的傳法，在這2n種傳法中，有2n－an種傳法第n次不是傳給甲，而第n次沒有傳給甲時(shí)，在第n＋1次傳球時(shí)可傳給甲，故第n＋1次傳給甲的傳法為an＋1＝2n－an，易知a1＝0，經(jīng)計(jì)算得a5＝10，則經(jīng)過5次傳球后，球仍回到甲手中，有10種不同的傳球方式.

點(diǎn)評(píng)

該題也可直接列樹狀圖解答，但相對(duì)來說較為復(fù)雜，若增加傳球的次數(shù)，則樹狀圖更加繁雜，容易出錯(cuò)，而采用構(gòu)造遞推關(guān)系式表達(dá)傳球次數(shù)之間的聯(lián)系，則可簡化解題過程，由此可將問題拓展.

模型5m(m≥2)個(gè)人互相傳球，甲先發(fā)球，并作為第一次傳球，經(jīng)過n次(n≥2)傳球后，球仍回到甲手中，則共有種不同的傳球方式.

證明設(shè)第n次將球傳給甲的方式有an種，傳n次球共有(m－1)n種不同的傳法，在這(m－1)n種傳法中，有(m－1)n－an種傳法第n次不是傳給甲，而第n次沒有傳給甲時(shí)，在第n＋1次傳球時(shí)可傳給甲，故第n＋1次傳給甲的傳法為an＋1＝(m－1)nan，則

即

易知a1＝0，則數(shù)列為首項(xiàng)，為公比的等比數(shù)列，所以

即

通過以上五道例題，筆者介紹了構(gòu)造遞推關(guān)系式來解決五類計(jì)數(shù)問題，并在此基礎(chǔ)上將問題拓展到一般化模型，找到解題規(guī)律，簡化解題步驟.