A bijection for tree-rooted maps and some applications

A tree-rooted map is a planar map together with a

distinguished spanning tree. In the sixties, Mullin proved that the

number of tree-rooted maps with $n$ edges is the product $C_n C_{n+1}$

of two consecutive Catalan numbers. We will present a bijection

between tree-rooted maps (of size $n$) and pairs made of two trees (of

size $n$ and $n+1$ respectively) explaining this result.

Then, we will show that our bijection generalizes a correspondence by

Schaeffer between quandrangulations and so-called \emph{well labelled

trees}. We will also explain how this bijection can be used in order

to count bijectively several classes of planar maps