2
$\begingroup$

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!

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

  • $\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.