Bijective Counting of Tree-Rooted Maps and Shuffles of Parenthesis Systems

Abstract

The number of tree-rooted maps, that is, rooted planar maps with a distinguished spanning tree, of size $n$ is ${\cal C}_{n} {\cal C}_{n+1}$ where ${\cal C}_{n}={1\over n+1}{2n \choose n}$ 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 Cori, Dulucq and Viennot.