The OEIS is supported by the many generous donors to the OEIS Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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. 12
 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 0,3 COMMENTS Row n contains floor((n+2)/2) terms. 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, Dec 18 2007 LINKS Gheorghe Coserea, Rows n = 0..200, flattened E. T. Akhmedov and Sh. Shakirov, Gluing of Surfaces with Polygonal Boundaries, arXiv:0712.2448 [math.CO], 2007-2008, see p. 1. Sean R. Carrell and Guillaume Chapuy, Simple recurrence formulas to count maps on orientable surfaces, arXiv:1402.6300 [math.CO], 2014. Ricky X. F. Chen and Christian M. Reidys, A Combinatorial Identity Concerning Plane Colored Trees and its Applications, Journal of Integer Sequences, Vol. 20 (2017), Article 17.3.7. Benoit Collins, Ion Nechita, and Deping Ye, The absolute positive partial transpose property for random induced states, Random Matrices: Theory Appl. 01, 1250002 (2012); arXiv:1108.1935 [math-ph], 2011. I. P. Goulden and A. Nica, A direct bijection for the Harer-Zagier formula, J. Comb. Theory, A, 111, No. 2 (2005), 224-238. 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 B. Lass, Démonstration combinatoire de la formule de Harer-Zagier, C. R. Acad. Sci. Paris, Serie I, 333, No.3 (2001), 155-160. T. R. S. Walsh and A. B. Lehman, Counting rooted maps by genus, J. Comb. Theory B 13 (1972), 192-218 (Tab. 1). Liang Zhao and Fengyao Yan, Note on Total Positivity for a Class of Recursive Matrices, Journal of Integer Sequences, Vol. 19 (2016), Article 16.6.5. Jian Zhou, Hermitian One-Matrix Model and KP Hierarchy, arXiv:1809.07951 [math-ph], 2018. FORMULA Let c be the 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 + 2*Sum_{g>=0} Sum_{n>=2*g} a(n,g) * x^(n+1) * y^(n-2*g+1) / (2*n-1)!! = (1+x/(1-x))^y. Equivalently, for n >= 0, Sum_{g=0..floor(n/2)} a(n,g)*y^(n-2*g+1) = (2*n-1)!! * Sum_{k=0..n} 2^k * C(n,k) * C(y,k+1). (n+2)*a(n+1,g) = (4*n+2)*a(n,g) + (4*n^3-n)*a(n-1,g-1) for n,g > 0, a(0,0)=1 and a(0,g)=0 for g > 0. The g.f. for column g > 0 is x^(2*g) * A270790(g) * P_g(x) / (1-4*x)^(3*g-1/2), where P_g(x) is the polynomial associated with row g of the triangle A270791. - Gheorghe Coserea, Apr 17 2016 EXAMPLE Triangle starts: n\g                                                 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;    ... MATHEMATICA a[n_, g_] := (2n)!/(n+1)!/(n-2g)! 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}]] (* Jean-François Alcover, Aug 30 2011, after E. T. Akhmedov & Sh. Shakirov *) PROG (PARI) N = 10; F = 1; gmax(n) = n\2; Q = matrix(N + 1, N + 1); Qget(n, g) = { if (g < 0 || g > n/2, 0, Q[n+1, g+1]) }; Qset(n, g, v) = { Q[n+1, g+1] = v }; Quadric({x=1}) = {   Qset(0, 0, x);   for (n = 1, length(Q)-1, for (g = 0, gmax(n),     my(t1 = (1+x)*(2*n-1)/3 * Qget(n-1, g),        t2 = (2*n-3)*(2*n-2)*(2*n-1)/12 * Qget(n-2, g-1),        t3 = 1/2 * sum(k = 1, n-1, sum(i = 0, g,        (2*k-1) * (2*(n-k)-1) * Qget(k-1, i) * Qget(n-k-1, g-i))));     Qset(n, g, (t1 + t2 + t3) * 6/(n+1)))); }; Quadric('x + O('x^(F+1))); concat(vector(N+2-F, n, vector(1 + gmax(n-1), g, polcoeff(Qget(n+F-2, g-1), F)))) \\ Gheorghe Coserea, Mar 16 2016 CROSSREFS Row sums give A001147(n). Columns g=0-2 give: A000108, A002802, A006298. The last entries in the even rows give A035319. Cf. A270406, A270790, A270791. Sequence in context: A247368 A019098 A333829 * A174218 A226308 A226309 Adjacent sequences:  A035306 A035307 A035308 * A035310 A035311 A035312 KEYWORD nonn,tabf,nice AUTHOR EXTENSIONS More terms and additional comments and references from Valery A. Liskovets, Apr 13 2006 Offset corrected by Gheorghe Coserea, Mar 17 2016 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified September 24 13:14 EDT 2022. Contains 356932 sequences. (Running on oeis4.)