DMTCS Proceedings, 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009)

Font Size:  Small  Medium  Large

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

Guillaume Chapuy

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 εg(n) of unicellular maps of size n and genus g to the numbers εj(n)'s, for j<g. In particular for each g this enables to compute the closed-form formula for ε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 εg(n)=Rg(n)Cat(n), where Cat(n) is the n-th Catalan number and Rg is a polynomial of degree 3g, with explicit interpretation.
Résumé. 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 εg(n) de cartes à une face de taille n et genre g aux nombres εj(n), pour j<g. En particulier, pour tout g, cela permet de calculer la formule close donnant ε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 εg(n)=Rg(n)Cat(n), où Cat(n) est le nième nombre de Catalan et Rg est un polynôme de degré 3g, à l'interprétation explicite.

Full Text: GZIP Compressed PostScript PostScript PDF

Valid XHTML 1.0 Transitional