|
|
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.
|
|
12
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
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
|
|
LINKS
|
|
|
FORMULA
|
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
|
|
EXAMPLE
|
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] ...
|
|
MATHEMATICA
|
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 *)
|
|
PROG
|
(PARI)
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))))
|
|
CROSSREFS
|
The last entries in the even rows give A035319.
|
|
KEYWORD
|
nonn,tabf,nice
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|