Chauve, Cedric - A bijection between planar constellations and some colored Lagrangian trees

dmtcs:340 - Discrete Mathematics & Theoretical Computer Science, January 1, 2003, Vol. 6 no. 1
A bijection between planar constellations and some colored Lagrangian trees

Authors: Chauve, Cedric

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.

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]


Consultation statistics

This page has been seen 110 times.
This article's PDF has been downloaded 108 times.