A269919 Triangle read by rows: T(n,g) is the number of rooted maps with n edges on an orientable surface of genus g.

1, 2, 9, 1, 54, 20, 378, 307, 21, 2916, 4280, 966, 24057, 56914, 27954, 1485, 208494, 736568, 650076, 113256, 1876446, 9370183, 13271982, 5008230, 225225, 17399772, 117822512, 248371380, 167808024, 24635754, 165297834, 1469283166, 4366441128

Offset

0,2

Comments

Row n contains floor((n+2)/2) terms.

Equivalently, T(n,g) is the number of rooted bipartite quadrangulations with n faces of an orientable surface of genus g.

Links

Gheorghe Coserea, Rows n = 0..200, flattened

Sean R. Carrell, Guillaume Chapuy, Simple recurrence formulas to count maps on orientable surfaces, arXiv:1402.6300 [math.CO], 2014.

Formula

(n+1)/6 * T(n, g) = (4*n-2)/3 * T(n-1, g) + (2*n-3)*(2*n-2)*(2*n-1)/12 * T(n-2, g-1) + 1/2 * Sum_{k=1..n-1} Sum_{i=0..g} (2*k-1) * (2*(n-k)-1) * T(k-1, i) * T(n-k-1, g-i) for all n >= 1 and 0 <= g <= n/2, with the initial conditions T(0,0) = 1 and T(n,g) = 0 for g < 0 or g > n/2.

For column g, as n goes to infinity we have T(n,g) ~ t(g) * n^(5*(g-1)/2) * 12^n, where t(g) = (A269418(g)/A269419(g)) / (2^(g-2) * gamma((5*g-1)/2)) and gamma is the Gamma function.

Example

Triangle starts:
n\g    [0]          [1]          [2]          [3]          [4]
[0]    1;
[1]    2;
[2]    9,           1;
[3]    54,          20;
[4]    378,         307,         21;
[5]    2916,        4280,        966;
[6]    24057,       56914,       27954,       1485;
[7]    208494,      736568,      650076,      113256;
[8]    1876446,     9370183,     13271982,    5008230,     225225;
[9]    17399772,    117822512,   248371380,   167808024,   24635754;
[10]   ...

Mathematica

T[0, 0] = 1; T[n_, g_] /; g<0 || g>n/2 = 0; T[n_, g_] := T[n, g] = ((4n-2)/ 3 T[n-1, g] + (2n-3)(2n-2)(2n-1)/12 T[n-2, g-1] + 1/2 Sum[(2k-1)(2(n-k)- 1) T[k-1, i] T[n-k-1, g-i], {k, 1, n-1}, {i, 0, g}])/((n+1)/6);
Table[T[n, g], {n, 0, 10}, {g, 0, n/2}] // Flatten (* Jean-François Alcover, Jul 20 2018 *)

Prog

(PARI)
N = 9; 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, N, 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();
concat(vector(N+1, n, vector(1 + gmax(n-1), g, Qget(n-1, g-1))))

Crossrefs

Columns g=0-10 give: A000168, A006300, A006301, A104742, A215402, A238355, A238356, A238357, A238358, A238359, A238360.

Cf. A269418, A269419.

Same as A238396 except for the zeros.

Sequence in context: A021778 A095178 A289632 * A178418 A365637 A249270

Adjacent sequences: A269916 A269917 A269918 * A269920 A269921 A269922

Keyword

nonn,tabf

Author

Gheorghe Coserea, Mar 07 2016

Status

approved