login
This site is supported by donations to The OEIS Foundation.

 

Logo

The OEIS Foundation is grateful to everyone who made a donation during our Annual Appeal.     Visit the new and spectacular Pictures from the OEIS page!

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 5
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

1,3

COMMENTS

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

Table of n, a(n) for n=1..42.

E. T. Akhmedov and Sh. Shakirov, Gluing of Surfaces with Polygonal Boundaries, arXiv:0712.2448 [math.CO], 2007-2008, see p. 1.

Benoit Collins, Ion Nechita, 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.

T. R. S. Walsh and A. B. Lehman, Counting rooted maps by genus, J. Comb. Theory B 13 (1972), 192-218 (Tab.1).

FORMULA

Let c be 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(0<=g<=floor(n/2), a(n,g)*y^(n-2*g+1) ) = (2*n-1)!! * sum(0<=k<=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.

EXAMPLE

For n=0,..,6, we have the array:

    1

    1

    2    1

    5   10

   14   70   21

   42  420  483

  132 2310 6468 1485

The n-th row sum is (2n-1)!! = A001147(n).

The first three columns (for g=0,1,2) are respectively A000108 (Catalan; plane trees), A002802 and A006298. The last entries in the even rows form A035319.

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

CROSSREFS

First 3 cols are A000108, A002802, A006298.

Sequence in context: A178627 A247368 A019098 * A174218 A226308 A226309

Adjacent sequences:  A035306 A035307 A035308 * A035310 A035311 A035312

KEYWORD

nonn,tabf,nice

AUTHOR

Dylan Thurston

EXTENSIONS

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

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified February 9 08:53 EST 2016. Contains 268105 sequences.