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

dmtcs:2747 - Discrete Mathematics & Theoretical Computer Science, January 1, 2009, DMTCS Proceedings vol. AK, 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009) - https://doi.org/10.46298/dmtcs.2747
A new combinatorial identity for unicellular maps, via a direct bijective approach.Article

Authors: Guillaume Chapuy 1

  • 1 Laboratoire d'informatique de l'École polytechnique [Palaiseau]

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.


Volume: DMTCS Proceedings vol. AK, 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009)
Section: Proceedings
Published on: January 1, 2009
Imported on: January 31, 2017
Keywords: Polygon gluings,combinatorial identity,bijection,[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO],[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]
Funding:
    Source : OpenAIRE Graph
  • Combinatorial methods, from enumerative topology to random discrete structures and compact data representations.; Funder: European Commission; Code: 208471

46 Documents citing this article

Consultation statistics

This page has been seen 205 times.
This article's PDF has been downloaded 264 times.