A bijection between planar constellations and some colored Lagrangian trees
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...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2003-06-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Online Access: | http://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/174 |
| _version_ | 1818514556168699904 |
|---|---|
| author | Cedric Chauve |
| author_facet | Cedric Chauve |
| author_sort | Cedric Chauve |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-12-11T00:17:25Z |
| format | Article |
| id | doaj.art-e9c3e794cb88452c8808154499c1ba89 |
| institution | Directory Open Access Journal |
| issn | 1462-7264 1365-8050 |
| language | English |
| last_indexed | 2024-12-11T00:17:25Z |
| publishDate | 2003-06-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-e9c3e794cb88452c8808154499c1ba892022-12-22T01:27:54ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1462-72641365-80502003-06-0161A bijection between planar constellations and some colored Lagrangian treesCedric ChauveConstellations 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.http://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/174 |
| spellingShingle | Cedric Chauve A bijection between planar constellations and some colored Lagrangian trees Discrete Mathematics & Theoretical Computer Science |
| title | A bijection between planar constellations and some colored Lagrangian trees |
| title_full | A bijection between planar constellations and some colored Lagrangian trees |
| title_fullStr | A bijection between planar constellations and some colored Lagrangian trees |
| title_full_unstemmed | A bijection between planar constellations and some colored Lagrangian trees |
| title_short | A bijection between planar constellations and some colored Lagrangian trees |
| title_sort | bijection between planar constellations and some colored lagrangian trees |
| url | http://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/174 |
| work_keys_str_mv | AT cedricchauve abijectionbetweenplanarconstellationsandsomecoloredlagrangiantrees AT cedricchauve bijectionbetweenplanarconstellationsandsomecoloredlagrangiantrees |