Another Proof of the Harer-Zagier Formula

  • Boris Pittel
Keywords: Surfaces, Chord diagrams, Genus, Random permutations, Fourier transform, Irreducible characters, Murnaghan-Nakayama, Generating functions


For a regular $2n$-gon there are $(2n-1)!!$ ways to match and glue the $2n$ sides. The Harer-Zagier bivariate generating function enumerates the gluings by $n$ and the genus $g$ of the attendant surface and leads to a recurrence equation for the counts of gluings with parameters $n$ and $g$. This formula was originally obtained using multidimensional Gaussian integrals. Soon after, Jackson and later Zagier found alternative proofs using symmetric group characters. In this note we give a different, characters-based, proof. Its core is computing and marginally inverting the Fourier transform of the underlying probability measure on $S_{2n}$. A key ingredient is the Murnaghan-Nakayama rule for the characters associated with one-hook Young diagrams.
Article Number