# 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.

• If I were you I would try out the first several values of $n$ and see how they form the Catalan numbers, then try to understand and prove the relation $C_n=C_0C_{n-1}+C_1C_{n-2}+\cdots+C_{n-1}C_0$. – Elliot G Nov 3 '15 at 8:18
• Have you looked at Wikipedia? – Ross Millikan Dec 18 '18 at 5:29

## 2 Answers

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.

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.