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

Author

Gheorghe Coserea, Mar 07 2016

Keywords

• nonn
• tabf

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.

Examples

			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]   ...
		

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.

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.

Programs

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

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

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.