ARS MATHEMATICA CONTEMPORANEA Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.) ARS MATHEMATICA CONTEMPORANEA 7 (2014) 263-280 Efficient enumeration of rooted maps of a given orientable genus by number of faces and vertices Timothy R. S. Walsh Department of Computer Science, University of Quebec in Montreal (UQAM), P. O. Box 8888, Station A, Montreal, Quebec, Canada, HC3-3P8 Alain Giorgetti * Department of Computer Science for Complex Systems, FEMTO-STInstitute (UMR 6174), University of Franche-Comté (UFC), 16 route de Gray, 25030 Besancon, France Received 11 February 2011, accepted 1 March 2013, published online 7 May 2013 We simplify the recurrence satisfied by the polynomial part of the generating function that counts rooted maps of positive orientable genus g by number of vertices and faces. We have written an optimized program in C++ for computing this generating function and constructing tables of numbers of rooted maps, and we describe some of these optimizations here. Using this program we extended the enumeration of rooted maps of orientable genus g by number of vertices and faces to g = 4, 5 and 6 and by number of edges to g = 5 and 6 and conjectured a further simplification of the generating function that counts rooted maps by number of edges. Our program is documented and available on request, allowing anyone with a sufficiently powerful computer to carry the calculations even further. Keywords: Efficient enumeration, rooted maps, orientable genus, generating functions Math. Subj. Class.: 05C30, 05A15 1 Introduction: definitions and history A map is defined topologically as a 2-cell imbedding of a connected graph, loops and multiple edges allowed, in a 2-dimensional surface. The faces of a map are the connected components of the complement of the graph in the surface. In this article the surface is * Corresponding author. E-mail addresses: walsh.timothy@uqam.ca (Timothy R. S. Walsh), alain.giorgetti@femto-st.fr (Alain Giorgetti) Abstract ©® This work is licensed under http://creativecommons.org/licenses/by/3.0/ 340 Ars Math. Contemp. 7 (2014) 337-340 assumed to be without boundary and orientable, with an orientation already attributed to it (clockwise, say), so that it is completely described by a non-negative integer g, its genus. For short, a map on a surface of genus g will be called a genus-g map. A planar map is a genus-0 map (a map on a sphere) and a toroidal map is a genus-1 map (a map on a torus or donut). If a map on a surface of genus g has v vertices, e edges and f faces, then by the Euler-Poincare formula [7, chap. 9] Two maps are equivalent if there is an orientation-preserving homeomorphism between their imbedding surfaces that takes the vertices, edges and faces of one map into the vertices, edges and faces of the other. A dart of a map or graph is a semi-edge. A loop is assumed to be incident twice with the same vertex, so that every edge, whether or not it is a loop, is incident to two darts. The degree of a vertex is the number of darts incident to it. The face incident to a dart d is the face incident to the edge containing d and on the left of an observer on d facing away from the vertex incident to d and the degree of a face is the number of darts incident to it. A rooted map is a map with a distinguished dart, its root. Two rooted maps are equivalent if there is an orientation-preserving homeomorphism between their imbedding surfaces that takes the vertices, edges, faces and the root of one map into the vertices, edges, faces and the root of the other. A combinatorial map is a connected graph with a cyclic order imposed on the darts incident to each vertex, representing the order in which the darts of a (topological) map are encountered during a rotation around the vertex according to the orientation of the imbedding surface. The darts incident to a face are encountered by successive application of the following pair of actions: go from the current dart to the dart on the other end of the same edge and then to the next dart incident to the same vertex according to the cyclic order. In this way the faces of a combinatorial map can be counted, so that its genus can be calculated from (1.1). Two combinatorial maps are equivalent if they are related by a map isomorphism - a graph isomorphism that preserves this cyclic order - with an analogous definition for the equivalence of two rooted combinatorial maps. It is worth noting that rooted combinatorial maps with e edges are in one-to-one correspondence with torsion-free subgroups of index 2e in the triangle group A(to, 2, to) = (x, y, z\y2 = xyz = 1} = Z * Z2 [12]. Rooted combinatorial maps are indeed a permutation representation of these groups. Details about this correspondence may be found e.g. in [13]. By enumerating maps with a given set of properties, whether rooted or not, we mean counting the number of equivalence classes of maps with these properties. It was shown in [12] that each equivalence class of topological maps is uniquely defined by an equivalence class of combinatorial maps; so for the purposes of enumeration, the term "map" can be taken to mean "combinatorial map". Let mg (v, f) be the number of rooted genus-g maps with v vertices and f faces. By face-vertex duality, this number is equal to the number mg (f, v) of rooted genus-g maps with f vertices and v faces. The generating function that counts rooted genus-g maps is the following formal power series in two variables u and w: v - e + f = 2(1 - g). (1.1) (1.2) v,f >1 Rooted maps were introduced in [15] because they are easier to count than unrooted T. R. S. Walsh and A. Giorgetti: Efficient enumeration of rooted maps... 265 maps; this is because only the trivial map automorphism preserves the root [16], so that rooted maps can be counted without considering map automorphisms. In [15], W. T. Tutte found a closed-form formula for the number of rooted planar maps with n edges. In [16], he found a parametric system of equations defining M0(w, u). In [1] D. Arques obtained the simpler expression Mo(w,u)= pq(1 - 2p - 2q) (1.3) with the parameters p and q defined by w = p(1 - p - 2q) (1.4) and u = q(1 - 2p - q), (1.5) where p = q = 0 when w = u = 0. In [16], a recursive formula was found for the number of rooted planar maps given the number of vertices, the number of edges, and the degree of the face containing the root; these numbers of maps were then added over all possible degrees of this face and the result expressed in terms of generating functions. In [17], the first author generalized this method to obtain a recursive formula for the number of maps of genus g with a distinguished dart in each vertex given the number of vertices and the degree of each one; these numbers were then multiplied by the appropriate factor and added over all possible non-increasing sequences of vertex-degrees summing to 2e to obtain the number of rooted maps of genus g with e edges and v vertices. A table of these numbers of maps with up to 14 edges appears in [17] (see [19] for a published account of this work and a table of maps with up to 11 edges) but no attempt was made there to express this result in terms of generating functions. We note here that a similar generalization in which the degrees of all the faces are known but only some of them have a distinguished edge on their boundary, and these faces must be of degree at least 3, appears in [8], where it is attributed to Tutte under the name of Tutte's recursion equations. In [5] an improvement on the method of [17] was introduced: to count rooted genus-g maps it is sufficient to know the degree of the first g + 1 vertices and to distinguish a dart of only the first vertex as the root, thus reducing the number of maps that have to be considered. Using doubly-rooted maps, D. Arques [2] obtained the analogue of (1.3) for toroidal maps: pq(1 - p - q) Mi(w,u) = -^—----j. (1.6) (1 - 2p - 2q)2 - 4pq From this result, he obtained a closed-form formula for the number of rooted toroidal maps with e edges and another one for the number of rooted toroidal maps with v vertices and f faces. In [6] a generating function was obtained for the number of rooted maps of genus 2 and 3 with e edges. In [9] the second author generalized (1.6) and obtained a general form for the generating function Mg (w, u) counting rooted maps of any genus g > 0: jit- , n pq(1 -p- q)pgfaq) n ~ Mg (w u) = 7-:-75g-3, (L7) (1 - 2p - 2q)2 - 4pq where Pg (p, q) is a symmetric polynomial in p and q of total degree bounded by 6g - 6 with integral coefficients (in what follows, unless otherwise specified, all the polynomials defined here are polynomials in p and q). 266 Ars Math. Contemp. 7(2014)263-280 Let us now briefly explain the interest of this result for rooted map counting. In [3, 9] the polynomials Pg [p, q] were calculated for g = 2 and 3. In this article we extend this calculation to g = 4, 5 and 6. To derive the generating function Mg (w, u) from Pg [p, q], we compute p and q as power series in w and u iteratively from (1.4) and (1.5) and then we replace p and q by their respective power series in (1.7) to obtain Mg(w, u). By (1.2) the number of rooted maps of genus g with v vertices and f faces is the coefficient of wv uf in Mg (w, u). In this way we enumerate rooted maps of genus 4, 5 and 6 with v vertices and f faces for any v and f greater than or equal to 1. The polynomial Pg in (1.7) is defined in terms of another polynomial Tg of degree bounded by 10g - 8 by Pg = ,L8) and that polynomial, in turn, is defined in terms of a family of polynomials Rg (n,..., nr) in p and q by g-1 Tg = Rg-1 (0,0) + £q(1 -p - q)Rj(0)Rg-j(0). (1.9) j=i The degree of the polynomial Rg (n,..., nr) is defined by the equation deg Rg (ni, ...,nr) = 2(n + ... + nr) + 7r + 10g - 12. (1.10) The polynomials Rg (ni,... ,nr) are defined recursively in terms of several other families of polynomials and a recursively-defined family of rational functions of p and q. We have two finite families of polynomials in p alone defined by the following two sets of equations. Ko(p) = -p; Ki(p) = -1 - p; k2 (p) = -1; (111) Km(p) = 0 for all m > 3. (1.11) Lo(p) = -p; Li(p) = -1 - 2p; l2(p) = -2 -p; L3 = -1; (1.12) Lk (p) =0 for all k > 4. In what follows, the parameter p will be omitted, so that these polynomials will be referred to as Km and Lk. We then have two polynomials H and J (in p and q) defined by J = q(1 - p - q) (1.13) and H = (1 - 2p - 2q)2 - 4pq. (1.14) Finally we have an infinite family (Ek) k> i of rational functions of p and q, all but the first two of which are polynomials, defined recursively by Ei =- 2 J (1 - p)2 -p - 4q + 2p2 +4q2 + 4pq E2 =--; (1.15) E3 = -1; Ek = - J(1 - p)2 £i=k-i EiEk+i-i for all k > 4. T. R. S. Walsh and A. Giorgetti: Efficient enumeration of rooted maps... 267 To make the recursive definition of the polynomials Rg (ni,..., nr) comprehensible, we first explain the abbreviations and conventions we use. For any positive integer r, [r] denotes the sequence (2,... ,r) if r > 2 and the empty sequence if r = 1. For any subsequence X of [r], [r] - X denotes the subsequence of the elements of [r] that are not in X. For any sequence (n2,..., nr) of integers, NX denotes the sequence of those n, such that i is in X and Nj denotes the sequence (n2,..., nj_i, nj+i,..., nr). By convention, a sum over an empty domain is equal to zero. The polynomials Ro(ni) are not defined. The anchor of this recursive definition is Ro(0,0) = (1 - p)2. (1.16) If g = 0 and r = 2 but (ni, n2) = (0,0), then we have Ro(ni,n2) = (1 - p)2 (-n2#£ni +n2+2 - (n + 1)E„1+„2+3) +2J(1 -p)2 ^ (-1)j+i HjEiRo(k,n2). (1.17) i+j+k=ni + i i>0, k0, k = (0,0) (j,X) = (g,[r]) terms = ]T KmHmRg_i(i, j, NH) (1.21) i+j+m=n i + i and term4 = V ( n^k+1=ni+n3 +2 LkHk+iRg (/, Nj ) \ (1 22) term4 = h V +(nj + 1) 1=ni+nj +3 LkHkRg(l, Nj) ) . (L22) It was shown in [9] that each polynomial Rg(ni,..., nr) is symmetric in all its variables. This was made possible by distinguishing a dart incident to each of the vertices whose degree is considered, which increases the size of the coefficients but does not increase the number of polynomials that have to be calculated. We note here that in the account of these results published in [3] formula (1.17) and the sum in (1.15) are missing; the formulas are presented correctly in [9]. At that time the second author, programming in Maple, calculated the polynomial Pg and the generating 340 Ars Math. Contemp. 7 (2014) 337-340 function Mg (w, u) for g = 2 and g = 3 (these results are published in [3]) and also computed the generating function that counts rooted maps of genus 4 by number of edges. This result was recently included in [13], where it was used to count both rooted and unrooted maps of genus 4 by number of edges. Recently, the second author extended his enumeration results to genus 5. The first author, programming mainly in C, optimized the calculation of the polynomials Rg(n\,..., nr) and thus extended the enumeration by number of vertices and faces, as well as by number of edges, to genus 6. Although each author used a different algorithm and a different programming language, we both obtained the same answers, and the numbers of rooted maps we calculated agree with the tables in [17], providing evidence of the correctness of our results. An account of these extensions is given in Sections 2 and 3. Tables of rooted map numbers are given in Appendix A. A discussion of the enumeration of rooted genus-g maps by number of edges appears in Section 4 and the polynomial part of each of the corresponding generating functions appears in Appendix B. Finally, a discussion of some open problems appears in Section 5. 2 Results from the Maple program A first version of the Maple code written in 1998 implemented recurrence relations between the rational functions introduced in [4] for the computation of the generating functions Mg. It was not designed for efficiency but for validating formulas from [4]. That code has also been used for validating the formulas from (1.2) through (1.22) for the first values of g, r and n\,...,nr (these formulas were first obtained from a long computation that was done by hand and is thus error-prone). When executed in 1998 with Maple V for computing M4(w, u) that code ran into a fundamental limitation (wired into the Maple kernel) of a maximal number of 65,535 terms in any polynomial. That old code has been recently replaced by a simpler code implementing directly the recursion between polynomials described by the formulas from (1.2) through (1.22). The code is short (less than 400 lines) and resembles the mathematical formulas as much as possible in order to detect errors. All the results obtained by this new code match known results in rooted map enumeration. For all these reasons, it can be considered as a reference for the debugging of optimized implementations. With a personal computer running under Windows XP with an Intel Core 2 Duo CPU at 2.19 GHz and 3.5 Gb of memory, and a Maple 14 release supporting larger objects, the next two generating functions M4(w, u) and M5(w, u) were successfully computed in 4 minutes and 5 hours, respectively. It was, however, not sensible to continue using this inefficient prototype for computing the next generating functions. A better idea was to write an independent implementation optimizing memory space and execution time. 3 Optimizations and the C program Aside from the advantage in execution speed that C has over Maple, the first author optimized the calculation of the polynomials Rg (n\,... ,nr ). One of these optimizations was made possible by the following observation. Proposition 3.1. For any (g, r) = (0,1) and any sequence n\,...,nr, the polynomial Rg (n1,..., nr) is divisible by (1 — p)2. Proof. We use generalized induction on the degree of a polynomial of the form Rg (n1,..., T. R. S. Walsh and A. Giorgetti: Efficient enumeration of rooted maps... 269 nr), which we call an R-polynomial. Basic step (degree 2). The only R-polynomial of degree 2 is Ro(0,0) = (1 - p)2: see (1.16). Induction step. Suppose that the degree d of a given R-polynomial Rg (ni, ..., nr), as defined by (1.10), is greater than 2 and that every R-polynomial of degree < d is divisible by (1 - p)2. We show that Rg(ni,... ,nr) is also divisible by (1 - p)2. Since every R-polynomial on the right side of equations (1.17), (1.19), (1.20), (1.21) and (1.22) is of degree < d, it follows from the induction hypothesis that each such polynomial is divisible by (1 - p)2. We examine each of these equations in turn. Equation (1.17). The first line contains a factor (1 - p)2. The term E„1+„2+3 is a polynomial for any non-negative ni and n2. The term E„1+„2+2 is a polynomial unless ni = n2 = 0, but in this case E„1+„2+2 is multiplied by n2 = 0; so the first line of (1.17) is divisible by (1 - p)2. In the second line, each term of the sum contains a polynomial R0(k, n2), which, by the induction hypothesis, is divisible by (1 - p)2. This factor of (1 - p)2 could be cancelled by Ei or E2, but the sum is nevertheless a polynomial, and the factor (1 - p)2 by which the sum is multiplied ensures that the second line of (1.17) too is divisible by (1 - p)2; so the right side of (1.17) is divisible by (1 - p)2. Equation (1.19). By an argument similar to the one used for the second line of (1.17), the right side of (1.19) is divisible by (1 - p)2. Equations (1.20)-(1.22). Each term in the sum contains at least one R-polynomial that is divisible by (1 - p)2; so the right side of each of these equations is divisible by (1 - p)2. It follows from (1.18) that Rg(ni,..., nr) is divisible by (1 - p)2, which completes the proof. □ We now modify equations (1.8)-(1.10), and (1.16)-(1.22) in the light of Proposition 3.1. We introduce a new family of polynomials (which we call S-polynomials) defined by Sg (ni, ..., nr) = Rg (ni,...,nr )/(1 - p)2 (3.1) and we also let Ug = Tg/(1 - p)2. (3.2) Then Ug is a polynomial of degree 10(g - 1) and (1.8)-(1.10) become (3.3)-(3.5), respectively. Pg = (1 -pg4g-4, (33) g-i Ug = Sg-i (0, 0) + q(1 - p - q) (1 - p)2 £ Sj (0)Sg-j (0). (3.4) j=i deg Sg (ni,...,nr) = 2(ni + ... + nr) + 7(r - 2) + 10g. (3.5) Also, (1.16)-(1.22) become (3.6)-(3.12), respectively. So(0,0) = 1, (3.6) 340 Ars Math. Contemp. 7 (2014) 337-340 So(n1,U2) = (-U2HEni+n2+2 - (n + 1)E„1+„2+3) +2J(1 - p)2 ^ (-1)j+1 Hj EiS0(k,n2). (3.7) i+j + k=n 1 +1 i>0, k0, k 0; so these polynomials do not have to be defined. All the S-polynomials are stored in a single one-dimensional array s. A preliminary recursion does not calculate any of these polynomials. Instead, it calculates all the quadruples (d,g,r,c) of parameters of the S-polynomials that will later be calculated, where d = deg Sg(n1,..., nr) and c is an integer coding the sequence (n1,... ,nr), and stores the list of quadruples in four parallel arrays, one array for each of the four parameters d, g, r, c and one element of all four arrays for each quadruple (d, g, r, c). The program then sorts the four parallel arrays by degree d using bucket sort, computes the number of S-polynomials that have to be calculated and the total number of terms in these polynomials and stores in two arrays the index in s and the one in the four parallel arrays of the first term for each degree d. Then the S-polynomials are calculated in increasing order of their T. R. S. Walsh and A. Giorgetti: Efficient enumeration of rooted maps... 271 degree and stored in s. This can be done non-recursively because all the S-polynomials that need to be used will have already been stored and need only be found by searching the four parallel arrays, starting with the first index for the appropriate degree d, for the appropriate parameters, and adding (d + 1)(d + 2)/2 to the index in s each time the index in the four parallel arrays is increased by 1. Once the last polynomial Sg-1(0,0) has been calculated, first (3.4) is used to calculate Ug and then (3.3) is used to calculate Pg and its coefficients are stored in a text file, which is available from the first author on request. The number of S-polynomials that have to be calculated is roughly the total number of partitions of all the positive integers up to 10(g - 1). For each of these polynomials, the most expensive calculation is term6, because the sum there runs over all the partitions of the sequence [r] = (2,..., r), where r can be as great as g + 1, and involves multiplying two S-polynomials. The time-complexity of calculating Pg is therefore exponential in g, but the optimizations made here nevertheless made it possible to calculate Pg for a greater value of g than was possible previously. Another program computes a table of numbers of rooted genus-g maps counted by number of vertices and faces by reading this file and using (1.2) if g > 1 or (1.3) if g = 0. Tables of numbers of rooted genus-g maps for any g < 6 and with up to any reasonable number of edges are available from the first author on request. The programs were written mainly in C. The one that computes the polynomials is about 2000 lines long and the one that computes the tables is about 300 lines long. They both use the C++ library CLN to do arithmetic on big integers because CLN reads arithmetic expressions in C that use only addition, multiplication and subtraction; only statements involving quotients, remainders, input/output of big integers and file management had to be modified. Since CLN requires a GNU compiler, XCODE was downloaded and installed by Jerome Tremblay, a computer technician at UQAM, who also downloaded and installed CLN and wrote sample C++ statements for input/output of big numbers and file management. The programs were executed on a 2004 Macintosh GR4 computer. The time taken to compute the polynomial Pg varied from run to run. In Table 1 we show, for each g from 1 to 6, the number of S-polynomials that were calculated, the total number of terms in all these S-polynomials, and a typical execution time. Once the S-polynomials had been computed and stored, it took the computer only 48 seconds to make a table of numbers of genus-6 maps with up to 42 edges counted by number of vertices and faces. Source codes for both programs are included in release 0.3.2 and higher of the MAP project [11]. The polynomials P2 and P3 appear in [3]. The polynomials P4, P5 and P6 are too large to be reproduced here. The coefficients of the polynomials Pg [p, q] for 1 < g < 6 are included in the MAP project and available from the first author on request. For 1 < g < 6 tables of numbers of rooted genus-g maps up to 20 edges are given in Appendix A. More numbers of rooted genus-g maps for any g < 6 and with up to any reasonable number of edges can be obtained from code included in the MAP project and are available from the first author on request. 4 Counting by number of edges To compute the generating function Mg(z) = z2g_2Mg(z, z) that counts rooted genus-g maps by number of edges alone, we use the substitution obtained in [13], which is a more compact form of the one obtained in [9] and published in [3]. Let p = q = m, (4.1) 340 Ars Math. Contemp. 7 (2014) 337-340 g number of S-polynomials total number of terms execution time 1 1 1 instantaneous 2 16 507 1 second 3 67 7407 10 seconds 4 205 49796 2 minutes 5 543 235410 20 minutes 6 1314 900114 3.5 hours Table 1: Evaluation of the computation cost where z = m(1 — 3m) and m = 0 when z = 0. (4.2) By substituting from (4.1) into (1.4) and (1.5) to express w and u in terms of m and then substituting into (1.7), we obtain the following equation for g > 1: M (z)= m2g(1 — 3m)2g-2P5(m,m) g() (1 — 6m)5s-3(1 — 2m)5g-4 . (.3) For g = 0, we substitute into (1.3) instead of (1.7) and obtain M0(z) = (1 — 3m)-2(1 — 4m). (4.4) The first author computed Mg (z) from the computed values of Mg (w, u) for g < 6. The program divides the polynomial Pg (m, m) by 1 — 2m as often as possible. The program then divides the resulting polynomial by 2 and by 3 as often as possible, extracts the appropriate constant factor and then stores the resulting generating function in another text file, also available from the first author. The second author computed Mg (z) directly for g < 6. We then compared our formulas and verified that they agree. The formulas for Pg (m, m) for 1 < g < 6 appear in Appendix B. Now Pg (m, m) is of degree 6g — 6, but we found experimentally in 2009 that for 1 < g < 6, Pg(m, m) is divisible by (1 — 2m)2g-2, so that the quotient is only of degree 4g — 4, and we conjectured that this is the case for any positive integer g. In 2010, the second author proved that conjecture [10]. 5 Some interesting open problems The recurrences satisfied by the R- and ^-polynomials both result from proofs by induction. After the right conjecture has been guessed by observing the first computed terms, these proofs are not difficult to find, but they are tedious and error-prone due to the length of the expressions involved. Thus they are good candidates for automation. We plan to develop a suitable formal framework for assisting this kind of proofs with a computer algebra system. The challenge is to shorten the chain of conjectures and proofs about the general pattern of generating functions for counting rooted maps. Once the numbers of rooted maps of genus up to g are known, the number of unrooted maps up to genus g can be calculated using the methods presented in [14]. As was mentioned above, the second author collaborated with A. Mednykh to count rooted and unrooted maps of genus 4 by number of edges [13]. It would be interesting to count unrooted genus-g maps by number of vertices and faces for as many values of g as possible (see [18] for an account of the progress made on this problem). T. R. S. Walsh and A. Giorgetti: Efficient enumeration of rooted maps... 273 6 Acknowledgments The authors are grateful to Roman Nedela, Alexander Mednykh and the anonymous referees for helpful comments and suggestions. References [1] D. Arques, Une relation fonctionnelle nouvelle sur les cartes planaires pointees, J. Comb. Theory B 39 (1985), 27-42. [2] D. Arques, Relations fonctionnelles et denombrement des cartes pointees sur le tore, J. Comb. Theory B 43 (1987), 253-274. [3] D. Arques and A. Giorgetti, Enumeration des cartes pointees de genre quelconque en fonction des nombres de sommets et de faces, J. Comb. Theory B 77 (1999), 1-24. [4] D. Arques and A. Giorgetti, Counting rooted maps on a surface, Theor. Comput. Sci. 234 (2000), 255-272. [5] E. A. Bender and E. R. Canfield, The asymptotic number of rooted maps on a surface, J. Comb. Theory A 43 (1986), 244-257. [6] E. A. Bender and E. R. Canfield, The number of rooted maps on an orientable surface, J. Comb. Theory B 53 (1991), 293-299. [7] H. S. M. Coxeter, Regular Polytopes, 3rd ed., Dover, New York, 1973. [8] B. Eynard and N. S. Orantin, Topological recursion in enumerative geometry and random matrices, J. Phys. A-Math. Theor. 42 (2009), 293001. [9] A. Giorgetti, Combinatoire bijective et énumérative des cartes pointées sur une surface, PhD thesis, Universite de Marne-la-Vallee, Institut Gaspard Monge, 1998, http://tel. archives-ouvertes.fr/tel-00724977. [10] A. Giorgetti, Guessing a Conjecture in Enumerative Combinatorics and Proving It with a Computer Algebra System, in: T. Jebelean, M. Mosbah and N. Popov (eds.), SCSS'10, July 2010, pp. 5-18. [11] A. Giorgetti, MAP project release 0.3.2, https://sourceforge.net/projects/ combi/files/map/, January 2013. [12] G. A. Jones and D. Singerman, Theory of maps on orientable surfaces, Proc. London Math. Soc. 37 (1978), 273-307. [13] A. Mednykh and A. Giorgetti, Enumeration of genus four maps by number of edges, Ars Math. Contemp. 4 (2011), 351-361. [14] A. Mednykh and R. Nedela, Enumeration of unrooted maps of a given genus, J. Comb. Theory B 96 (2006), 706-729. [15] W. T. Tutte, A census of planar maps, Canad. J. Math. 15 (1963), 249-271. [16] W. T. Tutte. On the enumeration of planar maps. Bull. Amer. Math. Soc. 74 (1968), 64-74. [17] T. R. S. Walsh, Combinatorial enumeration of non-planar maps, PhD thesis, University of Toronto, 1971. [18] T. R. S. Walsh, A. Giorgetti and A. Mednykh, Enumeration of unrooted orientable maps of arbitrary genus by number of edges and vertices, Discrete Math. 312 (2012), 2660-2671. [19] T. R. S. Walsh and A. B. Lehman, Counting rooted maps by genus I, J. Comb. Theory B 13 (1972), 192-218. 340 Ars Math. Contemp. 7 (2014) 337-340 Appendix A Number mg (v, f) of rooted maps of genus g with e edges and v vertices, for 1 < g < 6 and 2g < e < 20. Lines whose column of v is empty give the total number mg (e) of rooted maps of genus g with e edges. e v g = 1 g = 2 g = 3 2 1 1 2 1 3 1 10 3 2 10 3 20 4 1 70 21 4 2 167 4 3 70 4 307 21 5 1 420 483 5 2 1720 483 5 3 1720 5 4 420 5 4280 966 6 1 2310 6468 1485 6 2 14065 15018 6 3 24164 6468 6 4 14065 6 5 2310 6 56914 27954 1485 7 1 12012 66066 56628 7 2 100156 258972 56628 7 3 256116 258972 7 4 256116 66066 7 5 100156 7 6 12012 7 736568 650076 113256 8 1 60060 570570 1169740 8 2 649950 3288327 2668750 8 3 2278660 5554188 1169740 8 4 3392843 3288327 8 5 2278660 570570 8 6 649950 8 7 60060 8 9370183 13271982 5008230 9 1 291720 4390386 17454580 9 2 3944928 34374186 66449432 9 3 17970784 85421118 66449432 9 4 36703824 85421118 17454580 9 5 36703824 34374186 9 6 17970784 4390386 9 7 3944928 9 8 291720 9 117822512 248371380 167808024 10 1 1385670 31039008 211083730 T. R. S. Walsh and A. Giorgetti: Efficient enumeration of rooted maps... 275 e v g = i g = 2 g = 3 10 2 22764165 313530000 1171704435 10 3 129726760 1059255456 1955808460 10 4 344468530 1558792200 1171704435 10 5 472592916 1059255456 211083730 10 6 344468530 313530000 10 7 129726760 31039008 10 8 22764165 10 9 1385670 10 1469283166 4366441128 4721384790 11 1 6466460 205633428 2198596400 11 2 126264820 2583699888 16476937840 11 3 875029804 11270290416 40121261136 11 4 2908358552 22555934280 40121261136 11 5 5188948072 22555934280 16476937840 11 6 5188948072 11270290416 2198596400 11 7 2908358552 2583699888 11 8 875029804 205633428 11 9 126264820 11 10 6466460 11 18210135416 73231116024 117593590752 12 1 29745716 1293938646 20465052608 12 2 678405090 19678611645 196924458720 12 3 5593305476 106853266632 647739636160 12 4 22620890127 276221817810 945068384880 12 5 50534154408 375708427812 647739636160 12 6 65723863196 276221817810 196924458720 12 7 50534154408 106853266632 20465052608 12 8 22620890127 19678611645 12 9 5593305476 1293938646 12 10 678405090 12 11 29745716 12 224636864830 1183803697278 2675326679856 13 1 135207800 7808250450 174437377400 13 2 3550829360 140725699686 2079913241120 13 3 34225196720 925572602058 8789123742880 13 4 164767964504 2979641557620 17326957790896 13 5 448035881592 5235847653036 17326957790896 13 6 729734918432 5235847653036 8789123742880 13 7 729734918432 2979641557620 2079913241120 13 8 448035881592 925572602058 174437377400 13 9 164767964504 140725699686 13 10 34225196720 7808250450 13 11 3550829360 13 12 135207800 13 2760899996816 18579191525700 56740864304592 14 1 608435100 45510945480 1384928666550 14 2 18182708362 955708437684 19925913354061 14 3 201976335288 7454157823560 104395235785256 14 4 1137369687454 29079129795702 264477214235234 14 5 3682811916980 63648856688592 357391270819604 14 6 7302676928666 82234427131416 264477214235234 14 7 9145847808784 63648856688592 104395235785256 14 8 7302676928666 29079129795702 19925913354061 14 9 3682811916980 7454157823560 1384928666550 14 10 1137369687454 955708437684 14 11 201976335288 45510945480 14 12 18182708362 14 13 608435100 14 33833099832484 284601154513452 1137757854901806 15 1 2714556600 257611421340 10369994005800 340 Ars Math. Contemp. 7 (2014) 337-340 e v g = i g = 2 g = 3 iS 2 91B9218S080 6216S914V2V28 1V6BSVSB09SSB20 iS B 11S6128848680 S6SB244V160SB6 111SS2SS002S0V60 iS 4 VS069010S1000 2616BV840B42860 BS0S01861800B600 iS S 28442B1624V080 694146691V4S820 608VSS8B11B98000 iS 6 6V1VBVB9068V60 Í11V2S9292848016 608VSS8B11B98000 iS V 1024B2266S4S800 Í11V2S9292848016 BS0S01861800B600 iS 8 1024B2266S4S800 694146691V4S820 111SS2SS002S0V60 iS 9 6V1VBVB9068V60 2616BV840B42860 1V6BSVSB09SSB20 iS 10 28442B1624V080 S6SB244V160SB6 10B6999400S800 iS ii VS069010S1000 6216S914V2V28 iS 12 11S6128848680 2SV611421B40 iS 1B 91B9218S080 iS 14 2V14SS6600 iS 41B61091V006000 42V2100949982600 21V896S9909226960 i6 1 1202160V800 14221S6202V40 VB920866B62200 i6 2 4S20VVS62620 B898S2V9V4S2B0 1461629029629B40 i6 B 644VSBB9B8280 40V6SB880116680 109BB9S9V20960V60 i6 4 4VV002B4SS1918 22006269486B1B86 4149124291S292B06 i6 S 2084624224281S2 692841B2B49S9820 89B90908VB2820144 i6 6 SV6218VS22VV4V6 1BS189844S246B6B0 1148990V02VS212424 i6 V 10466VVV4V6V2B60 1684244S2BSS60944 89B90908VB2820144 i6 8 12V4461449989V1S 1BS189844S246B6B0 4149124291S292B06 i6 9 10466VVV4V6V2B60 692841B2B49S9820 109BB9S9V20960V60 i6 10 SV6218VS22VV4V6 22006269486B1B86 1461629029629B40 i6 11 2084624224281S2 40V6SB880116680 VB920866B62200 i6 12 4VV002B4SS1918 B898S2V9V4S2B0 i6 1B 644VSBB9B8280 14221S6202V40 i6 14 4S20VVS62620 i6 iS 1202160V800 i6 S04640B0B006692V 6B0B461V1B9V99916 401602B9280SB41924 iV i S289S0V4B20 V68B009S44980 S0S29V8291BB240 iV 2 220SBS9B90S92 2B692B660B9V1V2 Í14604119B4448048 iV B BS1SS92B8V2640 281S9ÍBB91V1S4S2 99V2V841192820016 iV 4 29BBV00969SVS04 1V4861429S61BB684 44VV0888V118S04600 iV S 1461B0VSVB81B824 642B2028100V041S6 Í16S1V21B6S42282424 iV 6 4660202610SB2480 148VSS2684982864B6 18SV9VS64S02BS18VS2 iV V 9908V486S1241088 2246862V840V291148 18SV9VS64S02BS18VS2 iV 8 14BVB1B6466094880 2246862V840V291148 Í16S1V21B6S42282424 iV 9 14BVB1B6466094880 148VSS2684982864B6 44VV0888V118S04600 iV 10 9908V486S1241088 642B2028100V041S6 99V2V841192820016 iV 11 4660202610SB2480 1V4861429S61BB684 Í14604119B4448048 iV 12 1461B0VSVB81B824 281S9ÍBB91V1S4S2 S0S29V8291BB240 iV 1B 29BBV00969SVS04 2B692B660B9V1V2 iV 14 BS1SS92B8V2640 V68B009S44980 iV iS 220SBS9B90S92 iV 16 S289S0V4B20 iV 61468BS91SB9S46S6 9164404V60481460S6 Vi6S1004B928i4i4i60 i8 i 2B141S9S01S0 40V2920V226400 BBB1B09V410S9B00 i8 2 1062V9S601924S Í40109VS461619B6 8S6940991VB90VS10 i8 B 18V9S9014S6S840 18V4B1884980S6288 8SSVV9B29B6VVB6840 i8 4 1VSB94S289216484 1B2B4469S964811V20 44V0S4V99198S864B22 i8 S 98SV66S4VV08S8B2 SS9BVBB6V4624906S6 iBV6VB19i602i00Vi404 i8 6 BS8B90S2BSV4221B2 iSiiVi8920VV89S1024 26S222B60S6202SSS206 i8 V 8V9B094BB0SV42S12 2V10B82626VSS160416 B2904419BV892V91SBV6 i8 8 149B144VV24S194262 B2861SVS60248860SB2 26S222B60S6202SSS206 i8 9 1VV882V00BSBVSV460 2V10B82626VSS160416 iBV6VB19i602i00Vi404 i8 10 149B144VV24S194262 iSiiVi8920VV89S1024 44V0S4V99198S864B22 i8 11 8V9B094BB0SV42S12 SS9BVBB6V4624906S6 8SSVV9B29B6VVB6840 i8 12 BS8B90S2BSV4221B2 1B2B4469S964811V20 8S6940991VB90VS10 i8 1B 98SV66S4VV08S8B2 18V4B1884980S6288 BBB1B09V410S9B00 i8 14 1VSB94S289216484 Í40109VS461619B6 i8 iS 18V9S9014S6S840 40V2920V226400 i8 16 1062V9S601924S i8 1V 2B141S9S01S0 T. R. S. Walsh and A. Giorgetti: Efficient enumeration of rooted maps... 277 e v g = 1 g = 2 g = 3 18 747672504476150374 13154166812674577412 124314235272290304540 19 1 1007340018300 212347275857640 21280393666593600 19 2 50668344988068 8089830217844928 614960028331370816 19 3 987658610225052 120789163612555200 6968569097113244096 19 4 10229201477344752 960323177351524512 41790549086980226368 19 5 64309102366765200 4616545437250956192 149789855223187292608 19 6 263868150558327376 14358354462488121408 341505418008822731328 19 7 738178726378902064 30044423965980553536 511895831411154922176 19 8 1446563778096423816 43241609165618454096 511895831411154922176 19 9 2017523504473479992 43241609165618454096 341505418008822731328 19 10 2017523504473479992 30044423965980553536 149789855223187292608 19 11 1446563778096423816 14358354462488121408 41790549086980226368 19 12 738178726378902064 4616545437250956192 6968569097113244096 19 13 263868150558327376 960323177351524512 614960028331370816 19 14 64309102366765200 120789163612555200 21280393666593600 19 15 10229201477344752 8089830217844928 19 16 987658610225052 212347275857640 19 17 50668344988068 19 18 1007340018300 19 9083423595292949240 186700695099591735024 2105172926498512761984 20 1 4365140079300 1090848505817070 132216351453357600 20 2 239250231713210 45732525474843801 4257157940494918160 20 3 5110652802256260 756589971284883792 54217755730994858080 20 4 58364244137596695 6716133365837116980 369061676845849000520 20 5 407372683115470800 36362952155187558600 1518921342035154605600 20 6 1870153808268516280 128656798319026864068 4031165546220945277040 20 7 5905479331377981200 309859885439753598768 7151648337964982801760 20 8 13196809961724011350 520516978029736518606 8640883781524178188980 20 9 21241931655650633720 617910462111714896820 7151648337964982801760 20 10 24868664942648145372 520516978029736518606 4031165546220945277040 20 11 21241931655650633720 309859885439753598768 1518921342035154605600 20 12 13196809961724011350 128656798319026864068 369061676845849000520 20 13 5905479331377981200 36362952155187558600 54217755730994858080 20 14 1870153808268516280 6716133365837116980 4257157940494918160 20 15 407372683115470800 756589971284883792 132216351453357600 20 16 58364244137596695 45732525474843801 20 17 5110652802256260 1090848505817070 20 18 239250231713210 20 19 4365140079300 20 110239596847544663002 2623742783421329300190 34899691847703927826500 340 Ars Math. Contemp. 7 (2014) 337-340 e v g = 4 g = 5 g = 6 8 1 22S22S 8 22S22S 9 1 12B1V8VV 9 2 12B1V8VV 9 246BSVS4 10 1 BS168B046 S9S2082S 10 2 V92SB401S 10 B BS168B046 10 149S90010V S9S2082S 11 1 V0B4SB8S11 4B04016990 11 2 2622S260226 4B04016990 11 B 2622S260226 11 4 V0B4SB8S11 11 66S19S9V4V4 86080BB980 12 1 1111S9V40692 1S89S9VS4226 24B2SV0BB2S 12 2 600B98249SS0 BS4949166S6S 12 B 99B49482V480 1S89S9VS4226 12 4 600B98249SS0 12 S 1111S9V40692 12 241661080V964 6V28686VS01V 24B2SV0BB2S 1B 1 1480S9B01B900 40B4VBS9S9800 220814B028BVS 1B 2 10V4BV9V9111B2 1480S4SVBB9920 220814B028BVS 1B B 2SV662BS4SVB00 1480S4SVBB9920 1B 4 2SV662BS4SVB00 40B4VBS9S9800 1B S 10V4BV9V9111B2 1B 6 1480S9B01B900 1B VS9812S2V64664 BV680B86S99440 44162860S6VS0 14 1 1VB0219062SV20 V9SSB49VV60100 100940VV1124B60 14 2 160SV6S94V66S88 420V9VB06S22S02 22BV9001B148S00 14 B S1VS929626V2296 6916S0S82088SB6 100940VV1124B60 14 4 VS0260619S02B10 420V9VB06S22S02 14 S S1VS929626V2296 V9SSB49VV60100 14 6 160SV6S94V66S88 14 V 1VB0219062SV20 14 214120411S6B1S18 1692BS21906SBV40 42S6V1SSSB9V220 1S 1 1822B1849209410 1B02VV2V18028600 B1B0208V69V8BV80 1S 2 20890BS241981688 9220982S1V96S400 11B4402844844B8B2 1S B 861S949B11B108V2 218SBVS8VB6216200 11B4402844844B8B2 1S 4 16V891186021SS860 218SBVS8VB6216200 B1B0208V69V8BV80 1S S 16V891186021SS860 9220982S1V96S400 1S 6 861S949B11B108V2 1B02VV2V18028600 1S V 20890BS241981688 1S 8 1822B1849209410 1S SSBS26V0009B1S660 64VSS02V944420400 289484V44B64SS224 16 1 1V6B184SV1VB0010 184VS99V006212200 V4S2069VV0V149S80 16 2 24B2SS9012V6SSSB1 166V1BS1V116449940 B8V6891460S029V186 16 B 12B9810428S41B2SB6 S2888VVS102SS84600 6BB8B2SB6898S19848 16 4 B0919V8V10988V18B8 V626846V466BSB6626 B8V6891460S029V186 16 S 41S6912944042B0V48 S2888VVS102SS84600 V4S2069VV0V149S80 16 6 B0919V8V10988V18B8 166V1BS1V116449940 16 V 12B9810428S41B2SB6 184VS99V006212200 16 8 24B2SS9012V6SSSB1 16 9 1V6B184SV1VB0010 T. R. S. Walsh and A. Giorgetti: Efficient enumeration of rooted maps... 279 e v g = 4 g = 5 g = 6 16 1334226671709010578 2190839204960030106 1558252224413413380 17 1 15894791312284170 233454817237201560 1457897216520222060 17 2 258634264294653390 2595050050431235488 10115530661997850556 17 3 1587135819804394530 10499075716384241952 23746474580826741940 17 4 4892650539994184868 20269771718252599536 23746474580826741940 17 5 8419549939292302908 20269771718252599536 10115530661997850556 17 6 8419549939292302908 10499075716384241952 1457897216520222060 17 7 4892650539994184868 2595050050431235488 17 8 1587135819804394530 233454817237201560 17 9 258634264294653390 17 10 15894791312284170 17 30347730709395639732 67194704604610557072 70639804918689629112 18 1 134951136993773100 2682208751185413450 24464684545968004800 18 2 2548272396065512974 35801820369640556595 215810538282954699872 18 3 18451302662846918700 178505550201444784920 675870370096399329024 18 4 68503375296263488977 439591872915483185214 970559177597162956688 18 5 145737674581607574840 588564117958709029644 675870370096399329024 18 6 186553519919803261860 439591872915483185214 215810538282954699872 18 7 145737674581607574840 178505550201444784920 24464684545968004800 18 8 68503375296263488977 35801820369640556595 18 9 18451302662846918700 2682208751185413450 18 10 2548272396065512974 18 11 134951136993773100 18 657304672067357799042 1901727022434216910002 2802850363447807024080 19 1 1088243826731751690 28449551653853229900 362610922310040035940 19 2 23532893106071038404 447016944351510642564 3931547761898967889520 19 3 197822824662547694148 2677324515710001081372 15658846910857993085360 19 4 866831237081712285138 8127109896970086044280 30002691954232352277608 19 5 2221381417843144801098 13881153040572190501512 30002691954232352277608 19 6 3515647035511186627416 13881153040572190501512 15658846910857993085360 19 7 3515647035511186627416 8127109896970086044280 3931547761898967889520 19 8 2221381417843144801098 2677324515710001081372 362610922310040035940 19 9 866831237081712285138 447016944351510642564 19 10 197822824662547694148 28449551653853229900 19 11 23532893106071038404 19 12 1088243826731751690 19 13652607304062788395788 50322107898515282999256 99911395098598706576856 20 1 8391311316938069520 281858111998039476900 4848655679592076350570 20 2 205518653220527665304 5131008990500486096250 63004600211616713352227 20 3 1979281881126113225376 36188783145801243558900 308528931105126354302392 20 4 10071757699155275906824 131989618396827099239715 751928550048308520251566 20 5 30468100266480917147760 277921666244135490925320 1003326321163364778495004 20 6 58089920897558352891672 354556747218700475500140 751928550048308520251566 20 7 71823371612912533887168 277921666244135490925320 308528931105126354302392 20 8 58089920897558352891672 131989618396827099239715 63004600211616713352227 20 9 30468100266480917147760 36188783145801243558900 4848655679592076350570 20 10 10071757699155275906824 5131008990500486096250 20 11 1979281881126113225376 281858111998039476900 20 12 205518653220527665304 20 13 8391311316938069520 20 273469313030628783700080 1257582616997225194094310 3259947795252652107008514 340 Ars Math. Contemp. 7 (2014) 337-340 Appendix B Polynomial Pg (m, m)/( 1 — 2m)(2g-2) in the generating function Mg (z). Pg(m,m)/(1 - 2m)(2g-2) 1 3(7-32 - 70m + 295m2 - 636m3 + 588m4) 165 - 2596m + 19835m2 - 102138m3 + 397742m4 -1162744m5 + 2360496m6 - 2918016m7 + 1642656m8 25025 - 465894m + 4245462m2 - 28633200m3 +178608786m4 - 1025233956m5 + 4855070265m6 -17709582732m7 + 48202134300m8 - 95026128096m9 +128766120048m10 - 107657028288m11 + 41956066368m1' 6613425 - 128153480m + 1123286598m2 - 7641539820m3 +68489369190m4 - 681945904584m5 + 5453799804351m6 -33175983024306m7 + 157025924018370m8 -590662433458296m9 + 1778501684246544m10 -4258112783048352m11 + 7946769062433024m12 -11156448512891520m13 + 11087677481748480m14 -6955529138076672m15 + 2071316467035648m16 900951975 - 16624244750m + 105922471285m2 -402327939748m3 + 9014122899102m4 -183050473605084m5 + 2152106046117936m6 -17716916701552824m7 + 113738504396139378m8 -602051461456822740m9 + 2694620167659984726m10 -10264333975933057272m11 + 33144207748349404248m12 -89851078246171110912m13 + 201700042332545251008m14 -368052722019205320960m15 + 531966143515513800960m16 -586003188281237388288m17 + 462270648384927677952m18 -232608604432295245824m19 + 56102738197832792064m20 3 2 4 3 2 5 3 3 6 3