%I A035309
%S A035309 1,1,2,1,5,10,14,70,21,42,420,483,132,2310,6468,1485,429,12012,66066,
%T A035309 56628,1430,60060,570570,1169740,225225,4862,291720,4390386,17454580,
%U A035309 12317877,16796,1385670,31039008,211083730,351683046,59520825,58786,6466460,
               205633428,2198596400,7034538511,4304016990
%N A035309 Triangle read by rows giving number of ways to glue sides of a 2n-gon 
               so as to produce a surface of genus g.
%C A035309 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.
%C A035309 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
%D A035309 J. L. Harer and D. B. Zagier, The Euler characteristic of the moduli 
               space of curves, Invent. Math., 85, No.3 (1986), 457-486.
%D A035309 S. Lando and A. Zvonkin, Graphs on surfaces and their applications (Encyclopaedia 
               of Mathematical Sciences, 141), Springer, 2004, p. 157.
%D A035309 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).
%H A035309 I. P. Goulden and A. Nica, <a href="http://dx.doi.org/10.1016/j.jcta.2004.12.003">
               A direct bijection for the Harer-Zagier formula</a>,J. Comb. Theory, 
               A, 111, No. 2 (2005), 224-238.
%H A035309 B. Lass, <a href="http://euler.univ-lyon1.fr/home/lass/articles/pub3zagierj.pdf">
               De'monstration combinatoire de la formule de Harer-Zagier</a>,C. 
               R. Acad. Sci. Paris, Se'rie, I, 333, No.3 (2001), 155-160.
%H A035309 E. T. Akhmedov and Sh. Shakirov, <a href="http://arXiv.org/pdf/0712.2448">
               Gluing of Surfaces with Polygonal Boundaries</a>, Dec 18, 2007, p. 
               1.
%F A035309 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
%F A035309 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.
%e A035309 1; 1; 2,1; 5,10; 14,70,21; 42,420,483; ...
%e A035309 For n=0,..,6, we have the array:
%e A035309 1
%e A035309 1
%e A035309 2 1
%e A035309 5 10
%e A035309 14 70 21
%e A035309 42 420 483
%e A035309 132 2310 6468 1485
%e A035309 The n-th row sum is (2n-1)!!=A001147(n).
%e A035309 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.
%Y A035309 First 3 cols are A000108, A002802, A006298.
%Y A035309 Sequence in context: A021467 A011132 A019098 this_sequence A049948 A110352 
               A107310
%Y A035309 Adjacent sequences: A035306 A035307 A035308 this_sequence A035310 A035311 
               A035312
%K A035309 nonn,tabf,nice
%O A035309 1,3
%A A035309 Dylan Thurston (Dylan.Thurston(AT)math.unige.ch)
%E A035309 More terms and additional comments and references from Valery A. Liskovets 
               (liskov(AT)im.bas-net.by), Apr 13 2006