New formulas counting one-face maps and Chapuy's recursion

arXiv1510.05038MaRDI QIDQ6266504

Christian M. Reidys, Ricky X. F. Chen

Publication date: 16 October 2015

Abstract: In this paper, we begin with the Lehman-Walsh formula counting one-face maps and construct two involutions on pairs of permutations to obtain a new formula for the number $A(n,g)$ of one-face maps of genus $g$. Our new formula is in the form of a convolution of the Stirling numbers of the first kind which immediately implies a formula for the generating function $A_n(x)=su{m}_{ggeq0}A(n,g)x^{n+1-2g}$ other than the well-known Harer-Zagier formula. By reformulating our expression for $A_n(x)$ in terms of the backward shift operator $E:f(x)ightarrowf(x-1)$ and proving a property satisfied by polynomials of the form $p(E)f(x)$, we easily establish the recursion obtained by Chapuy for $A(n,g)$. Moreover, we give a simple combinatorial interpretation for the Harer-Zagier recurrence.

Mathematics Subject Classification ID

Trees (05C05) Combinatorial identities, bijective combinatorics (05A19) Permutations, words, matrices (05A05)

This page was built for publication: New formulas counting one-face maps and Chapuy's recursion

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6266504)