Question

如圖，人從格外只能進(jìn)入第一格，在格中每次可向前跳1格或2格，那么人從格外跳到第8格，可以有____________種不同方法.

1

2

3

4

5

6

7

8

  

   

Answer 1

這是一道較平常的排列組合問題，解法較多，一般從類似于下面思路去考慮：

    分析：第1格與第8格必選，故只有2、3、4、5、6、7格可省（省格不超過3，也不能連省2格）.

    每格必過的方案1種；

    省1格的方案6種；

    省2格的方案4+3+2+1=10種；

    省3格的方案3+1=4種；

    總共有1+6+10+4=21種.此法很難用于多格.

    下面再介紹兩種解法：

    法一：（插空法）從2、3、4、5、6、7格中，將“要省格”去插“不省格”留下的空，則有：

    每格必過（省0格）的方案

    ·|·|·|·|·|·|·（7個空）種；

    省1格的方案

    ·|·|·|·|·|· （6個空）種；

    省2格的方案

    ·|·|·|·|·  （5個空）種；

    省3格的方案

    ·|·|·|·   （4個空）種；

    總共有+++=21種.用此法很容易將此題推廣到n格，得到跳動法種數(shù)為+… (n為奇數(shù)時，末項是,n為偶數(shù)時，末項是).

法二：當(dāng)n≥3時，人到第n格只能是：①從第n-2格跳進(jìn)，②從第n-1格跳（走）進(jìn)兩種方式，那么人到第n格方法數(shù)為第n-2格方法數(shù)與第n-1格方法數(shù)之和：

人到第1格                    1種；

人到第2格                    1種；

人到第3格                    1+1=2種；

人到第4格                  1+2=3種；

人到第5格                  2+3=5種；

人到第6格                  3+5=8種；

人到第7格                  5+8=13種；

人到第8格                  8+13=21種；

由此可得到結(jié)論：人到第n格的方法數(shù)為斐波那契數(shù)列：1，1，2，3，5，8，13，21，34，……的第n項a_n.

數(shù)列{a_n}中,a₁=1,a₂=1,且a_n+2=a_n+1+a_n,

由特征方程r²=r+1，得r=,

a_n=()ⁿc₁+()ⁿc₂.

由

∴a_n=［(1+)ⁿ-(1-)ⁿ］(n∈N).

上述兩法不僅有“思維體操”美，也意外地得到了一個組合數(shù)恒等式:+……=［(1+)ⁿ-(1-)ⁿ］(n∈N).