Skip to Main content Skip to Navigation
Journal articles

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.
Document type :
Journal articles
Complete list of metadata

Cited literature [24 references]  Display  Hide  Download

https://hal.inria.fr/hal-00958985
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Submitted on : Thursday, March 13, 2014 - 4:58:28 PM
Last modification on : Tuesday, October 6, 2020 - 10:56:02 AM
Long-term archiving on: : Friday, June 13, 2014 - 12:08:22 PM

File

dm060102.pdf
Files produced by the author(s)

Identifiers

  • 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⟩

Share

Metrics

Record views

132

Files downloads

818