Number of paths in a grid below a diagonal

Question

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)$.

Answer 1

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.