Also available at http://amc.imfm.si ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.) ARS MATHEMATICA CONTEMPORANEA 5 (2012) 77–97 Asymptotic enumeration of reversible maps regardless of genus Michael Drmota ∗ Institute of Discrete Mathematics and Geometry, Vienna University of Technology Wiedner Hauptstrasse 8–10, A-1040 Wien, Austria Roman Nedela † Matej Bel University and Mathematical Institute, Slovak Academy of Sciences Banská Bystrica, Slovakia. Received 31 January 2010, accepted 18 April 2011, published online 12 December 2011 Abstract We derive asymptotic expansions for the numbers U(n) of isomorphism classes of sensed maps on orientable surfaces with given number of edges n, where we do not specify the genus and for the numbers A(n) of reflexible maps with n edges. As expected the ratio A(n)/U(n) → 0 for n → ∞. This shows that almost all maps are chiral. Moreover, we show logA(n) ∼ 12 logU(n) ∼ (n/2) log n. Due to a correspondence between sensed maps with given number of edges and torsion-free subgroups of the group Γ = 〈x, y|y2 = 1〉 of given index, the obtained results give an information on asymptotic expansions for the number of conjugacy classes of such subgroups of given index. Keywords: Graph, map, enumeration, asymptotic. Math. Subj. Class.: 05C30,05A16 1 Introduction A map is a 2-cell decomposition of a compact connected surface. In this paper we prefer- ably consider maps on orientable surfaces without boundary. A sensed (respectively un- sensed) map is an equivalence class of maps on a closed orientable surface, where two maps ∗This author is supported by the Austrian Science Foundation FWF, project S9604, part of the Austrian Na- tional Research Network “Analytic Combinatorics and Probabilistic Number Theory”. †This author is supported by the national grants APVV-0223-10, VEGA and the Centre of Excellence in Information Systems CAKS, grant no. ITMS NFP26220120023. E-mail addresses: michael.drmota@tuwien.ac.at (Michael Drmota), nedela@savbb.sk (Roman Nedela) Copyright c© 2012 DMFA Slovenije 78 Ars Math. Contemp. 5 (2012) 77–97 are equivalent if one can be transformed into the other by a sense-preserving homeomor- phism (respectively, by any homeomorphism either sense-preserving or sense-reversing) of the underlying surface. N. C. Wormald [18],[19] and T. R. Walsh [17] have calculated sensed and unsensed 1−, 2− and 3−connected planar maps. A formula for the number of sensed planar maps with given number of edges was obtained by V. Liskovets [10]. In [11] using a geometric approach sensed maps of a given genus are enumerated. Sensed and unsensed maps of all genera were counted in a beautiful lecture by R. W. Robinson [15]. Breda, Mednykh and Nedela in [4] employ a new geometric approach to enumerate sensed and unsensed maps regardless of genus. This method further extends the one used in [11] and [12] to count sensed unrooted maps and hypermaps on closed orientable surface of given genus. It is worth to mention that the enumeration results on maps can be trans- lated into results on enumeration of free subgroups and their conjugacy classes in certain universal Fuchsian groups (see Subsection 5.5). This paper is aimed at the asymptotic analysis of the enumeration formulas derived in [4]. We show in two different ways that the number U(n) of sensed maps with n edges is asymptotically given by U(n) ∼ √ 2 (2n)ne−n, which is actually a result known between experts in map enumeration nevertheless to our best knowledge it was not published. A sensed mapM is either isomorphic with its mirror image or not. In the first caseM is called reflexible, in the second caseM is chiral. Chiral maps appear in pairs (a map and its mirror image) which are sometimes called chiral twins. Furthermore we prove that the number A(n) of reflexible maps with n edges is A(n) ∼ e − 34 2 √ 2πn (2n) n 2 e− n 2 e2 √ 2n. It follows that the ratio A(n)/U(n)→ 0 for n→ 0 and logA(n) ∼ 12 logU(n) ∼ n 2 log n which means that almost all maps are chiral. The structure of the paper follows. In Section 2 we present and discuss our asymp- totic results, in particular, we indicate why the the asymptotic formula for U(n) holds. In Section 3 we collect formulas for the enumeration of several classes of maps employed in the explicit formulas for U(n) and A(n). Section 4 provides an analytic tool to obtain the asymptotic expansion of quickly increasing sequences. This tool is applied in Section 5 to derive the asymptotic behavior of certain classes of maps. Section 6 is devoted to the proof of the asymptotic formula for A(n) which is our main finding. Finally, in Section 7 we present two proofs of the asymptotic formula for U(n). First one follows from an ele- mentary estimation, the second one is based on the explicit formulas and provides precise second order terms. 2 Results Let U(n) denote the number of (unrooted) unbranched sensed maps with n edges andA(n) denote the number of (unrooted) orientable reflexible maps with n edges. The main result of this paper follows. Theorem 2.1. The numbers U(n) and A(n) are asymptotically given by U(n) = √ 2 (2n)ne−n ( 1− 13 24n +O ( 1 n2 )) , (2.1) M. Drmota and R. Nedela: Asymptotic enumeration of reversible maps regardless of genus 79 A(n) = e− 3 4 2 √ 2πn (2n) n 2 e− n 2 e2 √ 2n ( 1− 35 √ 2 96 √ n +O ( 1 n )) . (2.2) The asymptotic expansion for U(n) is much easier to obtain than that for A(n). Actu- ally it is not very difficult to obtain the asymptotic leading term of U(n).1 Here we use the fact that an n-edged map on an orientable surface can be also represented by a pair of per- mutations (α, ρ) of degree 2n, where α is a fixed point free involution and the pair (α, ρ) generate a transitive subgroup, see [9, 13, 16]. Furthermore, two maps are isomorphic if and only if their corresponding permutation pairs are jointly conjugate by some permu- tation. By [2, Theorem 13] (where a classical result of Dixon [5] is extended) it follows that the probability that a pair (α, ρ) (of the above type) that does not generate a transitive subgroup is O(1/n). Hence, the number of transitive pairs is (2n)! 2nn! (2n)! ( 1 +O ( 1 n )) . It is an elementary fact that for almost all transitive pairs, their automorphism group is trivial, we shall investigate this in detail in Section 7. This means that asymptotically U(n) ∼ (2n)! 2nn! (2n)! (2n)! = (2n)! 2nn! . Of course, this provides the asymptotic leading term for U(n). It is definitely more difficult to get asymptotics for A(n) by using a combinatorial- algebraic approach. A basic observation is that the mirror image of a map that is represented by a pair (α, ρ) corresponds to the pair (α, ρ−1). Hence, reflexible maps can be modelled by permutation pairs (α, ρ), (α, ρ−1) that are conjugate, that is, there is a permutation π with π−1απ = α and π−1ρπ = ρ−1. However, in contrast to the case of (general) sensed maps it seems that it is not that direct to translate this observation into a counting problem that can be easily handled. 3 Explicit formulas for map enumeration Although our primary object is to investigate isomorphism classes of maps on compact orientable connected surfaces without boundary, in order to express the enumeration for- mulas we need to consider a broader family of maps. Namely, we allow our maps to have semiedges, the underlying surface can be non-orientable, or may have a non-empty boundary. This happens because map automorphisms play a key role in enumeration of iso-classes of maps, but maps on compact orientable connected surfaces without boundary are not closed under taking quotients by actions of discrete groups of automorphisms. This can be easily demonstrated even on the sphere. All this topological notions can be formal- ized in terms of the permutational description of topological maps, see [4]. In particular, a dart is an edge endowed with an orientation. Two darts underlying the same edge are transposed by the dart-reversing involution α. Then the semiedges correspond to the fixed points of the involution α and the cycles of length two gives correspond to complete edges of M . 1We are grateful to one of the referees for this hint. 80 Ars Math. Contemp. 5 (2012) 77–97 Let R+(m, q) denote the number of rooted orientable maps with m darts and q com- plete edges and R(m, q) denote the number of rooted boundary-free maps with m darts and q complete edges. In [4] the following identities for generating functions were derived: ∑ m≥1 ∑ q≥1 R+(m, q) m xmyq = log ∑ m≥0 ∑ q≥0 m! (m− 2q)!2qq! xmyq  (3.1) ∑ m≥1 ∑ q≥1 R(m, q) 2m x2myq = log ∑ m≥0 ∑ q≥0 (2m)! 22mm!(m− 2q)!q! x2myq  . (3.2) Flags of a mapM correspond to topological triangles of the first barycentric subdivision ofM. The side of a flag (v, e, f) joining the center of the face f to the vertex v is called diagonal. An internal diagonal is a diagonal incident with two flags. Let R(m, q, s) de- note the number of rooted compact maps with 2m flags, q complete edges and s internal diagonals. A diagonal which is not internal lies on the boundary. The following identity for generating functions was derived in (see [4]):∑ m≥1 ∑ q,s≥0 R(m, q, s) 2m w2mxqys (3.3) = log ∑ m≥0 ∑ q,s≥0 (2m)! 22q+s(m− 2q)!(2m− 2s)!q!s! w2mxqys  . Finally, let ϕp(`) = ∑ d|` µ ( ` d ) dp denote the Jordan function, ϕevenp (`) = ∑ d|`, d even µ ( ` d ) dp = { 0 if ` ≡ 1 mod 2, 2pϕp(` ′) if ` ≡ 0 mod 2. denote the even Jordan function, and ϕoddp (`) = ∑ d|`, `/d odd µ ( ` d ) dp = { ϕp(`) if ` ≡ 1 mod 2, 2prϕp(` ′) if ` = 2r`′, `′ ≡ 1 mod 2 denote the odd Jordan function. With the help of this notation one can express U(n) and A(n) explicitly (see [4]). Lemma 3.1. The numbers U(n) and A(n) are explicitly given by U(n) = 1 2n ∑ `|2n  ∑ 0≤q 0. If the sequence (bm)m≥1 is linked to (am)m≥1 by the generating function relation (4.1) then we have bm = am − a1am−1 +O ( am m2α ) . (4.5) This result can be derived from a theorem of Bender [3], see also [14, Theorem 7.2]. However, since we will need a bivariate extension of the used methods (Propositions 5.2 and 5.4) we have decided to include a short direct proof of Theorem 4.1. Note that am−1 = Θ(am/mα). Hence, (4.5) contains the first two terms of an asymp- totic expansion. Actually it is possible to derive an asymptotic expansion of arbitrary length. But this is not needed for our purposes. It is also worth mentioning that the radius of convergence of the generating function a(x) = ∑ m amx m equals zero if am grows like (4.4) with α > 0. Therefore one cannot use complex analysis in order to derive asymptotics for the coefficients. We start with an easy lemma. Lemma 4.2. Suppose that a sequence (am)m≥1 of positive real numbers satisfies Am,2 = m−1∑ r=1 aram−r ≤ C am−1 (4.6) for some constant C > 0 and for all m ≥ 2. Then for all 2 ≤ k ≤ m we have Am,k ≤ Ck−1am−k+1. (4.7) Proof. We proceed by induction. Of course, (4.7) is satisfied for k = 2 by assumption (4.6). Now assume that (4.7) holds for some 2 ≤ k < m. Then the recursion Am,k+1 = m−k∑ `=1 a`Am−`,k implies Am,k+1 ≤ Ck−1 m−k∑ `=1 a`am−k−`+1 ≤ Ckam−k which completes the proof. M. Drmota and R. Nedela: Asymptotic enumeration of reversible maps regardless of genus 83 With help of Lemma 4.2 we can easily estimate Ak,m if the sequence am grows suffi- ciently fast. Lemma 4.3. Suppose that (am)m≥1 satisfies an asymptotic relation of the form (4.4) for given real numbers α, β, γ, δ with α > 0. Then there exits C > 0 such that (4.6) holds for all m ≥ 2. Furthermore, we have the upper bound m∑ k=3 Am,k = O(am−2) = O ( am m2α ) (4.8) as m→∞ and the asymptotic expansion Am,2 = 2a1am−1 +O ( am m2α ) . (4.9) Proof. First observe that (4.4) implies log ar+1 − log ar = α log r +O(1) and consequently ar+1am−r−1 aram−r = eα log r m−r+O(1). Hence there exists µ > 0 such that for rm−r ≤ µ ar+1am−r−1 aram−r ≤ 1 2 . This direcly implies ∑ 1≤r≤ µ1+µm aram−r ≤ 2a1am−1 and similarly ∑ 1 1+µm≤r≤m−1 aram−r ≤ 2a1am−1. Next suppose that µ1+µm < r < 1 1+µm. Then with (4.4) we get the upper bound log ar + log am−r ≤ αm logm+ βm+ |γ| √ 2m+ 2|δ| logm+O(1) − α ( µ 1 + µ log 1 + µ µ + 1 1 + µ log(1 + µ) ) m. which implies that∑ µ 1+µm 0. Hence, (4.6) holds for some constant C > 4. 84 Ars Math. Contemp. 5 (2012) 77–97 Finally, observe that (4.4) implies Ckam−k Ck−1am−k+1 = Ce−α(m−k)+O(1) ≤ 1 2 if m− k ≥ k0 (for some k0). Hence,∑ 3≤k≤m−k0 Ck−1am−k+1 ≤ 2Cam−2 = O ( am m2α ) . Further we have∑ m−k0 0 this function is admissible in the sense of Hayman (see [7]). Thus (for every fixed y > 0) we have the asymptotic expansion3 Am(y) = m! f(rm(y), y)rm(y) −m√ 2πb(rm(y)) ( 1 +O ( d(rm) b(rm)2 )) (m→∞) (4.14) 3In Hayman’s paper [7] only the asymptotic leading term is given. The full asymptotic series expansion (that applies to f(z) = eyz 2+z) is given in [6]. 86 Ars Math. Contemp. 5 (2012) 77–97 where rm(y) is determined by the equation a(rm(y)) = m and where a(r) = rf ′(r, y)/f(r, y) = r + 2yr2, b(r) = ra′(r) = r + 4yr2, and d(r) = r(rb′(r))′ = r + 16yr2. Asympotically we have rm(y) = √ m 2y − 1 4y + 1 32y2 √ 2y m +O ( 1 m ) and consequently the leading term (4.11) and the second order term C1(y)/ √ m follows. Finally, since d(rm)/b(rm)2 ∼ 2/m, the error term in (4.14) is given by O(1/m) and does not change the second order term. In order to prove the upper bound we again use f(z, y). If y is positive then Am(y) is positive, too. Hence, for every r > 0 we get the trivial upper bound Am(y) m! rm ≤ er+yr 2 . In particular, if we set r = √ m/(2y) we get Am(y) ≤ m!e− m 2 log m 2y+ m 2 + √ m 2y . Since m! ≤ 3mm+ 12 e−m we also get (4.13). With help of this lemma we directly derive the following asymptotic relations. Lemma 4.6. We have the following asymptotic relations:∑ q≥0 m! (m− 2q)!q! = e− 1 8 √ 2 (2m) m 2 e− m 2 + √ m 2 ( 1 + 5 √ 2 192 √ m +O ( 1 m )) , ∑ q≥0 2q(2m)! 22mm!(m− 2q)!q! = e− 1 16 √ 2πm 2mm m 2 e− m 2 + √ m 4 ( 1 + 53 384 √ m +O ( 1 m )) and ∑ q,s≥0 (2m)! 22q+s(m− 2q)!(2m− 2s)!q!s! = e− 3 4 2 √ 2πm (2m) m 2 e− m 2 e2 √ 2m × ( 1 + 61 √ 2 96 √ m +O ( 1 m )) . Proof. We just have to apply Lemma 4.5 and Stirling’s formula since∑ q≥0 m! (m− 2q)!q! = Am(1), ∑ q≥0 2q(2m)! 22mm!(m− 2q)!q! = (2m)! 22m(m!)2 Am(2) M. Drmota and R. Nedela: Asymptotic enumeration of reversible maps regardless of genus 87 and ∑ q,s≥0 (2m)! 22q+s(m− 2q)!(2m− 2s)!q!s! = 1 m! Am ( 1 4 ) A2m ( 1 2 ) . 5 Asymptotics for Rooted Maps 5.1 Rooted Unbranched Sensed Maps Recall that a dart of a map is an edge endowed with an orientation and that the edges composed from two darts are complete. Furthermore, an edge with just one underlying dart is called a semiedge. A semiedge joins a vertex to a branch point of index two. A sensed map without semiedges is called unbranched. A sensed map is called rooted if one of the darts is distiguished as a root. Let R+(m) denote the number of rooted unbranched sensed maps with m edges. In [4] the following identity for generating functions was derived: ∑ m≥1 R+(m) m 2m−1um = log ∑ m≥0 (2m)! m! um  . (5.1) Note that another formula for R+(m) was determined earlier by D. M. Jackson and T. I. Visentin [8] and by Arquès and J.-F. Béraud [1]. It is now easy to obtain the following asymptotic expansion. Proposition 5.1. The numbers R+(m) are asymptotically given by R+(m) = (2m)! 2m−1(m− 1)! ( 1− 1 2m +O ( 1 m2 )) = 2m+ 3 2mm+1e−m ( 1− 13 24m +O ( 1 m2 )) . (5.2) Furthermore we have the upper bound R+(m) ≤ (2m)! 2m−1(m− 1)! . (5.3) Proof. By Lemma 4.4, the sequence am = (2m)!/m! satisfies an asymptotic relation of the form (4.4) with α = 1. Hence, by Theorem 4.1 we obtain R+(m) m 2m−1 = am − a1am−1 +O (am m2 ) = (2m)! m! ( 1− 1 2m +O ( 1 m2 )) . Thus, (5.2) follows from Lemma 4.4. The upper bound (5.3) follows from (4.3) since we know a-priori thatR+(m) ≥ 0. 88 Ars Math. Contemp. 5 (2012) 77–97 5.2 Rooted orientable maps Recall that R+(m, q) denotes the number of rooted orientable maps with m darts and q complete edges. Clearly 0 ≤ 2q ≤ m, and we have R+(2m,m) = R+(m) which is asymptotically given by (5.2). With the help of the relation (3.1) and the methods of Section 4 we derive the following asymptotic relations for general m and q, however the error term is not optimal in the whole range. Proposition 5.2. The numbers R+(m, q) are asymptotically given by R+(m, q) = m m! (m− 2q)!2qq! +O ( m m 2 + 1 2 e− m 2 + √ m ) (5.4) and we have the upper bound R+(m, q) ≤ m m! (m− 2q)!2qq! . (5.5) Furthermore, for every positive real y we have∑ q≥0 R+(m, q) yq = m ∑ q≥0 m! (m− 2q)!2qq! yq · ( 1 +O ( 1√ m )) = e− 1 4ym√ 2 (ym) m 2 e− m 2 + √ m y · ( 1 +O ( 1√ m )) . (5.6) Remark 5.3. Note that the asymptotic relation (5.4) is only significant if∣∣∣∣q − m2 + √ m 2 ∣∣∣∣ = O (m 14) . If q is in that range then the order of magnitude of R+(m, q) is m m 2 + 3 4 e− m 2 + √ m. This is certainly a range of interest since it covers all large numbers R+(m, q). The sum of the remainingR+(m, q) can be made arbitrarily small compared to the whole sum choosing the O-constant in the term O(m 1 4 ) to be sufficiently large. Nevertheless it is expected that the upper bound (5.5) is actually the asymptotic leading term in a wider range. For example, it matches for q = m2 , see Proposition 5.1. Proof. The inequality (5.5) follows from the general principle (4.3) since we know that R+(m, q) ≥ 0. Further, the asymptotic relation (5.6) follows from Theorem 4.1 and Lemma 4.5. From (3.1) it follows that 1 m R+(m, q) = m! (m− 2q)!2qq! + [yq] m∑ k=2 1 k (−1)k−1 ∑ r1+···+rk=m, rj≥1 Ar1 (y 2 ) · · ·Ark (y 2 ) . M. Drmota and R. Nedela: Asymptotic enumeration of reversible maps regardless of genus 89 First observe that∣∣∣∣∣∣[yq] m∑ k=2 1 k (−1)k−1 ∑ r1+···+rk=m, rj≥1 Ar1 (y 2 ) · · ·Ark (y 2 )∣∣∣∣∣∣ ≤ [yq] m∑ k=2 ∑ r1+···+rk=m, rj≥1 Ar1 (y 2 ) · · ·Ark (y 2 ) , where the right hand side has only non-negative coefficients. We now again use the prin- ciple that the n-th coefficient an of a power series a(x) = ∑ n≥0 anx n can be estimated by an ≤ r−na(r) for every r > 0. In particular, if we choose r = y = 1 then we get the estimate [yq] m∑ k=2 ∑ r1+···+rk=m, rj≥1 Ar1 (y 2 ) · · ·Ark (y 2 ) ≤ m∑ k=2 ∑ r1+···+rk=m, rj≥1 Ar1 ( 1 2 ) · · ·Ark ( 1 2 ) . However, it follows from Lemma 4.3 and Lemma 4.5 that m∑ k=2 ∑ r1+···+rk=m, rj≥1 Ar1 ( 1 2 ) · · ·Ark ( 1 2 ) = O ( Am ( 1 2 ) √ m ) = O ( m m 2 − 1 2 e− m 2 + √ m ) . This implies 1 m R+(m, q) = m! (m− 2q)!2qq! +O ( m m 2 − 1 2 e− m 2 + √ m ) and completes the proof of (5.4). 5.3 Rooted boundary-free maps Next we consider the numbers R(m, q) of rooted boundary-free maps with m darts and q complete edges. Here we have: Proposition 5.4. The numbers R(m, q) are asymptotically given by R(m, q) = (2m)! 22m−1(m− 1)!(m− 2q)!q! +O ( 2 m 2 m m 2 e− m 2 + √ m 2 ) (5.7) and we have the upper bound R(m, q) ≤ (2m)! 22m−1(m− 1)!(m− 2q)!q! . (5.8) 90 Ars Math. Contemp. 5 (2012) 77–97 Furthermore, for every positive real y we have∑ q≥0 R(m, q) yq = ∑ q≥0 (2m)! 22m−1(m− 1)!(m− 2q)!q! yq · ( 1 +O ( 1√ m )) = e− 1 8y √ 2m√ π (2ym) m 2 e− m 2 + √ m 2y · ( 1 +O ( 1√ m )) (5.9) Proof. The proof is exactly the same as that of Proposition 5.2. 5.4 Rooted compact maps Finally we consider the numbers R(m, q, s) of rooted compact maps with 2m flags, q complete edges and s internal diagonals. A diagonal which is not internal lies on the boundary. Proposition 5.5. The numbers R(m, q, s) are bounded by R(m, q, s) ≤ 2m(2m)! 22q+s(m− 2q)!(2m− 2s)!q!s! (5.10) Furthermore, the sum ∑ q,sR(m, q, s) is asymptotically given by∑ q,s≥0 R(m, q, s) = ∑ q,s≥0 2m(2m)! 22q+s(m− 2q)!(2m− 2s)!q!s! · ( 1− 2√ 2m +O ( 1√ m )) = e− 3 4 √ m√ 2π (2m) m 2 e− m 2 e2 √ 2m (5.11) · ( 1− 35 √ 2 96 √ m +O ( 1 m )) . Proof. We just apply Theorem 4.1 and Lemma 4.6 with am = ∑ q,s≥0 (2m)! 22q+s(m− 2q)!(2m− 2s)!q!s! . Note that a1 = 2 and am−1 = am√ 2m ( 1 +O ( 1√ m )) . 5.5 Subgroup counting As already noted map enumeration is closely related with counting (free) subgroups of given index and their conjugacy classes in the universal triangle group ∆+ = 〈x, y| y2 = 1〉 and in the extended triangle group ∆ = 〈x, y, z| x2 = y2 = z2 = (xy)2 = 1〉. In M. Drmota and R. Nedela: Asymptotic enumeration of reversible maps regardless of genus 91 particular, R+(m) is the number of free subgroups of rank m + 1 in ∆+ and U(m) is the number of conjugacy classes of such subgroups in ∆+. Next we define R(m) as the number of rooted closed maps (orientable or not) with m edges.4 Then R(m) is the number of free subgroups rank m+ 1 in ∆. In [4] the following identity for generating functions was derived: ∑ m≥1 R(m) m 42m−1um = log ∑ m≥0 (4m)! (2m)!m! um  . (5.12) Similarly to Proposition 5.1 we obtain the following asymptotic result: Proposition 5.6. The numbers R(m) are asymptotically given by R(m) = (4m)! 42m−1(2m)!(m− 1)! ( 1 +O ( 1 m )) = 1√ π 22m+1mm+ 1 2 e−m ( 1 +O ( 1 m )) (5.13) Furthermore we have the upper bound R(m) ≤ (4m)! 42m−1(2m)!(m− 1)! . (5.14) 6 Reflexible Maps The purpose of this section is to prove the asymptotic expansion (2.2) for A(n). Proof. We use the explicit representation (3.5) (where E(`,m) is given in (3.6)). The crucial observation is that the term with ` = 1 in the explicit representation (3.5) dominates the whole sum, that is, the term 1 2n ∑ q,s≥0 R (n, q, s) is dominating. By Proposition 5.5 this term is asymptotically given by e− 3 4 2 √ 2πn (2n) n 2 e− n 2 e2 √ 2n ( 1− 35 √ 2 96 √ n +O ( 1 n )) Thus, we just have to deal with the terms ` 6= 1. Recall that we have the following trivial 4A map on a compact connected surface without boundary is called closed. 92 Ars Math. Contemp. 5 (2012) 77–97 bounds R(m, q, s) ≤ 2m (2m)! 22q+s(m− 2q)!(2m− 2s)!q!s! , R+(m,m/2) ≤ m m! 2m/2(m/2)! if m ≡ 0 mod 2, R+(m, q) ≤ m m! (m− 2q)!2qq! , R(m, q) ≤ 2m (2m)! 22mm!(m− 2q)!q! , ϕoddp (`) ≤ max{1, `p}. Hence, by using the upper bound (4.13) we get ∑ q,s≥0 R(m, q, s)ϕodd−m+q+s+1(`) ≤ m ∑ q,s≥0 (2m)! 22q+s(m− 2q)!(2m− 2s)!q!s! ( `−m+q+s+1 + 1 ) = `−m+1 (m− 1)! Am ( ` 4 ) A2m ( ` 2 ) + 1 (m− 1)! Am ( 1 4 ) A2m ( 1 2 ) ≤ 3 √ 2m 3 2 e m 2 log(2m`)− m 2 +2 √ 2m ` + 3m 3 2 e m 2 log(2m)− m 2 +2 √ 2m. This implies that 1 2n ∑ `|n, `≥3 odd ∑ q,s≥0 R (n ` , q, s ) ϕodd−n` +q+s+1(`) ≤ 3 √ 2 2n ∑ `|n, `≥3 odd (n ` ) 3 2 e n 2` log(2n)− n 2`+2 √ 2n `2 + 3 2n ∑ `|n, `≥3 odd (n ` ) 3 2 e n 2` log 2n ` − n 2`+2 √ 2n ` = O (√ n e n 6 log(2n)− n 6 +2 √ 2n 9 ) +O (√ n e n 6 log 2n 3 − n 6 +2 √ 2n 3 ) Similarly we get an upper bound for 1 2n ∑ `|n, ` odd R+ (n ` , n 2` ) ϕoddn 2`+1 (`) ≤ 2 √ 2 ∑ `|n, ` odd ` n e n 2` log n 2− n 2` = O ( 1 n e n 2 log n 2− n 2 ) M. Drmota and R. Nedela: Asymptotic enumeration of reversible maps regardless of genus 93 Finally, for even ` we have∑ q≥0 ( R(m, q)−R+(m, q) ) ϕoddq+1(`) ≤ ∑ q≥0 R(m, q)ϕoddq+1(`) ≤ 2m ∑ q≥0 (2m)! 22mm!(m− 2q)!q! `q+1 = 2m` (2m)! 22m(m!)2 Am(`) ≤ 6m`e m 2 log(m`)+ √ m 2` which implies that 1 2n ∑ `|n, `≥2 even ∑ q≥0 ( R (n ` , q ) −R+ (n ` , q )) ϕoddq+1(`) ≤ 3 ∑ `|n, `≥2 even e n ` log(2n)+ √ n `2 = O ( e n 4 logn+ √ n 8 ) Of course, this proves (2.2) since the order of magnitude of theses three terms is much smaller than that of the leading term. 7 Unrooted Maps In this final section we provide two proofs for the asymptotic expansion of U(n). 7.1 Permutation counting In Section 2 it was already indicated that the asymptotic formula for U(n) follows from the fact that for almost all pairs (α, ρ) the automorphism group is trivial. For the reader’s convenience we present as short proof of the following upper bound. Lemma 1. Let Tn denote the set of pairs α, ρ ∈ S2n such that α is fixed point free involu- tion and that the group generated by α, ρ is transitive. Then #{(α, ρ) ∈ Tn : ∃π ∈ S2n, π 6= 1, πα = απ, πρ = ρπ} (2n)! 2nn! (2n)! = O ( (1.05)nn−n/3 ) Proof. We recall that the automorphism group of transitive pairs (α, ρ) is given by {π ∈ S2n : πα = απ, πρ = ρπ}. Hence, the proposed bound estimates the probability that the automorphism group of a (random) transitive pair is non-trivial. Actually, we can be more precise on non-trivial permutations π in such automorphism groups. Since we are only considering transitive pairs, it follows that all such π 6= 1 consist of independent cycles of an equal length ` > 1. Let S2n[`] denote the set of such permutations (if `|2n) and S◦2n the set of fixed point free involutions. 94 Ars Math. Contemp. 5 (2012) 77–97 By double counting we obtain the estimate #{(α, ρ) ∈ Tn : ∃π ∈ S2n, π 6= 1 πα = απ, πρ = ρπ} ≤ ∑ `≥2, `|2n ∑ π∈S2n[`] #{α ∈ S◦2n : πα = απ} ·#{ρ ∈ S2n : πρ = ρπ} First it is easy to show that (for π ∈ S2n[`] and ρ ∈ S2n) #{ρ ∈ S2n : πρ = ρπ} = `2n/`(2n/`)!. (7.1) This follows from the fact that the ρ-image of each cycle of π is again a cycle of π (in the corresponding order). Hence, by constructing such ρ there are (2n/`)! possible ways of grouping the cycles (of lengths `) in pairs, and for each pair there are ` possibilities to glue them together. The number of α ∈ S◦2n that commute with π is more difficult to describe. However, if ` ≥ 3 we will use the trivial estimate #{α ∈ S◦2n : πα = απ} ≤ `2n/`(2n/`)!. Thus, we just have to look at the special case ` = 2. Here we have #{α ∈ S◦2n : πα = απ} = ∑ k≥0 n! (n− 2k)!2kk! 2k = An (1) . (7.2) This follows from the observation that αmaps a 2-cycle from π either identically to itself or two different 2-cycles from π are mapped to each other. SinceAn(1) = O ( (2n)n/2e √ n/2 ) we thus obtain #{(α, ρ) ∈ Tn : ∃π ∈ S2n, π 6= 1, πα = απ, πρ = ρπ} ≤ (2n)! 2nn! 2nn!An(1) + ∑ `≥3, `|2n (2n)! `2n/`(2n/`)! ( `2n/`(2n/`)!) )2 = O ( (2n)!32n/3Γ(2n/3 + 1) ) = O ( (2n)! 2nn! (2n)!(1.05)nn−n/3 ) . This proves the lemma. Summing up, Lemma 1 assures that for almost all transitive pairs the isomorphy classes of transitive pairs consist of (2n)! elements. This implies the asymptotic formula for U(n) as explained in Section 2. 7.2 Map counting Finally we present a second proof for the asymptotic formula for U(n) that is based on the explicit representation (3.4). Note that this proof can be extended to a full asymptotic series expansion and is, thus, more precise than the first one. M. Drmota and R. Nedela: Asymptotic enumeration of reversible maps regardless of genus 95 Proof. Set S1 := 1 n ∑ `′|n ∑ 0≤q< n 2`′ R+ (n `′ , q ) 2qϕq+1(` ′) and S2 := 1 2n ∑ `|2n,`>1 R+ ( 2n ` , n ` ) ϕn/`+1(`) Then U(n) = S1 + S2 + R+(2n, n) 2n . The crucial observation is that the last term R+(2n, n)/(2n) = R+(n)/(2n) dominates the whole sum. Note that by Proposition 5.1 R+(n) 2n = √ 2 (2n)ne−n ( 1− 13 24n +O ( 1 n2 )) . Using the trivial bound ϕp(`) ≤ `p and R+(m) ≤ (2m)!/(2m−1(m− 1)!) we can directly estimate the second sum S2 ≤ 1 2n ∑ `|2n,`>1 ( 2n ` ) !( n ` − 1 ) !2 n ` −1 ` n ` +1 = ∑ `|2n,`>1 ( 2n ` ) !( n ` ) !2 n ` ` n ` +1 ≤ 2 ∑ `|2n,`>1 2 n ` (n ` )n ` e− n ` ` n ` = 2 ∑ `|2n,`>1 ( 2n e )n ` = O ( n n 2 ) . For the first sum we again use the trivial estimates ϕp(`) ≤ `p and R+(m, q) ≤ mm! (m− 2q)!2qq! to get S1 ≤ 1 n ∑ `|n ∑ 0≤q< n2` n ` ( n ` ) !( n ` − 2q ) !2qq! 2q`q+1 = ∑ `|n An ` (2`), 96 Ars Math. Contemp. 5 (2012) 77–97 with Am(y) defined in (4.11). By applying the upper bound (4.13) we thus get S1 ≤ 3 √ n ∑ `|n (2n) n 2` e− n 2`+ √ n/(2`2) ≤ 3 √ n e √ n/2 ∑ `|n ( 2n e ) n 2` = O (√ n e √ n/2 (2n) n 2 ) . Of course, these bounds for S1 and S2 are of much smaller order of magnitude than the leading term R+(n)/(2n). Acknowledgement. The authors thank the two referees for their valuable hints to improve the presentation and for pointing out a mistake concerning constants and their comments on a more direct proof for the asymptotics of U(n). References [1] D. Arquès and J.-F. Béraud, Rooted maps on orientable surfaces, Riccati’s equation and con- tinued fractions, Discrete Math. 215 (2000), 1–12. [2] L. Babai and T. P. Hayes, The probability of generating the symmetric group when one of the generators is random, Publ. Math. 69 (2006), 271–280. [3] E. A. Bender, An asymptotic expansion for the coefficients of some formal power series, J. London Math. Soc 9 (1975), 451–458. [4] A. Breda, A. Mednykh and R. Nedela, Enumeration of maps regardless of genus. Geometric approach, Discrete Math. 310 (2010), 1184–1203. [5] J. D. Dixon, The probability of generating the symmetric group, Math. Z. 110 (1969), 199–205. [6] B. Harris and L. Schoenfeld, Asymptotic expansions for the coefficients of analytic functions, Illinois J. Math. 12 (1968), 264–277. [7] W. K. Hayman, A generalisation of Stirling’s formula, J. Reine Angew. Math. 196 (1956), 67– 95. [8] D. M. Jackson and T. I. Visentin, A character-theoretic approach to embeddings of rooted maps in an orientable surface of given genus, Trans. Amer. Math. Soc. 332 (1990), 343–363. [9] G. A. Jones and D. Singerman, Theory of maps on orientable surfaces, Proc. London Math. Soc. 37 (1978), 273–307. [10] V. A. Liskovets, Enumeration of nonisomorphic planar maps, Selecta Math. Sovietica 4 (1985), 303–323. [11] A. D. Mednykh and R. Nedela, Enumeration of unrooted maps of a given genus, J. Combin. Theory Ser. B 96 (2006), 706–729. [12] A. D. Mednykh and R. Nedela, Counting unrooted hypermaps on closed orientable surface, Proceedings of the 18th International Conference on Formal Power Series and Algebraic Com- binatorics, June 19–23, 2006, San Diego, California, 2006, 1–19. [13] R. Nedela and M. Škoviera, Exponents of orientable maps, Proc. London Math. Soc. 75 (1997), 1–31. M. Drmota and R. Nedela: Asymptotic enumeration of reversible maps regardless of genus 97 [14] A. M. Odlyzko, Asymptotic enumeration methods, in: R. L. Graham, M. Groetschel, and L. Lovasz (eds.), Handbook of Combinatorics, vol. 2, Elsevier, 1995, 1063–1229. [15] R. W. Robinson, Counting Unrooted Maps of all Genera, Conference talk at the Twenti- eth Clemson Mimi-Conference on Discrete Mathamatics and Related Fields, October 2005, http://www.cs.uga.edu/˜rwr. [16] A. Vince, Combinatorial maps, J. Combin. Theory Ser. B 34 (1983),1–21. [17] T. R. Walsh, Efficient emumeration of sensed planar maps, Discrete Math. 293 (2005), 263– 289. [18] N. C. Wormald, Counting unrooted planar maps, Discrete Math. 36 (1981), 205–225. [19] N. C. Wormald, On the number of planar maps, Canad. J. Math. 33 (1981), 1–11.