The number of non-crossing matchings of sides of $2n$-gon (i.e. the number of ways to connect sides pairwise by non-intersecting paths) is $n$’th Catalan number, $\text{Cat}_n$.

How to prove combinatorially that $(n+2)\text{Cat}_{n+1}=(4n+2)\text{Cat}_n$ for this interpretation of Catalan numbers?

For example, proof of this recurrence for triangulations of $(n+2)$-gon is described in Wikipedia: after choosing a side of $(n+3)$-gon and contracting corresp. triangle we get an $(n+2)$-gon with one (marked and) oriented edge — I want something like this.

In principle, triangulations and non-crossing matchings are connected by a chain of bijections (e.g. matchings $\leftrightarrow$ balanced parentheses $\leftrightarrow$ binary trees $\leftrightarrow$ triangulations) and one can try to transfer the description from the previous paragraph via this chain. But this way quickly becomes too convoluted (for me, at least).


(It will be slightly more convenient to use the language of non-crossing matchings of points on a line aka balanced parentheses.)

Let's call () (i.e. a pair of adjacent elements that are paired in the matching) a leaf. Each non-crossing matching has at least one leaf. To get the recurrence relation Let's count the number of non-crossing matchings of $2(n+1)$ elements with a marked leaf.

Example ($n=2$, leaves are red). $((\color{red}{()}))$, $\color{red}{()}\color{red}{()}\color{red}{()}$, $(\color{red}{()}\color{red}{()})$, $(\color{red}{()})\color{red}{()}$, $\color{red}{()}(\color{red}{()})$,

On one hand, there are $(2n+1)Cat_n$ such 'decorated' matchings (just throw away the marked leaf). On other hand, to get a decorated matching we just need to choose a leaf in one of $Cat_{n+1}$ matchings.

Lemma. On average an nc-matching of $2(n+1)$ elements has $(n+2)/2$ leaves.

(So once Lemma is proven we have $(2n+1)Cat_n=\frac{(n+2)}2Cat_{n+1}$, qed.)

To prove Lemma define an involution on nc-matchings by the rule $\overline{(\alpha)\beta}=(\overline\beta)\overline\alpha$. So, for example, $\overline{((()))}=()()()$, $\overline{()(())}=(()())$ (and vice versa), $\overline{(())()}=(())()$. Now observe that if $\sigma$ has $k$ leaves, $\overline\sigma$ has $n+2-k$ leaves, so we're done.

  • $\begingroup$ Understanding is its own reward. $\endgroup$
    – Grigory M
    Jun 20 '15 at 17:26

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.