A035319 -id:A035319 - 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.

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

Offset: 0

Dylan Thurston

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

			Triangle starts:
n\g    [0]        [1]        [2]        [3]        [4]        [5]
[0]    1;
[1]    1;
[2]    2;         1;
[3]    5,         10;
[4]    14,        70,        21;
[5]    42,        420,       483;
[6]    132,       2310,      6468,      1485;
[7]    429,       12012,     66066,     56628;
[8]    1430,      60060,     570570,    1169740,   225225;
[9]    4862,      291720,    4390386,   17454580,  12317877;
[10]   16796,     1385670,   31039008,  211083730, 351683046, 59520825;
[11]   ...

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.
A. Mironov, A. Morozov, A. Popolitov, and Sh. Shakirov, Summing up perturbation series around superintegrable point, arXiv:2401.14392 [hep-th], 2024.
T. R. S. Walsh and A. B. Lehman, Counting rooted maps by genus, J. Comb. Theory B 13 (1972), 192-218 (Tab. 1).
Nikolai Wyderka and Andreas Ketterer, Probing the geometry of correlation matrices with randomized measurements, arXiv:2211.09610 [quant-ph], 2022.
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.

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.

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 *)

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

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

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

Offset corrected by Gheorghe Coserea, Mar 17 2016

A185259 Irregular triangle read by rows: coefficients in order of decreasing exponents of polynomials P_g(x) related to Hultman numbers.

Original entry on oeis.org

1, 1, 12, 8, 1, 72, 528, 704, 180, 1, 324, 8760, 53792, 98124, 56160, 8064, 1, 1344, 103040, 1759520, 9936360, 21676144, 19083456, 6356160, 604800, 1, 5436, 1054056, 41312704, 539233128, 2901894144, 7118351104, 8247838464, 4418632656, 988952832, 68428800, 1, 21816, 10106736, 823376896, 21574613676, 235937470944, 1230387808384, 3281254260864, 4608240745104, 3390175943424, 1247151098880, 204083712000, 10897286400

Offset: 1

N. J. A. Sloane, Jan 21 2012

Row n contains 2*n-1 terms.

Evaluating the polynomials at 1 gives A035319.

			Triangle begins:
[1] 1
[2] 1   12      8
[3] 1   72    528     704     180
[4] 1  324   8760   53792   98124    56160     8064
[5] 1 1344 103040 1759520 9936360 21676144 19083456 6356160 604800
[6] ...

Gheorghe Coserea, Rows n=1..101, flattened
Nikita Alexeev and Peter Zograf, Hultman numbers, polygon gluings and matrix integrals, arXiv preprint arXiv:1111.3061 [math.PR], 2011.
Robert Coquereaux and Jean-Bernard Zuber, Counting partitions by genus. II. A compendium of results, arXiv:2305.01100 [math.CO], 2023. See p. 9.

Cf. A035319, A185263.

P[n_, x_] := (f = (1-x)^(4n+1); s = Sum[-StirlingS1[2n+2+k, k+1]/ Binomial[2n+2+k, 2] x^k, {k, 0, 2n-2}]; f s + O[x]^(2n-1) // Normal);
row[n_] := CoefficientList[P[n, x], x] // Reverse;
Array[row, 7] // Flatten (* Jean-François Alcover, Sep 05 2018, after Gheorghe Coserea *)

P(n, v='x) = {
  my(x='x+O('x^(2*n-1)), f=(1-x)^(4*n+1),
     s=sum(k=0, 2*n-2, -stirling(2*n+2+k, k+1, 1)/binomial(2*n+2+k,2)*x^k));
  subst(Pol(f*s, 'x), 'x, v);
};
concat(vector(7, n, Vec(P(n))))
\\ test: N=50; vector(N, n, P(n,1)) == vector(N, n, (4*n)!/((2*n+1)!*4^n))
\\ Gheorghe Coserea, Jan 30 2018

More terms from Gheorghe Coserea, Jan 30 2018

A270790 Multiplier of polynomial P_n(x) arising from RNA combinatorics.

Original entry on oeis.org

1, 21, 11, 143, 88179, 111435, 111435, 1361270295, 1137235, 9945637, 16009448637, 19293438101, 3607872924887, 2630885818709841, 195084537038811, 45500599374052095, 1472444896343699846295, 1997334750675075735, 145805436799280528655, 107268833547674677179

Offset: 1

N. J. A. Sloane, Mar 28 2016

Gheorghe Coserea, Table of n, a(n) for n = 1..100
R. C. Penner, Moduli Spaces and Macromolecules, Bull. Amer. Math. Soc., 53 (2015), 217-268. See p. 259.

Cf. A035309, A035319, A270791.

G = 20; N = 3*G + 1; F = 1; gmax(n) = min(n\2, G);
Q = matrix(N+1, G+1); Qn() = (matsize(Q)[1] - 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, Qn(), 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)));
Kol(g) = vector(Qn()+2-F-2*g, n, polcoeff(Qget(n+F-2 + 2*g, g), F, 'x));
P(g) = {
  my(x = 'x + O('x^(G+2)));
  return(Pol(Ser(Kol(g)) * (1-4*x)^(3*g-1/2), 'x));
};
vector(G, g, content(P(g)))  \\ Gheorghe Coserea, Apr 17 2016

a(g) * P_g(0) = A035319(g) = (4*g-1)!!/(2*g+1), where P_g(x) is the polynomial associated with row g of the triangle A270791.

More terms from Gheorghe Coserea, Apr 17 2016

A270791 Triangle read by rows: coefficients of polynomials P_n(x) arising from RNA combinatorics.

Original entry on oeis.org

1, 1, 1, 158, 558, 135, 2339, 18378, 13689, 1575, 1354, 18908, 28764, 9660, 675, 617926, 13447818, 34604118, 23001156, 4534875, 218295, 525206428, 16383145284, 63886133214, 70424606988, 26926791930, 3567422250, 127702575, 50531787, 2134308548, 11735772822, 19350632598, 12106771137, 3063221550, 295973325, 8292375

Offset: 1

N. J. A. Sloane, Mar 28 2016

"... polynomials like these with nonnegative integral coefficients might reasonably be expected to be generating polynomials for some as yet unknown fatgraph structure."

			For n = 3 we have P_3(x) = 158*x^2 + 558*x + 135.
For n = 4 we have P_4(x) = 2339*x^3 + 18378*x^2 + 13689*x + 1575.
Triangle begins:
n\k  [1]        [2]        [3]        [4]        [5]        [6]
[1]  1;
[2]  1,         1;
[3]  158        558,       135;
[4]  2339,      18378,     13689,     1575;
[5]  1354,      18908,     28764,     9660,      675;
[6]  617926,    13447818,  34604118,  23001156,  4534875,   218295;
[7]  ...

Gheorghe Coserea, Rows n = 1..100, flattened
J. E. Andersen, R. C. Penner, C. M. Reidys, M. S. Waterman, Topological classification and enumeration of RNA structures by genus, J. Math. Biol. 65 (2013) 1261-1278
R. C. Penner, Moduli Spaces and Macromolecules, Bull. Amer. Math. Soc., 53 (2015), 217-268. See p. 259.

Cf. A035309, A035319, A270790.

G = 8; N = 3*G + 1; F = 1; gmax(n) = min(n\2, G);
Q = matrix(N+1, G+1); Qn() = (matsize(Q)[1] - 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, Qn(), 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)));
Kol(g) = vector(Qn()+2-F-2*g, n, polcoeff(Qget(n+F-2 + 2*g, g), F, 'x));
P(g) = {
  my(x = 'x + O('x^(G+2)));
  return(Pol(Ser(Kol(g)) * (1-4*x)^(3*g-1/2), 'x));
};
concat(vector(G, g, Vec(P(g) / content(P(g)))))  \\ Gheorghe Coserea, Apr 17 2016

The g.f. for column g>0 of triangle A035309 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. - Gheorghe Coserea, Apr 17 2016

More terms from Gheorghe Coserea, Apr 17 2016

A305872 Number of nonseparable rooted maps of genus n with one vertex and one face.

Original entry on oeis.org

1, 1, 17, 1259, 200589, 54766516, 22839203295, 13532959408258, 10826939105517381, 11256605684271733244, 14762470788227855508388, 23845795018908512860754771, 46527914721396710095597849515, 107904469663880176355586920421756, 293401777662120053352713701982623322

Offset: 0

R. J. Mathar, Jun 12 2018

nonn

Gheorghe Coserea, Table of n, a(n) for n = 0..200
T. R. S. Walsh, A. B. Lehman, Counting rooted maps by genus. III: Nonseparable maps, J. Combinatorial Theory Ser. B 18 (1975), 222-259.

Cf. A035319.

g := 1+x ;
for itr from 2 to 14 do
    g := g+a*x^itr;
    Ax := add(A035319(i)*x^i,i=0..itr+1) ;
    x*Ax^4 ;
    z := subs(x=%,g)-Ax ;
    z := expand(z) ;
    z := taylor(z,x=0,itr+1) ;
    z := convert(z,polynom) ;
    aa := solve(z,a) ;
    g := g-a*x^itr+aa*x^itr ;
    print(g) ;
end do:

seq(N) = {
  my(s = 1+'x*Ser(vector(N, n, (4*n)!/((2*n+1)!*4^n))));
  Vec(subst(s, 'x, serreverse('x*s^4)));
};
seq(14) \\ Gheorghe Coserea, Jun 13 2018

The g.f. A(x) satisfies A035319(x) = A[x*(A035319(x)^4)], where A035319 is the o.g.f. of A035319.

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A185259 Irregular triangle read by rows: coefficients in order of decreasing exponents of polynomials P_g(x) related to Hultman numbers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A270790 Multiplier of polynomial P_n(x) arising from RNA combinatorics.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

Extensions

A270791 Triangle read by rows: coefficients of polynomials P_n(x) arising from RNA combinatorics.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A305872 Number of nonseparable rooted maps of genus n with one vertex and one face.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

PARI

Formula

A118450 Number of rooted n-edge one-vertex one-face maps on a non-orientable surface (of genus n).

Views

Author

Keywords

Comments

References

Crossrefs

Extensions

A347951 a(n) = number of maximal chord diagrams by genus d^(||)_2n.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula