%I #99 Feb 06 2024 12:11:52
%S 1,1,2,1,5,10,14,70,21,42,420,483,132,2310,6468,1485,429,12012,66066,
%T 56628,1430,60060,570570,1169740,225225,4862,291720,4390386,17454580,
%U 12317877,16796,1385670,31039008,211083730,351683046,59520825,58786,6466460,205633428,2198596400,7034538511,4304016990
%N 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 Row n contains floor((n+2)/2) terms.
%C 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 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
%H Gheorghe Coserea, <a href="/A035309/b035309.txt">Rows n = 0..200, flattened</a>
%H E. T. Akhmedov and Sh. Shakirov, <a href="http://arXiv.org/abs/0712.2448">Gluing of Surfaces with Polygonal Boundaries</a>, arXiv:0712.2448 [math.CO], 2007-2008, see p. 1.
%H Sean R. Carrell and Guillaume Chapuy, <a href="http://arxiv.org/abs/1402.6300">Simple recurrence formulas to count maps on orientable surfaces</a>, arXiv:1402.6300 [math.CO], 2014.
%H Ricky X. F. Chen and Christian M. Reidys, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL20/Chen/chen32.html">A Combinatorial Identity Concerning Plane Colored Trees and its Applications</a>, Journal of Integer Sequences, Vol. 20 (2017), Article 17.3.7.
%H Benoit Collins, Ion Nechita, and Deping Ye, <a href="http://arxiv.org/abs/1108.1935">The absolute positive partial transpose property for random induced states</a>, Random Matrices: Theory Appl. 01, 1250002 (2012); arXiv:1108.1935 [math-ph], 2011.
%H 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 J. L. Harer and D. B. Zagier, <a href="http://people.mpim-bonn.mpg.de/zagier/files/doi/10.1007/BF01390325/fulltext.pdf">The Euler characteristic of the moduli space of curves</a>, Invent. Math., 85, No.3 (1986), 457-486.
%H S. Lando and A. Zvonkin, <a href="http://dx.doi.org/10.1007/978-3-540-38361-1">Graphs on surfaces and their applications</a>, Encyclopaedia of Mathematical Sciences, 141, Springer, 2004, p. 157.
%H B. Lass, <a href="http://math.univ-lyon1.fr/~lass/articles/pub3zagierj.pdf">Démonstration combinatoire de la formule de Harer-Zagier</a>, C. R. Acad. Sci. Paris, Serie I, 333, No.3 (2001), 155-160.
%H A. Mironov, A. Morozov, A. Popolitov, and Sh. Shakirov, <a href="https://arxiv.org/abs/2401.14392">Summing up perturbation series around superintegrable point</a>, arXiv:2401.14392 [hep-th], 2024.
%H T. R. S. Walsh and A. B. Lehman, <a href="http://dx.doi.org/10.1016/0095-8956(72)90056-1">Counting rooted maps by genus</a>, J. Comb. Theory B 13 (1972), 192-218 (Tab. 1).
%H Nikolai Wyderka and Andreas Ketterer, <a href="https://arxiv.org/abs/2211.09610">Probing the geometry of correlation matrices with randomized measurements</a>, arXiv:2211.09610 [quant-ph], 2022.
%H Liang Zhao and Fengyao Yan, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL19/Zhao/zhao17.html">Note on Total Positivity for a Class of Recursive Matrices</a>, Journal of Integer Sequences, Vol. 19 (2016), Article 16.6.5.
%H Jian Zhou, <a href="https://arxiv.org/abs/1809.07951">Hermitian One-Matrix Model and KP Hierarchy</a>, arXiv:1809.07951 [math-ph], 2018.
%F 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.
%F 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.
%F 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).
%F (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.
%F 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
%e Triangle starts:
%e n\g [0] [1] [2] [3] [4] [5]
%e [0] 1;
%e [1] 1;
%e [2] 2; 1;
%e [3] 5, 10;
%e [4] 14, 70, 21;
%e [5] 42, 420, 483;
%e [6] 132, 2310, 6468, 1485;
%e [7] 429, 12012, 66066, 56628;
%e [8] 1430, 60060, 570570, 1169740, 225225;
%e [9] 4862, 291720, 4390386, 17454580, 12317877;
%e [10] 16796, 1385670, 31039008, 211083730, 351683046, 59520825;
%e [11] ...
%t 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 *)
%o (PARI)
%o N = 10; F = 1; gmax(n) = n\2;
%o Q = matrix(N + 1, N + 1);
%o Qget(n, g) = { if (g < 0 || g > n/2, 0, Q[n+1, g+1]) };
%o Qset(n, g, v) = { Q[n+1, g+1] = v };
%o Quadric({x=1}) = {
%o Qset(0, 0, x);
%o for (n = 1, length(Q)-1, for (g = 0, gmax(n),
%o my(t1 = (1+x)*(2*n-1)/3 * Qget(n-1, g),
%o t2 = (2*n-3)*(2*n-2)*(2*n-1)/12 * Qget(n-2, g-1),
%o t3 = 1/2 * sum(k = 1, n-1, sum(i = 0, g,
%o (2*k-1) * (2*(n-k)-1) * Qget(k-1, i) * Qget(n-k-1, g-i))));
%o Qset(n, g, (t1 + t2 + t3) * 6/(n+1))));
%o };
%o Quadric('x + O('x^(F+1)));
%o concat(vector(N+2-F, n, vector(1 + gmax(n-1), g, polcoeff(Qget(n+F-2, g-1), F))))
%o \\ _Gheorghe Coserea_, Mar 16 2016
%Y Row sums give A001147(n).
%Y Columns g=0-2 give: A000108, A002802, A006298.
%Y The last entries in the even rows give A035319.
%Y Cf. A270406, A270790, A270791.
%K nonn,tabf,nice
%O 0,3
%A _Dylan Thurston_
%E More terms and additional comments and references from _Valery A. Liskovets_, Apr 13 2006
%E Offset corrected by _Gheorghe Coserea_, Mar 17 2016