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!
Best Answer
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.