Answer

问题及解答

[Ex.6.6-6]

Posted by haifeng on 2019-05-24 16:44:15 last update 2019-05-24 17:51:18 | Edit | Answers (1)

某人上一共有 $n$ 级台阶的楼梯. 如果规定他每步只能上一级台阶或三级台阶, 问有多少种不同的上楼梯方法?

 

记号:

$f(n)$ 指对于 $n$ 级台阶上楼梯的方案总数.


[分析]

当 $n=6$ 时, 上楼梯的方案有 $f(6)=6$ 种:

  • 1,1,1,1,1,1
  • 1,1,1,3
  • 1,1,3,1
  • 1,3,1,1
  • 3,1,1,1
  • 3,3

当 $n=5$ 时, 上楼梯的方案有以下 $f(5)=4$ 种:

  • 1,1,1,1,1
  • 1,1,3
  • 1,3,1
  • 3,1,1

当 $n=4$ 时, 上楼梯的方案有以下 $f(4)=3$ 种:

  • 1,1,1,1
  • 1,3
  • 3,1

当 $n=3$ 时, 上楼梯的方案有以下 $f(3)=2$ 种:

  • 1,1,1
  • 3

 

因此, 一种办法是可以按有几个3来分类.

例如: 当 $n=7$ 时, $n\equiv 1\pmod 3$, 此时 $[\frac{n}{3}]=[\frac{7}{3}]=2$.

  • 0个3, 有 1 种. ($11\ldots1$)
  • 1个3, 有 $C_5^1$ 种. (31111, 13111, 11311, 11131, 11113)
  • 2个3, 有 $C_3^1$ 种. (331, 313, 133)

故 $f(7)=1+C_5^1+C_3^1=9$.


当 $n=8$ 时, $n\equiv 2\pmod 3$, 此时 $[\frac{n}{3}]=[\frac{8}{3}]=2$.

  • 0个3, 有 1 种. ($11\ldots1$)
  • 1个3, 有 $C_6^1$ 种.
  • 2个3, 有 $C_3^1+C_3^2$ 种. (将 33 放到 []1[]1[] 中, 分两种情形, 33 不分离, 33 分离)

故 $f(8)=1+C_6^1+(C_3^1+C_3^2)=13$.


当 $n=9$ 时, $n\equiv 0\pmod 3$, 此时 $[\frac{n}{3}]=[\frac{9}{3}]=3$.

  • 0个3, 有 1 种. ($11\ldots1$)
  • 1个3, 有 $C_7^1$ 种.
  • 2个3, 有 $C_4^1+C_4^2$ 种. (将 33 放到 []1[]1[]1[] 中, 分两种情形, 33 不分离, 33 分离)
  • 3个3, 有 1 种.

故 $f(9)=1+C_7^1+(C_4^1+C_4^2)+1=19$.


当 $n=10$ 时, $n\equiv 1\pmod 3$, 此时 $[\frac{n}{3}]=[\frac{10}{3}]=3$.

  • 0个3, 有 1 种. ($11\ldots1$)
  • 1个3, 有 $C_8^1$ 种.
  • 2个3, 有 $C_5^1+C_5^2$ 种. (将 33 放到 []1[]1[]1[]1[] 中, 分两种情形, 33 不分离, 33 分离)
  • 3个3, 有 $C_4^1$ 种.

故 $f(10)=1+C_8^1+(C_5^1+C_5^2)+1=28$.


一般的, 记 $[\frac{n}{3}]=k$, $n\equiv r\pmod 3$. 于是,

  • 0个3, 有 1 种. ($11\ldots1$, $n$ 个 1.)
  • 1个3, 有 $C_{n-2}^1$ 种.
  • 2个3, 有 $C_{n-6+1}^1+C_{n-6+1}^2$ 种. (将 33 放到 []1[]1[]...[]1[] 中, 分两种情形, 33 不分离, 33 分离)
  • $j$个3, 则剩余 $n-3j$ 个 1. 但是这种分析会比较复杂. 还要分 $j$ 是奇数和偶数的情形.

 

因此, 可以从另一个角度来考虑这个问题. 比如, 能否写出递推关系?

 

通过上面的计算,  我们得到前若干个 $f(n)$:

\[
1,1,2,3,4,6,9,13,19,28,\ldots
\]

因此, 猜测有

\[
f(n)=f(n-1)+f(n-3),\quad n\geqslant 4.
\]

试证明之.

1

Posted by haifeng on 2019-05-24 17:53:11

证明其实非常简单.

设有 $n$ 个台阶, 第一步如果跨出 1 个台阶, 则有 $f(n-1)$ 种可能, 如果跨出 3 个台阶, 则有 $f(n-3)$ 种可能.

因此 $f(n)=f(n-1)+f(n-3)$.