This site is supported by donations to The OEIS Foundation.



Annual Appeal: Today, Nov 11 2014, is the 4th anniversary of the launch of the new OEIS web site. 70,000 sequences have been added in these four years, all edited by volunteers. Please make a donation (tax deductible in the US) to help keep the OEIS running.

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



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


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


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.


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.


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



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.


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


First 3 cols are A000108, A002802, A006298.

Sequence in context: A178627 A247368 A019098 * A174218 A226308 A226309

Adjacent sequences:  A035306 A035307 A035308 * A035310 A035311 A035312




Dylan Thurston


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



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 December 19 04:51 EST 2014. Contains 252175 sequences.