Given there is a $n\times n$ square grid . I was trying to calculate the number of paths from $(0,0)$ to $(n,n)$ under the condition that one might move either up or to the right one step at a time. Also there is an additional restriction that one has to travel below the diagonal joining the square at all times. One can be on point $(i,i)$ but not on $(i,i+1)$.
$\begingroup$
$\endgroup$
2
-
2$\begingroup$ Catalan numbers? $\endgroup$– Angina SengCommented Feb 3, 2018 at 7:31
-
$\begingroup$ You are a regular user so please consider using mathjax. I edited the post for you. $\endgroup$– Gaurang TandonCommented Feb 3, 2018 at 7:37
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
We know that there are $\binom{2n}{n}$ ways of going $(n,n)$ from $(0,0)$ when there is no restriction. So the answer should be $\binom{2n}{n}-B$ where $B$ is the number of "bad paths", that is, number of paths that go above the diagonal line.
Now, in order to calculate $B$, we should notice something: When we go above the diagonal line, we will pass through another diagonal line, which is shown as $\color{red}{red}$ in the figure. And for each bad path (passes through the red line), let us create a new path which has the same moves until we go above the diagonal line (or pass through the red line), and then does the symmetric moves to our original path (original path is shown as $\color{blue}{blue}$, symmetric moves are shown in $\color{lime}{green}$). Therefore, number of bad paths become the number of paths from $(0,0)$ to $(n-1,n+1)$, which means $B = \binom{2n}{n+1}$. So the answer becomes $$\binom{2n}{n}-\binom{2n}{n-1}$$ which is also called the $n^{th}$ Catalan Number.
