cp's OEIS Frontend

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.

%I A035309 #99 Feb 06 2024 12:11:52
%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 Row n contains floor((n+2)/2) terms.
%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_, Dec 18 2007
%H A035309 Gheorghe Coserea, <a href="/A035309/b035309.txt">Rows n = 0..200, flattened</a>
%H A035309 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 A035309 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 A035309 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 A035309 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 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 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 A035309 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 A035309 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 A035309 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 A035309 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 A035309 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 A035309 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 A035309 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 A035309 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 A035309 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 A035309 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 A035309 (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 A035309 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 A035309 Triangle starts:
%e A035309 n\g    [0]        [1]        [2]        [3]        [4]        [5]
%e A035309 [0]    1;
%e A035309 [1]    1;
%e A035309 [2]    2;         1;
%e A035309 [3]    5,         10;
%e A035309 [4]    14,        70,        21;
%e A035309 [5]    42,        420,       483;
%e A035309 [6]    132,       2310,      6468,      1485;
%e A035309 [7]    429,       12012,     66066,     56628;
%e A035309 [8]    1430,      60060,     570570,    1169740,   225225;
%e A035309 [9]    4862,      291720,    4390386,   17454580,  12317877;
%e A035309 [10]   16796,     1385670,   31039008,  211083730, 351683046, 59520825;
%e A035309 [11]   ...
%t A035309 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 A035309 (PARI)
%o A035309 N = 10; F = 1; gmax(n) = n\2;
%o A035309 Q = matrix(N + 1, N + 1);
%o A035309 Qget(n, g) = { if (g < 0 || g > n/2, 0, Q[n+1, g+1]) };
%o A035309 Qset(n, g, v) = { Q[n+1, g+1] = v };
%o A035309 Quadric({x=1}) = {
%o A035309   Qset(0, 0, x);
%o A035309   for (n = 1, length(Q)-1, for (g = 0, gmax(n),
%o A035309     my(t1 = (1+x)*(2*n-1)/3 * Qget(n-1, g),
%o A035309        t2 = (2*n-3)*(2*n-2)*(2*n-1)/12 * Qget(n-2, g-1),
%o A035309        t3 = 1/2 * sum(k = 1, n-1, sum(i = 0, g,
%o A035309        (2*k-1) * (2*(n-k)-1) * Qget(k-1, i) * Qget(n-k-1, g-i))));
%o A035309     Qset(n, g, (t1 + t2 + t3) * 6/(n+1))));
%o A035309 };
%o A035309 Quadric('x + O('x^(F+1)));
%o A035309 concat(vector(N+2-F, n, vector(1 + gmax(n-1), g, polcoeff(Qget(n+F-2, g-1), F))))
%o A035309 \\ _Gheorghe Coserea_, Mar 16 2016
%Y A035309 Row sums give A001147(n).
%Y A035309 Columns g=0-2 give: A000108, A002802, A006298.
%Y A035309 The last entries in the even rows give A035319.
%Y A035309 Cf. A270406, A270790, A270791.
%K A035309 nonn,tabf,nice
%O A035309 0,3
%A A035309 _Dylan Thurston_
%E A035309 More terms and additional comments and references from _Valery A. Liskovets_, Apr 13 2006
%E A035309 Offset corrected by _Gheorghe Coserea_, Mar 17 2016