Number of ways in which a man can cross the river | Permutation and Combination

There are 5 floating stones on a river. A man wants to cross the river. He can move either 1 or 2 steps at a time. Find the number of ways in which he can cross the river?

3Comments
Sumit Verma @sumitkgp
18 Apr 2017 01:11 pm

There are 5 floating stones so total 6 steps are required to cross the river.
6 moves each of 1 step = 1 way
4 moves each of 1 step + 1 move of 2 step :
Here move of 2 step can be at the start or after 1 st stone or after 2nd stone or after 3rd stone or after 4th stone. Total ways = 5
2 moves each of 1 step + 2 moves each of 2 steps:
If 1st move of 2 steps is in start, 2nd move of 2 steps can be at 2nd stone or 3rd stone or 4th stone = 3 ways
if 1st move of 2 steps is after 1st stone, 2nd move of 2 steps can be at 3rd or 4th stone = 2 ways
if 1st move of 2 stepd is after 2nd stone then 2nd move of 2 steps will be after 4th stone. = 1 way
Total = 6 ways
​3 moves each of 2 step = 1 way
Hence total number of ways to cross the river = 1 + 5 + 6 + 1 = 13 ways.

Parth Sharma @parthsharmau
23 Apr 2017 03:44 pm

Lets do this another way 

For 1 stone only 2 steps are needed 

Ways are either 1,1 or 2 step at a time.

For 2 stone 3 steps are needed ways are   1,1,1 or 2,1 or 1,2  that is 3 ways 

For 3 stone 4 steps are needed  nd ways are 1,1,1,1 or 1 ,1,2 or 1,2,1 or 2,1,1 or 2,2  that is 5 ways

For 4 stones 5 steps are    needed  d ways are 1,1,1 ,1,1 or 1,1,1 2  or 1,1,2 ,1 or 1,2,1,1 or 2,1,1 1 or 2,2 ,1 or 2,1,2 or 1,2 ,2  8 ways 

If u can see  o. Of ways form fibonicci series 2,3,5,8 and then 5+8 = 13 ways 

Noufal @muhammednoufalk
5 Aug 2018 06:40 am
Hint: Use recurrence.

Here points are 0, 1, 2, 3, 4, 5, 6 where 0 is the place where man stands at beginning, 6 is the place where man want to reach.

Number of ways to reach location 1, T(1) = 1
Number of ways to reach location 2, T(2) = 2
Number of ways to reach location 3, T(3) = 3
Number of ways to reach location 4, T(4) = 5
Number of ways to reach location 5, T(5) = 8

Recurrence here is, T(N) = T(N-1) + T(N-2)
and base conditions are,
T(2) = 2 , T(1) = 1

The answer,
Number of ways to reach location 6, T(6) = T(5)+T(4) = 8 + 5 = 13

What if frog can jump at max 3 steps in a single jump?
T(N) = T(N-1) + T(N-2) + T(N-3)
Base conditions,
T(1) = 1, T(2) = 2, T(3) = 4