Tree-Decorated Planar Maps

Abstract

We introduce the set of (non-spanning) tree-decorated planar maps, and show that they are in bijection with the Cartesian product between the set of trees and the set of maps with a simple boundary. As a consequence, we count the number of tree decorated triangulations and quadrangulations with a given number of faces and for a given size of the tree. Finally, we generalise the bijection to study other types of decorated planar maps and obtain explicit counting formulas for them.