

A035309


Triangle read by rows giving number of ways to glue sides of a 2ngon so as to produce a surface of genus g.


5



1, 1, 2, 1, 5, 10, 14, 70, 21, 42, 420, 483, 132, 2310, 6468, 1485, 429, 12012, 66066, 56628, 1430, 60060, 570570, 1169740, 225225, 4862, 291720, 4390386, 17454580, 12317877, 16796, 1385670, 31039008, 211083730, 351683046, 59520825, 58786, 6466460, 205633428, 2198596400, 7034538511, 4304016990
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,3


COMMENTS

a(n,g) is also the number of unicellular (i.e., 1faced) rooted maps of genus g with n edges. #(vertices) = n  2g + 1. Dually, this is the number of 1vertex 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 twodimensional 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 twodimensional surfaces, we derive recursive relations between N_{g,L}. We show that HarerZagier numbers appear as a particular case of N_{g,L} and derive a new explicit expression for them.  Jonathan Vos Post, Dec 18 2007


LINKS

Table of n, a(n) for n=1..42.
E. T. Akhmedov and Sh. Shakirov, Gluing of Surfaces with Polygonal Boundaries, arXiv:0712.2448 [math.CO], 20072008, see p. 1.
Benoit Collins, Ion Nechita, Deping Ye, The absolute positive partial transpose property for random induced states, Random Matrices: Theory Appl. 01, 1250002 (2012); arXiv:1108.1935 [mathph], 2011.
I. P. Goulden and A. Nica, A direct bijection for the HarerZagier formula, J. Comb. Theory, A, 111, No. 2 (2005), 224238.
J. L. Harer and D. B. Zagier, The Euler characteristic of the moduli space of curves, Invent. Math., 85, No.3 (1986), 457486.
S. Lando and A. Zvonkin, Graphs on surfaces and their applications, Encyclopaedia of Mathematical Sciences, 141, Springer, 2004, p. 157
B. Lass, Démonstration combinatoire de la formule de HarerZagier, C. R. Acad. Sci. Paris, Serie I, 333, No.3 (2001), 155160.
T. R. S. Walsh and A. B. Lehman, Counting rooted maps by genus, J. Comb. Theory B 13 (1972), 192218 (Tab.1).


FORMULA

Let c be number of cycles that appear in product of a (2n)cycle and a product of n disjoint transpositions; genus is g = (nc+1)/2.
The HarerZagier formula: 1+2*sum(g>=0, sum(n>=2*g, a(n,g) * x^(n+1) * y^(n2*g+1) / (2*n1)!! ) ) = (1+x/(1x))^y.
Equivalently, for n>=0, sum(0<=g<=floor(n/2), a(n,g)*y^(n2*g+1) ) = (2*n1)!! * sum(0<=k<=n, 2^k * C(n,k) * C(y,k+1) ).
(n+2)*a(n+1,g) = (4*n+2)*a(n,g) + (4*n^3n)*a(n1,g1) for n,g>0, a(0,0)=1 and a(0,g)=0 for g>0.


EXAMPLE

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 nth row sum is (2n1)!! = 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.


MATHEMATICA

a[n_, g_] := (2n)!/(n+1)!/(n2g)! Coefficient[Series[(x/2/Tanh[x/2])^(n+1), {x, 0, n}], x, 2g]; Flatten[DeleteCases[#, 0]& /@ Table[a[n, g], {n, 0, 11}, {g, 0, n}]] (* JeanFrançois Alcover, Aug 30 2011, after E. T. Akhmedov & Sh. Shakirov *)


CROSSREFS

First 3 cols are A000108, A002802, A006298.
Sequence in context: A178627 A247368 A019098 * A174218 A226308 A226309
Adjacent sequences: A035306 A035307 A035308 * A035310 A035311 A035312


KEYWORD

nonn,tabf,nice


AUTHOR

Dylan Thurston


EXTENSIONS

More terms and additional comments and references from Valery A. Liskovets, Apr 13 2006


STATUS

approved



