Number of pathsin a grid with restrictions

Question

Please help, I am stuck with this example. Prove that the Catalan number $C_n$ equals the number of lattice paths from $(0,0)$ to $(2n, 0)$ using only upsteps $(1, 1)$ and downsteps $(1, -1)$ that never go above the horizontal axis (so there are as many up steps as there are downsteps). (These are sometimes called Dyck paths.) Thanks.

Answer 1

Note that these paths are the same as the lattice paths from $(0,0)$ to $(n,n)$ that stay below the diagonal line $\{(x,x) : x \in \mathbb{R} \}$. Let such paths be called "good paths" and let "bad paths" be lattice paths from $(0,0)$ to $(n,n)$ that cross the diagonal. Then

# good paths = # paths - # bad paths

The total number of lattice paths from $(0,0)$ to $(n,n)$ is $\dbinom{2n}{n}$ since we have to take $2n$ steps, and we have to choose when to take the $n$ steps to the right.

To count the total number of bad paths, we do the following: every bad path crosses the main diagonal, implying that it touches the diagonal just above it. Specifically, every bad path must touch the line $L = \{(x,x+1) : x \in \mathbb{R}\}$. Given a bad path, break it up into two portions: the portion before the first time the path touches $L$, and the portion after. If we reflect the first portion over the line $L$, then we have a lattice path from $(-1,1)$ to $(n,n)$. This gives a bijection between bad paths and lattice paths from $(-1,1)$ to $(n,n)$. Since there are $\dbinom{2n}{n+1}$ such lattice paths, there must be $\dbinom{2n}{n+1}$ bad paths.

Putting this all together yields $$\binom{2n}{n} - \binom{2n}{n-1} = C_n$$ total good paths.

Answer 2

The typical method for counting Dyck paths (that I know) goes as follows:

For every Dyck path $D$ from $(0,0)$ to $(2n,0)$, $D$ must begin with an upstep and eventually return to the x-axis with a downstep. Say $(2m,0)$ is the the first time $D$ returns to the x-axis. Then the sub-path of $D$ which goes from $(1,1)$ to $(2m-1,1)$ is a Dyck path (albeit shifted up) of length $m-1$, and the part of $D$ which goes from $(2m,0)$ to $(2n,0)$ is also a Dyck path (of length $n-m$).

Every Dyck path admits a unique decomposition in this way. That is, each Dyck path of length $n$ yields an ordered pair of Dyck paths, the first of length $m-1$ and the second of length $n-m$. Here, $m$ may be any positive integer less than or equal to $n$.

Too, every ordered pair of Dyck paths, the first of length $m-1$ and the second of length $n-m$ gives a unique Dyck path under the this construction.

So $$C_n=\sum_{m=1}^{n} C_{m-1}C_{n-m},$$ which gives the Catalan numbers.