# Catalan Numbers: lattice paths with n+1 steps

I had this questions that I was having trouble with:

Show that $C_n$ counts the number of (unordered) pairs of lattice paths with n+1 steps each subject to the conditions:

i)starting at (0,0);

ii) using steps (1,0) or (0,1);

iii) ending at the same point, and;

iv) only intersecting at the beginning and end

My first instinct is usually start at one of the smaller Catalan Numbers such as n=3 (which we know to be 5). From there I tried to establish a bijection between this particular problem and another similar one (most of which can be found [here] http://en.wikipedia.org/wiki/Catalan_number). For example, the two I thought to be most similar were:

The number of lattice paths from the origin to (n,n), subject to the restrictions that a move can only be made to the right or up one step at a time and the path cannot cross the line y=x (touch is okay), is the $n^{th}$ Catalan number, $C_n$

or

The number of binary trees with n vertices

Both of which are illustrated on the wiki page (link above). Others include:

parentherization of n-pairs of parenthesis,

the number of sequences $a_1,a_2,...,a_{2n}$ of 1s and -1s such that every partial sum $a_1 + a_2 +...+ a_k$ is non-negative and $a_1 + a_2 +...+ a_k = 0$,

and the number of binary words consisting of n 1s and n 0s such that the number of 1s in each substring - starting from the far left to right - is greater than or equal to the number of 0s in the substring.

(I can provide examples of each if necessary...) However, I couldn't come up with a good bijection. Could someone help me out? Thank you in advance for your help, I really appreciate it! Because Catalan Numbers are abstract in nature, a good explanation of why your bijection works with $C_n$ and/or the lattice paths with n+1 steps and/or why a bijection can be formed between two things in order than the second thing can have a bijection between the lattice paths with n+1 steps would be greats appreciated!

The two paths enclose an array of unit squares forming a convex polyomino. (Note that in this context convex has a special meaning.) Say that the region has $m$ columns, with $c_k$ squares in column $k$. For $k=1,\ldots,m-1$ let $r_k$ be the number of rows shared by columns $k$ and $k+1$. The upper righthand corner is at the point $\langle m,n+1-m\rangle$.

The idea is to use these numbers to construct a Dyck path (mountain range) of length $2n$. It will have $m$ peaks, of heights $c_1,\ldots,c_m$ from left to right. For $k=1,\ldots,m-1$ the descent after peak $k$ will have length $c_k-r_k+1$, while the descent after peak $m$ will of course have length $c_m$. The valley between peak $k$ and peak $k+1$ will have height $c_k-(c_k-r_k+1)=r_k-1$, so the ascent from it to peak $k+1$ will have length $c_{k+1}-r_k+1$.

Now $c_{k+1}-r_k$ is the number of squares by which the top of column $k+1$ rises above the top of column $k$, so

$$c_1+\sum_{k=1}^{m-1}(c_{k+1}-r_k)+c_m$$

is the height above the baseline of the top of column $m$, which is $n+1-m$, and

$$c_1+\sum_{k=1}^{m-1}(c_{k+1}-r_k+1)+c_m=n+1-m+(m-1)=n\;,$$

as desired.

I leave it to you to check that the total descents is also $n$, that the path never drops below the baseline, and that the convex polyomino and hence the original two paths can be recovered from the Dyck path.

Let $E=(0,1)$, $N=(1,0)$, $U=(1,1)$, $D=(1,-1)$, and denote the upper and lower paths by $P_1$ and $P_2$, respectively. Note that $P_1=NP_1'E$ and $P_2=EP_2'N$ for some Dyck paths $P_1'$ and $P_2'$. Then map the columns of the biword $\dbinom{P_1}{P_2}$ of length $n+1$ as follows:

• for the first and last columns only: $$\binom{N}{E}\mapsto U, \qquad \binom{E}{N}\mapsto D;$$
• for the remaining ("middle") columns: $$\binom{N}{E}\mapsto UU, \qquad \binom{N}{N}\mapsto UD, \qquad \binom{E}{E}\mapsto DU, \qquad \binom{E}{N}\mapsto DD.$$

I will leave it to you to prove that this is indeed a bijection to Dyck paths of semilength $n$.