Bijective counting of tree-rooted maps and shuffles of parenthesis systems (Q870065): Difference between revisions

Summary: The number of tree-rooted maps, that is, rooted planar maps with a distinguished spanning tree, of size \(n\) is \({\mathcal C}_n {\mathcal C}_{n+1}\) where \({\mathcal C}_n=\frac{1}{n+1}\binom 2n\) is the \(n\)th Catalan number. We present a (long awaited) simple bijection which explains this result. Then, we prove that our bijection is isomorphic to a former recursive construction on shuffles of parenthesis systems due to \textit{R. Cori, S. Dulucq} and \textit{G. Viennot} [J. Comb. Theory, Ser. A 13, 1--22 (1986; Zbl 0662.05004)].