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

 

Logo

Invitation: celebrating 50 years of OEIS, 250000 sequences, and Sloane's 75th, there will be a conference at DIMACS, Rutgers, Oct 9-10 2014.

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

REFERENCES

Benoit Collins, Ion Nechita, Deping Ye, The absolute positive partial transpose property for random induced states, Arxiv preprint arXiv:1108.1935, 2011

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.

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

LINKS

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

Benoit Collins, Ion Nechita, Deping Ye, The absolute positive partial transpose property for random induced states, Random Matrices: Theory Appl. 01, 1250002 (2012).

I. P. Goulden and A. Nica, A direct bijection for the Harer-Zagier formula, J. Comb. Theory, A, 111, No. 2 (2005), 224-238.

B. Lass, Démonstration combinatoire de la formule de Harer-Zagier, C. R. Acad. Sci. Paris, Serie I, 333, No.3 (2001), 155-160.

E. T. Akhmedov and Sh. Shakirov, Gluing of Surfaces with Polygonal Boundaries, Dec 18, 2007, p. 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: A011132 A178627 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.

Content is available under The OEIS End-User License Agreement .

Last modified July 29 21:54 EDT 2014. Contains 245046 sequences.