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

2015/10/16 by Ricky X. F. Chen, Chen, Ricky X. F., Christian M. Reidys +1
Mathematics · #05A05 #05A19 #05C05 #Advanced Combinatorial Mathematics #Advanced Mathematical Identities #Algebraic structures and combinatorial models #Combinatorics (math.CO) #FOS: Mathematics

paper · pdf · doi:10.48550/arxiv.1510.05038

openalex publication_date 2015/10/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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)=∑_{g≥ 0}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)→ f(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.

Related

• Generalisations of the Harer-Zagier recursion for 1-point functions
• Constructing large tables of numbers of maps by orientable genus
• Enumeration of Tree-like Maps with Arbitrary Number of Vertices
• Methods of Enumerating Two Vertex Maps of Arbitrary Genus
• Springer Numbers and Arnold Families Revisited