Luke the cat likes jumping on steps. One day, Luke the cat finds a bowl of its favourite food, salmon, in a bowl on top of a flight of 1 2 steps. However, Luke the cat is tired and hungry and can only jump up 1 or 2 steps at a time. How many ways are there for it to get to the bowl of salmon?
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
Nice recurrence involved with Fibonacci :D. I would like you latex your solutions, its very dificult to read
fibonacci series lol
12 STEPS (T = 2 STEPS, O = 1 STEP)
12O -> 1
1T+10O = (10+1)! / 10! 1! = 11
2T+8O = (2+8)!/2! 8! = 45
3T+6O = (3+6)!/ 3! 6! = 84
4T+ 4O = (4+4)!/ 4! 4! = 70
5T+2O = (5+2)!/ 5! 2! = 21
6T -> 1
TOTAL = 1+11+45+84+70+21 = 233
It's actually simple to calculate it by recurrence. If we call f ( n ) the number of ways the cat can get the bowl, and since there's just 2 different ways of it starts doing it, we have:
i) Either the cat jumps 1 step at a time, reaching the first step; and the cat has now f ( n − 1 ) ways of getting the bowl.
ii) Or the cat jumps 2 steps at a time, reaching the second step; and the cat has now f ( n − 2 ) ways of getting the bowl.
So we have: f ( n ) = f ( n − 1 ) + f ( n − 2 )
We can easily calculate it by knowing that f ( 1 ) = 1 (if there's just one step, then there's just one way to gettong the bowl: by jumping just 1 step) and f ( 2 ) = 2 (if there's just two steps, then there's two ways to getting the bowl: either jumping 1 step at a time or jumping 2 steps at a time, reaching the bowl).
Therefore:
f ( 1 ) = 1
f ( 2 ) = 2
f ( 3 ) = 1 + 2 = 3
f ( 4 ) = 2 + 3 = 5
f ( 5 ) = 3 + 5 = 8
f ( 6 ) = 5 + 8 = 1 3
f ( 7 ) = 8 + 1 3 = 2 1
f ( 8 ) = 1 3 + 2 1 = 3 4
f ( 9 ) = 2 1 + 3 4 = 5 5
f ( 1 0 ) = 3 4 + 5 5 = 8 9
f ( 1 1 ) = 5 5 + 8 9 = 1 4 4
f ( 1 2 ) = 8 9 + 1 4 4 = 2 3 3
Problem Loading...
Note Loading...
Set Loading...
Yay Im a cat~ Anyways to find the number of ways: Number of ways when there are 6 "2"s and 0 "1"s: 6!/6!=1 Number of ways when there are 5 "2"s and 2 "1"s: (5+2)!/(5!x2!)=21 Number of ways when there are 4 "2"s and 4 "1"s: (4+4)!/(4!x4!)=70 ............. Number of ways when there are 0 "2"s and 12 "1"s: 12!/12!=1 Therefore the total number of ways: 1+21+70+84+45+11+1=233