Recurrence $(n+2)\text{Cat}_{n+1}=(4n+2)\text{Cat}_n$ for non-crossing matchings 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).
 A: (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.
