A bijection between planar constellations and some colored Lagrangian trees

Abstract : 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.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2003, 6 (1), pp.13-40
Liste complète des métadonnées

Littérature citée [24 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00958985
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : jeudi 13 mars 2014 - 16:58:28
Dernière modification le : mercredi 29 novembre 2017 - 10:26:22
Document(s) archivé(s) le : vendredi 13 juin 2014 - 12:08:22

Fichier

dm060102.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00958985, version 1

Collections

Citation

Cedric Chauve. A bijection between planar constellations and some colored Lagrangian trees. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2003, 6 (1), pp.13-40. 〈hal-00958985〉

Partager

Métriques

Consultations de la notice

61

Téléchargements de fichiers

177