The one with the Triangular grid.

Probability Level 3

Find the number of ways from ( 0 , 0 ) (0,0) to ( 8 , 8 ) (8,8) in the right angled isosceles triangle forming the sides:

1 ) ( 0 , 0 ) 1) \quad(0,0) to ( 8 , 0 ) (8,0) ,
2 ) ( 8 , 0 ) 2) \quad(8,0) to ( 8 , 8 ) (8,8) ,
3 ) ( 0 , 0 ) 3) \quad(0,0) to ( 8 , 8 ) (8,8) .

You can only go in positive vertical or horizontal directions(only integer co-ordinates). Diagonals are not allowed.

Bonus : Try to find the number of ways for a general case like ( 0 , 0 ) (0,0) to ( m , m ) (m,m) .

1460 12870 1608 1430

Saarthak Marathe by Saarthak Marathe , 22, India

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.

1 solution

Saarthak Marathe
Dec 4, 2015

These kind of paths are represented by Catalan numbers,

The n t h {n}^{th} Catalan number gives the number of ways to go from ( 0 , 0 ) t o ( n , n ) (0,0) to (n,n) in an isosceles right angled triangle.

It is given by, C n = 1 n + 1 . ( 2 n n ) { C }_{ n }=\frac { 1 }{ n+1 } .\binom{2n}{n}

Try to prove it!! I will post the proof if you don't get it.

Then for n = 8 n=8 ,

C n = 1430 {C}_{n}=1430

0 Helpful 0 Interesting 0 Brilliant 0 Confused

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...