兔子跳台阶 IV

Rabbit Hop IV

专题: Discrete Math / 离散数学
难度: L4
来源: QuantQuestion

个人笔记

题目详情

一只兔子从楼梯前的地面出发，要到达第 10 阶的顶端。

每次跳跃它可以向上跳任意多阶，但每次跳的阶数必须严格大于 1（即每次至少跳 2 阶）。

问：从地面到达第 10 阶顶端共有多少条不同路径？

英文原题

A rabbit starts at the floor in front of a staircase of $10$ stairs. The rabbit can hop up any amount of steps strictly larger than $1$ at each movement. In particular, this means that the rabbit can't go up a one stair staircase. How many distinct paths are there from the floor to the top of the staircase (i.e. to the top of the $10$ th stair)?

解析

令 $f(n)$ 表示到达第 $n$ 阶的路径数。

由于每次至少跳 2 阶，最后一步可能来自 $n-2,n-3,\dots,0$ ：

f(n)=\sum_{k=2}^{n} f(n-k)=f(n-2)+f(n-3)+\cdots+f(0),

并取 $f(0)=1$ （空路径）， $f(1)=0$ 。

由此可推出递推 $f(n)=f(n-1)+f(n-2)$ （ $n\ge 3$ ），且 $f(2)=1$ 。

于是 $f(n)$ 等于斐波那契数列的平移： $f(10)=F_9=34$ 。

所以答案为 $\boxed{34}$ 。

英文解析

Let $f(n)$ indicate the number of paths to level $n$ .

Since there are at least 2 steps at a time, the final step may come from $n-2,n-3,\dots,0$ :

f(n)=\sum_{k=2}^{n} f(n-k)=f(n-2)+f(n-3)+\cdots+f(0),

Also take $f(0)=1$ (empty path), $f(1)=0$ .

This results in a pushback of $f(n)=f(n-1)+f(n-2)$ ( $n\ge 3$ ) and $f(2)=1$ .

So $f(n)$ equals the translation of the Fibonacci sequence: $f(10)=F_9=34$ .

So the answer is $\boxed{34}$ .