214 views

How to solve this question?

Refer : https://gateoverflow.in/214618/counting
Number of paths from (0, 0) to (n, n) without crossing y = x line is given by nth catalan number.

But the answer is not 5. See their solution which I donβt think is wrong. Is there any technique to solve them or just manually like this?

Yeah answer is 10, I only considered number of paths below x = y line (for lower triangle). Same number of paths will also exists for upper triangle.

Number of paths from $(0, 0)$ to $(n,n)$ that does not go above $x=y$ line is also known as Dyck path.

The number of Dyck path from $(0, 0)$ to $(n, n)$ is Catalan number

$C_n$ = ${2n} \choose{n}$$* \frac{1}{n+1}$

Sourcehttps://www.math.toronto.edu/balazse/2019_Summer_MAT344/Lec_4.pdf

So for the above problem total number of path from $(0, 0)$ to $(n, n)$ is number of path that are below $x = y$ line + number of path that is above $x = y$ line
= $2 * C_3 = 2*5 = 10$

by

Thanks Man!

Thanks to you I got to learn something new :)

@Aditya_ Even Me :D Have been struggling since this morning and trying to point out the error in the prev link youv'e sent :P

π I forgot to count properly my bad

1 vote