in Mathematical Logic
408 views
1 vote
1 vote

How to solve this question?

in Mathematical Logic
408 views

4 Comments

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. 

0
0

@Aditya_ 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?

0
0

@Abhrajyoti00 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.

0
0

1 Answer

2 votes
2 votes
Best answer

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$

selected by
by

4 Comments

Thanks Man!
1
1

@Abhrajyoti00 Thanks to you I got to learn something new :)

1
1

@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

0
0

😂 I forgot to count properly my bad 

 
0
0

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true