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?
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?
