##### 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?

There are 5 floating stones so total 6 steps are required to cross the river.

= 1 way6 moves each of 1 step4 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 stepsIf 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

= 1 waymoves each of 2 stepHence total number of ways to cross the river = 1 + 5 + 6 + 1 = 13 ways.

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

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