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

Abstract : 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.
Keywords :
Document type :
Conference papers
Domain :
Complete list of metadata

Cited literature [8 references]

https://hal.inria.fr/hal-01185440
Contributor : Coordination Episciences Iam <>
Submitted on : Thursday, August 20, 2015 - 11:09:54 AM
Last modification on : Thursday, March 5, 2020 - 6:31:07 PM
Long-term archiving on: : Wednesday, April 26, 2017 - 10:19:54 AM

File

dmAK0124.pdf
Publisher files allowed on an open archive

Identifiers

• HAL Id : hal-01185440, version 1

Citation

Guillaume Chapuy. A new combinatorial identity for unicellular maps, via a direct bijective approach.. 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009), 2009, Hagenberg, Austria. pp.289-300. ⟨hal-01185440⟩

Record views