Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. A new combinatorial ...
Conference paper

A new combinatorial identity for unicellular maps, via a direct bijective approach.

Guillaume Chapuy (1)
(1) Laboratoire d'informatique de l'École polytechnique [Palaiseau]
Download article
Open on HAL
Imported on
January 31, 2017
Published on
December 31, 2008
Last modified on
March 31, 2025
Volume
DMTCS Proceedings vol. AK, 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009)
Proceedings
DOI
10.46298/dmtcs.2747
License
https://about.hal.science/hal-authorisation-v1
European Commission
208471
Combinatorial methods, from enumerative topology to random discrete structures and compact data representations.
Indicators
744
Views
579
Downloads

A new combinatorial identity for unicellular maps, via a direct bijective approach.

Guillaume Chapuy (1)
(1) Laboratoire d'informatique de l'École polytechnique [Palaiseau]
Abstract
English
We give a bijective operation that relates unicellular maps of given genus to unicellular maps of lower genus, with distinguished vertices. This gives a new combinatorial identity relating the number $\epsilon_g(n)$ of unicellular maps of size $n$ and genus $g$ to the numbers $\epsilon _j(n)$'s, for $j \lt g$. In particular for each $g$ this enables to compute the closed-form formula for $\epsilon_g(n)$ much more easily than with other known identities, like the Harer-Zagier formula. From the combinatorial point of view, we give an explanation to the fact that $\epsilon_g(n)=R_g(n) \mathrm{Cat}(n)$, where $\mathrm{Cat}(n$) is the $n$-th Catalan number and $R_g$ is a polynomial of degree $3g$, with explicit interpretation.
French
On décrit une opération bijective qui relie les cartes à une face de genre donné à des cartes à une face de genre inférieur, portant des sommets marqués. Cela conduit à une nouvelle identité combinatoire reliant le nombre $\epsilon_g(n)$ de cartes à une face de taille $n$ et genre $g$ aux nombres $\epsilon _j(n)$, pour $j \lt g$. En particulier, pour tout $g$, cela permet de calculer la formule close donnant $\epsilon_g(n)$ bien plus facilement qu'à l'aide des autres identités connues, comme la formule d'Harer-Zagier. Du point de vue combinatoire, nous donnons une explication au fait que $\epsilon _g(n)=R_g(n) \mathrm{Cat}(n)$, où $\mathrm{Cat}(n)$ est le $n$ième nombre de Catalan et $R_g$ est un polynôme de degré $3g$, à l'interprétation explicite.
Keywords
  • [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]
  • [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
  • Polygon gluings
  • combinatorial identity
  • bijection
Cited by

Source: OpenCitations

  • A Bijection for Tricellular Maps

    ISRN Discrete Mathematics

    Authors : Hillary S. W. Han, Christian M. Reidys ORCID

    Journal reference : Volume 2013, 2013, pp. 1-12

    DOI : 10.1155/2013/712431

  • Shapes of Interacting RNA Complexes

    PubMed Central

    Authors : Benjamin M.M. Fu, Christian M. Reidys ORCID

    Journal reference : Volume 21, 2014, pp. 649-664

    DOI : 10.1089/cmb.2014.0107

  • Curves on surfaces and surgeries

    arXiv (Cornell University)

    Authors : Abdoul Karim Sane

    Journal reference : Volume 93, 2020, pp. 103281

    DOI : 10.1016/j.ejc.2020.103281

  • Topological language for RNA

    arXiv (Cornell University)

    Authors : Fenix W.D. Huang ORCID, Christian M. Reidys ORCID

    Journal reference : Volume 282, 2016, pp. 109-120

    DOI : 10.1016/j.mbs.2016.10.006

  • Loop homology of bi-secondary structures

    arXiv (Cornell University)

    Authors : Andrei C. Bura ORCID, Qijun He ORCID, Christian M. Reidys ORCID

    Journal reference : Volume 344, 2021, pp. 112371

    DOI : 10.1016/j.disc.2021.112371

  • A Genus Comparison in the Topological Analysis of RNA Structures

    Acta Biotheoretica

    Authors : Nicolò Cangiotti ORCID, Stefano Grasso ORCID

    Journal reference : Volume 73, 2025, pp. 11

    DOI : 10.1007/s10441-025-09500-9

  • Local limits of uniform triangulations in high genus

    arXiv (Cornell University)

    Authors : Thomas Budzinski ORCID, Baptiste Louf ORCID

    Journal reference : Volume 223, 2020, pp. 1-47

    DOI : 10.1007/s00222-020-00986-3

  • Simple Maps, Hurwitz Numbers, and Topological Recursion

    Communications in Mathematical Physics

    Authors : Gaëtan Borot, Elba Garcia-Failde ORCID

    Journal reference : Volume 380, 2020, pp. 581-654

    DOI : 10.1007/s00220-020-03867-1

  • A topological framework for signed permutations

    Discrete Mathematics

    Authors : Fenix W.D. Huang ORCID, Christian M. Reidys ORCID

    Journal reference : Volume 340, 2017, pp. 2161-2182

    DOI : 10.1016/j.disc.2017.03.019

  • A new family of bijections for planar maps

    arXiv (Cornell University)

    Authors : Baptiste Louf ORCID

    Journal reference : Volume 168, 2019, pp. 374-395

    DOI : 10.1016/j.jcta.2019.06.006

  • Weighted Homology of Bi-Structures over Certain Discrete Valuation Rings

    Mathematics

    Authors : Andrei Bura ORCID, Qijun He ORCID, Christian Reidys ORCID

    Journal reference : Volume 9, 2021, pp. 744

    DOI : 10.3390/math9070744

  • Classical curves via one-vertex maps

    arXiv (Cornell University)

    Authors : Anthony Weaver

    Journal reference : Volume 163, 2012, pp. 141-158

    DOI : 10.1007/s10711-012-9740-2

  • Contribution of n-cylinder square-tiled surfaces to Masur–Veech volume of $\mathcal{H}(2g-2)$

    Geometric and Functional Analysis

    Authors : Ivan Yakovlev ORCID

    Journal reference : Volume 33, 2023, pp. 1682-1716

    DOI : 10.1007/s00039-023-00652-9

  • Introduction

    Springer theses

    Authors : Luca Lionni ORCID

    Journal reference : Volume , 2018, pp. 1-16

    DOI : 10.1007/978-3-319-96023-4_1

  • Shapes of topological RNA structures

    arXiv (Cornell University)

    Authors : Fenix W.D. Huang ORCID, Christian M. Reidys ORCID

    Journal reference : Volume 270, 2015, pp. 57-65

    DOI : 10.1016/j.mbs.2015.10.004

  • A versatile combinatorial approach of studying products of long cycles in symmetric groups

    arXiv (Cornell University)

    Authors : Ricky X.F. Chen ORCID

    Journal reference : Volume 133, 2021, pp. 102283

    DOI : 10.1016/j.aam.2021.102283

  • Random 2-cell embeddings of multistars

    arXiv (Cornell University)

    Authors : Jesse Campion Loth, Kevin Halasz ORCID, Tomáš Masařík ORCID, Bojan Mohar ORCID, Robert Šámal ORCID

    Journal reference : Volume 150, 2022, pp. 3699-3713

    DOI : 10.1090/proc/15899

  • On RNA–RNA interaction structures of fixed topological genus

    Mathematical Biosciences

    Authors : Benjamin M.M. Fu, Hillary S.W. Han, Christian M. Reidys ORCID

    Journal reference : Volume 262, 2015, pp. 88-104

    DOI : 10.1016/j.mbs.2014.12.008

  • Random 2-Cell Embeddings of Multistars

    Trends in mathematics

    Authors : Jesse Campion Loth, Kevin Halasz ORCID, Tomáš Masařík ORCID, Bojan Mohar ORCID, Robert Šámal ORCID

    Journal reference : Volume , 2021, pp. 805-810

    DOI : 10.1007/978-3-030-83823-2_128

  • Encoding Toroidal Triangulations

    arXiv (Cornell University)

    Authors : Vincent Despré, Daniel Gonçalves ORCID, Benjamin Lévêque

    Journal reference : Volume 57, 2016, pp. 507-544

    DOI : 10.1007/s00454-016-9832-0

  • Fatgraph models of RNA structure

    Computational and Mathematical Biophysics

    Authors : Fenix Huang ORCID, Christian Reidys ORCID, Reza Rezazadegan ORCID

    Journal reference : Volume 5, 2017, pp. 1-20

    DOI : 10.1515/mlbmb-2017-0001

  • Simple Formulas for Constellations and Bipartite Maps with Prescribed Degrees

    arXiv (Cornell University)

    Authors : Baptiste Louf

    Journal reference : Volume 73, 2019, pp. 160-176

    DOI : 10.4153/s0008414x19000555

  • Calculating the Euler Characteristic of the Moduli Space of Curves

    Authors : Bodo Lass

    Journal reference : Volume 42, 2022, pp. 749-762

    DOI : 10.1007/s00493-021-4688-1

  • A bijection for covered maps, or a shortcut between Harer–Zagierʼs and Jacksonʼs formulas

    Journal of Combinatorial Theory Series A

    Authors : Olivier Bernardi ORCID, Guillaume Chapuy ORCID

    Journal reference : Volume 118, 2011, pp. 1718-1748

    DOI : 10.1016/j.jcta.2011.02.006

  • Roaming moduli space using dynamical triangulations

    arXiv (Cornell University)

    Authors : J. Ambjørn ORCID, J. Barkley, T.G. Budd ORCID

    Journal reference : Volume 858, 2012, pp. 267-292

    DOI : 10.1016/j.nuclphysb.2012.01.010

  • Enumeration of Regular Maps on Surfaces of a Given Genus

    Journal of Mathematical Sciences

    Authors : E. S. Krasko, A. V. Omelchenko ORCID

    Journal reference : Volume 232, 2018, pp. 44-60

    DOI : 10.1007/s10958-018-3858-1

  • Loop homology of bi-secondary structures II

    Journal of Algebraic Combinatorics

    Authors : Andrei C. Bura ORCID, Qijun He ORCID, Christian M. Reidys ORCID

    Journal reference : Volume 56, 2022, pp. 785-798

    DOI : 10.1007/s10801-022-01132-3

  • Explicit formulas for a family of hypermaps beyond the one-face case

    Journal of Combinatorial Theory Series A

    Authors : Zi-Wei Bai, Ricky X.F. Chen ORCID

    Journal reference : Volume 206, 2024, pp. 105905

    DOI : 10.1016/j.jcta.2024.105905

  • Direct Bijective Computation of the Generating Series for 2 and 3-Connection Coefficients of the Symmetric Group

    The Electronic Journal of Combinatorics

    Authors : Alejandro H. Morales ORCID, Ekaterina A. Vassilieva

    Journal reference : Volume 20, 2013, pp.

    DOI : 10.37236/3226

  • Statistics of topological RNA structures

    arXiv (Cornell University)

    Authors : Thomas J. X. Li ORCID, Christian M. Reidys ORCID

    Journal reference : Volume 74, 2016, pp. 1793-1821

    DOI : 10.1007/s00285-016-1078-1

  • Generation of RNA pseudoknot structures with topological genus filtration

    Mathematical Biosciences

    Authors : Fenix W.D. Huang ORCID, Markus E. Nebel, Christian M. Reidys ORCID

    Journal reference : Volume 245, 2013, pp. 216-225

    DOI : 10.1016/j.mbs.2013.07.014

  • The Harer-Zagier and Jackson formulas and new results for one-face bipartite maps

    Proceedings of the American Mathematical Society

    Authors : Ricky Chen

    Journal reference : Volume 152, 2024, pp. 4245-4259

    DOI : 10.1090/proc/16929

  • Bijective Methods

    Springer theses

    Authors : Luca Lionni ORCID

    Journal reference : Volume , 2018, pp. 75-137

    DOI : 10.1007/978-3-319-96023-4_3

  • RNA Secondary Structures

    Elsevier eBooks

    Authors : Christian M. Reidys ORCID

    Journal reference : Volume , 2015, pp. 347-362

    DOI : 10.1016/b978-0-12-801213-0.00014-9

  • The joint distribution of the marginals of multipartite random quantum states

    arXiv (Cornell University)

    Authors : Stephane Dartois, Luca Lionni, Ion Nechita

    Journal reference : Volume 09, 2019, pp. 2050010

    DOI : 10.1142/s2010326320500100

  • Random generation and scaling limits of fixed genus factorizations into transpositions

    Probability Theory and Related Fields

    Authors : Valentin Féray ORCID, Baptiste Louf ORCID, Paul Thévenin ORCID

    Journal reference : Volume 184, 2022, pp. 681-748

    DOI : 10.1007/s00440-022-01170-9

  • Plane Permutations and Applications to a Result of Zagier--Stanley and Distances of Permutations

    arXiv (Cornell University)

    Authors : Ricky X. F. Chen ORCID, Christian M. Reidys ORCID

    Journal reference : Volume 30, 2016, pp. 1660-1684

    DOI : 10.1137/15m1023646

  • Combinatorial and Algebraic Enumeration: a survey of the work of Ian P. Goulden and David M. Jackson

    Algebraic Combinatorics

    Authors : Angèle M. Foley, Alejandro H. Morales ORCID, Amarpreet Rattan, Karen Yeats

    Journal reference : Volume 5, 2022, pp. 1205-1226

    DOI : 10.5802/alco.269

  • Strong log-convexity of genus sequences

    Journal of Combinatorial Theory Series B

    Authors : Bojan Mohar ORCID

    Journal reference : Volume 178, 2026, pp. 164-179

    DOI : 10.1016/j.jctb.2025.12.005

  • Planar Maps

    Discrete mathematics and its applications

    Authors : Gilles Schaeffer ORCID

    Journal reference : Volume , 2015, pp. 335-395

    DOI : 10.1201/b18255-8

  • Generating series of non-oriented constellations and marginal sums in the Matching-Jack conjecture

    Algebraic Combinatorics

    Authors : Houcine Ben Dali ORCID

    Journal reference : Volume 5, 2022, pp. 1299-1336

    DOI : 10.5802/alco.207

  • Combinatorially refine a Zagier–Stanley result on products of permutations

    arXiv (Cornell University)

    Authors : Ricky X.F. Chen ORCID

    Journal reference : Volume 343, 2020, pp. 111912

    DOI : 10.1016/j.disc.2020.111912

  • Virtual Euler characteristics via topological recursion

    Journal of Geometry and Physics

    Authors : Leonid O. Chekhov

    Journal reference : Volume 199, 2024, pp. 105152

    DOI : 10.1016/j.geomphys.2024.105152

  • Planarity and non-separating cycles in uniform high genus quadrangulations

    Probability Theory and Related Fields

    Authors : Baptiste Louf ORCID

    Journal reference : Volume 182, 2021, pp. 1183-1206

    DOI : 10.1007/s00440-021-01050-8

  • Moduli spaces and macromolecules

    Bulletin of the American Mathematical Society

    Authors : R. Penner ORCID

    Journal reference : Volume 53, 2016, pp. 217-268

    DOI : 10.1090/bull/1524

  • Enumeration of 4-regular one-face maps

    European Journal of Combinatorics

    Authors : Evgeniy Krasko, Alexander Omelchenko ORCID

    Journal reference : Volume 62, 2017, pp. 167-177

    DOI : 10.1016/j.ejc.2016.12.004

  • Large unicellular maps in high genus

    Annales de l Institut Henri Poincaré Probabilités et Statistiques

    Authors : Gourab Ray

    Journal reference : Volume 51, 2015, pp.

    DOI : 10.1214/14-aihp618

  • Hypergraph matrix models and generating functions

    Combinatorics and Number Theory

    Authors : Paul E. Gunnells ORCID

    Journal reference : Volume 13, 2024, pp. 149-178

    DOI : 10.2140/cnt.2024.13.149

  • The topological filtration of -structures

    University of Southern Denmark Research Portal (University of Southern Denmark)

    Authors : Thomas J.X. Li ORCID, Christian M. Reidys ORCID

    Journal reference : Volume 241, 2012, pp. 24-33

    DOI : 10.1016/j.mbs.2012.09.006

  • An analogue of the Harer–Zagier formula for unicellular maps on general surfaces

    Advances in Applied Mathematics

    Authors : Olivier Bernardi ORCID

    Journal reference : Volume 48, 2011, pp. 164-180

    DOI : 10.1016/j.aam.2011.06.005

  • Combinatorial study of graphs arising from the Sachdev–Ye–Kitaev model

    European Journal of Combinatorics

    Authors : É. Fusy ORCID, L. Lionni ORCID, A. Tanasa ORCID

    Journal reference : Volume 86, 2020, pp. 103066

    DOI : 10.1016/j.ejc.2019.103066

  • A simple model of trees for unicellular maps

    Journal of Combinatorial Theory Series A

    Authors : Guillaume Chapuy ORCID, Valentin Féray ORCID, Éric Fusy ORCID

    Journal reference : Volume 120, 2013, pp. 2064-2092

    DOI : 10.1016/j.jcta.2013.08.003
Preview
Loading PDF preview...