1,3

a(n,g) is also the number of unicellular (i.e. 1-faced) rooted maps of genus g with n edges. #(vertices)=n-2g+1. Dually, this is the number of 1-vertex maps. Catalan(n)=A000108(n) divides a(n,g)2^g.

From Akhmedov and Shakirov's abstract: By pairwise gluing of sides of a polygon, one produces two-dimensional surfaces with handles and boundaries. We give the number N_{g,L}(n_1, n_2, ..., n_L) of different ways to produce a surface of given genus g with $L$ polygonal boundaries with given numbers of sides n_1, n_2, >..., n_L. Using combinatorial relations between graphs on real two-dimensional surfaces, we derive recursive relations between N_{g,L}. We show that Harer-Zagier numbers appear as a particular case of N_{g,L} and derive a new explicit expression for them. - Jonathan Vos Post (jvospost3(AT)gmail.com), Dec 18 2007

J. L. Harer and D. B. Zagier, The Euler characteristic of the moduli space of curves, Invent. Math., 85, No.3 (1986), 457-486.

S. Lando and A. Zvonkin, Graphs on surfaces and their applications (Encyclopaedia of Mathematical Sciences, 141), Springer, 2004, p. 157.

T. R. S. Walsh and A. B. Lehman, Counting rooted maps by genus. I, J. Comb. Theory, B, 13, No.3 (1972), 192-218 (Tab.1).

I. P. Goulden and A. Nica, A direct bijection for the Harer-Zagier formula,J. Comb. Theory, A, 111, No. 2 (2005), 224-238.

B. Lass, De'monstration combinatoire de la formule de Harer-Zagier,C. R. Acad. Sci. Paris, Se'rie, I, 333, No.3 (2001), 155-160.

E. T. Akhmedov and Sh. Shakirov, Gluing of Surfaces with Polygonal Boundaries, Dec 18, 2007, p. 1.

Let c be number of cycles that appear in product of a (2n)-cycle and a product of n disjoint transpositions; genus is g = (n-c+1)/2

The Harer-Zagier formula: 1+2Sum_{g>=0}Sum_{n>=2g}a(n,g)x^{n+1}y^{n-2g+1}/(2n-1)!!=(1+x/(1-x))^y. Equivalently, for n>=0, Sum_{0<=g<=floor(n/2)}a(n,g)y^{n-2g+1}=(2n-1)!!Sum_{0<=k<=n}2^kC(n,k)C(y,k+1). (n+2)a(n+1,g)=(4n+2)a(n,g)+(4n^3-n)a(n-1,g-1) for n,g>0, a(0,0)=1 and a(0,g)=0 for g>0.

1; 1; 2,1; 5,10; 14,70,21; 42,420,483; ...

For n=0,..,6, we have the array:

1

1

2 1

5 10

14 70 21

42 420 483

132 2310 6468 1485

The n-th row sum is (2n-1)!!=A001147(n).

The first three columns (for g=0,1,2) are respectively A000108 (Catalan; plane trees), A002802 and A006298. The last entries in the even rows form A035319.

First 3 cols are A000108, A002802, A006298.

Sequence in context: A021467 A011132 A019098 this_sequence A049948 A110352 A107310

Adjacent sequences: A035306 A035307 A035308 this_sequence A035310 A035311 A035312

nonn,tabf,nice

Dylan Thurston (Dylan.Thurston(AT)math.unige.ch)

More terms and additional comments and references from Valery A. Liskovets (liskov(AT)im.bas-net.by), Apr 13 2006