How many ways can a boy go up a staircase?

A staircase consists of 10 steps. A boy can move up to a maximum of 3
steps in each hop. How many different ways can he walk/run/jump the
staircase?

For a 5-step staircase, possible patterns are
(1-1-1-1-1),(1-1-1-2),(1-1-2-1),(1-1-3),(1-2-1-1),(1-2-2),(1-3-1),
(2-1-1-1),(2-1-2),(2-2-1),(2-3),(3-1-1),(3-2)
13 different patterns in total.

Let S be the number of steps in the staircase
and M be the maximum # of steps one can reach.
For the special case M = 1, # of ways = 1
For the special case M = S, # of ways = 2^(M-1) or 2^(S-1)
Is there a general method to solve this type of problem?

.

Relevant Pages
Quantcast