A flight of stairs has 19 steps...?

Question

A man can go up the stairs one at a time, two at a time, three at a time, or any combination of ones, twos or threes. In how many ways can the man go up the stairs? And yes, order matters.

boy you're never going to get 10 points SPLATT with that attitude...

boy i thought someone would try this one.....

check your program Michael M

somethings amiss with your analysis michael.. the number of ways should always increase with the number of steps. 1 way for 19 steps?

Michael M your algorithm is missing some I think.....

Answer 1

Define N_k as the number of ways this gentleman can climb k stairs.

N_1 = 1 (1)
N_2 = 2 (11,2)
N_3 = 4 (111,12,21,3)

For a staircase with more than 3 steps, if the first step is 1,2 or 3, the total number of ways of climbing the remaining stairs is N_(k-1), N_(k-2), and N_(k-3) respectively. That is:

N_k = N_(k-1) + N_(k-2) + N_(k-3)

So starting with 1,2,4 and adding the last three numbers to get each succeeding number:

1 (N_1)
2
4
7
13
24
44
81
149
274
504
927
1705
3136
5768
10609
19513
35890
66012 (N_19)

--> The answer appears to be 66012 if I haven't made any mistakes. It's probably possible to come up with a formula to solve the recusion relation but it isn't necessary in this case.

Answer 2

According to the computer program I just wrote, there are 65494 ways.

19 foot moves = 1 way
18 foot moves = 18 ways
17 foot moves = 153 ways
16 foot moves = 800 ways
15 foot moves = 2835 ways
14 foot moves = 7098 ways
13 foot moves = 12727 ways
12 foot moves = 16236 ways
11 foot moves = 14355 ways
10 foot moves = 8224 ways
9 foot moves =2515 ways
8 foot moves = 504 ways
7 foot moves = 28 ways
6 - 1 foot moves = 0 ways

Total = 65494

Answer 3

Work in reverse.

If he had to go up 1 step, there would be one way (1)

If he had to go up 2 steps, there would be two ways (2, 11)

If he had to go up 3 steps, there woud be four ways (3, 21, 12, 111).

Now finish the problem yourself.

Answer 4

Only 1 way, up! Derrrrrr!