{'fraction_non_alphanumeric': 0.04064935064935065, 'fraction_numerical': 0.015779220779220778, 'mean_word_length': 3.9568715803025425, 'pattern_counts': {'":': 0, '<': 7, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Constructing large tables of numbers of maps by orientable genus

The Carrell-Chapuy recurrence formulas dramatically improve the efficiency of counting orientable rooted maps by genus, either by number of edges alone or by number of edges and vertices. This paper presents an implementation of these formulas with three applications: the computation of an explicit rational expression for the ordinary generating functions of rooted map numbers with a given positive genus, the construction of large tables of rooted map numbers, and the use of these tables, together with the method of A. Mednykh and R. Nedela, to count unrooted maps by genus and number of edges and vertices.


Introduction
A map is a 2-cell imbedding of a connected graph, loops and multiple edges allowed, on a compact surface, which in this article will be taken to be orientable and without boundaries, and is thus characterized by a single non-negative integer, its genus. A map is rooted if a dart -an edge-vertex incidence pair -is distinguished as the root. By counting maps we mean counting equivalence classes of maps under orientation-preserving homeomorphism; in the case of rooted maps, the homeomorphism must preserve the distinguished oriented edge. In this case the homeomorphism preserves all the darts [15], so that rooted maps can be counted without considering the symmetries of the maps, which is why rooted maps were counted before unrooted maps.
Let m g (n) be the number of rooted maps with n edges on the orientable surface of genus g. Let M g (z) = n≥0 m g (n)z n be the ordinary generating function counting genus-g rooted maps by number of edges (the exponent of z). Let m g (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 m g (f, v) of rooted genus-g maps with f vertices and v faces. The ordinary generating function that counts rooted genus-g maps is the following formal power series in two variables u and w: The Carrell-Chapuy recurrence formulas [6] dramatically improve the efficiency of counting rooted maps by genus. We show how to use them to determine explicit rational expressions for the generating functions M g (z) and closed-form formulas for the numbers m g (n). We also have used Carrell-Chapuy recurrence formulas to construct large tables of numbers of rooted and unrooted maps of genus up to 50 with up to 100 edges. Our goal is to provide these numbers to researchers for further studies of their properties.
The paper is organized as follows. Section 2 summarizes the history of two closely related problems, namely computing numbers of rooted maps by genus and finding a closed form for their generating functions. Section 3 presents formulas for numbers of rooted maps with a fixed genus. In Section 4 we discuss counting unrooted maps and in Section 5 we give a complexity analysis and the results of time trials. In the appendix we include a table of numbers of unrooted maps counted by genus, number of edges and number of vertices. We do not include a table of numbers of rooted maps because the reader can easily construct such a table from the recurrence in [6,Corollary 3] or the optimized version of it that we present as formula (4) here. A larger table, a table of numbers of rooted maps and a text file of the source code are available from the second author on request and can be found in release 0.4.0 of the MAP project [9]. The source code can also be found in [20].

Historical notes
For counting by number of edges alone, W. T. Tutte [15] first showed that the generating function M 0 (z) for rooted planar maps can be parametrically defined by M 0 (z) = (3 − ξ)(ξ − 1)/3, where the parameter ξ is the series in z satisfying ξ = 1 + 3zξ 2 . Tutte also found a closed-form formula for m 0 (n). For counting with two parameters (i.e. by number of edges and vertices, edges and faces, or vertices and faces), W. T. Tutte [16] and D. Arquès [1,Theorem 4] respectively found a parametric polynomial definition of M 0 (w, u) and a parametric rational definition of M 1 (w, u). Arquès also obtained a closed-form formula for the number of rooted toroidal maps with n edges and another one for the number of rooted toroidal maps with v vertices and f faces.
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], this method was generalized 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 2n to obtain the number of rooted maps of genus g with n edges and v vertices. A table of these numbers of maps with up to 14 edges appears in [17] (see [23] 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. In [3] 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.
For any genus g the existence of a parametric rational expression for the generating functions M g (z) and M g (w, u) is stated by E. Bender and E. Canfield, in [4] for M g (z) and in [5] for M g (w, u). The first of these two papers [4] also presents explicit rational functions for M 2 (z) and M 3 (z). A common pattern for all these rational functions is proposed, and an upper bound for the degree of their numerator is conjectured. For the univariate function M g (z) a bound was found in [7] and refined in [8]. For the bivariate function M g (w, u) a bound was proved in [2]. These results are summarized in the following two theorems.
. For any positive integer g, the ordinary generating function M g (z) counting rooted maps on a closed orientable surface of genus g by number of edges (exponent of z) can be written as and P g (m) is a polynomial of m of degree at most 4g − 4.
Theorem 2 ([2, Theorem 1]). For any positive integer g, the ordinary generating function M g (w, u) counting rooted maps on a closed orientable surface of genus g by number of vertices (exponent of w) and faces (exponent of u) can be written as where P g (p, q) is a symmetric polynomial in p and q of total degree at most 6g − 6 with integral coefficients.
In [21] the first and second authors calculated the polynomial P g (p, q) for g up to 6 and thus counted rooted maps of genus up to 6 by number of vertices and faces as well as by number of edges (using Theorem 1). In [22] the first author of that paper, using a more powerful computer, extended these calculations up to genus 10 and also counted unrooted maps of genus up to 10 by number of vertices and faces, the second author counted rooted maps of genus up to 11 by number of edges and the third author, A. Mednykh, counted unrooted maps of genus 11 by number of edges. The cost of counting unrooted maps, once a table of numbers of rooted maps has been constructed, was greatly dominated by the cost of counting rooted maps.
More recently, a far more efficient method for counting rooted maps with a fixed genus was discovered by S. R. Carrell and G. Chapuy [6]. They showed [6, Theorem 1] that the number m g (n) of rooted maps of genus g with n edges satisfies the following recurrence relation (we have modified the formulas for the sake of computational efficiency): for n ≥ 1, with the initial conditions m 0 (0) = 1 and m g (n) = 0 if g < 0 or n < 2g. For counting with two parameters, Carrell and Chapuy showed [6, Corollary 3] that the number m g (n, f ) of rooted maps of genus g with n edges and f faces satisfies the following recurrence relation: for n, f ≥ 1, with the initial conditions m 0 (0, 1) = 1 and m g (n, f ) = 0 if g < 0 or n < 2g or f < 1 or n − f + 2(1 − g) < 1.

Fixed genus formulas
This section shows simple -but as far as we know not yet published -consequences of Theorem 1 (about the rationality of the generating series M g (z)) for the computation of rooted map numbers. The first consequence, given in Theorem 4, is a recurrence formula between numbers of rooted maps with the same positive genus g. The second consequence, given in Theorem 5, is a closed formula for the number m g (n), for any positive genus g and any number of edges n. This formula depends on integers which are the coefficients of the polynomial P g (m) from Theorem 1. We start this section with a theorem completing Theorem 1 with an explicit relation between this polynomial and the numbers of rooted maps with the same genus and up to 6g − 4 edges. In this section [x n ]S(x) denotes the coefficient of x n in the formal power series S(x). By convention, a sum over an empty domain is equal to zero.
Theorem 3. For any positive integer g, the ordinary generating function M g (z) counting rooted maps on a closed orientable surface of genus g by number of edges (exponent of z) is and F g (m) and P g (m) are the polynomials defined by and P g (m) = l≤4g−4 p g,l m l with Proof. On the one hand, M g (z) = n≥2g m g (n)z n since m g (n) = 0 if n < 2g. On the other hand, Since the degree of the polynomial P g (m) is at most 4g − 4, P g (m) = l≤4g−4 p g,l m l with which implies Formula (7).
The polynomial P 1 (m) can be derived from [1] and the polynomials P 2 (m) and P 3 (m) from [4]. The polynomial P 4 (m) was first given in [11]. All the polynomials P g (m) with 1 ≤ g ≤ 6 can be found in [21,Appendix B]. They were computed by a complicated recurrence formula involving additional parameters. Theorem 3 and Carrell-Chapuy recurrence formula (3) provide a much more efficient way to compute the polynomials P g (m).
Theorem 4. For any positive integer g, the number m g (n) of rooted maps of positive genus g with n edges is recursively defined for n ≥ 6g − 3 by Proof. For n ≥ 4g − 3 it follows from (8) and the fact that the degree of the polynomial P g (m) is at most 4g − 4 that i.e.
By isolating m g (n + 2g) in the left-hand side, we obtain and Formula (9) follows from (1 − am) k = k i=0 k i (−a) i m i . Theorems 3 and 4 also imply that the series (m g (n)) n≥0 of rooted maps of positive genus g is uniquely determined by its first 6g − 4 values (among which the first 2g values are known to be 0).
Theorem 5. For any positive integer g, the number m g (n) of rooted maps of positive genus g with n edges is defined by the closed formula where the integers p g,l are defined in Theorem 3.
As far as we know, these formulas are the first ones relating numbers of genus-g rooted maps only with other numbers of rooted maps of the same genus. These formulas can be easily generalized to bivariate generating functions. We did not use them for counting unrooted maps because they are computationally less efficient than (3).

Counting unrooted maps
The second author has written a program in C++ that counts rooted maps by genus, number of edges and number of vertices using Formula (4) (an optimized version of [6, Corollary 3]) and also counts unrooted maps with these parameters. A table of numbers and a text file of the source code are available from the second author on request and in release 0.4.0 of the MAP project [9]. The source code can also be found in [20]. The method used to count unrooted maps given a table of numbers of rooted maps was presented by A. Mednykh and R. Nedela in [12] and refined by V. Liskovets in [10]. The second author used Liskovets' method. Details of the calculations were presented in [22]; a more pedagogical exposition can be found in [19]. For the sake of brevity we do not include the details here. Suffice it to say that the program uses the software CLN to handle big integers and the C/C++ compiler XCODE to run CLN; both of these software packages can be downloaded free of charge from the internet.

Complexity analysis and time trials
Let n be the largest number of edges in the maps to be enumerated. Then the maximum genus of the maps is n 2 , since a map of genus g must have at least 2g edges. The recurrence in [6] uses O(n 2 ) arithmetic operations to obtain the number of rooted maps with at most These asymptotic estimates are overoptimistic if we are considering CPU time rather than number of arithmetic operations because we are working with big numbers. The arithmetic operation executed most often in counting rooted maps is multiplying one number of rooted maps by another one. The naïve method of multiplying two numbers of size (number of bits) bounded by b takes O(b 2 ) bit operations. When the numbers get big enough, CLN uses the Schönhage-Strassen method of multiplication [13], which uses O(b log b log log b) bit operations. In [3] it was shown that the number of rooted maps of genus g with n edges is asymptotic to 12n multiplied by a polynomial in n whose degree depends linearly on g. It follows that the number of bits in such a number is in O(n + g log n), and since g is in O(n), the size of the number is in O(n log n). The true cost of counting rooted maps with up to n edges is found by multiplying the number of arithmetic operations by O(n 2 (log n) 2 ) if naïve multiplication is used and by O(n(log n) 2 log log n) if the Schönhage-Strassen method is used.
The second author's program calculates m g (n, f ) for g going from 0 to a user-defined maximum, for n going from 2g to a user-defined maximum and from f going from 1 to a maximum that makes v = n − f + 2(1 − g) = 1 and reinterprets f as the number of vertices rather than the number of faces (by face-vertex duality). He conducted time trials on a portable Macintosh with a 2.66 GHz Intel Core 2 Duo processor, making n range from 20 to 100 in steps of 10 and setting the maximum value of g to be n/2. Here is the time in seconds for counting rooted maps for each of these values of n (0 means too small to be measured). We do not have a time-complexity analysis for counting unrooted maps, but in the time trials it took less time to count unrooted maps than rooted ones. For n = 100, the time to count unrooted maps was 178 seconds.

Appendix: Numbers of unrooted maps
A table of numbers of unrooted planar maps (genus 0) with up to 6 edges can be found in [18]. Larger tables of numbers of unrooted planar maps were computed by N.C. Wormald and given privately to the second author, but as far as we know, they have never been published. A table of numbers of unrooted maps of genus 1-5 with up to 11 edges appears in [19] and [22]. We extend this table, both in terms of genus and number of edges, in this appendix.
The following table gives the numbers u g (e, v) of genus-g unrooted maps with e edges and v vertices, for g from 0 to 19 and for v from 1 to its maximal value e + 1 − 2g. The minimal value of e is 2g. The maximal value of e is arbitrarily fixed so that the table fits five pages for genera 0 to 2, two pages for genera 3 to 5, and one page for higher genera. The maximal value for g is such that numbers fit in the page width.