1
$\begingroup$

The Wikipedia article on Catalan numbers lists various combinatorial objects that are described by them. I posit that there might be bijections between these various combinatorial objects. For some of them (like Dyck paths, correctly matched parentheses and paths from the bottom left to top right of a $2n \times 2n$ grid) they are quite obvious.

I was then trying to find a bijection between the number of Dyck words and the number of ways of associating $n$ applications of a binary operator to $n+1$ items (third one on the list). I attempted to do this for a simple case ($n=3$ which is the example provided in the Wikipedia article). However, couldn't find one after multiple hours. Is it reasonable to expect such a bijection will exist? If so, how do we go about finding it?


EDIT: In addition to the very nice answer by @Marc, the following page also helped me see the bijection: http://math.sfsu.edu/federico/Clase/EC/Homework/3.3.Jorge.pdf

"Let $P$ be the Dyck path and $f(P)$ be the binary tree. If you go up in the Dyck path, create a left child. Otherwise, go up one vertex until creating a new right child is possible and create one."


Here is one of my attempts:

Number of Dyck words with length $2 \times 3$ is $\frac{6 \choose 3}{4} = 5$. They are:

hhhttt; hhthtt; hhttht; hthhtt; hththt

And the number of applications of a binary operator among $3+1=4$ factors is:

((ab)c)d; (a(bc))d; (ab)(cd); a((bc)d); a(b(cd))

Both combinatorial objects have been arranged in a way that there is some kind of ordering between them. For the Dyck words for example, if h equals +1 and t equals -1, then the order is lexicographical from the left to the right of the cumulative score along the sequence.

Now, the first and last characters of the Dyck words are always h and t respectively. So, we can ignore them. We are left with:

hhtt; htht; htth; thht; thth

I tried to start from the left of the sequence abcd and if I see 'h', merge the character with the one to its right. This approach didn't produce a valid mapping from the third Dyck word to the third binary operator precedence order.

$\endgroup$
4
$\begingroup$

Yes this one is well known. Often for finding a bijection it suffices to compare the reasons why the two interpretations satisfy the fundamental recurrence $C_{n+1}=\sum_{i=0}^nC_i\,C_{n-i}$ for Catalan numbers. For $n+1$-leaf binary trees, which is what combining $n+1$ atoms using $n$ applications of a binary operator amounts to, this is quite clear: for $C_{n+1}$ one is looking at trees with $n+1$ internal nodes one of which is the root; if it has a left subtree with $i$ internal nodes its right subtree has $n-i$ internal nodes, and the value of $i$ together with the choice of such subtrees determines the tree. For $2n$-step Dyck paths it is slightly less natural since an asymmetric choice is necessary to decompose a path in sub-paths. Still there is a fairly obvious way to do this: the first step of a $2(n+1)$ step path is always an up-step (opening parenthesis), and there is a unique matching down-step (closing parenthesis) where we first re-descend to level$~0$. Then there are $2i$ steps in between them that form a Dyck path, and $2(n-i)$ steps left after the matching down-step, for some $0\leq i\leq n$. Repeating this decomposition constructs a binary tree associated to a Dyck path. For instance with $n=3$ and the path corresponding to $(())()$ one finds $i=1$ (the first descent to level$~0$ is at step$~4$) and the unique binary tree with $4$ leaves and the root in the middle: $(a*b)*(c*d)$. Note that the left-right symmetry is not preserved. Here are all $5$ cases with $n=3$: $$ \matrix{(~)~(~)~(~) & (~)~(~(~)~)~&(~(~)~)~(~) & (~(~)~(~)~)&(~(~(~)~)~)\\ a*(b*(c*d))&a*((b*c)*d) &(a*b)*(c*d) & (a*(b*c))*d & ((a*b)*c)*d} $$

Here is a maybe somewhat easier to see way to state this correspondence. First write the binary tree expression using symbols '[', '$*$', ']' together with atoms, so that each '$*$' has a pair '[' and ']' that surrounds its own operands, so for instance $a*((b*c)*d)$ becomes $[~a*[~[~b*c~]*d~]~]$ (note the outer brackets). Then substitute '(' for '[', and ')' for '$*$', and drop both the atoms and the symbols ']', to get a balanced list of parentheses, in the example $(.)((.)..)...$ where the dots mark positions where symbols were dropped.

$\endgroup$
  • $\begingroup$ Sorry, I've been reading through this since yesterday and am still having a very hard time mapping the Dyck paths to the trees (or seeing why they should satisfy the recurrence). First, You mention (())() corresponds to $i=1$. However, it descends to $0$ at step 4. Shouldn't $i$ equal $2$? Also, why should Dyck paths satisfy $C_{n+1}=\sum\limits_{I=0}^nC_iC_{n-i}$ and not (for instance) $C_{n+1} = \sum_i \sum_j C_i C_j C_{n-i-j}$? $\endgroup$ – Rohit Pandey Jan 6 at 6:06
  • 1
    $\begingroup$ First point, when I said "between", I meant excluding the matching parentheses themselves (which I think is what the word it usually taken to mean). So with an upstep at position $1$ and a downstep at position $4$, there are $2$ steps in between, so $i=1$. This interpretation is necessary, since one wants $i=0$ to be possible (and $i=n$ is also possible as nothing has to follow the downstep). Second, you only get a decomposition with just two subpaths, since only one pair of matching parentheses is obligatory (taking the leftmost parenthesis as opening one of the pair). $\endgroup$ – Marc van Leeuwen Jan 6 at 7:43
  • 1
    $\begingroup$ By the way, one could instead start with the very rightmost downstep and search for the matching upstep; that gives a different (but just as good) correspondence. This is the reason I said this part is somewhat less natural than the binary tree part. $\endgroup$ – Marc van Leeuwen Jan 6 at 7:45

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.