Constellations are colored planar maps that generalize different families of maps (planar maps, bipartite planar maps, bi-Eulerian planar maps, planar cacti, ...) and are strongly related to factorizations of permutations. They were recently studied by Bousquet-Mélou and Schaeffer who describe a correspondence between these maps and a family of trees, called Eulerian trees. In this paper, we derive from their result a relationship between planar constellations and another family of trees, called stellar trees. This correspondence generalizes a well known result for planar cacti, and shows that planar constellations are colored Lagrangian objects (that is objects that can be enumerated by the Good-Lagrange formula). We then deduce from this result a new formula for the number of planar constellations having a given face distribution, different from the formula one can derive from the results of Bousquet-Mélou and Schaeffer, along with systems of functional equations for the generating functions of bipartite and bi-Eulerian planar maps enumerated according to the partition of faces and vertices.

Source : oai:HAL:hal-00958985v1

Volume: Vol. 6 no. 1

Published on: January 1, 2003

Submitted on: March 26, 2015

Keywords: Planar maps,trees,enumeration,bijection,Lagrange formula,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

This page has been seen 110 times.

This article's PDF has been downloaded 108 times.