2
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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$. $\endgroup$ – Elliot G Nov 3 '15 at 8:18
  • $\begingroup$ Have you looked at Wikipedia? $\endgroup$ – Ross Millikan Dec 18 '18 at 5:29
2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.