A stairway has 7 steps. John always walk up the stairs by taking either 1 step or 2 steps or 3 steps at a time. How many ways can he walk up the stairs?
The solution looks like this. (It might be wrong cos i vaguely remember it to be like this only)
Suppose only 1 step, there will only be 1 way.
Suppose there are 2 steps, there will be 2 ways to go up.
Suppose there are 3 steps, there will be 4 ways to go up. {1,1,1}{1,2}{2,1}{3}
Suppose there are 4 steps, there will be 1 + 2 + 4 = 7 ways to go up.
Suppose there are 5 steps, there will be 2 + 4 + 7 = 13 ways
Suppose there are 6 steps, there will be 4 + 7 + 13 = 24 ways.
Suppose there are 7 steps, there will be 7 + 13 + 24 = 44 ways.
Answer: 44 ways.
My friend told me this is the advanced fibonacci sequence whereby you add 3 terms instead of 2 terms.
Can someone check if there is any mistake and what is the real formula called? And explain to me the rationale of adding previous 3 terms?
Thanks in advance again.
1111111 ==> 1 way
111112 ==> 6 ways
11122 ==> ? ways
1222 ==> 4 ways
11113 ==> 5 ways
133 ==> 3 ways
1123 ==> ? ways
223 ==> 3 ways
Originally posted by skythewood:1111111 ==> 1 way
111112 ==> 6 ways
11122 ==> ? ways
1222 ==> 4 ways11113 ==> 5 ways
133 ==> 3 ways1123 ==> ? ways
223 ==> 3 ways
11122 => 5!/2!3! = 10 ways
1123 = > 4!/2! = 12 ways
total = 44ways.
Thanks for your input and method.
Originally posted by HyuugaNeji:11122 => 5!/2!3! = 10 ways
1123 = > 4!/2! = 12 ways
total = 44ways.
yup. that's the way i will advise sec sch student to approach bah... down to earth, step by step...
unless you are going to find a very big number of steps, than find the pattern....
fibonacci goes like this... 1,1,2,3,5,8,13,21,34....
i know why liao. So stupid. Only now then i understand the logic.
For steps more than 4, You can assume John take can make any of the 3 moves: 1 step, 2 steps and 3 steps.
If he take 1 step in the first move, then you just need to count for the remaining 3 steps.
If he take 2 steps in the first move, then you just need to count for the remaining 2 steps.
If he takes 3 steps in the first move, then you just need to count for the remaining 1 step.
Then you can just repeat them again.