Séminaire Lotharingien de Combinatoire 54A (2007), Article B54Al

COUNTING UNROOTED MAPS USING TREE-DECOMPOSITION

ÉRIC FUSY

Abstract. We present a new method to count unrooted maps on the sphere up to orientation-preserving homeomorphisms. The principle, called tree-decompo-sition, is to deform a map into an arborescent structure whose nodes are occupied by constrained maps. Tree-decomposition turns out to be very efficient and flexible for the enumeration of constrained families of maps. In this article, the method is applied to count unrooted 2-connected maps and, more importantly, to count unrooted 3-connected maps, which correspond to the combinatorial types of oriented convex polyhedra. Our method improves significantly on the previously best-known complexity to enumerate unrooted 3-connected maps.

Acknowledgments. The author would like to thank Gilles Schaeffer for his invaluable help in developing this new method. In particular he pointed out the idea of tree-decomposition and helped to do some calculations and to correct the article.

Introduction

The enumeration of unrooted maps has been a well-studied problem for more than 20 years. The first general method for the enumeration of unrooted maps on the sphere up to orientation-preserving homeomorphisms was developed by Liskovets [4]. It relies on an adaptation of Burnside’s orbit-counting formula to maps and then study of the structure of the quotient maps.

With an adaptation of Burnside’s (orbit counting) formula, counting unrooted maps comes down to counting rooted maps with a symmetry of rotation. For a family of maps enumerated according to the number n of edges, we write respectively c_{n}, c′_{n} and c_{n}^{(k)} for the number of unrooted maps, rooted maps and rooted maps with a symmetry of order k ⩾ 2; then c_{n} can be computed by the formula:

(1)  c_{n} = \frac{1}{2n} (c′_{n} + ∑_{k=2}^{n} ϕ(k)c_{n}^{(k)}) ,

and a similar formula exists for the enumeration according to the number of vertices and faces, see Section 1. As the only possible symmetries are rotations, the problem reduces to counting rooted maps with a rotation symmetry. It is convenient for us to represent rooted map with a symmetry of order k ⩾ 2 as maps bearing k roots so as to induce a symmetry of order k. Such maps are called k-rooted. The quotient a k-rooted map is a rooted map with two marked cells, the cells intersected by the rotation-axis, which are either a vertex or the middle of a face or the middle of an edge. The enumeration of these maps is easy to handle for the family of unconstrained maps [4]. The method of quotient-maps can also be adapted to the enumeration of some families of constrained maps, such as loopless maps [8], Eulerian and unicursal maps [6] and 2-connected maps [5] but the structure of the quotient maps is less easy to characterize and to handle for these families.

In this article, we introduce a new general method for the enumeration of unrooted maps of a constrained family, based on the concept of tree-decomposition. We apply the method to the enumeration of unrooted 2-connected and, above all, of unrooted 3-connected maps, already counted by Walsh [14], but with a costly step of extraction of coefficients. In order to apply the method of tree-decomposition to 2-connected and 3-connected maps, it turns out more convenient to work with quadrangulations rather than with maps. Indeed, a well-known bijection between maps and quadrangulations, recalled in Section 1.5, ensures that counting 2-connected maps and 3-connected maps is respectively equivalent to counting simple quadrangulations (i.e., quadrangulations without multiple edges) and irreducible quadrangulations (i.e., quadrangulations without separating 4-cycles).

Then, we introduce two tree-decompositions on quadrangulations. A first treedecomposition “by multiple edges”, ensures that a quadrangulation can be seen as an arborescent structure with nodes that are simple quadrangulations. The symmetry of order k of a k-rooted quadrangulation fixes the decomposition-tree, hence it also fixes the node at the centre of the tree, called the core-node, see Figure 4 that best summarizes the essence of the method. This yields an equation linking the generating function of k-rooted simple quadrangulations and the generating functions of k-rooted quadrangulations, which are easy to obtain using the method of quotient map (see Section 1.7 where we briefly re-derive the results of Liskovets [4] for generating functions, and Sections A.1 and B.1 for all explicit expressions). Then, a second tree-decomposition “by separating 4-cycles”, introduced by Kunz–Jacques and Schaeffer in [3] for the enumeration of prime alternating links, states that a simple quadrangulation can be seen as an arborescent structure whose nodes are irreducible quadrangulations. In a similar way as for the first tree-decomposition, the symmetry of a k-rooted simple quadrangulation also fixes the “core” of the decomposition-tree, yielding equations linking the generating functions of k-rooted irreducible quadrangulations and the generating functions of k-rooted simple quadrangulations, which have already been obtained thanks to the first tree-decomposition. However, for this second tree-decomposition, a careful treatment of cases has to be done in Section 4.3 for 2-rooted objects, since the core of the decomposition-tree can be different from the centre of the tree. Once the generating functions of k-rooted simple quadrangulations (equal to those of k-rooted 2-connected maps) and the generating functions of k-rooted irreducible quadrangulations (equal to those of k-rooted 3-connected maps) are obtained, Burnside’s Figure 1. The scheme of the method to enumerate unrooted 2connected and unrooted 3-connected maps

formula (1) yields respectively the enumeration of unrooted 2-connected and unrooted 3-connected maps, see Figure 1 for a summarizing diagram.

Main results. Two results are obtained: a theorem about the algebraic structure of k-rooted maps and a theorem giving the complexity of enumerating unrooted 2-connected and unrooted 3-connected maps. First we need a few notations. Given a series α(t), a series f(t) is said to be α-rational if there exists a rational function R(T) such that f(t) = R(α(t)). Given two series in two variables α_{1}(t_{•}, t_{∘}) and α_{2}(t_{•}, t_{∘}), a series in two variables f(t_{•}, t_{∘}) is said to be (α_{1}, α_{2})- rational if there exists a rational function R(T_{1}, T_{2}) in two variables such that f(t_{•}, t_{∘}) = R(α_{1}(t_{•}, t_{∘}), α_{2}(t_{•}, t_{∘})).

Now we introduce the three series in one variable (they correspond to families of trees) β(x), η(y) and γ(z) ^{1} given by

β(x) = x + 3β(x)^{2},  η(y) = \frac{y}{(1 − η(y))^{2}} ,  γ(z) = z(1 + γ(z))^{2},

(it is easy to see that they are algebraic), and their versions in two variables β_{1,2}(x_{•}, x_{∘}), η_{1,2}(y_{•}, y_{∘}), and γ_{1,2}(z_{•}, z_{∘}) (corresponding to bicolored trees of the respective families) given by

\{ \begin{matrix}β_{1} = x_{•} + β_{1}^{2} + 2β_{1}β_{2} \\ β_{2} = x_{∘} + β_{2}^{2} + 2β_{1}β_{2} \end{matrix} ,  \{ \begin{matrix}η_{1} = \frac{y_{•}}{(1−η_{2})^{2}} \\ η_{2} = \frac{y_{∘}}{(1−η_{1})^{2}} \end{matrix} , \{ \begin{matrix}γ_{1} = z_{•}(1 + γ_{2})^{2} \\ γ_{2} = z_{∘}(1 + γ_{1})^{2} \end{matrix} .

It is already known that the generating function of rooted maps is β-rational in one variable [13] and (β_{1}, β_{2})-rational in two variables [11]; that the generating function of rooted 2-connected maps is η-rational in one variable and (η_{1}, η_{2})- rational in two variables [1]; and that the generating function of rooted 3-connected planar maps is γ-rational in one variable and (γ_{1}, γ_{2})-rational in two variables [9]. The following theorem states that the same property also holds for k-rooted maps:

1We use three different variable names x, y, z, because they will later be linked by relations of change of variable.

Theorem 1. For k ⩾ 2, the series of k-rooted maps, k-rooted 2-connected maps and k-rooted 3-connected maps counted according to the number of edges of their quotient map are respectively β-rational, η-rational, and γ-rational. The explicit expressions are given in Appendix A.

For k ⩾ 2, the series of k-rooted maps, k-rooted 2-connected maps and k-rooted 3-connected maps counted according to the number of vertices and the number of faces of their quotient map are respectively (β_{1}, β_{2})-rational, (η_{1}, η_{2})-rational and (γ_{1}, γ_{2})-rational. The explicit expressions are given in Appendix B.

In particular, all these series are algebraic.

To have a uniform presentation, we give all our counting results in terms of generating functions. In the case of 1-connected and 2-connected k-rooted maps, there exist closed formulas for the coefficients in one and in two variables [5]. These formulas can be recovered from our expressions by using Lagrange inversion formulas, as explained in the appendix.

Using the algebraicity of the series of k-rooted maps, methods of computer algebra can be used to quickly extract their initial coefficients, see [10]. Using Burnside’s formula (1) and its version in two variables if counting is done according to the number of vertices and faces, the enumeration of unrooted maps can be performed very efficiently: using Maple, several hundreds of initial coefficients are easily computed. As in [15], the complexity models used here is that of arithmetic operation, where an arithmetic operation is either the addition of two large integers both of size O(N) bits, or it is the multiplication or division of a large integer of size O(N) bits with a “small” integer of size O(log(N)) bits. We also assume that the values of Euler’s totient function are already precomputed (in practice, these are easily calculated on the fly, e.g., using sieve methods).

Theorem 2. For the enumeration of unrooted 2-connected and unrooted 3-con-nected maps with respect to the number of edges, a table of the N first coefficients can be computed in O(N log(N)) operations.

For the enumeration of unrooted 2-connected and unrooted 3-connected maps with respect to the number of vertices and faces, a table of the first coefficients with indices (i, j) verifying i + j ⩽ N can be computed in O(N^{2}) operations.

For unrooted 2-connected maps, the same complexity results were obtained by Liskovets and Walsh [5], with the difference that they give explicit formulas for the coefficients whereas we give explicit formulas for the generating functions. The improvement obtained by our method is for the family of 3-connected maps, which is interesting as these objects correspond to oriented polyhedra. Walsh found no closed formula for the coefficients counting these maps, and proceeded with a costly procedure of iterative extraction of the coefficients from their cycle index sum [14].

In contrast, our method yields explicit (algebraic) expressions for all generating functions of k-rooted 3-connected maps. Our complexity, in O(N log(N)) for one parameter and O(N^{2}) for two parameters, improves significantly on the complexity obtained by Walsh [15], which is O(N^{3}) for one parameter and O(N^{5}) for two parameters.

1. Definitions

1.1. Maps. A map is a proper embedding of a connected graph (with possibly loops and multiple edges) on a closed oriented surface, where proper means that edges are smooth arcs that do not cross. All the maps that are considered in this article are on the sphere. For enumeration, maps are considered up to orientationpreserving homeomorphisms of the topological sphere. Equivalently, two maps are identified if it is possible to obtain the second one from the first one by performing a continuous deformation of the sphere. A map with at least two edges is said to be 2-connected (or non-separable) if it has no loop and if at least two of the vertices have to be removed to disconnect the map. The two maps with one edge (i.e., the loop-map and the link-map) are also considered as 2-connected. A map is said to be 3-connected if it has at least 4 vertices, no loops nor multiple edges, and at least three of the vertices have to be removed to disconnect the map. A map is rooted by marking and orienting one of its edges. This operation suffices to eliminate all non trivial homeomorphisms of the map. Counting rooted maps is easier than counting maps because the root can be used to start a recursive decomposition. For k ⩾ 2, a k-rooted map is a map with k roots, such that the k objects obtained by marking differently (say, in blue) one of the k roots are equal. Rooted maps endowed with an automorphism of order k ⩾ 2 are in bijection with k-rooted maps (see [4] for more details). As k-rooted maps are easier to handle for our purpose, we will manipulate them rather than rooted maps with an automorphism of order k.

1.2. Quadrangulations. A quadrangulation is a map whose faces have degree 4. A quadrangulation is said to be simple if it has no multiple edge. A quadrangulation is said to be irreducible if each 4-cycle of edges of the quadrangulation is the contour of one of its faces. For each quadrangulation, its vertices can be colored in black and white so that each edge connects a black and a white vertex. Such a bicoloration is unique up to the choice of the colors. A quadrangulation endowed with such a bicoloration is said to be bicolored. A bi-rooted quadrangulation is a rooted quadrangulation having a secondary root. This secondary root is differently marked (say in blue), and we allow that it is at the same half-edge as the primary root. Taking the bicoloration into account, a bi-rooted quadrangulation Q is said to be bicolor-consistent if the origins of the two roots have the same color when Q is bicolored.

1.3. Structure of k-rooted maps and method of quotient maps. It was observed by Liskovets [4] that a k-rooted map can be realized as an embedding on the geometrical sphere such that the embedding is invariant by a rotation of angle 2π/k of the sphere ^{2}. In addition, the two points of intersection of the sphere with the rotation-axis are either a vertex or the centre of a face if k > 2, and can also be the middle of an edge if k = 2. These points are called the poles of the k-rooted map. The type of a k-rooted map is the type of its two poles. For example, if the two poles are a vertex and the center of a face, then the k-rooted map is said to have type face-vertex.

If we cut the sphere of the symmetrical embedding along two meridians forming a dihedral angle of 2π/k, we can extract a sector of the map bordered by these two meridians. By pasting together the two meridians, the sector becomes a map on the sphere. The symmetry of order k of the initial geometrical embedding ensures that this map does not depend on the choice of the two meridians. We call it the quotient-map of the k-rooted map. Observe that the quotient map has one root and two marked cells (the poles of the k-rooted map). The method of quotient maps developed by Liskovets consists in counting k-rooted maps of a family by studying the structure of their quotient map. In the case of unconstrained maps it works well, as quotient maps are essentially rooted maps with two marked cells.

1.4. Burnside’s formula adapted to unrooted maps. Consider a family of maps on the sphere (for example the family of 2-connected maps). Let c_{n}, c′_{n} and c_{n}^{(k)} denote respectively the number of unrooted, rooted and k-rooted (k ⩾ 2) maps of the family with n edges. Let c_{ij}, c′_{ij} and c_{ij}^{(k)} denote respectively the number of unrooted, rooted and k-rooted (k ⩾ 2) maps of the family with i + 1 vertices and j + 1 faces. Burnside’s (orbit counting) formula was adapted by Liskovets [4] to give the two following enumerative formulas for unrooted maps, where ϕ(.) is Euler’s totient function:

(2)  2nc_{n} = c′_{n} + ∑_{k=2}^{n} ϕ(k)c_{n}^{(k)},  2(i + j)c_{ij} = c′_{ij} + ∑_{k=2}^{i+j} ϕ(k)c_{ij}^{(k)}.

As a consequence, counting unrooted maps in one parameter (two parameters) comes down to counting rooted maps (already done for 2-connected and 3-connected maps, see [9]) and k-rooted maps of the family with one parameter (two parameters, respectively).

1.5. Bijection between maps and quadrangulations. A classical result in map theory is a bijection between maps and bicolored quadrangulations, that we shall refer to as the angular bijection. We just detail its properties here. The angular bijection is a bijection between maps with n edges (with i vertices and j faces) and bicolored quadrangulations with n faces (with i black and j white vertices, respectively). Precisely, under this bijection, {vertices, faces, edges} of a map correspond to {black vertices, white vertices, faces} of the bicolored quadrangulation.

2This point of view is not topologically relevant but it helps to have a geometrical intuition and it gives a handy way to define the quotient of a k-rooted map.

In addition, rooted maps are in bijection with rooted quadrangulations and krooted maps are in bijection with so called k-rooted bicolored quadrangulations, which are defined as k-rooted quadrangulations such that the origins of the k roots have the same color when the quadrangulation is bicolored. We will only deal with such k-rooted quadrangulations and will shortly call them k-rooted quadrangulations. Observe that the type of a k-rooted map and the type of its associated k-rooted quadrangulation are linked by the above mentioned correspondence: for example 2-rooted maps with type edge-face are in bijection with 2-rooted quadrangulations with type face-white vertex. We have seen in Section 1.3 that the two poles of a k-rooted map are a face or a vertex if k > 2 and can also be an edge if k = 2. Hence, a k-rooted quadrangulation can only have type vertex-vertex if k > 2, and can also have type face-face and type face-vertex if k = 2.

Moreover, the angular bijection has the nice property that 2-connected maps are in bijection with bicolored simple quadrangulations and 3-connected maps are in bijection with bicolored irreducible quadrangulations. As a consequence, counting k-rooted 2-connected maps according to the number of edges (according to the numbers of vertices and faces) comes down to counting k-rooted simple quadrangulations according to the number of faces (according to the numbers of black vertices and white vertices, respectively). The situation is the same for 3-connected maps, but with irreducible quadrangulations instead of simple quadrangulations, see Figure 1.

1.6. Notations and conventions for the generating functions. We will use the letters F, G and H to denote respectively generating functions of k-rooted, k-rooted simple and k-rooted irreducible quadrangulations. We will use the subscripts f, v, b, and w to denote respectively a pole which is a face, a vertex, a black vertex and a white vertex. The subscripts b and w are only used for generating functions with two variables, where we have to take the bicoloration into account. Moreover we will use the exponent (k) to denote a k-rooted quadrangulation. For example, G_{vv}^{(k)}(y) is the series counting k-rooted simple quadrangulations of type vertex-vertex by the number of faces of their quotient map, and H_{bw}^{(k)}(z_{•}, z_{∘}) is the series counting k-rooted irreducible quadrangulations, whose poles are a black and a white vertex, by the number of black and white vertices in their quotient map (and without counting the two axial vertices).

More precisely, we adopt the following conventions for the generating functions. These conventions will always be adopted for the series counting rooted or krooted quadrangulations. The reader is advised to examine them carefully only for the sake of verifying the later obtained equations (Section 3 and Section 4). For the series in one variable, rooted quadrangulations will be counted according to their number of faces, and k-rooted quadrangulations will be counted according to the number of faces in their quotient map without counting the axial faces. For example a 2-rooted quadrangulation of type face-face with 2n + 2 faces will be counted in the coefficient of x^{n} in the series F_{ff}(x). For the series in two variables, rooted quadrangulations will be counted according to their number of black vertices minus 1 and to their number of white vertices minus 1; k-rooted quadrangulations of type vertex-vertex will be counted according to the number of black and white vertices in their quotient map and without counting the two axial vertices; k-rooted quadrangulations of type face-vertex will be counted according to the number of black and white vertices in their quotient map and without counting the vertices incident to the axial face; k-rooted quadrangulations of type face-face will be counted according to the number of black vertices and white vertices of their quotient map and without counting the vertices of one axial face. For example, a 2-rooted irreducible quadrangulation of type “face-face” with 2i + 2 black vertices and 2j + 2 white vertices will be counted in the coefficient of y_{•}^{i}y_{∘}^{j} in the series H_{ff}(y_{•}, y_{∘}); a 2-rooted simple quadrangulation of type “black vertex-face” with 2i + 1 black vertices and 2j + 2 white vertices will be counted in the coefficient of y_{•}^{i}y_{∘}^{j} in the series G_{bf}(y_{•}, y_{∘}); a k-rooted irreducible quadrangulation of type “black vertex-white vertex” with ki + 1 black vertices and kj + 1 white vertices will be counted in the coefficient of z_{•}^{i}z_{∘}^{j} in the series H_{bw}^{(k)}(z_{•}, z_{∘}).

Our conventions and the property that a quadrangulation with n faces has n + 2 vertices yield the following pleasant property: for each family of k-rooted maps, its generating function f(w) in one variable and its generating function f(w_{•}, w_{∘}) in two variables are related by

f(w) = f(w, w).

For example, F_{ff}(x) = F_{ff}(x, x) and H_{vv}(z) = H_{bb}(z, z) + H_{bw}(z, z) + H_{ww}(z, z).

1.7. Algebraic structure of unconstrained k-rooted maps.

Lemma 3. For k ⩾ 2, the generating functions of k-rooted quadrangulations in one (two) variable are β-rational ((β_{1}, β_{2})-rational, respectively).

Proof. We take here only the example of k-rooted quadrangulations of type vertexvertex (the treatment is similar but a little more involved when there is an axial face). From the method of quotient-map of Liskovets, the quotient of a k-rooted quadrangulation of type vertex-vertex with kn faces is a rooted quadrangulation with n faces and two marked vertices. A rooted quadrangulation with n faces has n+2 vertices according to the Euler relation, so that there are (n+2)(n+1)/2 possible choices for a pair of poles. Hence, writing F_{n} for the number of rooted quadrangulations with n faces and F_{vv,n}^{(k)} for the number of k-rooted quadrangulations of type vertex-vertex with kn faces, we have F_{vv,n}^{(k)} = \frac{1}{2}(n + 2)(n + 1)F_{n}. Observe

Figure 2. Tree-decomposition of a quadrangulation by multiple edges.

that this implies that the series counting k-rooted quadrangulations of type vertexvertex by the number of faces of their quotient map does not depend on k. More precisely, we have F_{vv}^{(k)}(x) = \frac{1}{2}x^{2}d^{2}F/dx^{2} + 2xdF/dx + F. The other series counting k-rooted quadrangulations also involve the first and second derivatives (or partial derivatives for two variables) of the series F counting rooted quadrangulations. This series is well-known to be β-rational in one variable [1] and (β_{1}, β_{2})-rational in two variables [11]: F(x) = \frac{β(2−9β)}{(1−3β)^{2}} and F(x_{•}, x_{∘}) = \frac{β_{1}+β_{2}−5β_{1}β_{2}+2β_{1}^{2}+2β_{2}^{2}}{(1−β_{1}−2β_{2})(1−β_{2}−2β_{1})} . In addition, the property of being β-rational ((β_{1}, β_{2})-rational) is stable under taking derivatives. Indeed, dF/dx = (dF/dβ)/(dx/dβ) is the quotient of two β-rational expressions, and we can proceed similarly with two variables. The result follows. □

2. Tree-decompositions

2.1. Tree-decomposition by multiple edges. We explain here how to transform an unrooted quadrangulation Q (that may have multiple edges) into a tree with two kinds of nodes: nodes representing multiple edges and nodes representing simple quadrangulations.

One way to see this decomposition is as follows. Take a multiple edge of Q of multiplicity d. Cut the sphere along each of the d edges forming the multiple edge. In this way we obtain d sectors, each sector being delimited by two consecutive edges of the multiple edge. Now, for each sector, identify the two meridians corresponding to the two edges delimiting the sector by pasting them together. Thus we make out of each sector a map on the sphere, and we can link these d maps, at their edge corresponding to the initial multiple edge, around a new node: this will be the node of the tree corresponding to the multiple edge. Now we can carry on recursively the tree-decomposition for each of the d maps, until all multiple edges have been split into nodes of the tree.

Another way to see this decomposition is to imagine that we “blow” equally, from the interior of the sphere, each of the d sectors delimited by the multiple edge. We obtain thus d components drawn each on a sphere, where the d spheres are connected (glued) at the multiple edge, see Figure 2(b). We can then represent this multiple edge as a rigid link (see Figure 2(c)) around which the d components are linked via their unique edge belonging to the multiple edge. We can then carry on the decomposition for each of the d components.

2.2. Tree-decomposition by separating 4-cycles. We now present a second tree-decomposition, which consists in transforming a simple quadrangulation with at least 3 faces into a tree with two kinds of nodes: nodes corresponding to socalled axis-maps and nodes corresponding to irreducible quadrangulations. The description of this tree-decomposition can also be found in [3]. We describe first in a recursive way the tree-decomposition for rooted objects, giving rise to a (rooted) decomposition-tree. Then, similarly as for the first tree-decomposition, we give a topological argument ensuring that the tree-decomposition can be equivalently performed on unrooted objects.

For r ⩾ 3, we define the axis-map with r faces as the simple quadrangulation consisting of two vertices linked by r parallel chains of 2 edges, each pair of two consecutive paths forming one of the r faces of the axis-map, see Figure 3(a). The two vertices linked by the r chains are called the extremal vertices of the axis-map.

Now we state the following lemma of decomposition of a rooted simple quadrangulation Q with at least 3 faces:

Lemma 4. There exists a unique rooted quadrangulation Q_{0}, with maximal possible number r + 1 of faces such that:

• Q_{0} is an axis-map or an irreducible quadrangulation.

• There are r rooted simple quadrangulations Q_{1}, …, Q_{r} with at least 2 faces (including the rooted one) such that Q can be seen as the quadrangulation Q_{0} where each of the r non root faces f_{i} of Q_{0} is substituted in a canonical way by one of the Q_{i}, 1 ⩽ i ⩽ r, the contour of f_{i} being replaced by the contour of the root face of Q_{i}.

Proof. If there exists an internal chain of length 2 between two opposite vertices of the outer face of Q, take the sequence of all chains of length 2 (including the two outer ones) between these two vertices. Forgetting all other edges, we get an axis-map. Hence Q can be seen as this axis-map where each non root face is substituted by a quadrangulation.

Otherwise, define a proper 4-cycle of Q as a 4-cycle different from the contour of the root face of Q. Here we have to see Q as drawn in the plane with its root face as infinite face, so that we can distinguish interior and exterior. A proper 4-cycle is said to be maximal if it is not strictly included in the interior of any other proper 4-cycle. As Q has no path of length 2 connecting two opposite vertices of its outer face, it can easily be shown (see [9]) that the interiors of maximal proper 4-cycles partition the interior of the outer face of Q. Let Q_{0} be the rooted quadrangulation obtained from Q by keeping the contour of the root face and of the maximal proper 4-cycles of Q. The quadrangulation Q_{0} is irreducible by maximality of the 4-cycles Figure 3. An axis-map with 4 faces (a). The tree-decomposition of a quadrangulation by separating 4-cycles, performed with a root

(b) or without a root (c). The corresponding tree has 3 nodes: one axis-map and two irreducible quadrangulations (both the cube).

of which we have kept the contour. Hence we are in the case where Q can be seen as a rooted irreducible quadrangulation where each inner face is substituted by a rooted quadrangulation. □

The first (second) case of Lemma 4 corresponds to the case where the root node of the decomposition-tree is an axis-map (an irreducible quadrangulation, respectively). For example, on Figure 3(b), the rooted quadrangulation can be seen as a (rooted) cube where two faces are substituted by another cube and by an axis-map with 3 faces.

Remark. We make the following distinction when the root node of the decomposition-tree is an axis-map: if the parallel chains of length 2 are incident to the origin of the root, the root node of the tree is called a vertical axis-map, otherwise it is called a horizontal axis-map.

Now we can carry on the tree-decomposition for each rooted quadrangulation Q_{i} with 1 ⩽ i ⩽ k. Thus, we get finally a (rooted) decomposition-tree with two types of nodes: axis nodes and nodes that are irreducible quadrangulations. Observe that, if Q_{0} and the root node of one of the Q_{i} are simultaneously axis-maps, then they are stretched in perpendicular directions by maximality of the number of faces of Q_{0}.

The preceding decomposition of rooted objects is such that, as in Section 2.1, we can “blow” from the interior of the sphere to “sculpt” the quadrangulation Q into a tree whose nodes are irreducible quadrangulations and nodes that are axis-maps. The nodes are connected (glued) at so-called interconnection-faces, see Figure 3(c). Hence we can say that an unrooted simple quadrangulation “is” its tree-decomposition after a judicious deformation of the sphere. Thus we see that the topological shape of the decomposition-tree in the space does not depend on the face of the quadrangulation where we choose to place the root to start the tree-decomposition. Hence an unrooted simple quadrangulation yields an unrooted decomposition-tree.

Figure 4. Repercussion of the symmetry of a k-rooted quadrangulation on its decomposition-tree.

Figure 5. Construction of a k-rooted quadrangulation of type a (Figure a), and of type b (Figure b).

The important point is that the definition does not require that T is rooted. Hence the center is invariant under any symmetry of T.

3. Using the tree-decomposition by multiple edges to enumerate unrooted 2-connected maps

3.1. Repercussion of the symmetry on the decomposition-tree. As we have seen in Section 2.1, the decomposition-tree of a quadrangulation Q is obtained by deforming the sphere in such a way that multiple edges can be split into link-nodes. This gives rise to a decomposition-tree “living” in the 3D-space. In addition, if Q is k-rooted (k ⩾ 2), then its decomposition-tree is invariant under the rotationsymmetry of order k induced by its k-root.

Center of a tree. The center of a tree T is defined in the following recursive way. If T is reduced to an edge (a node), then the center of T is this edge (this node, respectively). Otherwise, remove all leaves of T to obtain a (shrunk) tree T̃. Then the center of T is defined to be the center of T̃.

Proposition 5. For k ⩾ 2, the center of the decomposition-tree of a k-rooted quadrangulation is a node (not an edge) of the tree, and it is the unique node of the tree fixed by the symmetry induced by the k-root. This node is called the core-node of the decomposition-tree.

Proof. Assume that several nodes of the decomposition-tree are fixed by the symmetry. Then the axis of the rotation-symmetry has to pass by all these nodes. Hence, these nodes form a chain x_{0}, …, x_{k}, where x_{i} is connected to x_{i+1} at a common edge e_{i} of Q. As a consequence, the symmetry has to be of order 2 and to turn over such an edge e_{i}. This is impossible, because what we shortly call k-rooted quadrangulations are indeed k-rooted quadrangulations such that the origins of the k roots have the same color when Q is bicolored. In particular, the symmetry of the k-root can not exchange the two extremities of an edge of Q. Hence, at most one node of the tree can be fixed by the symmetry. Now assume that the center of the decomposition-tree is an edge E. This edge of the tree connects a node of type multiple-edge to a node that is a simple-quadrangulation Q_{s} at an edge e of Q_{s}. In addition, as noted in the definition of the center of the tree, E has to be fixed by the symmetry induced by the k-root. There are two ways the symmetry can fix E: either it exchanges its two extremities, which is impossible as they are nodes of different types; or it fixes its two extremities, which is impossible because it would imply the presence of more than one node of the tree fixed by the symmetry. □

There are two possibilities for the core-node: either it is a node of type multiple edge –we say that Q has type a– or it is a node of type simple quadrangulation –we say that Q has type b–.

3.2. Construction of a k-rooted quadrangulation of type a. First we need to define a simply rooted quadrangulation as a quadrangulation whose root edge does not belong to a multiple edge.

Now we explain how to construct a k-rooted quadrangulation whose center of the decomposition-tree is a multiple edge with multiplicity k · d (d ⩾ 1), see Figure 5(a). Take a bi-rooted, simply-rooted (i.e., whose primary root is a simple edge) quadrangulation Q_{1}. Cut it along its primary root-edge, thus transforming Q_{1} into a sector with two bordering meridians. For convenience, we consider the root as an arrow placed slightly on the right of the root edge, so that cutting along the root edge does not “split” the root. Among these two meridians, we call root-meridian the one having the root slightly on its right after the cutting.

Now take d−1 simply rooted quadrangulations Q_{2}, …, Q_{d} and perform the same cutting operation on them as on Q_{1}. Then paste the root meridian of Q_{2} with the non-root meridian of Q_{1}, the pasting operation being such that the orientations of the roots of the two sectors coincide. Then, iteratively for each 2 ⩽ i ⩽ d, paste the root meridian of Q_{i} with the non-root meridian of Q_{i−1}, so as to obtain a big sector S whose root meridian is the root meridian of Q_{1}. Now make k copies S_{1}, …, S_{k} of S and, for each 1 ⩽ i ⩽ k, paste the root meridian of S_{i} with the non-root meridian of S_{i−1}. In this way we obtain finally a quadrangulation (on the sphere) consisting of k identical sectors, each carrying a blue root (the secondary root of Q_{1}). By erasing the mark of the primary root of Q_{1} and of the roots of Q_{2} … Q_{d} in each sector, we obtain a k-rooted quadrangulation of type a, see Figure 5(a). Observe that each k-rooted quadrangulation of type a is obtained exactly twice by this construction. Indeed, the inverse operation consists in choosing an extremity v (two possibilities) of the central multiple edge and then orienting all edges of the multiple edge toward v.

Observe also that, if Q_{1} is taken to be bi-rooted bicolor-consistent, then the 2-fold ambiguity of the construction disappears and it becomes a bijection.

We write f(x) for the series counting simply rooted quadrangulations by their number of faces. Observe that the generating function F(x) of rooted quadrangulations and f(x) are related by F(x) = f(x)/(1 − f(x)), following from the fact that a rooted quadrangulation whose root edge has multiplicity d can be decomposed into d simply rooted quadrangulations. The construction given above allows us to express the generating function F_{vv}^{(k)a}(x) of k-rooted quadrangulations of type a in terms of f(x):

F_{vv}^{(k)a}(x) = \frac{1}{2}(4xf′(x)).\frac{1}{1 − f(x)},

where we use the subscript vv for F_{vv}^{(k)a}(x) because all k-rooted quadrangulations of type a clearly have type vertex-vertex.

3.3. Construction of a k-rooted quadrangulation of type b. In this section, k-rooted quadrangulation whose core-node is a simple quadrangulation are constructed as composed objects, see Figure 5(b). Take a k-rooted simple quadrangulation Q_{s}. Then either leave the k root edges untouched (Case 1) or perform the following operation (Case 2): take a bi-rooted bicolor-consistent quadrangulation Q̃. Then cut Q_{s} along each of its k root edges and cut Q̃ along its primary root edge, transforming Q̃ into a sector S bordered by two meridians. Take k copies of S and for each root-edge e of Q_{s}, place a copy of S in the empty sector of Q_{s} left by cutting e. This substitution is done by pasting the two meridians of S with the two border-edges of Q_{s} created by cutting e, and by making the orientation of e and of the primary root edge of S coincide.

Proceed similarly for each k-orbit of non-root edges of Q_{s}, with the only difference that the quadrangulation used for the substitution is not bi-rooted but just rooted. Finally, keep only the k marks of the roots of Q_{s} if we are in Case 1 (i.e., no substitution at the root edges of Q_{s}), and keep only the marks of the secondary roots of the k copies of Q̃ if we are in Case 2. Thus, we obtain a k-rooted quadrangulation Q of type b.

Observe that k-rooted quadrangulations of type b obtained by this construction always have the following property: their k root edges are simple if their incident face (the face on their right) belongs to the central simple quadrangulation (because this case corresponds to Case 1 where there is no substitution at the root edges of Q_{s}). The missing k-rooted quadrangulations of type b, i.e., those whose root edges are not simple and are incident to the central simple quadrangulation, are obtained by the same construction, with the difference that we always cut the k root edges of Q_{s}. Then the other difference is that the first substituted quadrangulation Q̃ is not bi-rooted but just rooted. At the end of this construction, we only keep the marks of the k roots of Q_{s}.

Similarly as in Section 3.2, these two complementary constructions allow us to obtain all k-rooted quadrangulations of type b in a bijective way. We introduce the family E as the union of the set of bi-rooted bicolor consistent quadrangulations, of the set of rooted quadrangulations, and of the link-map (the map with one edge). The construction can be summarized by saying that the root edges of Q_{s} are substituted by k copies of an object of E. We write E(x) for the series counting objects of E by their number of faces, so that E(x) = 2xF′(x) + F(x) + 1.

We write G_{vv,n}^{(k)} for the number of k-rooted simple quadrangulations with n korbits of faces. A quadrangulation has always doubly more edges than faces, so that an object counted by G_{vv,n}^{(k)} has 2n orbits of k edges.

The construction by substitution gives rise to the following equation for the case where Q_{s} has type vertex-vertex,

F_{vv}^{(k)b}(x) := ∑_{n} F_{vv,n}^{(k)b}x^{n} = ∑_{n} G_{vv,n}^{(k)}E(x) (1 + F(x))^{2n−1}

= \frac{E(x)}{1 + F(x)}G_{vv}^{(k)} ((1 + F(x))^{2}) .

Similarly, the two following expressions can be obtained, corresponding respectively to the case where Q_{s} has type face-vertex and type face-face:

E(x)G_{vf}^{(2)} ((1 + F(x))^{2}) ,  E(x)(1+F(x))G_{ff}^{(2)} ((1 + F(x))^{2}) .

3.4. Obtaining the equations. As k-rooted quadrangulations are partitioned into two sets whether their core-node is a multiple edge or a simple quadrangulation, we obtain the following equations by taking the sum of the series obtained in Section 3.2 and Section 3.3:

(3)  F_{vv}^{(k)}(x) = 2\frac{xf′(x)}{1 − f(x)} + \frac{E(x)}{1 + F(x)}G_{vv}^{(k)} ((1 + F(x))^{2}) ,
(4)  F_{vf}^{(2)}(x) = E(x)G_{vf}^{(2)} ((1 + F(x))^{2}) ,
(5)  F_{ff}^{(2)}(x) = E(x)(1 + F(x))G_{ff}^{(2)} ((1 + F(x))^{2}) ,

where the only unknown series are G_{vv}^{(k)}, G_{vf}^{(2)} and G_{ff}^{(2)}.

Similar equations can be easily obtained in two variables by taking the bicoloration of vertices into account. We define df(x_{•}, x_{∘}) = \frac{d}{dt}f(tx_{•}, tx_{∘})_{t=1} and write E(x_{•}, x_{∘}) for the series in two variables counting the family E. It is easy to establish, having conventions of Section 1.6 in mind and using Euler relation (i.e., the sum of vertices and faces is the number of edges +2), that E(x_{•}, x_{∘}) = 2\frac{d}{dt}F(tx_{•}, tx_{∘})_{t=1} + F(x_{•}, x_{∘}) + 1. Then Equation (3) becomes for example:

(6)  \{ \begin{matrix}F_{bw}^{(k)}(x_{•}, x_{∘}) = 2\frac{df}{1−f} + \frac{E}{1+F}G_{bw}^{(k)} (x_{•}(1 + F)^{2}, x_{∘}(1 + F)^{2}) \\ F_{bb}^{(k)}(x_{•}, x_{∘}) = \frac{E}{1+F}G_{bb}^{(k)} (x_{•}(1 + F)^{2}, x_{∘}(1 + F)^{2}) \\ F_{ww}^{(k)}(x_{•}, x_{∘}) = \frac{E}{1+F}G_{ww}^{(k)} (x_{•}(1 + F)^{2}, x_{∘}(1 + F)^{2}) , \end{matrix}

where all series (including f and F) have two variables, one for the number of black vertices, and one for the number of white vertices.

As observed in Lemma 3, the series F_{vv}^{(k)} (and it is also the case for F_{bw}^{(k)}, F_{bb}^{(k)} and F_{ww}^{(k)}) does not depend on k. Hence it follows from the form of Equation (3) and (6) that the series G_{vv}^{(k)} (and also the series G_{bw}^{(k)}, G_{bb}^{(k)} and G_{ww}^{(k)}) does not depend on k. Hence the exponent (k) can be omitted.

Lemma 6. For k ⩾ 2, the generating functions of k-rooted simple quadrangulations in one variable (two variables) are η-rational ((η_{1}, η_{2})-rational, respectively).

Proof. From Lemma 3, we know that F_{vv}(x), F_{vf}(x) and F_{ff}(x) are β-rational, and so are x (because x = β − 3β^{2}), F(x) (as proved in [13]), f(x) (because F = f/(1 − f)), and E(x) (because β-rationality is stable under differentiation). Hence it follows from Equations (3),(4) and (5) that G_{vv} (x(1 + F)^{2}), G_{vf} (x(1 + F)^{2}) and G_{ff} (x(1 + F)^{2}) are β-rational. Now we have to make the change of variable y = x(1+F)^{2}. It was observed in [1] that β(x) = η(y)/(1+3η(y)) when y and x are linked by the change of variable y = x(1 + F)^{2}. Hence, replacing β(x) by η(y)/(1 + 3η(y)) in the respective β-rational expression of G_{vv} (x(1 + F)^{2}), G_{vf} (x(1 + F)^{2}) and G_{ff} (x(1 + F)^{2}), we obtain η-rational expressions for G_{vv}(y), G_{vf}(y) and G_{ff}(y).

We can proceed similarly in two variables, using the fact that β_{1}(x_{•}, x_{∘}) and β_{2}(x_{•}, x_{∘}) have a rational expression in terms of η_{1}(y_{•}, y_{∘}) and η_{2}(y_{•}, y_{∘}) when (y_{•}, y_{∘}) and (x_{•}, x_{∘}) are linked by the change of variable (y_{•}, y_{∘}) = (x_{•}(1+F)^{2}, x_{∘}(1+ F)^{2}). □

Lemma 7. The N initial coefficients counting unrooted 2-connected maps according to the number of edges can be computed with O(N log(N)) operations.

The table of initial coefficients with indices (i, j) and i+j ⩽ N counting unrooted 2-connected maps according to the number of vertices and faces can be computed with O(N^{2}) operations.

Proof. First we use the following notation. For a series f in one variable (two variables), we denote by C_{N}(f) the number of operations necessary to compute its N initial coefficients (its coefficients with indices (i, j) and i + j ⩽ N, respectively). Writing g_{n} (g_{ij}) for the number of unrooted 2-connected maps with n edges (i + 1 vertices and j + 1 faces, respectively), Burnside’s formula (2) translates to the following equations on series:

∑_{n} 2ng_{n}y^{n} = G(y) + yG_{vf}(y^{2}) + y^{2}G_{ff}(y^{2}) + ∑_{k⩾2}ϕ(k)G_{vv}(y^{k}),
∑_{i,j} 2(i + j)g_{ij}y_{•}^{i}y_{∘}^{j} = G(y_{•}, y_{∘}) + y_{∘}G_{bf}(y_{•}^{2}, y_{∘}^{2}) + y_{•}G_{wf}(y_{•}^{2}, y_{∘}^{2}) + y_{•}y_{∘}G_{ff}(y_{•}^{2}, y_{∘}^{2})

+ ∑_{k⩾2}ϕ(k) (\frac{y_{•}}{y_{∘}} G_{bb}(y_{•}^{k}, y_{∘}^{k}) + G_{bw}(y_{•}^{k}, y_{∘}^{k}) + \frac{y_{∘}}{y_{•}} G_{ww}(y_{•}^{k}, y_{∘}^{k})) .

According to [1], G(y) is η-rational; and according to Lemma 6, G_{vf}(y), G_{ff}(y) and G_{vv}(y) are η-rational. Hence these series are algebraic because they live in the algebraic extension of the algebraic series η(y). Hence, they are differentiably finite (see [12]), i.e., solution of a linear differential equation with polynomial coefficients. Taking coefficient [y^{n}] in this differential equation yields a linear recurrence with polynomial coefficients for the coefficients of these series. As a consequence, the N initial coefficients of these series can be computed with O(N) “arithmetical” operations. Hence, C_{N} (∑ 2ng_{n}) = C_{N}(G) + C_{N/2}(G_{vf} + G_{ff}) + ∑_{k=2}^{N} C_{N/k}(G_{vv}) = O(N) + O(N/2) + ∑_{k=2}^{N} O(N/k) = O(N log(N)).

Similarly, an algebraic series in two variables is also D-finite. Hence its coefficients verify two linear recurrences, one for each index. As a consequence, if f(y_{•}, y_{∘}) is algebraic, then C_{N}(f) = O(N^{2}). As the series of rooted and k-rooted simple quadrangulations in two variables are (η_{1}, η_{2})-rational, they are algebraic. Hence, C_{N} (∑_{i,j} 2(i + j)g_{ij}) = C_{N}(G) + C_{N/2}(G_{ff} + G_{bf} + G_{wf}) + ∑_{k=2}^{N} C_{N/k}(G_{bb} +

G_{bw} + G_{ww}) = O(N) + O((N/2)^{2}) + ∑_{k=2}^{N} O((N/k)^{2}) = O(N^{2}), where we use the fact that ∑_{k} 1/k^{2} converges. □

4. Using the tree-decomposition by separating 4-cycles to enumerate unrooted 3-connected maps

4.1. Introduction. In this part, we use the tree-decomposition by separating 4cycles presented in Section 2.2. This tree-decomposition states that a simple quadrangulation can be seen as an arborescent structure whose nodes are either irreducible quadrangulations or axis-maps. From this decomposition, we will obtain equations linking generating functions of k-rooted irreducible quadrangulations and generating functions of k-rooted simple quadrangulations. As we have already obtained expressions for the generating functions of k-rooted simple quadrangulations in Section 3, we will obtain from these equations the generating functions of k-rooted irreducible quadrangulations, from which unrooted 3-connected maps can be enumerated using the angular bijection and Burnside’s formula, see Figure 1.

We treat first the case of k-rooted objects with k ⩾ 3. The case of 2-rooted objects is more difficult (for example a symmetry of order 2 of an axis-map can exchange its extremal vertices), and will be thoroughly treated in Section 4.3.

4.2. The case of k-rooted irreducible quadrangulations with k ⩾ 3. A first important remark is that all k-rooted quadrangulations have type vertex-vertex for k > 2, as we have seen in Section 1.3. We introduce the families W of rooted simple quadrangulations with at least two faces (thus excluding the degenerated one-face quadrangulation) and the family J consisting of the objects of W whose root node of the decomposition tree is not an horizontal axis-map. We write W(y) and J(y) for the series counting these two families by their number of faces. Observe that W(y) = G(y)−2y, where G(y) is the series of rooted simple quadrangulations, and W(y)/y = \frac{J(y)/y}{1−J(y)/y}. We define also the families W′ and J′ of objects of W and J having a secondary root incident to a face different from the root face. The series counting objects of W′ and J′ by their number of faces are respectively 4C(y) and 4B(y) where C(y) = y \frac{d}{dy}W(y) − W(y) and B(y) = y \frac{d}{dy}J(y) − J(y).

Let Q be a k-rooted simple quadrangulation (k ⩾ 3) with at least 3 faces. The decomposition-tree of Q is invariant under the symmetry of order k induced by the k-root of Q. As k > 2, the center of the decomposition-tree is a node (not an edge) and is the unique node invariant by the symmetry. We call this node the core-node (we will see later that the definition of the core-node requires more attention for 2-rooted objects). Two cases can arise: either the core-node is an axis-map —we say that Q has type 𝔞— or it is an irreducible quadrangulation —we say that Q has type 𝔟—.

4.2.1. Construction of k-rooted simple quadrangulations of type 𝔞. Similarly as in Section 3.2, we give a construction, in terms of a composed object, of a k-rooted simple quadrangulation whose core-node is an axis-map with k · d faces. Take a k-rooted axis-map with k ·d faces and whose roots point toward the same extremal vertex of the axis-map, which we call the pointed extremal vertex. Then take k copies of an object Q_{1} ∈ J′ and substitute each root face of the axis-map by one of these copies, making the primary roots of the copies of Q_{1} oriented toward the pointed extremal vertex of the axis-map. Proceed similarly for each k-orbit of nonroot faces of the axis-map, with the only difference that the substituted objects are k copies of an object of J instead of J′. Finally keep only the marks of the secondary root of the k copies of Q_{1}.

As in Section 3.2, each k-rooted simple quadrangulation of type 𝔞 is obtained exactly twice by this construction. Hence, the series counting k-rooted simple quadrangulations of type 𝔞 is

G_{vv}^{(k)𝔞}(y) = 2\frac{B(y)}{y} \frac{1}{1 − J(y)/y} .

4.2.2. Construction of k-rooted simple quadrangulations of type 𝔟. As in Section 3.3, we give a construction of k-rooted simple quadrangulations of type 𝔟 as composed objects. Take a k-rooted irreducible quadrangulation Q_{irr}. Take k copies of an object Q_{1} of W′ and substitute each root face of Q_{irr} by one of the copies of Q_{1} in a “canonical” way, e.g., by superimposing the primary root edge of Q_{1} with the root edge of the face where the substitution takes place. Then proceed similarly for each k-orbit of non-root faces of Q_{irr}, with the difference that the substituted objects are k copies of an object of W instead of W′. Finally keep only the marks of the secondary root of the k copies of Q_{1}.

By this construction, all k-rooted simple quadrangulations of type 𝔟 are obtained exactly 4 times. Indeed, as a quadrangular face has 4 sides, there are 4 possibilities to guess the primary root edge of the k copies of Q_{1}. Hence the series counting k-rooted simple quadrangulations of type 𝔟 is given by the following expression, involving the series H_{vv}^{(k)}(z) of k-rooted irreducible quadrangulations,

G_{vv}^{(k)𝔟} = \frac{1}{4} ∑_{n} H_{vv,n}^{(k)} \frac{4C(y)}{y} (\frac{W(y)}{y})^{n−1} = \frac{C(y)}{W(y)}H_{vv}^{(k)}(W(y)/y).

4.2.3. Obtaining the equations. The set of k-rooted simple quadrangulations is partitioned into two sets whether the core-node is an axis-map or an irreducible quadrangulation. Hence, summing the series obtained in Section 4.2.1 and Section 4.2.2, we obtain the following equation linking the series of k-rooted simple quadrangulations with the series of k-rooted irreducible quadrangulations, for k > 2,

(7)  G_{vv}^{(k)}(y) = 2\frac{B(y)}{y} \frac{1}{1 − J(y)/y} + \frac{C(y)}{W(y)}H_{vv}^{(k)}(W(y)/y).

Similar equations can easily be obtained in two variables by taking the bicoloration of Q into account. Writing C(y_{•}, y_{∘}) = y_{•} \frac{∂W}{∂y_{•}} + y_{∘} \frac{∂W}{∂y_{∘}} − W and B(y_{•}, y_{∘}) = y_{•} \frac{∂J}{∂y_{•}} + y_{∘} \frac{∂J}{∂y_{∘}} − J for the versions in two variables of C(y) and B(y), the version in two variables of Equation (7) is

(8)  G_{bb}^{(k)}(y_{•}, y_{∘}) = \frac{B}{y_{•}} \frac{1}{1 − J/y_{•}} + \frac{C}{W}H_{bb}^{(k)}(W/y_{∘}, W/y_{•}),
(9)  G_{ww}^{(k)}(y_{•}, y_{∘}) = \frac{B}{y_{∘}} \frac{1}{1 − J/y_{∘}} + \frac{C}{W}H_{ww}^{(k)}(W/y_{∘}, W/y_{•}),
(10)  G_{bw}^{(k)}(y_{•}, y_{∘}) = \frac{C}{W}H_{bw}^{(k)}(W/y_{∘}, W/y_{•}).

Observe that these equations are the same for all values of k. As we have already seen that G_{vv}^{(k)}(y) does not depend on k, H_{vv}^{(k)}(z) does also not depend on k, so that we can denote this series by H_{vv}^{⩾3}(z). The same remark holds for the series in two variables, we adopt the same notation for the exponent.

Lemma 8. For k ⩾ 3, the series of k-rooted irreducible quadrangulations in one variable (two variables) is γ-rational ((γ_{1}, γ_{2})-rational, respectively) and does not depend on k.

Proof. The proof is similar to the proof of Lemma 6. In one variable, we use the form of Equation (7) to see that H_{vv}^{⩾3}(W(y)/y) is η-rational. Indeed all series appearing in Equation (7) and different from H_{vv}^{⩾3}(W(y)/y) have an explicit ηrational expression, as these series involve the series W (which is η-rational from [9]) or the series J (equal to W/(1+W/y)) or their derivatives, which are also η-rational because dW/dy = (dW/dη)/(dy/dη). Then we use the fact, shown in [9], that η(y) = γ(z)/(2γ(z) + 1) when z and y are linked by the change of variable z = W(y)/y. Substituting η by γ/(2γ +1) in the η-rational expression of H_{vv}^{⩾3}(W(y)/y), we obtain a γ-rational expression for H_{vv}^{⩾3}(z).

The proof in two variables is similar, using in particular the fact that η_{1}(y_{•}, y_{∘}) and η_{2}(y_{•}, y_{∘}) have a rational expression in terms of γ_{1}(z_{•}, z_{∘}) and γ_{2}(z_{•}, z_{∘}) when (z_{•}, z_{∘}) and (y_{•}, y_{∘}) are linked by the change of variable (z_{•}, z_{∘}) = (W/y_{∘}, W/y_{•}).

□

4.3. The case of 2-rooted irreducible quadrangulations.

4.3.1. Introduction. The case of 2-rooted objects requires a careful treatment. As we have seen in Section 1.3, a 2-rooted quadrangulations can have one or two axial faces. In addition, as opposed to the case k > 2, other nodes than the center of the decomposition tree can be fixed by the symmetry of order 2 induced by the 2-root. Another difficulty is the fact that a symmetry of order 2 of an axis-map can exchange its extremal vertices.

The object of this section is to show a result similar to Lemma 8 for 2-rooted objects, i.e., we would like to show first that the series of 2-rooted irreducible quadrangulations in one variable (two variables), composed with W(y)/y ((W/y_{∘}, W/y_{•})) are η-rational ((η_{1}, η_{2})-rational, respectively). From that, as in Lemma 8, it will follow that all series of 2-rooted irreducible quadrangulations in one variable (two variables) are γ-rational ((γ_{1}, γ_{2})-rational, respectively). In order to prove this result, we have to find simple equations linking the series of 2-rooted simple quadrangulations and the series of 2-rooted irreducible quadrangulations. This requires to find a convenient partition of 2-rooted irreducible and 2-rooted simple quadrangulations in several families, and then relate the families by decompositions.

4.3.2. Introduction of families of 2-rooted simple and irreducible quadrangulations. We define here 5 families of 2-rooted simple quadrangulations and 5 families of 2rooted irreducible quadrangulations that partition respectively the set of 2-rooted simple and the set of 2-rooted irreducible quadrangulations.

We will obtain 5 equations linking the 5 generating functions of irreducible quadrangulations, which are unknown, and the 5 generating functions of 2-rooted simple quadrangulations, which are known. Moreover, we will see that this system of 5 equations is upper triangular, so that it is easy to solve.

We define:

• The families G_{vv}^{(2)} (H_{vv}^{(2)}) of 2-rooted simple (irreducible) quadrangulations of type vertex-vertex. We write G_{vv}^{(2)}(y) (H_{vv}^{(2)}(z)) for their generating functions. If the bicoloration is taken into account, G_{vv}^{(2)} (H_{vv}^{(2)}) is partitioned into three families G_{bb}^{(2)}, G_{ww}^{(2)}, G_{bw}^{(2)} (H_{bb}^{(2)}, H_{ww}^{(2)}, H_{bw}^{(2)}) depending on the colors (black or white) of the two axial vertices. We write G_{bb}^{(2)}(y_{•}, y_{∘}), G_{ww}^{(2)}(y_{•}, y_{∘}), G_{bw}^{(2)}(y_{•}, y_{∘}) (H_{bb}^{(2)}(z_{•}, z_{∘}), H_{ww}^{(2)}(z_{•}, z_{∘}), H_{bw}^{(2)}(z_{•}, z_{∘})) for the associated series.

• The families G_{v𝔣}^{(2)} (H_{v𝔣}^{(2)}) of 2-rooted simple (irreducible) quadrangulations of type face-vertex and such that the 2-root is not incident to the axial face. Hence the two roots are incident to two different faces that form an orbit of faces of size 2 for the symmetry induced by the 2-root. We write G_{v𝔣}^{(2)}(y) (H_{v𝔣}^{(2)}(z)) for their respective generating functions. If we take the bicoloration into account, G_{v𝔣}^{(2)} (H_{v𝔣}^{(2)}) is partitioned into two families G_{b𝔣}^{(2)}, G_{w𝔣}^{(2)} (H_{b𝔣}^{(2)}, H_{w𝔣}^{(2)}) depending on the color of the axial vertex. We write G_{b𝔣}^{(2)}(y_{•}, y_{∘}), G_{w𝔣}^{(2)}(y_{•}, y_{∘}) (H_{b𝔣}^{(2)}(z_{•}, z_{∘}), H_{w𝔣}^{(2)}(z_{•}, z_{∘})) for the associated series.

• The families G_{v𝔣′}^{(2)} (H_{v𝔣′}^{(2)}) of 2-rooted simple (irreducible) quadrangulations of type face-vertex and such that the 2-root is incident to the axial face. We write G_{v𝔣′}^{(2)}(y) (H_{v𝔣′}^{(2)}(z)) for their respective generating functions. Similarly as above, taking the bicoloration into account, G_{v𝔣′}^{(2)} (H_{v𝔣′}^{(2)}) is partitioned in the families G_{b𝔣′}^{(2)}, G_{w𝔣′}^{(2)} (H_{b𝔣′}^{(2)}, H_{w𝔣′}^{(2)}) depending on the color of the axial vertex. We write G_{b𝔣′}^{(2)}(y_{•}, y_{∘}), G_{w𝔣′}^{(2)}(y_{•}, y_{∘}), (H_{b𝔣′}^{(2)}(z_{•}, z_{∘}), H_{w𝔣′}^{(2)}(z_{•}, z_{∘})) for the associated series.

• The families G_{𝔣𝔣}^{(2)} and H_{𝔣𝔣}^{(2)} respectively of 2-rooted simple and irreducible quadrangulations of type face-face and such that the 2-root is not incident to an axial face. In one variable (two variables), we write G_{𝔣𝔣}^{(2)}(y) and H_{𝔣𝔣}^{(2)}(z) (G_{𝔣𝔣}^{(2)}(y_{•}, y_{∘}) and H_{𝔣𝔣}^{(2)}(z_{•}, z_{∘})) for their generating functions.

• The families G_{𝔣𝔣′}^{(2)} (H_{𝔣𝔣′}^{(2)}) of 2-rooted simple (irreducible) quadrangulations of type face-face and such that the 2-root is incident to an axial face. In one variable (two variables), we write G_{𝔣𝔣′}^{(2)}(y) and H_{𝔣𝔣′}^{(2)}(z) (G_{𝔣𝔣′}^{(2)}(y_{•}, y_{∘}) and H_{𝔣𝔣′}^{(2)}(z_{•}, z_{∘})) for their generating functions.

Proposition 9. The generating functions of the 5 families of 2-rooted simple quadrangulations in one variable (two variables) are η-rational ((η_{1}, η_{2})-rational, respectively).

Proof. The families of 2-rooted simple quadrangulations of type vertex-vertex have already been proved in Section 3 to be η-rational in one variable and (η_{1}, η_{2})- rational in two variables.

We take the example of G_{𝔣𝔣′}^{(2)}(y). Let G_{ff,n} (G_{𝔣𝔣′,n}^{(2)}) be the number of 2-rooted simple quadrangulations of type face-face (of objects of G_{𝔣𝔣′}^{(2)}, respectively) with 2n + 2 faces. An object of G_{𝔣𝔣′,n}^{(2)} has (2n + 2) faces, hence (8n + 8) half-edges, hence (4n + 4) 2-orbits of half-edges. From this object, we can construct a bi-2-rooted object by marking differently one of the (4n + 4) orbits of half-edges. We obtain thus bijectively all bi-2-rooted simple quadrangulations of type face-face such that the first 2-root is incident to an axial face. Hence the family of these objects has cardinality (4n + 4)G_{𝔣𝔣′,n}^{(2)}. There is a second way to construct such a bi-2-rooted object, by taking a 2-rooted quadrangulation of type face-face and marking differently one of the 4 orbits of two half-edges that are incident to one of the two axial faces.

The two equivalent constructions yield the formula (4n + 4)G_{𝔣𝔣′,n}^{(2)} = 4G_{ff,n}. Hence, G_{𝔣𝔣′}^{(2)}(y) = 1/y ∫ G_{ff}(y)dy. We know that G_{ff}(y) = \frac{1}{(1−3η(y))(1−η(y))}. In

addition, y = η(1 − η)^{2}, so that dy = (1 − 3η)(1 − η)dη. Hence, G_{𝔣𝔣′}^{(2)}(y) = \frac{1}{η(1−η)^{2}} ∫ \frac{1}{(1−3η)(1−η)}(1 − 3η)(1 − η)dη = \frac{1}{η(1−η)^{2}} ∫ dη = \frac{1}{(1−η)^{2}} . We also obtain di-

rectly G_{𝔣𝔣}^{(2)}(y) = G_{ff}(y) − G_{𝔣𝔣′}^{(2)}(y) = \frac{2η}{(1−3η)(1−η)^{2}} . The case of G_{v𝔣′}^{(2)}(y) can be treated

similarly, yielding G_{v𝔣′}^{(2)}(y) = 2η/(1−η) and G_{v𝔣}^{(2)}(y) = G_{vf}(y)−G_{v𝔣′}^{(2)}(y) = \frac{4η}{(1−3η)(1−η)}.

Let us now deal with the case of two variables. We would like to obtain an (η_{1}, η_{2})-rational expression for G_{𝔣𝔣′}(y_{•}, y_{∘}) from the (η_{1}, η_{2})-rational expression of G_{ff}(y_{•}, y_{∘}). The two equivalent constructions of bi-2-rooted objects yields the equation (i + j + 1)G_{𝔣𝔣′,i,j}^{(2)} = G_{ff,i,j}. Hence, we have to “integrate” G_{ff}(y_{•}, y_{∘}). Unfortunately, unlike for the case in one variable, there is no systematic method of integration in two variables. However, G_{𝔣𝔣′}^{(2)} is the only solution f of the equation

(11)  y_{•} \frac{∂f}{∂y_{•}} + y_{∘} \frac{∂f}{∂y_{∘}} + f = G_{ff}.

Hence, we have to guess an (η_{1}, η_{2})-rational expression R(η_{1}, η_{2}) for which we have good hints that it is equal to G_{𝔣𝔣′}^{(2)}. Then we just have to check that the (η_{1}, η_{2}) rational expression corresponding to y_{•} \frac{∂R}{∂y_{•}} +y_{∘} \frac{∂R}{∂y_{∘}} +R is equal to the (η_{1}, η_{2})-rational expression of G_{ff}. What are the hints from which we have to guess the solution? For example, we can use the η-rational expression R̃(η) = \frac{1}{(1−η)^{2}} of G_{𝔣𝔣′}^{(2)}(y); as

G_{𝔣𝔣′}^{(2)}(y, y) = G_{𝔣𝔣′}^{(2)}(y) (because of the conventions given in Section 1.6), η_{1}(y, y) = η(y) and η_{2}(y, y) = η(y), a candidate R(η_{1}, η_{2}) has to verify R(η, η) = R̃(η). In addition, G_{𝔣𝔣′}^{(2)}(y_{•}, y_{∘}) is symmetric in y_{•} and y_{∘}. As η_{1}(y_{•}, y_{∘}) = η_{2}(y_{∘}, y_{•}), a candidate has to be symmetric in η_{1} and η_{2} (because such a candidate is symmetric in y_{•} and y_{∘}). These two hints lead us to guess that R(η_{1}, η_{2}) = \frac{1}{(1−η_{1})(1−η_{2})}. It

turns out that this candidate verifies Equation (11), hence G_{𝔣𝔣′}^{(2)} = \frac{1}{(1−η_{1})(1−η_{2})}. We

also get an (η_{1}, η_{2})-rational expression for G_{𝔣𝔣}^{(2)}, using G_{𝔣𝔣}^{(2)} = G_{ff} − G_{𝔣𝔣′}^{(2)}. Similarly, we can also guess and check an (η_{1}, η_{2})-rational expression for G_{b𝔣′}^{(2)}. We find G_{b𝔣′}^{(2)} = \frac{η_{1}}{1−η_{2}} , and find also an (η_{1}, η_{2})-rational expression for G_{b𝔣}^{(2)} using the relation

G_{b𝔣}^{(2)} = G_{bf} − G_{b𝔣′}^{(2)}. We also find (η_{1}, η_{2})-rational expressions for G_{w𝔣′}^{(2)} and G_{w𝔣}^{(2)}, observing that G_{w𝔣′}^{(2)}(y_{•}, y_{∘}) = G_{b𝔣′}^{(2)}(y_{∘}, y_{•}) and G_{w𝔣}^{(2)}(y_{•}, y_{∘}) = G_{b𝔣}^{(2)}(y_{∘}, y_{•}). Hence, one obtains (η_{1}, η_{2})-rational expressions of G_{b𝔣′}^{(2)} and G_{b𝔣}^{(2)} by substituting (η_{1}, η_{2}) by (η_{2}, η_{1}) in the respective (η_{1}, η_{2})-rational expressions of G_{b𝔣′}^{(2)} and G_{b𝔣}^{(2)}. □

In order to find expressions of the 5 generating functions of 2-rooted irreducible quadrangulations, we will relate them to the 5 generating functions of 2-rooted simple quadrangulations (for which we have expressions) by a triangular system of 5 equations: for each family of 2-rooted simple quadrangulations, an equation is derived from a canonical decomposition of the objects of the family, with an irreducible quadrangulation at the “core” of the decomposition.

To derive these equations, we will also need the two following auxiliary families of 2-rooted simple quadrangulations, as intermediates of calculation:

• Let L be the family of 2-rooted simple quadrangulations of type face-face such that the 2-root is incident to an axial face and such that the root node of the induced rooted quadrangulation (the induced rooted quadrangulation is obtained by keeping only the mark of one of the two roots) is not a vertical axis-map. We write L(y) (L(y_{•}, y_{∘})) for the series counting L in one variable (two variables, respectively). In two variables, we denote by ^{t}L the series tL(y_{•}, y_{∘}) := L(y_{∘}, y_{•}).

\begin{matrix}G_{𝔣𝔣′}^{(2)} \\ G_{v𝔣′}^{(2)} \end{matrix}

Figure 6. The two decompositions involving respectively the objects of L and K.

• Let K be the family of 2-rooted simple quadrangulations of type face-vertex such that the 2-root is incident to the axial face and such that the root node of the induced rooted quadrangulation is not a vertical axis-map. We write K(y) for the series counting K in one variable. In two variables, we write K_{b}(y_{•}, y_{∘}) (K_{w}(y_{•}, y_{∘})) for the series counting objects of K whose axial vertex is black (white, respectively). We also denote by ^{t}K_{b} and ^{t}K_{w} the series ^{t}K_{b}(y_{•}, y_{∘}) := K_{b}(y_{∘}, y_{•}) and ^{t}K_{w}(y_{•}, y_{∘}) = K_{w}(y_{∘}, y_{•}).

4.3.3. Calculation of the generating functions of K and L. There is an easy decomposition of the objects of G_{𝔣𝔣′}^{(2)} (G_{v𝔣′}^{(2)}) in terms of the objects of L (K, respectively). These decompositions are performed by looking if the root node of the decomposition-tree is a horizontal axis-map or not, see Figure 6. These two decompositions give the following equations, ensuring that the series of L and K in one variable (two variables) are η-rational ((η_{1}, η_{2})-rational, respectively),

G_{𝔣𝔣′}^{(2)}(y) = L(y)(W(y)/y + 1), (12)

G_{𝔣𝔣′}^{(2)} (y_{•}, y_{∘}) = L\frac{W}{y_{•}} + L, (13)

G_{v𝔣′}^{(2)}(y) = K(y)(W(y)/y + 1) + W(y)/y, (14)

\{ \begin{matrix}G_{b𝔣′}^{(2)}(y_{•}, y_{∘}) = K_{b} \frac{W}{y_{•}} + K_{b}, \\ G_{w𝔣′}^{(2)}(y_{•}, y_{∘}) = K_{w} \frac{W}{y_{•}} + K_{w} + \frac{W}{y_{•}}. \end{matrix} (15)

4.3.4. Calculation of the generating function of H_{𝔣𝔣′}^{(2)}. An object of L has a simple decomposition: it is either the trivial quadrangulation (i.e., with only two faces), or the root node of its decomposition tree is a vertical axis-map or is an irreducible quadrangulation.

K_{b}  ^{t}K_{w}  G_{b𝔣′}^{(2)}  H_{b𝔣′}^{(2)}

Figure 7. Decomposition of an object of K_{b}.

This decomposition yields in one variable and two variables the following equations,

(16)  L(y) = 1 + L(y)W(y)/y + H_{𝔣𝔣′}^{(2)} (W(y)/y) G_{𝔣𝔣′}^{(2)}(y),
(17)  L(y_{•}, y_{∘}) = 1 +^{t} L\frac{W}{y_{∘}} + H_{𝔣𝔣′}^{(2)} (W/y_{∘}, W/y_{•}) G_{𝔣𝔣′}^{(2)}(y_{•}, y_{∘}).

These equations ensure that H_{𝔣𝔣′}^{(2)} (W(y)/y) and H_{𝔣𝔣′}^{(2)} (W/y_{∘}, W/y_{•}) are respectively η-rational and (η_{1}, η_{2})-rational.

4.3.5. Calculation of the generating function of H_{v𝔣′}^{(2)}. Similarly as above, we perform here a decomposition of an object of K by looking if the root-node of its decomposition-tree is a vertical axis-map or an irreducible quadrangulation. In two variables, we perform the same decomposition, but we distinguish whether the axial vertex is black or white, see Figure 7 for the decomposition of an object of K_{b}. This yields the equations

(18) K(y) = W(y)/y + K(y)W(y)/y + H_{𝔣𝔣′}^{(2)} (W(y)/y) G_{v𝔣′}^{(2)}(y) + H_{v𝔣′}^{(2)} (W(y)/y) ,

(19)

\begin{cases}K_{b}(y_{•}, y_{∘}) = \frac{W}{y_{∘}} +^{t} K_{w} \frac{W}{y_{∘}} + H_{𝔣𝔣′}^{(2)} (W/y_{∘}, W/y_{•}) G_{b𝔣′}^{(2)}(y_{•}, y_{∘}) + H_{b𝔣′}^{(2)} (W/y_{∘}, W/y_{•}) , \\ K_{w}(y_{•}, y_{∘}) = ^{t}K_{b} \frac{W}{y_{∘}} + H_{𝔣𝔣′}^{(2)} (W/y_{∘}, W/y_{•}) G_{w𝔣′}^{(2)}(y_{•}, y_{∘}) + H_{w𝔣′}^{(2)} (W/y_{∘}, W/y_{•}) . \end{cases}

We already know from Sections 4.3.3 and 4.3.4 that H_{𝔣𝔣′}^{(2)} (W(y)/y) and K(y) are ηrational and that H_{𝔣𝔣′}^{(2)} (W/y_{∘}, W/y_{•}), K_{b}(y_{•}, y_{∘}) and K_{w}(y_{•}, y_{∘}) are (η_{1}, η_{2})-rational. Hence Equation (18) yields an η-rational expression for H_{v𝔣′}^{(2)} (W(y)/y) and Equation (19) yields (η_{1}, η_{2})-rational expressions for H_{b𝔣′}^{(2)} (W/y_{∘}, W/y_{•}) and H_{w𝔣′}^{(2)} (W/y_{∘}, W/y_{•}).

4.3.6. The trunk of the decomposition-tree and the core-node. Before proceeding further, we need a better understanding of how the symmetry of a 2-rooted quadrangulation can be seen in its decomposition-tree.

Let Q be a 2-rooted quadrangulation whose decomposition-tree has at least one node fixed by the induced symmetry, and whose 2-root is not incident to an axial face. As the axis of the rotation-symmetry passes by all nodes fixed by the symmetry, these nodes form a chain x_{0}, …, x_{k} (k ⩾ 0) of 2-rooted quadrangulations, x_{i} and x_{i−1} being connected at a common axial face. The chain x_{0}, …, x_{k} is called the trunk of the decomposition tree. Observe that x_{i} has type face-face for 1 ⩽ i ⩽ k − 1, and that the two axial cells of Q are the axial cell of x_{0} and the axial cell of x_{k} not involved in an interconnection.

If the 2-root is not incident to an axial face of Q, there exists a node x_{Q} of the trunk such that two identical quadrangulations, carrying each a root of Q, are connected at each face of a 2-orbit of faces of x_{Q}. The node x_{Q} is called the core-node of Q.

Lemma 10. A 2-rooted simple quadrangulation Q with at least one axial face has at least one node of its decomposition-tree fixed by the induced symmetry.

Proof. Let Q be a 2-rooted quadrangulation whose decomposition tree has no node fixed by the symmetry induced by the 2-root. Hence the center of the decomposition tree of Q has to be an edge, and the symmetry has to exchange the two nodes incident to the edge. Geometrically, an edge of the decomposition tree corresponds to an interconnection-face f connecting two nodes of the tree at two faces of these nodes. The symmetry can not exchange two vertices of Q with different colors when Q is bicolored. Hence, the symmetry necessarily turns over f around two vertices s_{1} and s_{2} that are diagonally opposite in f and that are hence the two axial cells of Q. Thus Q is necessarily of type vertex-vertex. □

4.3.7. Calculation of the generating function of H_{𝔣𝔣}^{(2)}. The idea is to perform a decomposition of an object of G_{𝔣𝔣}^{(2)} according to several cases. This decomposition yields an equation linking the generating functions of the families G_{𝔣𝔣′}^{(2)}, G_{𝔣𝔣}^{(2)} and H_{𝔣𝔣}^{(2)}.

Let Q ∈ G_{𝔣𝔣}^{(2)}. The rotation-symmetry of order 2 of Q induces a symmetry of its decomposition-tree. According to Lemma 10, Q has at least one node of its decomposition-tree fixed by the symmetry. Hence the definitions of trunk and of core-node apply to Q. Then there are two possibilities for the core-node x_{Q} of Q: either it is an axis-map or it is an irreducible quadrangulation.

The core-node is an axis-map. We present here a construction of composed objects that correspond bijectively to objects of G_{𝔣𝔣}^{(2)} whose core-node is an axismap with 2d + 2 faces. Take the 2-rooted axis-map A of type face-face, with 4 faces, and such that its 2-root is incident to an axial face with each of the two roots pointing toward each of the two extremal vertices of A.

Then take two copies of an object of W′ whose vertical multiplicity at the root node of its decomposition tree is d. Root each of these two copies on each of the two non rooted faces of A, superimposing the edge carrying the primary root of each copy of W′ with the edge carrying each of the two roots of A. Then, on each axial face of A, root an object of L in a canonical way and “vertically”. Finally keep only the mark of the secondary roots of each of the two copies of the objects of W′.

This construction allows us to obtain exactly twice all object of G_{𝔣𝔣′}^{(2)} whose corenode is an axis-map (the inverse construction consists in guessing which axial face of A was carrying the 2-root, which gives two choices).

Let r_{𝔣𝔣}^{(2)}(y) be the generating function of objects of G_{𝔣𝔣′}^{(2)} whose core-node is an axis-map. From the construction explained above, we have

(20)  r_{𝔣𝔣}^{(2)}(y) = 2\frac{C(y)}{y}L(y)^{2}.

In two variables, we have

(21)  r_{𝔣𝔣}^{(2)}(y_{•}, y_{∘}) = \frac{C}{y_{∘}}^{t}L^{2} + \frac{C}{y_{•}} L^{2}.

The core-node is an irreducible quadrangulation. The method is still to construct objects of G_{𝔣𝔣′}^{(2)} whose core-node is an irreducible quadrangulation as composed objects. Take Q ∈ H_{𝔣𝔣′}^{(2)} and take two copies of an object of W′. Root canonically each of these copies on each of the two rooted faces of Q. Then, for each 2-orbit of non rooted faces of Q, take two copies of an object of W and root canonically each copy on each face of the orbit. Then root canonically an object of G_{𝔣𝔣′}^{(2)} on each axial face of Q. Finally, keep only the mark of the secondary roots of the two copies of the object of W′. Similarly as in Section 4.2.2, each object of G_{𝔣𝔣}^{(2)} whose core-node is an irreducible quadrangulation is obtained exactly 4 times by this construction. We obtain the following series for these objects, in one and in two variables:

\frac{C(y)}{W(y)}H_{𝔣𝔣}^{(2)}(W(y)/y)G_{𝔣𝔣′}^{(2)}(y)^{2},

\frac{C}{W}H_{𝔣𝔣}^{(2)} (W/y_{∘}, W/y_{•}) G_{𝔣𝔣′}^{(2)}.(y_{•}, y_{∘})^{2}

Obtaining the equations. Summing the two contributions for the decomposition of an object of G_{𝔣𝔣}^{(2)}, we obtain the following equations , in one and two variables,

(22)  G_{𝔣𝔣}^{(2)}(y) = 2\frac{C(y)}{y}L(y)^{2} + \frac{C(y)}{W(y)}H_{𝔣𝔣}^{(2)}(W(y)/y)G_{𝔣𝔣′}^{(2)}(y)^{2},

(23)  G_{𝔣𝔣}^{(2)}(y_{•}, y_{∘}) = \frac{C}{y_{∘}}^{t}L^{2} + \frac{C}{y_{•}} L^{2} + \frac{C}{W}H_{𝔣𝔣}^{(2)} (W/y_{∘}, W/y_{•}) G_{𝔣𝔣′}^{(2)}(y_{•}, y_{∘})^{2}.

We deduce from Equation (22) that H_{𝔣𝔣}^{(2)} (W(y)/y) is η-rational, because all other series appearing in Equation (22) are already known and η-rational. Similarly, using Equation (23), we can obtain an (η_{1}, η_{2})-rational expression for H_{𝔣𝔣}^{(2)} (W/y_{∘}, W/y_{•}).

4.3.8. Calculation of the generating function of H_{v𝔣}^{(2)}. In this section, we find an equation linking the families G_{v𝔣}^{(2)}, G_{v𝔣′}^{(2)}, G_{𝔣𝔣′}^{(2)}, H_{𝔣𝔣}^{(2)} and H_{v𝔣}^{(2)}. This equation is derived from a construction of objects of G_{v𝔣}^{(2)} as composed objects, distinguishing several cases.

Let Q ∈ G_{v𝔣}^{(2)}. According to Lemma 10, the decomposition-tree of Q has at least one node fixed by the symmetry induced by the 2-root, so that the definitions of trunk and core-node apply. Let x_{0}, …, x_{k} be the trunk of Q. As Q has type facevertex, one extremity of the trunk, say x_{0}, has type face-vertex. As in Section 4.3.7, we have two possibilities for the core-node x_{Q}: either x_{Q} is an axis-map or x_{Q} is an irreducible quadrangulation.

The core-node is an axis-map. Two subcases can arise:

• The axis-map x_{Q} is not the node x_{0} of the trunk, i.e., x_{Q} has type face-face.

• The axis-map x_{Q} is the node x_{0} of the trunk, i.e., x_{Q} has type face-vertex. We treat the first case with a construction similar to the one that has led to

Equation (20) in Section 4.3.7. The only difference is that, at the end, we do not root two objects of L on the axial faces of the axis-map A, but we root “vertically” an object of K on the rooted axial face and an object of L on the second axial face of A. With this construction we obtain bijectively all objects of H_{v𝔣}^{(2)} such that x_{Q} is an axis-map of type face-face. A similar construction can be performed by taking the bicoloration of vertices (and in particular the color of the axial vertex of the object of K) into account. This yields the following generating functions for this case, respectively in one and two variables (the generating functions in two variables are those of objects whose axial vertex is black, as the generating function for objects whose axial vertex is white can be deduced by exchanging the variables):

4\frac{C(y)}{y}K(y)L(y),

2^{t}L^{t}K_{w} \frac{C}{y_{∘}} + 2LK_{b} \frac{C}{y_{•}} .

The second subcase is treated by performing a quite analogous construction of composed objects. Take the 2-rooted axis-map A with 3 faces and one axial face, such that its two roots are incident to the axial face and point toward each of the two extremal vertices of A. Then root two copies of an object of W′ on each of the two non axial faces of A, superimposing the root edge of each of the two copies with each of the two root edges of A. This construction gives rise bijectively to all objects of H_{v𝔣}^{(2)} whose core-node is an axis-map with type face-vertex. We obtain the following generating functions respectively in one and in two variables for these objects (once again, in two variables, we only consider objects whose axial vertex is black):

4\frac{C(y)}{y}L(y)

2^{t}L\frac{C}{y_{∘}}

The core-node is an irreducible quadrangulation. Two subcases can also arise here depending on x_{Q} having type face-face or type face-vertex. We perform a similar composition construction as in Section 4.3.7 for objects of G_{𝔣𝔣}^{(2)} whose core-node is irreducible. The only difference is that, at the end, we do not root two objects of G_{𝔣𝔣′}^{(2)} on the axial faces of the object of H_{𝔣𝔣}^{(2)}, but we root an object of G_{𝔣𝔣′}^{(2)} on one axial face and an object of G_{v𝔣′}^{(2)} on the other axial face of the irreducible quadrangulation. We obtain for this case the following generating functions respectively in one and two variables:

2\frac{C(y)}{W(y)}H_{𝔣𝔣}^{(2)} (W(y)/y) G_{𝔣𝔣′}^{(2)}(y)G_{v𝔣′}^{(2)}(y)

2\frac{C}{W}H_{𝔣𝔣}^{(2)} (W/y_{∘}, W/y_{•}) G_{𝔣𝔣′}^{(2)}(y_{•}, y_{∘})G_{b𝔣′}^{(2)}(y_{•}, y_{∘})

Then we treat the case where x_{Q} is an irreducible quadrangulation and has type face-vertex. This case is handled similarly as the preceding case, with the difference that we take an irreducible quadrangulation Q with type face-vertex at the beginning of the construction. At the end, we root an object of G_{𝔣𝔣′}^{(2)} on the unique axial face of Q. We obtain for this case the generating functions

\frac{C(y)}{W(y)}H_{v𝔣}^{(2)} (W(y)/y) G_{𝔣𝔣′}^{(2)}(y),

\frac{C}{W}H_{b𝔣}^{(2)} (W/y_{∘}, W/y_{•}) G_{𝔣𝔣′}^{(2)}(y_{•}, y_{∘}).

Finally, we obtain the following equations corresponding to all cases for the decomposition of an object of G_{v𝔣}^{(2)} (of G_{b𝔣}^{(2)}, respectively):

(24) G_{v𝔣}^{(2)}(z) = 4\frac{C(y)}{y} (1 + K(y)) + \frac{C(y)}{W(y)}H_{v𝔣}^{(2)} (W(y)/y) G_{𝔣𝔣′}^{(2)}(y)

+ 2\frac{C(y)}{W(y)}H_{𝔣𝔣}^{(2)}(W(y)/y)G_{𝔣𝔣′}^{(2)}(y)G_{v𝔣′}^{(2)}(y),

(25) G_{b𝔣}^{(2)}(y_{•}, y_{∘}) = 2^{t}L^{t}K_{w} \frac{C}{y_{∘}} +2L K_{b} \frac{C}{y_{•}} +2^{t}L\frac{C}{y_{∘}} + \frac{C}{W}H_{b𝔣}^{(2)} (W/y_{∘}, W/y_{•}) G_{𝔣𝔣′}^{(2)}(y_{•}, y_{∘})

+ 2\frac{C}{W}H_{𝔣𝔣}^{(2)} (W/y_{∘}, W/y_{•}) G_{𝔣𝔣′}^{(2)}(y_{•}, y_{∘})G_{b𝔣′}^{(2)}(y_{•}, y_{∘}).

The only unknown generating function in Equation (24) is H_{v𝔣}^{(2)}(W(y)/y), as all other series appearing in this equation are already known to be η-rational. Hence we obtain from this equation an η-rational expression for H_{v𝔣}^{(2)}(W(y)/y). Similarly, we obtain from Equation (25) an (η_{1}, η_{2})-rational expression for H_{b𝔣}^{(2)} (W/y_{∘}, W/y_{•}). Finally, we also obtain easily an (η_{1}, η_{2})-rational expression for H_{w𝔣}^{(2)} (W/y_{∘}, W/y_{•}). Indeed, H_{w𝔣}^{(2)}(z_{•}, z_{∘}) = H_{b𝔣}^{(2)}(z_{∘}, z_{•}), and

{η_{1}(y_{•}, y_{∘}) = η_{2}(y_{∘}, y_{•}), η_{2}(y_{•}, y_{∘}) = η_{1}(y_{∘}, y_{•})},

so that an (η_{1}, η_{2})-rational expression of H_{w𝔣}^{(2)} (W/y_{∘}, W/y_{•}) is obtained by exchanging η_{1} and η_{2} in the (η_{1}, η_{2})-rational expression of H_{b𝔣}^{(2)} (W/y_{∘}, W/y_{•}).

4.3.9. Calculation of the generating function of G_{vv}^{(2)}. It now remains to find the generating function of the family H_{vv}^{(2)}. To do this, we construct objects of G_{vv}^{(2)} as composed objects by distinguishing several cases. We will thus obtain an equation linking H_{vv}^{(2)}(z) and the generating functions of the other families of 2-rooted simple and irreducible quadrangulations.

The different cases for the repercussion of the symmetry. Let Q be an object of G_{vv}^{(2)}. This time a lot of cases can arise for the repercussion of the symmetry induced by the 2-root of Q on the decomposition-tree of Q. Indeed, it can happen that no node of the decomposition tree is fixed by the symmetry. As we have seen in the proof of Proposition 5, this corresponds to the situation where the center of the decomposition tree is an edge whose two extremities are exchanged by the symmetry: on the quadrangulation, this edge corresponds to an interconnection-face that is turned over by the symmetry. This situation is treated in Case 2.

Otherwise we consider the trunk of Q (i.e., the chain of nodes x_{0}, …, x_{k} that are fixed by the symmetry) and the core-node x_{Q}. Two cases can arise for the trunk: k = 0 i.e., the trunk has only one node x_{0} of type vertex-vertex and then x_{Q} = x_{0}; or k ⩾ 1, which implies that x_{0} and x_{k} have type face-vertex and that x_{i} has type face-face ∀1 ⩽ i ⩽ k − 1. Thus, if k ⩾ 1, x_{Q} can have type face-vertex if it is an extremity of the trunk, otherwise it has type face-face. In addition, we have each time to distinguish whether x_{Q} is an axis-map or an irreducible quadrangulation. Moreover we have to take care of the fact that, if x_{Q} is an axis-map, there are two distinct ways for x_{Q} to have type vertex-vertex (treated respectively in cases 3 and 4).

We distinguish the following cases:

(1) The quadrangulation Q has only two faces and its 2-root induces a symmetry of Q with two axial vertices. This case can be considered as degenerated by saying that the decomposition-tree of Q consists only of a degenerated axis-map with 2 faces.

(2) The center of the decomposition-tree of Q is an edge, and this edge is turned over by the symmetry. This edge corresponds to a so-called interconnectionface f connecting two nodes of the tree. Hence the two axial vertices of Q are two diagonally opposed vertices of f. Moreover it is easy to see that the two nodes connected at f are irreducible quadrangulations. Indeed, assume that these nodes n_{1} and n_{2} are axis-maps. As we have seen in Section 2.2, two incident axis-maps are stretched in perpendicular directions: if n_{1} is “horizontal” then n_{2} is “vertical”. The symmetry turns over the tree around the face f and sends n_{1} to the place where n_{2} was. But n_{1} clearly remains “horizontal” after this turn-over, and takes the place of n_{2}, which is vertical. Hence this turn over operation can not let Q invariant, so that we have a contradiction. Hence the two connected nodes are irreducible quadrangulations.

(3) The core-node x_{Q} is an axis-map and the rotation-axis of the symmetry of Q induced by the 2-root intersects x_{Q} at two diagonally opposed vertices in the equatorial plane of x_{Q}.

(4) The core-node x_{Q} is an axis-map and the rotation-axis of the symmetry of Q induced by the 2-root intersects x_{Q} at its two extremal vertices.

(5) The core-node x_{Q} is an axis-map and the rotation-axis of the symmetry of Q induced by the 2-root intersects x_{Q} at a vertex v of the equatorial plane of x_{Q} and at the center of the face diametrically opposed to v in the equatorial plane of x_{Q}. This corresponds to the case where x_{Q} is an axis-map of type face-vertex.

(6) The core-node x_{Q} is an axis-map and the rotation-axis of the symmetry of Q induced by the 2-root intersects x_{Q} at the centers of two diametrically opposed faces of x_{Q}. This corresponds to the case where x_{Q} is an axis-map of type face-face.

(7) The core-node x_{Q} is an irreducible quadrangulation that has type face-face for the symmetry induced by the 2-root.

(8) The core-node x_{Q} is an irreducible quadrangulation that has type facevertex for the symmetry induced by the 2-root.

(9) The core-node x_{Q} is an irreducible quadrangulation that has type vertexvertex for the symmetry induced by the 2-root.

The core-node is a (possibly degenerated) axis-map. Cases 1, 2 and 3 can be treated together by constructing the following composed objects: let A be the 2-rooted simple quadrangulation with two faces and type vertex-vertex and such that the two roots point toward the same vertex of A. We call this vertex the root-vertex of A. We can consider A as a sort of degenerated axis-map with only two faces. Hence we can perform the same construction as in Section 4.2.1. Here this construction comes down to taking two copies of an object Q′ of Ĵ′ and rooting each copy on each of the two faces of A so that the primary roots of the two copies point toward the root vertex of A. By definition of J, Q′ is not stretched horizontally at its root face (the face incident to the primary root). If Q′ is not vertically stretched, then Q′ is either a trivial quadrangulation with two faces, corresponding to Case 1, or Q′ is an irreducible quadrangulation, corresponding to Case 2. The situation where Q′ is vertically stretched at its root face corresponds to Case 3.

Finally, the sum of the contributions of Case 1, Case 2 and Case 3 is

2\frac{B(y)}{y}.

Case 4 can also be treated similarly as in Section 4.2.1. However we have to take care of the fact that the axis-map at the core of the decomposition-tree is a real axis-map, so that it has at least 3 faces. Hence it has 2 · l faces with l ⩾ 2. Thus Case 4 gives the generating function

2\frac{B(y)}{y} \frac{J(y)/y}{1 − J(y)/y} .

Finally, the sum of the contributions of Case 1, Case 2, Case 3 and Case 4 is

2\frac{B(y)}{y} \frac{1}{1 − J(y)/y} .

Case 5, where the core-node x_{Q} is an axis-map of type face-vertex, can be treated similarly as in Section 4.3.8. For this construction, we took a 2-rooted axis-map A with 3 faces and with type face-vertex at the beginning of the construction. The only difference here is that, at the end of the construction, we do not root “vertically” an object of L on the axial face of A but an object of K. We obtain for Case 5 the generating function

4\frac{C(y)}{y}K(y).

Case 6 can also be treated similarly as in the construction of Section 4.3.7 where we took a 2-rooted axis-map A with 4 faces and 2 axial faces. The only difference here is that, at the end of the construction, we root two objects of K “vertically” on the two axial faces of A. Hence Case 6 gives the generating function

2\frac{C(y)}{y}K(y)^{2}.

Finally we can group the 6 first cases in a generating function r_{vv}^{(2)}(y) of objects of G_{vv}^{(2)} whose core-node is a (possibly degenerated) axis-map:

r_{vv}^{(2)}(y) = 2\frac{B(y)}{y} \frac{1}{1 − J(y)/y} + 4\frac{C(y)}{y}K(y) + 2\frac{C(y)}{y}K(y)^{2}

The core-node is an irreducible quadrangulation. Cases 7, 8 and 9 correspond to objects of G_{vv}^{(2)} whose core-node is an irreducible quadrangulation. These cases can be treated by constructing composed objects from a 2-rooted irreducible quadrangulation that has type face-face for Case 7, type face-vertex for Case 8 and type vertex-vertex for Case 9.

Hence, the generating function for Case 7 is

\frac{C(y)}{W(y)}H_{𝔣𝔣}^{(2)} (W(y)/y) G_{v𝔣′}^{(2)}(y)^{2},

the generating function for Case 8 is

\frac{C(y)}{W(y)}H_{v𝔣}^{(2)} (W(y)/y) G_{v𝔣′}^{(2)}(y),

and the generating function for Case 9 is

\frac{C(y)}{W(y)}H_{vv}^{(2)} (W(y)/y) .

Obtaining the equation. Finally we obtain the following equation corresponding to the different ways to construct objects of G_{vv}^{(2)} as composed objects:

(26) G_{vv}^{(2)}(y) = r_{vv}^{(2)}(y) + \frac{C(y)}{W(y)}H_{𝔣𝔣}^{(2)} (W(y)/y) G_{v𝔣′}^{(2)}(y)^{2}

+ \frac{C(y)}{W(y)}H_{v𝔣}^{(2)} (W(y)/y) G_{v𝔣′}^{(2)}(y) + \frac{C(y)}{W(y)}H_{vv}^{(2)} (W(y)/y) .

Except for H_{vv}^{(2)} (W(y)/y), all generating functions of this equation are known and are η-rational. Hence we obtain from this equation an η-rational expression for H_{vv}^{(2)} (W(y)/y).

Similarly, for two variables, the same decomposition yields the following equations depending on the colors of the two axial vertices,

G_{ww}^{(2)} (W/y_{∘}, W/y_{•}) = r_{ww}(y_{•}, y_{∘}) + \frac{y_{•}}{y_{∘}} \frac{C}{W}H_{𝔣𝔣}^{(2)} (W/y_{∘}, W/y_{•}) G_{w𝔣′}^{(2)}(y_{•}, y_{∘})^{2}

+ \frac{y_{•}}{y_{∘}} \frac{C}{W}H_{w𝔣}^{(2)} (W/y_{∘}, W/y_{•}) G_{w𝔣′}^{(2)}(y_{•}, y_{∘}) + \frac{C}{W}H_{ww}^{(2)} (W/y_{∘}, W/y_{•}) ,

where

r_{ww}(y_{•}, y_{∘}) = \frac{B}{y_{∘}} \frac{1}{1 − J/y_{∘}} + 2\frac{C}{y_{∘}} K_{w} + \frac{C}{y_{∘}} K_{w}^{2} + \frac{y_{•}C}{y_{∘}^{2}}^{t}K_{b}^{2},

and

G_{bw}^{(2)} (W/y_{∘}, W/y_{•}) = r_{bw}(y_{•}, y_{∘}) + 2\frac{C}{W}H_{𝔣𝔣}^{(2)} (W/y_{∘}, W/y_{•}) G_{b𝔣′}^{(2)}(y_{•}, y_{∘})G_{w𝔣′}^{(2)}(y_{•}, y_{∘})

+ \frac{C}{W}H_{b𝔣}^{(2)} (W/y_{∘}, W/y_{•}) G_{w𝔣′}^{(2)}(y_{•}, y_{∘})

+ \frac{C}{W}H_{w𝔣}^{(2)} (W/y_{∘}, W/y_{•}) G_{b𝔣′}^{(2)}(y_{•}, y_{∘}) + \frac{C}{W}H_{bw}^{(2)} (W/y_{∘}, W/y_{•}) ,

where

r_{bw}(y_{•}, y_{∘}) = 2\frac{C}{y_{•}} K_{b} + 2\frac{C}{y_{∘}}^{t}K_{b} + 2\frac{C}{y_{•}} K_{b}K_{w} + 2\frac{C}{y_{∘}}^{t}K_{b}^{t}K_{w}.

We conclude from these equations that the series H_{ww}^{(2)} (W/y_{∘}, W/y_{•}) and H_{bw}^{(2)} (W/y_{∘}, W/y_{•}) are (η_{1}, η_{2})-rational. Moreover, the equality

H_{bb}^{(2)} (W/y_{∘}, W/y_{•}) = H_{ww}^{(2)} (W/y_{•}, W/y_{∘}) ,

ensures that H_{bb}^{(2)} (W/y_{∘}, W/y_{•}) has also an (η_{1}, η_{2})-rational expression, obtained by exchanging η_{1} and η_{2} in the (η_{1}, η_{2})-rational expression of H_{ww}^{(2)} (W/y_{∘}, W/y_{•}).

4.3.10. Conclusion. We have proved that all series of 2-rooted quadrangulations in one variable, composed with W(y)/y, are η-rational and all series of 2-rooted quadrangulations in two variables, composed with (W/y_{∘}, W/y_{•}), are (η_{1}, η_{2})-rational. This allows us to state the following lemma, which completes Lemma 8 (see the proof of Lemma 8 for the transition between (η_{1}, η_{2})-rational and (γ_{1}, γ_{2})-rational):

Lemma 11. All series of 2-rooted irreducible quadrangulations are γ-rational in one variable and are (γ_{1}, γ_{2})-rational in two variables.

4.4. Complexity result. Burnside’s formula for 3-connected maps can be formulated as follows: let h_{n} be the number of unrooted 3-connected maps with n edges and h_{ij} be the number of unrooted 3-connected maps with i + 1 vertices and j + 1 edges. Then

∑_{n} 2nh_{n}z^{n} = H(z) + zH_{v𝔣′}(z^{2}) + zH_{v𝔣}(z^{2}) + z^{2}H_{𝔣𝔣′}(z^{2}) + z^{2}H_{𝔣𝔣}(z^{2})

+ H_{vv}^{(2)}(z^{2}) + ∑_{k⩾3}ϕ(k)H_{vv}^{⩾3}(z^{k}),

∑_{i,j} 2(i + j)h_{ij}z_{•}^{i}z_{∘}^{j} = H(z_{•}, z_{∘}) + z_{∘}H_{b𝔣′}(z_{•}^{2}, z_{∘}^{2}) + z_{∘}H_{b𝔣}(z_{•}^{2}, z_{∘}^{2}) + z_{•}H_{w𝔣′}(z_{•}^{2}, z_{∘}^{2})

+ z_{•}H_{w𝔣}(z_{•}^{2}, z_{∘}^{2}) + z_{•}z_{∘}H_{𝔣𝔣′}(z_{•}^{2}, z_{∘}^{2}) + z_{•}z_{∘}H_{𝔣𝔣}(z_{•}^{2}, z_{∘}^{2})

+ \frac{z_{•}}{z_{∘}} H_{bb}^{(2)}(z_{•}^{2}, z_{∘}^{2}) + \frac{z_{∘}}{z_{•}} H_{ww}^{(2)}(z_{•}^{2}, z_{∘}^{2}) + H_{bw}^{(2)}(z_{•}^{2}, z_{∘}^{2})

+ ∑_{k⩾3}ϕ(k) (\frac{z_{•}}{z_{∘}} H_{bb}^{⩾3}(z_{•}^{k}, z_{∘}^{k}) + \frac{z_{∘}}{z_{•}} H_{ww}^{⩾3}(z_{•}^{k}, z_{∘}^{k}) + H_{bw}^{⩾3}(z_{•}^{k}, z_{∘}^{k})) .

Lemma 8 and Lemma 11 imply the following result on the complexity of the enumeration of unrooted 3-connected maps:

Lemma 12. The N initial coefficients counting unrooted 3-connected maps according to their number of edges can be computed with O(N log(N)) operations.

The table of initial coefficients with indices (i, j) and i+j ⩽ N counting unrooted 3-connected maps according to their number of vertices and faces can be computed with O(N^{2}) operations.

Proof. The proof is similar to that of Lemma 7, i.e., we use the property of Dfiniteness of the series of rooted and k-rooted 3-connected maps, following from the fact that these series are algebraic. Indeed, in one variable they are in the algebraic extension of γ, and in two variables they are in the algebraic extension of (γ_{1}, γ_{2}). □

Finally, Lemmas 7 and 12 yield Theorem 2 (complexity result). The angular bijection ensures that the generating functions of k-rooted maps, k-rooted 2connected maps and k-rooted 3-connected maps are respectively equal to the series of k-rooted quadrangulations, k-rooted simple quadrangulations and k-rooted irreducible quadrangulations. Hence, Lemmas 3, 6, 8 and 11 yield Theorem 1 (algebraic structure).

5. Conclusion

We have proposed a new general and efficient method to enumerate unrooted maps. In particular, we have improved significantly on the complexity of counting oriented convex polyhedra (unrooted 3-connected maps).

Our method is flexible and can be adapted to enumerate other families of unrooted maps. For example, a similar scheme can be used to count unrooted loopless and subsequently unrooted maps without loops and multiple edges. This time, a first tree decomposition, “by loops”, allows us to enumerate k-rooted loopless maps from k-rooted maps. Then the tree decomposition by multiple edges (this time on k-rooted maps instead of k-rooted quadrangulations as in this article) allows us to enumerate k-rooted maps without loop and multiple edge from k-rooted loopless maps. A similar calculation chain yields the enumeration of unrooted triangulations on the sphere: start with the enumeration of triangulated maps with loops and multiple edges allowed, then deduce the enumeration of unrooted loopless triangulated maps, and finally derive the enumeration of unrooted triangulations.

Another interesting problem is the enumeration of unrooted 3-connected maps on the sphere up to all homeomorphisms (including orientation-reversing). Indeed according to Whitney’s Theorem, 3-connected planar graphs have a unique topological embedding on the sphere, so that these unrooted 3-connected maps exactly correspond to unlabeled 3-connected planar graphs. In this case, another adaptation of Burnside’s formula by Liskovets [7] is also available, giving an expression for the number of unrooted maps that involves the number of orientation-preserving k-rooted 3-connected maps and also the number of orientation-reversing ones (for example 2-rooted 3-connected maps where the 2-root induces a reflection). The tree-decomposition by separating 4-cycles can be used to obtain an equation linking 2-rooted 2-connected maps and 2-rooted 3-connected maps of type reflection. But it seems difficult to obtain a simple expression for the series of 2-rooted 2connected maps of type reflection. Nevertheless, the method of tree decomposition is also here promising.

References

[1] W.G. Brown, W.T. Tutte. On the enumeration of rooted non separable planar maps, Canad. J. Math. 16:572–577, 1964

[2] I. Gessel. A combinatorial proof of the multivariable Lagrange inversion formula. Journal of Combinatorial Theory Series A 45:178–195, 1987

[3] S. Kunz–Jacques, G. Schaeffer. The asymptotic number of prime alternating links. Proceedings of the International Conference FPSAC’01, Phoenix

[4] V.A. Liskovets. A census of non-isomorphic planar maps, Coll. Math. Soc. J. Bolyai, Proc. Conf. Algebr. Meth. in Graph Th. 25:479–494, 1981

[5] V.A. Liskovets, T.R.S. Walsh. The enumeration of non-isomorphic 2-connected planar maps. Canad. J. Math. 3:417–435, 1983

[6] V.A. Liskovets, T.R.S. Walsh. Enumeration of Eulerian and unicursal planar maps. Discrete Math. 282:209–221, 2004.

[7] V.A. Liskovets. A reductive technique for enumerating non-isomorphic planar maps. Discrete Math. 156:197–217, 1996

[8] V.A. Liskovets, T.R.S. Walsh. Counting unrooted loopless planar maps. Eur. J. Comb. 26:651–663, 2005

[9] R.C. Mullin, P.J. Schellenberg. The enumeration of c-nets via quadrangulations. J. Combinatorial Theory 4:259–276, 1968 [10] B. Salvy, P. Zimmermann. Gfun: A Maple package for the manipulation of generating and

holonomic functions in one variable. ACM Transactions on Mathematical Software 20:163– 177, June 1994.

[11] G. Schaeffer. Bijective census and random generation of Eulerian planar maps with prescribed vertex degrees. Electron. J. Combin. 4(1):Research Paper 20. 1997

[12] R. P. Stanley. Differentiably finite power series. Europ. J. Combinatorics, 1:175–188, 1980 [13] W.T. Tutte. A census of planar maps, Canad. J. Math. 15:249-271, 1963

[14] T.R.S. Walsh. Counting non-isomorphic three-connected planar maps. J. Combinatorial Theory. Series B 32:33–44, 1982

[15] T.R.S. Walsh. Efficient enumeration of sensed maps. Discrete Math. 293: 263–289

Appendix A. Enumeration with respect to the number of edges

A.1. Unrooted maps. Let β := β(x) be the algebraic function defined by the equation

β(x) = x + 3β(x)^{2}.

Let f_{n} be the number of unrooted maps with n edges. Then Burnside’s formula for unconstrained maps is

∑_{n} 2nf_{n}x^{n} = F(x) + xF_{vf}(x^{2}) + x^{2}F_{ff}(x^{2}) + ∑_{k⩾2}ϕ(k)F_{vv}(x^{k}),

where

F(x) = \frac{β (2 − 9 β)}{(1 − 3 β)^{2}}
F_{vf}(x) = \frac{2}{(1 − 6 β) (1 − 3 β)}
F_{ff}(x) = \frac{1}{(1 − 3 β)^{2} (1 − 6 β)}
F_{vv}(x) = \frac{6β}{1 − 6 β} .

The first coefficients of the series of unrooted maps are 2 x + 4 x^{2} + 14 x^{3} + 57 x^{4} + 312 x^{5} + 2071 x^{6} + 15030 x^{7} + 117735 x^{8} + 967850 x^{9} + 8268816 x^{10} + …

A.2. Unrooted 2-connected maps. Let η := η(y) be the algebraic function defined by the equation

η(y) = y/(1 − η(y))^{2}.

Let g_{n} be the number of unrooted 2-connected maps with n edges. Then Burnside’s formula for 2-connected maps is

∑_{n} 2ng_{n}y^{n} = G(y) + yG_{vf}(y^{2}) + y^{2}G_{ff}(y^{2}) + ∑_{k⩾2}ϕ(k)G_{vv}(y^{k}),

where

G(y) = η (2 − 3 η)
G_{vf}(y) = \frac{2}{1 − 3 η}
G_{ff}(y) = \frac{1}{(1 − 3 η) (1 − η)}
G_{vv}(y) = \frac{2η}{1 − 3 η} .

The first coefficients of the series of unrooted 2-connected maps are 2 y +y^{2} +2 y^{3} + 3 y^{4} + 6 y^{5} + 16 y^{6} + 42 y^{7} + 151 y^{8} + 596 y^{9} + 2605 y^{10} + … Remark. For the sake of uniformity, we present all results in terms of generating functions. However, in the case of 1-connected and 2-connected maps, the coefficients of the generating functions of k-rooted maps admit explicit sum-free formulas. This has been proved by Liskovets for 1-connected maps [4], and by Liskovets and Walsh for 2-connected maps [5]. Whereas these expressions are easy to establish for 1-connected maps, they require more work for 2-connected maps.

Let us mention that these exact formulas can also be deduced from our generatingfunction expressions using Lagrange inversion formula. We take here the example of the series G_{vf}(y). According to the angular mapping, the nth coefficient of G_{vf}(y) is the number of 2-rooted 2-connected maps with 2n + 1 edges and with one axial edge. First, by differentiating the equation η(1 − η)^{2} = y, we obtain

η′(y) = \frac{1}{(1 − 3η(y))(1 − η(y))},

so that

G_{vf}(y) = 2η′(1 − η) = −((1 − η)^{2})′.

Hence, [y^{n−1}]G_{vf}(y) = −n[y^{n}](1 − η)^{2}. Lagrange inversion formula ensures that

n[y^{n}](1 − η)^{2} = [η^{n−1}](−2(1 − η)(1 − η)^{−2n}) = −2[η^{n−1}](1 − η)^{−2n+1}.

Hence

[y^{n}]G_{vf}(y) = 2\binom{3n}{n},

recovering the formula given in [5]. The same work can be done in two variables, using bivariate Lagrange inversion formula (see [2] for a survey on Lagrange inversion formula).

A.3. Unrooted 3-connected maps. Let γ := γ(z) be the algebraic function defined by the equation

γ(z) = z (1 + γ(z))^{2} .

Let h_{n} be the number of unrooted 3-connected maps with n edges. Then Burnside’s formula for 3-connected maps is

∑_{n} 2nh_{n}z^{n} = H(z) + zH_{v𝔣′}(z^{2}) + zH_{v𝔣}(z^{2}) + z^{2}H_{𝔣𝔣′}(z^{2}) + z^{2}H_{𝔣𝔣}(z^{2})

+ H_{vv}^{(2)}(z^{2}) + ∑_{k⩾3}ϕ(k)H_{vv}^{⩾3}(z^{k}),

where

H(z) = −\frac{γ^{6} (2 γ^{3} − 1 − 4 γ − 3 γ^{2} + γ^{4})}{(1 + γ)^{4} (1 + 3 γ + γ^{2})^{2} (2 γ + 1)^{3}}
H_{v𝔣}(z) = \frac{4 (1 + γ) (8 γ^{2} + 13 γ + 4) γ^{4}}{(1 − γ) (1 + 3 γ + γ^{2})^{2} (2 γ + 1)^{3}}
H_{v𝔣′}(z) = \frac{2γ^{4}}{(1 + 3 γ + γ^{2}) (2 γ + 1)^{2}}

H_{𝔣𝔣}(z) = \frac{2γ^{2} (1 + 5 γ + 10 γ^{2} + 9 γ^{3}) (1 + γ)^{2}}{(1 − γ) (1 + 3 γ + γ^{2})^{2} (2 γ + 1)^{3}}
H_{𝔣𝔣′}(z) = \frac{(1 + 3 γ + 3 γ^{2}) γ^{2}}{(1 + 3 γ + γ^{2}) (2 γ + 1)^{2}}
H_{vv}^{(2)}(z) = \frac{2 (8 γ^{5} + 28 γ^{4} + 31 γ^{3} + 21 γ^{2} + 10 γ + 2) γ^{4}}{(1 + 3 γ + γ^{2})^{2} (1 + γ)^{2} (1 − γ) (2 γ + 1)^{3}}
H_{vv}^{⩾3}(z) = \frac{2γ^{2} (3 γ + 2)}{(1 − γ) (1 + 3 γ + γ^{2}) (2 γ + 1)}

The first coefficients of the series of unrooted 3-connected maps are z^{6} +z^{8} +2 z^{9} + 3 z^{10} + 4 z^{11} + 15 z^{12} + 32 z^{13} + 89 z^{14} + 266 z^{15} + 797 z^{16} + 2496 z^{17} + …

Appendix B. Enumeration with respect to the number of vertices and the number of faces

B.1. Unrooted maps. Let β_{1} := β_{1}(x_{•}, x_{∘}) and β_{2} := β_{2}(x_{•}, x_{∘}) be the algebraic functions defined by the equation-system

\{ \begin{matrix}β_{1} = x_{•} + β_{1}^{2} + 2β_{1}β_{2} \\ β_{2} = x_{∘} + β_{2}^{2} + 2β_{1}β_{2} \end{matrix} .

Let f_{ij} be the number of unrooted maps with i + 1 vertices and j + 1 faces. Then Burnside’s formula for unconstrained maps is

∑_{i,j} 2(i + j)f_{ij}x_{•}^{i}x_{∘}^{j} = F(x_{•}, x_{∘}) + x_{∘}F_{bf}(x_{•}^{2}, x_{∘}^{2}) + x_{•}F_{wf}(x_{•}^{2}, x_{∘}^{2}) + x_{•}x_{∘}F_{ff}(x_{•}^{2}, x_{∘}^{2})

+ ∑_{k⩾2}ϕ(k) (\frac{x_{•}}{x_{∘}} F_{bb}(x_{•}^{k}, x_{∘}^{k}) + \frac{x_{∘}}{x_{•}} F_{ww}(x_{•}^{k}, x_{∘}^{k}) + F_{bw}(x_{•}^{k}, x_{∘}^{k})) ,

where

F(x_{•}, x_{∘}) = −\frac{−β_{2} − β_{1} + 5 β_{1} β_{2} + 2 β_{1}^{2} + 2 β_{2}^{2}}{(−1 + β_{1} + 2 β_{2}) (−1 + β_{2} + 2 β_{1})}
F_{bf}(x_{•}, x_{∘}) = \frac{−1 + 2 β_{2}}{(4 β_{1} β_{2} + 1 − 4 β_{2} − 4 β_{1} + 4 β_{2}^{2} + 4 β_{1}^{2}) (−1 + β_{2} + 2 β_{1})}
F_{wf}(x_{•}, x_{∘}) = \frac{−1 + 2 β_{1}}{(4 β_{1} β_{2} + 1 − 4 β_{2} − 4 β_{1} + 4 β_{2}^{2} + 4 β_{1}^{2}) (−1 + β_{1} + 2 β_{2})}
F_{ff}(x_{•}, x_{∘}) = \frac{1 − β_{1} − β_{2}}{(1−β_{1}−2 β_{2}) (1−β_{2}−2 β_{1}) (4 β_{1} β_{2}+1−4 β_{2}−4 β_{1}+4 β_{2}^{2}+4 β_{1}^{2})}
F_{bb}(x_{•}, x_{∘}) = \frac{β_{2}}{4 β_{1} β_{2} + 1 − 4 β_{2} − 4 β_{1} + 4 β_{2}^{2} + 4 β_{1}^{2}}
F_{ww}(x_{•}, x_{∘}) = \frac{β_{1}}{4 β_{1} β_{2} + 1 − 4 β_{2} − 4 β_{1} + 4 β_{2}^{2} + 4 β_{1}^{2}}
F_{bw}(x_{•}, x_{∘}) = −2 \frac{2 β_{1}^{2} − β_{1} + 2 β_{1} β_{2} − β_{2} + 2 β_{2}^{2}}{4 β_{1} β_{2} + 1 − 4 β_{2} − 4 β_{1} + 4 β_{2}^{2} + 4 β_{1}^{2}} .

The first coefficients of the series of unrooted maps are (x_{∘} + x_{•}) + (x_{∘}^{2} + 2 x_{•}x_{∘} + x_{•}^{2}) + (2 x_{•}^{3} + 5 x_{•}^{2}x_{∘} + 5 x_{•}x_{∘}^{2} + 2 x_{∘}^{3}) + (14 x_{•}^{3}x_{∘} + 14 x_{•}x_{∘}^{3} + 23 x_{•}^{2}x_{∘}^{2} + 3 x_{∘}^{4} + 3 x_{•}^{4}) + (108 x_{•}^{2}x_{∘}^{3} + 6 x_{•}^{5} + 42 x_{•}^{4}x_{∘} + 6 x_{∘}^{5} + 108 x_{•}^{3}x_{∘}^{2} + 42 x_{•}x_{∘}^{4}) + …

B.2. Unrooted 2-connected maps. Let η_{1} := η_{1}(y_{•}, y_{∘}) and η_{2} := η_{2}(y_{•}, y_{∘}) be the algebraic functions defined by the equation-system

\{ \begin{matrix}η_{1} = y_{•}/(1 − η_{2})^{2} \\ η_{2} = y_{∘}/(1 − η_{1})^{2} \end{matrix} .

Let g_{ij} be the number of unrooted 2-connected maps with i + 1 vertices and j + 1 faces. Then Burnside’s formula for unrooted 2-connected maps is

∑_{i,j} 2(i + j)g_{ij}y_{•}^{i}y_{∘}^{j} = G(y_{•}, y_{∘}) + y_{∘}G_{bf}(y_{•}^{2}, y_{∘}^{2}) + y_{•}G_{wf}(y_{•}^{2}, y_{∘}^{2}) + y_{•}y_{∘}G_{ff}(y_{•}^{2}, y_{∘}^{2})

+ ∑_{k⩾2}ϕ(k) (\frac{y_{•}}{y_{∘}} G_{bb}(y_{•}^{k}, y_{∘}^{k}) + \frac{y_{∘}}{y_{•}} G_{ww}(y_{•}^{k}, y_{∘}^{k}) + G_{bw}(y_{•}^{k}, y_{∘}^{k})) ,

where

G(y_{•}, y_{∘}) = −3 η_{1} η_{2} + η_{1} + η_{2},
G_{bf}(y_{•}, y_{∘}) = −\begin{matrix}(−1 + η_{2}) & (η_{1} + 1) \\ (−1 + η_{1}) & (3 η_{1} η_{2} + η_{2} − 1 + η_{1}) \end{matrix},
G_{wf}(y_{•}, y_{∘}) = −\begin{matrix}(η_{2} + 1) & (−1 + η_{1}) \\ (−1 + η_{2}) & (3 η_{1} η_{2} + η_{2} − 1 + η_{1}) \end{matrix},
G_{ff}(y_{•}, y_{∘}) = \frac{η_{1} η_{2} − 1}{(−1 + η_{2}) (−1 + η_{1}) (3 η_{1} η_{2} + η_{2} − 1 + η_{1})},
G_{bb}(y_{•}, y_{∘}) = \frac{η_{2} (−1 + η_{1})}{3 η_{1} η_{2} + η_{2} − 1 + η_{1}} ,
G_{ww}(y_{•}, y_{∘}) = \frac{η_{1} (−1 + η_{2})}{3 η_{1} η_{2} + η_{2} − 1 + η_{1}} ,
G_{bw}(y_{•}, y_{∘}) = −4 \frac{η_{1} η_{2}}{3 η_{1} η_{2} + η_{2} − 1 + η_{1}} .

The first coefficients of the series of unrooted 2-connected maps are (y_{•} + y_{∘}) + y_{•}y_{∘} + (y_{•}^{2}y_{∘} + y_{•}y_{∘}^{2}) + (y_{•}^{2}y_{∘}^{2} + y_{•}y_{∘}^{3} + y_{•}^{3}y_{∘}) + (2 y_{•}^{3}y_{∘}^{2} + 2 y_{•}^{2}y_{∘}^{3} + y_{•}^{4}y_{∘} + y_{•}y_{∘}^{4}) + (3 y_{•}^{2}y_{∘}^{4} + 3 y_{•}^{4}y_{∘}^{2} + y_{•}y_{∘}^{5} + y_{•}^{5}y_{∘} + 8 y_{•}^{3}y_{∘}^{3}) + …

B.3. Unrooted 3-connected maps. Let γ_{1} := γ_{1}(x_{•}, x_{∘}) and γ_{2} := γ_{2}(x_{•}, x_{∘}) be the algebraic functions defined by the equation-system

\{ \begin{matrix}γ_{1} = z_{•}(1 + γ_{2})^{2} \\ γ_{2} = z_{∘}(1 + γ_{1})^{2} \end{matrix} .

Let h_{ij} be the number of unrooted 3-connected maps with i + 1 vertices and j + 1 faces. Then Burnside’s formula for unrooted 3-connected maps is

∑_{i,j} 2(i + j)h_{ij}z_{•}^{i}z_{∘}^{j} = H(z_{•}, z_{∘}) + z_{∘}H_{b𝔣′}(z_{•}^{2}, z_{∘}^{2}) + z_{∘}H_{b𝔣}(z_{•}^{2}, z_{∘}^{2}) + z_{•}H_{w𝔣′}(z_{•}^{2}, z_{∘}^{2})

+ z_{•}H_{w𝔣}(z_{•}^{2}, z_{∘}^{2}) + z_{•}z_{∘}H_{𝔣𝔣′}(z_{•}^{2}, z_{∘}^{2}) + z_{•}z_{∘}H_{𝔣𝔣}(z_{•}^{2}, z_{∘}^{2})

+ \frac{z_{•}}{z_{∘}} H_{bb}^{(2)}(z_{•}^{2}, z_{∘}^{2}) + \frac{z_{∘}}{z_{•}} H_{ww}^{(2)}(z_{•}^{2}, z_{∘}^{2}) + H_{bw}^{(2)}(z_{•}^{2}, z_{∘}^{2})

+ ∑_{k⩾3}ϕ(k) (\frac{z_{•}}{z_{∘}} H_{bb}^{⩾3}(z_{•}^{k}, z_{∘}^{k}) + \frac{z_{∘}}{z_{•}} H_{ww}^{⩾3}(z_{•}^{k}, z_{∘}^{k}) + H_{bw}^{⩾3}(z_{•}^{k}, z_{∘}^{k})) ,

COUNTING UNROOTED MAPS USING TREE-DECOMPOSITION 43

where

H(z_{•}, z_{∘}) = − \begin{matrix}γ_{1} & 3 & γ_{2} & 3 & (γ_{1}^{2}γ_{2}^{2} − γ_{1}^{2} + γ_{1}^{2}γ_{2} − γ_{1} γ_{2} − 2 γ_{2} − 2 γ_{1} − 1 − γ_{2}^{2} + γ_{2}^{2}γ_{1}) \\ (1 + γ_{2}) & 2 & (1 + γ_{1}) & 2 & (γ_{1} + 1 + 2 γ_{2} + γ_{2}^{2}) & (1 + 2 γ_{1} + γ_{1}^{2} + γ_{2}) & (γ_{1} + 1 + γ_{2}) & 3 \end{matrix}
H_{b𝔣}(z_{•}, z_{∘}) = −2 γ_{1}^{2}γ_{2}^{2} (4 + 16 γ_{2} + 13 γ_{1} + 24 γ_{2}^{2} + 14 γ_{1}^{2} + 34 γ_{1} γ_{2} + 5 γ_{1}^{3} + 8 γ_{2}^{3}γ_{1}

+3 γ_{1}^{3}γ_{2} + 9 γ_{1}^{2}γ_{2}^{2} + 29 γ_{2}^{2}γ_{1} + 16 γ_{2}^{3} + 4 γ_{2}^{4} + 21 γ_{1}^{2}γ_{2}) /

((3 γ_{1} γ_{2} − γ_{2} − γ_{1} − 1) (γ_{1} + 1 + 2 γ_{2} + γ_{2}^{2})^{2} (γ_{1} + 1 + γ_{2})^{3})
H_{w𝔣}(z_{•}, z_{∘}) = subs({γ_{1} = γ_{2}, γ_{2} = γ_{1}}, H_{b𝔣})
H_{b𝔣′}(z_{•}, z_{∘}) = \begin{matrix}γ_{1} & 2 & γ_{2} & 2 \\ (γ_{1} + 1 + 2 γ_{2} + γ_{2}^{2}) & (γ_{1} + 1 + γ_{2}) & 2 \end{matrix}
H_{w𝔣′}(z_{•}, z_{∘}) = subs({γ_{1} = γ_{2}, γ_{2} = γ_{1}}, H_{b𝔣′})
H_{𝔣𝔣}(z_{•}, z_{∘}) = − (2 + 112 γ_{1}^{3} + 112 γ_{2}^{3} + 56 γ_{1}^{2} + 56 γ_{2}^{2} + 950 γ_{1}^{2}γ_{2}^{2} + 353 γ_{1}^{2}γ_{2} + 114 γ_{1} γ_{2}

+353 γ_{2}^{2}γ_{1} + 1708 γ_{1}^{3}γ_{2}^{3} + 140 γ_{2}^{4} + 620 γ_{2}^{3}γ_{1} + 620 γ_{1}^{3}γ_{2} + 140 γ_{1}^{4} +91 γ_{1}^{3}γ_{2}^{6} + 675 γ_{1}^{4}γ_{2} + 466 γ_{1}^{5}γ_{2} + 683 γ_{1}^{5}γ_{2}^{2} + 10 γ_{2}^{5}γ_{1}^{5} + 122 γ_{2}^{5}γ_{1}^{4} +122 γ_{2}^{4}γ_{1}^{5} + 445 γ_{2}^{3}γ_{1}^{5} + 548 γ_{1}^{4}γ_{2}^{4} + 445 γ_{1}^{3}γ_{2}^{5} + 1263 γ_{2}^{2}γ_{1}^{4} + 1164 γ_{1}^{4}γ_{2}^{3} +1415 γ_{1}^{2}γ_{2}^{3} + 1415 γ_{1}^{3}γ_{2}^{2} + 1263 γ_{1}^{2}γ_{2}^{4} + 9 γ_{1}^{3}γ_{2}^{7} + 1164 γ_{1}^{3}γ_{2}^{4} + 199 γ_{1}^{6}γ_{2} +216 γ_{1}^{6}γ_{2}^{2} + 91 γ_{1}^{6}γ_{2}^{3} + 10 γ_{1}^{6}γ_{2}^{4} + 37 γ_{1}^{7}γ_{2}^{2} + 9 γ_{1}^{7}γ_{2}^{3} + 48 γ_{1}^{7}γ_{2} + 5 γ_{1}^{8}γ_{2} +3 γ_{1}^{8}γ_{2}^{2} + 675 γ_{1} γ_{2}^{4} + 466 γ_{1} γ_{2}^{5} + 199 γ_{1} γ_{2}^{6} + 48 γ_{1} γ_{2}^{7} + 5 γ_{1} γ_{2}^{8} +683 γ_{1}^{2}γ_{2}^{5} + 216 γ_{1}^{2}γ_{2}^{6} + 37 γ_{1}^{2}γ_{2}^{7} + 3 γ_{1}^{2}γ_{2}^{8} + 10 γ_{1}^{4}γ_{2}^{6} + 2 γ_{1}^{8} + 56 γ_{1}^{6} +16 γ_{1}^{7} + 112 γ_{1}^{5} + 56 γ_{2}^{6} + 2 γ_{2}^{8} + 16 γ_{2}^{7} + 112 γ_{2}^{5} + 16 γ_{1} + 16 γ_{2}) γ_{1} γ_{2} /

((3 γ_{1} γ_{2} − γ_{2} − γ_{1} − 1) (γ_{1} + 1 + 2 γ_{2} + γ_{2}^{2})^{2} (1 + 2 γ_{1} + γ_{1}^{2} + γ_{2})^{2} (γ_{1} + 1 + γ_{2})^{3})
H_{𝔣𝔣′} (z_{•}, z_{∘}) = (1 + 3 γ_{2} + 3 γ_{1} + 3 γ_{2}^{2} + 3 γ_{1}^{2} + 7 γ_{1} γ_{2} + γ_{1}^{3} + γ_{2}^{3}γ_{1} + γ_{1}^{3}γ_{2} + γ_{1}^{2}γ_{2}^{2}

+5 γ_{2}^{2}γ_{1} + γ_{2}^{3} + 5 γ_{1}^{2}γ_{2}) γ_{1} γ_{2} /

((1 + 2 γ_{1} + γ_{1}^{2} + γ_{2}) (γ_{1} + 1 + 2 γ_{2} + γ_{2}^{2}) (γ_{1} + 1 + γ_{2})^{2})
H_{bb}^{(2)}(z_{•}, z_{∘}) = −γ_{1}^{2}γ_{2}^{4} (3 + 15 γ_{2} + 20 γ_{1} + 30 γ_{1} γ_{2}^{4} + 3 γ_{1} γ_{2}^{5} + 11 γ_{1}^{4}γ_{2} + 12 γ_{1}^{4} + 30 γ_{2}^{2}

+3 γ_{2}^{2}γ_{1}^{4} + 43 γ_{1}^{2} + 9 γ_{1}^{3}γ_{2}^{3} + 81 γ_{1} γ_{2} + 55 γ_{1}^{2}γ_{2}^{3} + 38 γ_{1}^{3} + 43 γ_{1}^{3}γ_{2}^{2} +92 γ_{2}^{3}γ_{1} + 72 γ_{1}^{3}γ_{2} + 132 γ_{1}^{2}γ_{2}^{2} + 126 γ_{2}^{2}γ_{1} + 3 γ_{2}^{5} + 30 γ_{2}^{3} + 15 γ_{2}^{4} +127 γ_{1}^{2}γ_{2} + 7 γ_{1}^{2}γ_{2}^{4}) /

((3 γ_{1} γ_{2} − γ_{2} − γ_{1} − 1) (1 + 2 γ_{1} + γ_{1}^{2} + γ_{2}) (1 + γ_{1})^{2} (γ_{1} + 1 + 2 γ_{2} + γ_{2}^{2})^{2}
(γ_{1} + 1 + γ_{2})^{3})
H_{ww}^{(2)}(z_{•}, z_{∘}) = subs({γ_{1} = γ_{2}, γ_{2} = γ_{1}}, H_{bb}^{(2)})
H_{bw}^{(2)}(z_{•}, z_{∘}) = −4 \begin{matrix}γ_{1} & 2 & γ_{2} & 2 \\ (3 γ_{1} γ_{2} − γ_{2} − γ_{1} − 1) & (γ_{1} + 1 + γ_{2}) & 3 \end{matrix}
H_{bb}^{⩾3}(z_{•}, z_{∘}) = − \frac{γ_{2}^{2}γ_{1} (4 γ_{1} + 3 + 3 γ_{2})}{(3 γ_{1} γ_{2} − γ_{2} − γ_{1} − 1) (1 + 2 γ_{1} + γ_{1}^{2} + γ_{2}) (γ_{1} + 1 + γ_{2})}
H_{ww}^{⩾3}(z_{•}, z_{∘}) = subs({γ_{1} = γ_{2}, γ_{2} = γ_{1}}, H_{bb}^{⩾3})
H_{bw}^{⩾3}(z_{•}, z_{∘}) = −4 \frac{γ_{1} γ_{2}}{(γ_{1} + 1 + γ_{2}) (3 γ_{1} γ_{2} − γ_{2} − γ_{1} − 1)}

The first coefficients of the series of unrooted 3-connected maps are z_{•}^{3}z_{∘}^{3}+z_{•}^{4}z_{∘}^{4}+ (z_{•}^{5}z_{∘}^{4} + z_{•}^{4}z_{∘}^{5}) + 3 z_{•}^{5}z_{∘}^{5} + (2 z_{•}^{6}z_{∘}^{5} + 2 z_{•}^{5}z_{∘}^{6}) + (2 z_{•}^{7}z_{∘}^{5} + 2 z_{•}^{5}z_{∘}^{7} + 11 z_{•}^{6}z_{∘}^{6}) + (16 z_{•}^{7}z_{∘}^{6} + 16 z_{•}^{6}z_{∘}^{7}) + (10 z_{•}^{8}z_{∘}^{6} + 69 z_{•}^{7}z_{∘}^{7} + 10 z_{•}^{6}z_{∘}^{8}) + …

Éric Fusy, INRIA Rocquencourt, Projet ALGO BP 105, 78153 Le Chesnay, and École Polytechnique, LIX

  E-mail address: Eric.Fusy@inria.fr