# A direct proof of the Harer-Zagier recursion enumerating the ways to paste a 2n-gon to get a genus g surface?

In a 1986 paper, Harer and Zagier proved the recursion:

$$(n+1)e(g,n)=(4n-2)e(g,n-1)+(2n-1)(n-1)(2n-3)e(g-1,n-2)$$

where e(g,n) is the number of ways of grouping sides $S_1...S_{2n}$ of a 2n-gon into n pairs, such that, after identifying pairs with the corresponding orientation one gets an orientable surface of genus g.

Their proof is really indirect, it involves pages of calculations.

Is there a simple proof of this fact?

-
So it's actually Zagier and not Zaiger or Zager? –  Stopple Mar 28 '13 at 18:59

## 2 Answers

http://arxiv.org/abs/0712.2448

Gluing of Surfaces with Polygonal Boundaries E. T. Akhmedov, Sh. Shakirov

By pairwise gluing of edges of a polygon, o produces two-dimensional surfaces with handles and boundaries. In this paper, we count the number ${\cal N}_{g,L}(n_1, n_2, n_L)$ of different ways to produce a surfac of given genus $g$ with $L$ polygonal boundaries with given numbers of edges $n_1, n_2, >..., n_L$. Using combinatorial relations between graphs on real two-dimensional surfaces, we derive recursive relations between $\cal N_{g,L}$. We show that Harer-Zagier numbers appear as a particular case of ${\cal N}_{g,L}$ and deriv a new explicit expression for them. Comments: 7 pages, 9 figures

It seems proposes quite elementary proof. The key idea that they found some generalization which is more easy to prove.

-

How about

Goulden, I. P.; Nica, A. A direct bijection for the Harer-Zagier formula. J. Combin. Theory Ser. A 111 (2005), no. 2, 224–238.

or one of the references therein?

-
I'll just point out the work of Bodo Lass in 2000, which is a quite simple combinatorial proof (in French) cited by Goulden-Nica. His approach was extended in 2011 by Olivier Bernardi. A bijective proof can also be found in the work of Chapuy, Féray & Fusy (2012), building on earlier work of Chapuy. –  Philippe Nadeau Mar 28 '13 at 18:38