從遞推的視角看計數問題

岳躍朝

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

一、一階遞推關系的計數問題

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

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

由此遞推公式求通項公式，可采用正負號調節后的累加法：

累加

得

整理得。

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

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

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

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

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

以上三個背景各不相同的計數問題從數學上看都是一階遞推關系的遞推問題，相似的還有如下參考題：

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

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

二、二階遞推關系的計數問題

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

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

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

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

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

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

再累加得，所以。

上述給大家列舉的幾個遞推問題，是高中數學教學中經常遇到的經典問題，集趣味性和思想性于一體，如果用計算機編程語言實現，則這些問題也就是計算機數據結構算法中的典型案例。如能合理的滲透到高中數學教學中，相信必能促進學生的數學學習的熱情和思維的發展，提升學生的數學核心素養。

參考文獻

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

[2]PaulZeitz.怎樣解題·數學競賽攻關寶典.人民郵電出版社，2010年

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