從遞推的視角看計(jì)數(shù)問題

岳躍朝

在高中數(shù)學(xué)計(jì)數(shù)原理這一章學(xué)習(xí)中，常常碰到一些諸如圓環(huán)區(qū)域染色，三人互相傳球，爬樓梯等有著遞推背景的計(jì)數(shù)問題。這是計(jì)數(shù)知識與數(shù)列知識的交匯點(diǎn)，如果從遞推的視角看待探究這類問題，解題思路給人豁然開朗的感覺。筆者將教學(xué)中常遇到此類問題及遞推視角的解題思路舉例如下，供大家教學(xué)和學(xué)習(xí)參考。

一、一階遞推關(guān)系的計(jì)數(shù)問題

例1：（圓環(huán)染色問題）如下圖1，2所示，圓環(huán)形花壇區(qū)域等分，種植紅、黃、藍(lán)、白四色不同的花，要求相鄰區(qū)域種植不同顏色的花，問共有多少中不同的種植方法？

解析：記對于n等分的圓形花壇，共有種種植方法，任意指定一塊區(qū)域作為第一塊開始染色，按順時(shí)針順序，則有n=2時(shí)，a2=4×3=12;n=3時(shí)，a3=4×3×2=24;n=4時(shí)情況要復(fù)雜，這時(shí)要區(qū)分第三塊區(qū)域顏色和第一塊區(qū)域顏色相同還是不同，根據(jù)分類加分計(jì)數(shù)原理，共有;當(dāng)n≥5時(shí)，按照上述思路，分類將會(huì)變得無比復(fù)雜。如果按照順時(shí)針染色，先只考慮和前方區(qū)域顏色不同，則有4×3n-1，但此時(shí)，第n塊區(qū)域的染色有兩種可能性：①與第一塊區(qū)域顏色相同;②與第一塊區(qū)域顏色不同。②恰是我們需要的an，而①時(shí)，我們將第n塊區(qū)域與第一塊區(qū)域看成同一塊區(qū)域，則此時(shí)的染色恰為an-1，因此，得到遞推公式。

由此遞推公式求通項(xiàng)公式，可采用正負(fù)號調(diào)節(jié)后的累加法：

累加

得

整理得。

例2：（三人傳球問題）三人相互傳球，由甲開始發(fā)球，并作為第一次傳球，經(jīng)過n次傳球后，球仍回到甲手中，則不同的傳球方式有多少種？

解析：如圖所示，列舉前3次所有的傳球方式：

記n次傳球后，球仍回到甲的傳球方式有an種，則有上述列舉圖可知：，且可以發(fā)現(xiàn)，n次傳球后，共有2n中傳球方式，第n次傳球后，球傳到甲手中的次數(shù)等于上一次中球不在甲手中的次數(shù)，由此，我們得到遞推公式，類似例1的方法，求得通項(xiàng)公式。

例3：（漢諾塔問題）如圖，有三根桿子A，B，C。A桿上有個(gè)穿孔圓盤，盤的尺寸由上到下依次變大。要求按如下規(guī)則將所有圓盤移至C桿：①可以借助B桿;②每次只移動(dòng)一個(gè)圓盤;③在移動(dòng)的過程中始終保持每個(gè)桿上的圓盤自上而下都是由小變大順利排列。問最少需要移動(dòng)多少次圓盤？

解析：記按要求將A桿上的盤子移至C桿上最少需要移動(dòng)an次盤子。顯然，當(dāng)n=1時(shí)，直接移過去，有a1=1;當(dāng)n=2時(shí)，先將上面盤子移至B桿，再將第二個(gè)盤子移至C桿，第三步將B桿上的盤子移至C桿，因此a2=3;當(dāng)n時(shí)，先將上面n-1個(gè)盤子移至B桿，需移動(dòng)an-1次，再將最下一個(gè)盤子移至C桿，需移動(dòng)1次，第三步將B桿上的n-1個(gè)盤子移至C桿，需移動(dòng)an-1次，因此得到遞推公式：。解得。（關(guān)于此問題更有意思的描述請參看科普名著《從一到無窮大》）

以上三個(gè)背景各不相同的計(jì)數(shù)問題從數(shù)學(xué)上看都是一階遞推關(guān)系的遞推問題，相似的還有如下參考題：

練習(xí)1：如圖，將n-棱錐S-A1A2…An（n≥3）的每一個(gè)頂點(diǎn)涂上一種顏色，并使同一條棱的兩端點(diǎn)異色，如果只有5中顏色可供使用，那么有多少種不同的涂色方法？

練習(xí)2：某情報(bào)站有A，B，C，D四種互不相同的密碼，每周使用其中的一種密碼，且每周都是從上周未使用的三種密碼中等可能地隨機(jī)選用一種。設(shè)第一周使用A種密碼，那么第n周也使用A種密碼的概率是______。

二、二階遞推關(guān)系的計(jì)數(shù)問題

例4：（爬樓梯問題）一樓樓梯共n（n≥1）級，每步可以向上跨1級或2級，問共有多少種上樓梯的方式？

解析：記跨完n級樓梯共有an種走法，如下我們分兩類來考慮此問題：①第一步跨了1級，則剩下的還有an-1種走法;②第一步跨了2級，則剩下的還有an-2種走法。由此我們得到二階遞推公式an=an-2+an-1。這是著名的斐波那契數(shù)列的遞推公式，這里a1=2，a2=2。由特征根法我們知道通項(xiàng)公式。

練習(xí)3：（貼瓷磚問題）定義一個(gè)瓷磚為一個(gè)1×2的矩形，如下圖。有多少種將瓷磚平鋪在一起得到n×2的矩形的方法？

例6：（錯(cuò)位排列問題）現(xiàn)將n個(gè)編號分別為的小球放入編號為的n個(gè)盒子中，要求每個(gè)盒子只放1個(gè)小球，則球號與盒號都不相同的放法共有多少種？

解析：記球號與盒號都不相同的放法共有an種。顯然，當(dāng)n=1時(shí)，a1=0;當(dāng)n=2時(shí)，a2=1;當(dāng)n≥3時(shí)，如下我們分兩類來考慮此問題：①1號球放入k（2≤k≤n）號盒子且k號球放入1號盒子時(shí)，由于k有n-1種變化，故共有（n-1）an-2種放法;②1號球放入k（2≤k≤n）號盒子且k號球不放入1號盒子時(shí)，此時(shí)問題歸結(jié)為將2，3，...，n號球放入號盒子，且k號球不放入1號盒子，由于k有n-1種變化，故共有（n-1）an-1種放法。因此，我們得到二階遞推公式。利用遞歸迭代方法求出an，推導(dǎo)如下：

令，則有，整理得，對于n≥2，我們有

再累加得，所以。

上述給大家列舉的幾個(gè)遞推問題，是高中數(shù)學(xué)教學(xué)中經(jīng)常遇到的經(jīng)典問題，集趣味性和思想性于一體，如果用計(jì)算機(jī)編程語言實(shí)現(xiàn)，則這些問題也就是計(jì)算機(jī)數(shù)據(jù)結(jié)構(gòu)算法中的典型案例。如能合理的滲透到高中數(shù)學(xué)教學(xué)中，相信必能促進(jìn)學(xué)生的數(shù)學(xué)學(xué)習(xí)的熱情和思維的發(fā)展，提升學(xué)生的數(shù)學(xué)核心素養(yǎng)。

參考文獻(xiàn)

[1]單墫、熊斌.多功能題典·高中數(shù)學(xué)競賽華.東師范大學(xué)出版社，2008年

[2]PaulZeitz.怎樣解題·數(shù)學(xué)競賽攻關(guān)寶典.人民郵電出版社，2010年

[3]伽莫夫.從一到無窮大·科學(xué)中的事實(shí)和臆測.科學(xué)出版社，2013年