遞推思想在排列組合中的應用

韓文娟 霍忠林

利用遞推思想求解排列組合問題是一種解題思路，但對同學們的數學素養要求較高，是排列組合中的難點。如何借助分類加法計數原理和分步乘法計數原理找到遞推關系這是解題的關鍵點，下面通過六種題型來分析遞推思想在排列組合中的應用。

題型一、爬樓梯問題

例1 一段樓梯，有10個臺階，小明每次走一個或兩個臺階，則他有多少種不同的走法？

解析：問題一般化：一段樓梯，有n 個臺階，小明每次走一個或兩個臺階，則他有多少種不同的走法？

設小明走n 個臺階有an 種走法，則a1=1，a2=2。

思路一 按第一步走的臺階數分類

若第一步走一個臺階，則余下的n-1個臺階共有an-1 種走法。

若第一步走兩個臺階，則余下的n-2個臺階共有an-2 種走法。

所以an =an-1+an-2（n≥3）。

當n=10時，易得a10=89。

思路二 按最后一步走的臺階數分類

若最后一步走一個臺階，則前n-1個臺階共有an-1 種走法。

若最后一步走兩個臺階，則前n-2個臺階共有an-2 種走法。

所以an =an-1+an-2（n≥3）。

當n=10時，易得a10=89。

評析：“爬樓梯問題”本質上就是“斐波那契數列”，該數列是普通高中教材人教A 版《數學選擇性必修第二冊》第11頁、第12頁的內容。采用類似方法還可以處理下面變式。

變式1：一段樓梯，有5個臺階，小明每次走一個或兩個或三個臺階，則他有多少種不同的走法？

解析：該問題等價于：已知數列an =an-1+an-2+an-3（n≥4），其中a1=1，a2=2，a3=4，求a5 的值。過程略。

題型二、平面劃分問題

例2 3條直線最多能將平面分成幾部分？ 4條直線最多能將平面分成幾部分呢？

解析：問題一般化：n 條直線最多能將平面分成幾部分？……