Number of pathsin a grid with restrictions 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.
 A: 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.
A: 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.
