# A simple formula for the series of bipartite and quasi-bipartite maps with boundaries

Gwendal Collet and Éric Fusy†

LIX, École Polytechnique, 91128 Palaiseau, France

**Abstract.** We obtain a very simple formula for the generating function of bipartite (resp. quasi-bipartite) planar maps with boundaries (holes) of prescribed lengths, which generalizes certain expressions obtained by Eynard in a book to appear. The formula is derived from a bijection due to Bouttier, Di Francesco and Guitter combined with a process (reminiscent of a construction of Pitman) of aggregating connected components of a forest into a single tree.

**Résumé.** Nous obtenons une formule très simple pour la série génératrice des cartes biparties ayant des bords (trous) de tailles fixées, généralisant certaines expressions obtenues par Eynard dans un livre à paraître. Nous obtenons la formule à partir d'une bijection due à Bouttier, Di Francesco et Guitter, combinée avec un processus (dans l'esprit d'une construction due à Pitman) pour agréger les composantes connexes d'une forêt en un unique arbre.

**Keywords:** bijections, planar maps, enumeration

## 1 Introduction

Planar maps, i.e., connected graphs embedded on the sphere, have attracted a lot of attention since the seminal work of [Tutte(1962), Tutte(1963)]. By considering rooted maps (i.e., maps where a corner is marked) and using a recursive approach, Tutte found beautiful counting formulas for many families of maps (bipartite, triangulations,...). Several features occur recurrently (see [Bousquet-Mélou and Jehanne(2005)] for a unified treatment): the generating function $y = y(x)$ is typically algebraic, often lacrangean (i.e., there is a parametrization as $\{y = Q_1(t), x = Q_2(t)\}$, where $Q_1(.)$ and $Q_2(.)$ are explicit rational expressions), yielding simple (binomial-like) formulas for the counting coefficients $c_n$, and the asymptotics of the coefficients is in $c\gamma^{n}n^{-5/2}$ for some constants $c > 0$ and $\gamma > 1$. In this article we focus on bipartite maps (all faces have even degree) and on quasi-bipartite maps (all faces have even degree except for two, which have odd degree). One of the first counting results obtained by Tutte is a strikingly simple formula (called formula of slicings) for the number $A[\ell_1, \dots, \ell_r]$ of maps with $r$ numbered faces $f_1, \dots, f_r$ of respective degrees $\ell_1, \dots, \ell_r$, each face having a marked corner (for simple parity reasons the number of odd $\ell_i$ must be even). Solving a technically involved recurrence satisfied by these coefficients, he proved

<footnote>†Supported by the ERC grant StG 208471 – ExploreMaps.</footnote>
in [Tutte(1962)] that when zero or two of the $\ell_i$ are odd (bipartite and quasi-bipartite case, respectively), then:

$$A[\ell_1, \dots, \ell_r] = \frac{(e-1)!}{v!} \prod_{i=1}^{r} \alpha(\ell_i), \quad \text{with } \alpha(\ell) := \frac{\ell!}{[\ell/2]![(\ell-1)/2]!} \quad (1)$$

where $e = \sum_{i=1}^r \ell_i/2$ and $v = e - r + 2$ are the numbers of edges and vertices in such maps. The formula was recovered in [Cori(1975), Cori(1976)] (using a certain encoding procedure for planar maps); and the formula in the bipartite case was rediscovered bijectively in [Schaeffer(1997)], based on a correspondence with so-called *blossoming trees*. Alternatively one can use a more recent bijection given in [Bouttier et al. (2004)] (based on a correspondence with so-called *mobiles*) which itself extends earlier constructions in [Cori and Vauquelin(1981)] and [Schaeffer(1998), Sec. 6.1] for quadrangulations. The bijection with mobiles yields the following: if we denote by $R = R(t) = R(t; x_1, x_2, \dots)$ the generating function specified by

$$R = t + \sum_{i \ge 1} x_i \binom{2i-1}{i} R^i. \quad (2)$$

and denote by $M(t) = M(t; x_1, x_2, \dots)$ the generating function of rooted bipartite maps, where $t$ marks the number of vertices and $x_i$ marks the number of faces of degree $2i$ for $i \ge 1$, then $M'(t) = R(t)$. And one easily recovers (1) in the bipartite case by an application of the Lagrange inversion formula to extract the coefficients of $R(t)$. With a little work (to be detailed in Section 4), the formula (1) in the quasi-bipartite case can be recovered as well.

As we can see, maps might satisfy beautiful counting formulas, regarding *counting coefficients* (i). Regarding *generating functions*, formulas can be very nice and compact as well. In a book to be published, [Eynard(2011)] obtains general equations satisfied by the generating function of maps of arbitrary genus and with several marked faces, which we will call boundary-faces (or shortly boundaries). They can be easily specialized to certain families of maps and then solved by residue calculations. For example, he obtains formulae for the (multivariate) generating functions of bipartite and quasi-bipartite maps with two or three boundaries of arbitrary lengths $\ell_1, \ell_2, \ell_3$ (in the quasi-bipartite case two of these lengths are odd), where $t$ marks the number of vertices and $x_i$ marks the number of non-boundary faces of degree $2i$:

$$G_{\ell_1, \ell_2} = \gamma^{\ell_1+\ell_2} \sum_{j=0}^{[\ell_2/2]} (\ell_2 - 2j) \frac{\ell_1! \ell_2!}{j!(\frac{\ell_1-\ell_2}{2} + j)!(\frac{\ell_1+\ell_2}{2} - j)!(\ell_2 - j)!} \quad (3)$$

$$G_{\ell_1, \ell_2, \ell_3} = \frac{\gamma^{\ell_1+\ell_2+\ell_3-1}}{y'(1)} \left( \prod_{i=1}^{3} \frac{\ell_i!}{[\ell_i/2]! [(\ell_i-1)/2]!} \right). \quad (4)$$

In these formulae the series $\gamma$ and $y'(1)$ are closely related to $R(t)$, precisely $\gamma^2 = R(t)$ and one can check that $y'(1) = \gamma/R'(t)$.

In this article, we obtain new formulae which generalize Eynard's ones to any number of boundaries, both in the bipartite and the quasi-bipartite case. For $r \ge 1$ and $\ell_1, \dots, \ell_r$ positive integers, an *even map* of type $(\ell_1, \dots, \ell_r)$ is a map with $r$ (numbered) marked faces —called *boundary-faces*— $f_1, \dots, f_r$ of degrees $\ell_1, \dots, \ell_r$, each boundary-face having a marked corner, and with all the other faces of even

<footnote>(i) We also mention the work of [Krikun(2007)] where a beautiful formula is proved for the number of triangulations with multiple boundaries of prescribed lengths, a bijective proof of which is still to be found.</footnote>
degree. (Note that there is an even number of odd $\ell_i$ by a simple parity argument.) Let $G_{\ell_1, \dots, \ell_r} := G_{\ell_1, \dots, \ell_r}(t; x_1, x_2, \dots)$ be the corresponding generating function where $t$ marks the number of vertices and $x_i$ marks the number of non-boundary faces of degree $2i$. Our main result is:

**Theorem 1.1** When zero or two of the $\ell_i$ are odd, then the following formula holds:

$$G_{\ell_1, \dots, \ell_r} = \left( \prod_{i=1}^{r} \alpha(\ell_i) \right) \cdot \frac{1}{s} \cdot \frac{d^{r-2}}{dt^{r-2}} R^s, \text{ with } \alpha(\ell) = \frac{\ell!}{\lfloor \frac{\ell}{2} \rfloor! \lfloor \frac{\ell-1}{2} \rfloor!}, \quad s = \frac{\ell_1 + \dots + \ell_r}{2}, \qquad (5)$$

where $R$ is given by (2).

Our formula covers all parity cases for the $\ell_i$ when $r \le 3$. For $r = 1$, the formula reads $G_{2a}' = \binom{2a}{a}R^a$, which is a direct consequence of the bijection with mobiles. For $r = 2$ the formula reads $G_{\ell_1, \ell_2} = \alpha(\ell_1)\alpha(\ell_2)R^s/s$ (which simplifies the constant in (3)). And for $r = 3$ the formula reads $G_{\ell_1, \ell_2, \ell_3} = \alpha(\ell_1)\alpha(\ell_2)\alpha(\ell_3)R'R^{s-1}$. Note that (5) also “contains” the formula of slicings (1), by noticing that $A[\ell_1, \dots, \ell_r]$ equals the evaluation of $G_{\ell_1, \dots, \ell_r}$ at $\{t = 1; x_1 = 0, x_2 = 0, \dots\}$, which equals $(\prod_{i=1}^r \alpha(\ell_i)) \cdot \frac{(s-1)!}{(s-r+2)!}$. Hence, (5) can be seen as an “interpolation” between the two formulas of Eynard given above and Tutte’s formula of slicings. In addition, (5) has the nice feature that the expression of $G_{\ell_1, \dots, \ell_r}$ splits into two factors: (i) a constant factor which itself is a product of independent contributions from every boundary, (ii) a series-factor that just depends on the number of boundaries and the total length of the boundaries.

Even though the coefficients of $G_{\ell_1, \dots, \ell_r}$ have simple binomial-like expressions (easy to obtain from (1)), it does not explain why at the level of generating functions the expression (5) is so simple (and it would not be obvious to guess (5) by just looking at (1)). Relying on the bijection with mobiles (recalled in Section 2), we give a transparent proof of (5). In the bipartite case, our construction (described in Section 3) starts from a forest of mobiles with some marked vertices, and then we aggregate the connected components so as to obtain a single mobile with some marked black vertices of fixed degrees (these black vertices correspond to the boundary-faces). The idea of aggregating connected components as we do is reminiscent of a construction in [Pitman(1999)] giving for instance a very simple proof (see [Aigner and Ziegler(2004), Chap. 26]) that the number of Cayley trees with $n$ nodes is $n^{n-2}$. Then we show in Section 4 that the formula in the quasi-bipartite case can be obtained by a reduction to the bipartite case. It would be interesting as a next step (the present paper just looks at the cases where at most two of the $\ell_i$ are odd) to search for a simple formula for $G_{\ell_1, \dots, \ell_r}$ when four or more of the $\ell_i$ are odd (as noted in [Tutte(1962)], the coefficients do not seem to be that simple, they have large prime factors).

## 2 Bijection between vertex-pointed maps and mobiles

We recall here a well-known bijection due to [Bouttier et al.(2004)] between vertex-pointed planar maps and a certain family of decorated trees called mobiles. We actually follow a slight reformulation of the bijection given in [Bernardi and Fusy(2011)]. A mobile is a plane tree (i.e., a planar map with one face) with vertices either black or white, with dangling half-edges —called buds— at black vertices, such that there is no white-white edge, and such that each black vertex has as many buds as white neighbours. The degree of a black vertex $v$ is the total number of incident half-edges (including the buds) incident to $v$. Starting from a planar map $G$ with a pointed vertex $v_0$, and where the vertices of $G$ are considered as white, one obtains a mobile $M$ as follows (see Figure 1):
<figure><img src="image_1.png" /><figcaption>**Fig. 1:** (a) A vertex-pointed map endowed with the geodesic orientation (with respect to the marked vertex). (b) The local rule is applied to each edge of the map. (c) The resulting mobile.</figcaption></figure>

• Endow $G$ with its geodesic orientation from $v_0$ (i.e., an edge $\{v, v'\}$ is oriented from $v$ to $v'$ if $v'$ is one unit further than $v$ from $v_0$, and is left unoriented if $v$ and $v'$ are at the same distance from $v_0$).

• Put a new black vertex in each face of $G$.

• Apply the following local rule to each edge (oriented or not) of $G$:

<figure><img src="image_2.png" /></figure>

• Delete the edges of $G$ and the vertex $v_0$.

**Theorem 2.1 ([Bouttier et al. (2004) ])** *The above construction is a bijection between vertex-pointed maps and mobiles. Each non-root vertex in the map corresponds to a white vertex in the mobile. Each face of degree i in the map corresponds to a black vertex of degree i in the mobile.*

A mobile is called *bipartite* when all black vertices have even degree, and is called *quasi-bipartite* when all black vertices have even degree except for two which have odd degree. Note that bipartite (resp. quasi-bipartite) mobiles correspond to bipartite (resp. quasi-bipartite) vertex-pointed maps.

**Claim 2.1** *A mobile is bipartite iff it has no black-black edge. A mobile is quasi-bipartite iff the set of black-black edges forms a non-empty path whose extremities are the two black vertices of odd degrees.*

**Proof:** Let $T$ be a mobile and $F$ the forest formed by the black vertices and black-black edges of $T$. Note that for each black vertex of $T$, the degree and the number of incident black-black edges have same parity. Hence if $T$ is bipartite, $F$ has only vertices of even degree, so $F$ is empty; while if $T$ is quasi-bipartite, $F$ has two vertices of odd degree, so the only possibility is that the edges of $F$ form a non-empty path. $\square$

A bipartite mobile is called *rooted* if it has a marked corner at a white vertex. Let $R := R(t; x_1, x_2, \dots)$ be the generating function of rooted bipartite mobiles, where $t$ marks the number of white vertices and $x_i$ marks the number of black vertices of degree $2i$ for $i \ge 1$. As shown in [Bouttier et al. (2004)], a decomposition at the root ensures that $R$ is given by Equation (2); indeed if we denote by $S$ the generating function of bipartite mobiles rooted at a white leaf, then $R = t + RS$ and $S = \sum_{i \ge 1} x_i \binom{2i-1}{i} R^{i-1}$.
<figure><img src="image_3.png" /><figcaption>**Fig. 2:** From a bipartite mobile with 5 marked black vertices to a forest with 5 connected components and 4 marked white vertices {$w_1, w_2, w_3, w_4$}: (a) removing the buds on marked black vertices, (b) cutting the mobile at a marked black vertex into two connected components (5 - 1 choices) and a marked white vertex $w_1$, (c) repeating the same operation 3 more time to obtain 5 connected components and 4 marked white vertices.</figcaption></figure>

## 3 Bipartite case

In this section, we consider the two following families:

* $M_{2a_1,...,2a_r}$ is the family of bipartite mobiles with $r$ marked black vertices $v_1, ..., v_r$ of respective degrees $2a_1, ..., 2a_r$, the mobile being rooted at a bud incident to one of the marked vertices,

* $\mathcal{F}_s$ is the family of forests made of $s := \sum_{i=1}^r a_i$ rooted bipartite mobiles, and where additionally $r-1$ white vertices $w_1, ..., w_{r-1}$ are marked.

We also define the constant $c = \prod_{i=1}^{r} \binom{2a_i - 1}{a_i}$.

**Proposition 3.1** There is an $(r-1)!$-to-$(r-1)!$ correspondence between the family $M_{2a_1,...,2a_r}$ and the family $c \cdot \mathcal{F}_s$. If $\gamma \in M_{2a_1,...,2a_r}$ corresponds to $\gamma' \in \mathcal{F}_s$, then each white vertex in $\gamma$ corresponds to a white vertex in $\gamma'$, and each black vertex of degree $2i$ in $\gamma$ corresponds to a black vertex of degree $2i$ in $\gamma'$.

**Proof:** We will describe the correspondence in both ways (see Figure 2). First, one can go from the forest to the mobile through the following operations:
1. Group the first $a_1$ mobiles and bind them to a new black vertex $b_1$, then bind the next $a_2$ mobiles to a new black vertex $b_2$, and so on, to get a forest with $r$ connected components rooted at $b_1, \dots, b_r$.

2. The $r-1$ marked white vertices $w_1, \dots, w_{r-1}$ are ordered, pick one of the $r-1$ components which do not contain $w_{r-1}$. Bind this component to $w_{r-1}$ by merging $w_{r-1}$ with the rightmost white neighbour of $b_i$. Repeat the operation for each $w_{r-i}$ to reduce the number of components to one ($r-i$ possibilities in the choice of the connected component at the $i$th step), thus getting a decorated bipartite tree rooted at a corner incident to some $b_j$.

3. For $i \neq j$, decorate with $a_i$ buds the black vertex $b_i$, yielding a factor of $(2^{2a_i-1})$.

4. Replace now the root corner at $b_j$ by a bud which will be the root of the output mobile, and decorate $b_j$ with $a_j - 1$ buds, yielding another factor $(2^{a_j-1})$.

Conversely, one can go from the mobile to the forest through the following operations:

1. Remove every bud on marked black vertices, and replace the root bud by a root corner, yielding a factor of $1/\prod_{i=1}^{r} (2^{2a_i-1})$.

2. Pick one marked black vertex $b_k$, but the root, and separate it as in Figure 2 (transition from (a) to (b)), this creates a new connected component, rooted at $b_k$.

3. Repeat this operation, choosing at each step ($r-i$ possibilities at the $i$th step) a marked black vertex that is not the root in its connected components, until one gets $r$ connected components, each being rooted at one of the marked black vertices $\{b_1, \dots, b_r\}$.

4. Remove all marked black vertices and their incident edges; this yields a forest of $s$ rooted bipartite mobiles.

In both ways, there are $\prod_{i=1}^{r-1} (r-i) = (r-1)!$ possibilities, that is, the correspondence is $(r-1)!$-to-$(r-1)!$. $\square$

As a corollary we obtain the formula of Theorem 1.1 in the bipartite case:

**Corollary 3.1** For $r \ge 1$ and $a_1, \dots, a_r$ positive integers, the generating function $G_{2a_1, \dots, 2a_r}$ satisfies (5), i.e.,

$$G_{2a_1, \dots, 2a_r} = \left( \prod_{i=1}^{r} \frac{(2a_i)!}{a_i!(a_i-1)!} \right) \cdot \frac{1}{s} \cdot \frac{d^{r-2}}{dt^{r-2}} R^s, \quad \text{where } s = \sum_{i=1}^{r} a_i. \qquad (6)$$

**Proof:** As mentioned in the introduction, for $r=1$ the expression reads $G_{2a} = \binom{2a}{a} R^a$, which is a direct consequence of the bijection with mobiles (indeed $G_{2a}$ is the series of mobiles with a marked black vertex $v$ of degree $2a$, with a marked corner incident to $v$). So we now assume $r \ge 2$. Let $T_{2a_1, \dots, 2a_r} = T_{2a_1, \dots, 2a_r}(t; x_1, x_2, \dots)$ be the generating function of bipartite mobiles with $r$ marked black vertices of degrees $2a_1, \dots, 2a_r$, where $t$ marks the number of white vertices and $x_i$ marks the number of black vertices of degree $2i$. Let $M_{2a_1, \dots, 2a_r} = M_{2a_1, \dots, 2a_r}(t; x_1, x_2, \dots)$ be the generating function of $M_{2a_1, \dots, 2a_r}$ where again $t$ marks the number of white vertices and $x_i$ marks the number of black vertices of degree $2i$. By definition of $M_{2a_1, \dots, 2a_r}$, we have $s \cdot T_{2a_1, \dots, 2a_r} = M_{2a_1, \dots, 2a_r}$. Moreover,
<figure><img src="image_4.png" /><figcaption>Fig. 3: (a) A blossoming tree. (b) The corresponding rooted bipartite mobile.</figcaption></figure>

Theorem 2.1 ensures that $G_{2a_1,...,2a_r'} = (\prod_{i=1}^r 2a_i) \cdot T_{2a_1,...,2a_r}$, where the multiplicative constant is the consequence of a corner being marked in every boundary face, and where the derivative (according to $t$) is the consequence of a vertex being marked in the bipartite map. Next, Proposition 3.1 yields

$$M_{2a_1,...,2a_r} = \left( \prod_{i=1}^{r} \binom{2a_i - 1}{a_i} \right) \cdot \frac{d^{r-1}}{dt^{r-1}} R^s$$

hence we conclude that

$$G_{2a_1,...,2a_r'} = \frac{1}{s} \left( \prod_{i=1}^{r} 2a_i \binom{2a_i - 1}{a_i} \right) \cdot \frac{d^{r-1}}{dt^{r-1}} R^s,$$

which, upon integration according to $t$, gives the claimed formula. □

# 4 Quasi-bipartite case

So far we have obtained an expression for the generating function $G_{\ell_1,...,\ell_r}$ when all $\ell_i$ are even. In general, by definition of even maps of type $(\ell_1,...,\ell_r)$, there is an even number of $\ell_i$ of odd degree. While getting a simple explicit expression in the general case is open, we can get a formula when there are 2 odd boundaries. We proceed by a reduction to the bipartite case, using so-called *blossoming trees* (already considered in [Schaeffer(1997)]) as auxilary structures, see Figure 3(a) for an example.

**Definition 4.1 (Blossoming trees)** A planted plane tree is a plane tree with a marked leaf; classically it is drawn in a top-down way; each vertex $v$ (different from the root-leaf) has $i$ (ordered) children, and the integer $i$ is called the *arity of $v$*. Vertices that are not leaves are colored black (so a black vertex means a vertex that is not a leaf). A blossoming tree is a rooted plane tree where each black vertex $v$, whose *arity* $i$ is positive, carries additionally $i-1$ dangling half-edges called *buds* (leaves carry no bud). The degree of such a black vertex $v$ is defined to be $2i$.
By a standard decomposition at the root, the generating function $T := T(t; x_1, x_2, \dots)$ of blossoming trees, where $t$ marks the number of non-root leaves and $x_i$ marks the number of black vertices of degree $2i$, is given by:

$$T = t + \sum_{i \ge 1} x_i \binom{2i-1}{i} T^i. \qquad (7)$$

**Claim 4.1** There is a bijection between the family $\mathcal{T}$ of blossoming trees and the family $\mathcal{R}$ of rooted bipartite mobiles. For $\gamma \in \mathcal{T}$ and $\gamma' \in \mathcal{R}$ the associated rooted bipartite mobile, each non-root leaf of $\gamma$ corresponds to a white vertex of $\gamma'$, and each black vertex of degree $2i$ in $\gamma$ corresponds to a black vertex of degree $2i$ in $\gamma'$.

**Proof:** Note that the decomposition-equation (7) satisfied by $T$ is exactly the same as the decomposition-equation (2) satisfied by $\mathcal{R}$. Hence $T = \mathcal{R}$, and one can easily produce recursively a bijection between $\mathcal{T}$ and $\mathcal{R}$ that sends black vertices of degree $2i$ to black vertices of degree $2i$, and sends leaves to white vertices, for instance Figure 3 shows a blossoming tree and the corresponding rooted bipartite mobile. $\square$

The bijection between $\mathcal{T}$ and $\mathcal{R}$ will be used in order to get rid of the black path (between the two black vertices of odd degrees) which appears in a quasi-bipartite mobile. Note that, if we denote by $\mathcal{R}'$ the family of rooted mobiles with a marked white vertex (which does not contribute to the number of white vertices), and by $\mathcal{T}'$ the family of blossoming trees with a marked non-root leaf (which does not contribute to the number of non-root leaves), then $\mathcal{T}' \simeq \mathcal{R}'$.

Let $\tau$ be a mobile with two marked black vertices $v_1, v_2$. Let $P = (e_1, \dots, e_k)$ be the path between $v_1$ and $v_2$ in $\tau$. If we untie $e_1$ from $v_1$ and $e_k$ from $v_2$, we obtain 3 connected components: the one containing $P$ is called the middle-part $\tau'$ of $\tau$; the edges $e_1$ and $e_k$ are called respectively the first end and the second end of $\tau'$ in $\tau$. The vertices $v_1$ and $v_2$ are considered as taken away from $\tau'$, which therefore ends on edges, not vertices.

Let $\mathcal{H}$ be the family of structures that can be obtained as middle-parts of quasi-bipartite mobiles where $v_1$ and $v_2$ are the two black vertices of odd degree (hence the path between $v_1$ and $v_2$ contains only black vertices). And let $\mathcal{K}$ be the family of structures that can be obtained as middle-parts of bipartite mobiles with two marked black vertices $v_1, v_2$.

**Lemma 4.1** We have the following bijections:

$$\mathcal{H} \simeq \mathcal{T}' \simeq \mathcal{R}' \qquad \mathcal{K} \simeq \mathcal{R}' \times \mathcal{R}$$

Hence:

$$\mathcal{K} \simeq \mathcal{H} \times \mathcal{R}.$$

In these bijections each black vertex of degree $2i$ (resp. each white vertex) in an object on the left-hand side corresponds to a black vertex of degree $2i$ (resp. to a white vertex) in the corresponding object on the right-hand side.

**Proof:** Note that any $\tau \in \mathcal{H}$ consists of a path $P$ of black vertices, and each vertex of degree $2i$ on $P$ carries (outside of $P$) $i-1$ buds and $i-1$ rooted mobiles (in $\mathcal{R}$), as illustrated in Figure 4(b). Let $\tau'$ be $\tau$ where each rooted mobile attached to $P$ is replaced by the corresponding blossoming tree (using the isomorphism of Claim 4.1), and where the ends of $\gamma$ are considered as two marked leaves (respectively
<figure><img src="image_5.png" /><figcaption>Fig. 4: middle-parts in the bipartite case (a) and in the quasi-bipartite case (b).</figcaption></figure>

the root-leaf and a marked non-root leaf). We clearly have $\tau' \in \mathcal{T}'$. Conversely, starting from $\tau' \in \mathcal{T}'$, let $P$ be the path between the root-leaf and the non-root marked leaf. Each vertex of degree $2i$ on $P$ carries (outside of $P$) $i-1$ buds and $i-1$ blossoming trees. Replacing each blossoming tree attached to $P$ by the corresponding rooted mobile, and seeing the two marked leaves as the first and second end of $P$, one gets a structure in $\mathcal{H}$. So we have $\mathcal{H} \simeq \mathcal{T}'$.

The bijection $\mathcal{K} \simeq \mathcal{R}' \times \mathcal{R}$ is simpler. Indeed, any $\tau \in \mathcal{K}$ can be seen as a rooted mobile $\gamma$ with a secondary marked corner at a white vertex (see Figure 4(a)). Let $w$ (resp. $w'$) be the white vertex at the root (resp. at the secondary marked corner) and let $P$ be the path between $w$ and $w'$. Each white vertex on $P$ can be seen as carrying two rooted mobiles (in $\mathcal{R}$), one on each side of $P$. Let $r, r'$ be the two rooted mobiles attached at $w'$ (say, $r$ is the one on the left of $w'$ when looking toward $w$). If we untie $r$ from the rest of $\gamma$, then $w'$ now just acts as a marked white vertex in $\gamma$, so the pair $(\gamma, r)$ is in $\mathcal{R}' \times \mathcal{R}$. The mapping from $(\gamma, r) \in \mathcal{R}' \times \mathcal{R}$ to $\tau \in \mathcal{K}$ processes in the reverse way. We get $\mathcal{K} \simeq \mathcal{R}' \times \mathcal{R}$. $\square$

Now from Lemma 4.1 we can deduce a reduction from the quasi-bipartite to the bipartite case (in Lemma 4.2 thereafter, see also Figure 4). Let $a_1$ and $a_2$ be positive integers. Define $\mathcal{B}_{2a_1, 2a_2}$ as the family of bipartite mobiles with two marked black vertices $v_1, v_2$ of respective degrees $2a_1, 2a_2$. Similarly define $\mathcal{Q}_{2a_1-1, 2a_2-1}$ as the family of quasi-bipartite mobiles with two marked black vertices $v_1, v_2$ of respective degrees $2a_1-1, 2a_2-1$ (i.e., the marked vertices are the two black vertices of odd degree). For each mobile $\gamma$ with two marked black vertices, let $\phi(\gamma)$ be $\gamma$ where the buds on the two marked black vertices have been removed. Let $\tilde{\mathcal{B}}_{2a_1, 2a_2}$ be the image of the family $\mathcal{B}_{2a_1, 2a_2}$ by $\phi$, and let $\tilde{\mathcal{Q}}_{2a_1-1, 2a_2-1}$ be the image of the family $\mathcal{Q}_{2a_1-1, 2a_2-1}$ by $\phi$.
**Lemma 4.2** For $a_1, a_2$ two positive integers:

$$ \hat{B}_{2a_1, 2a_2} \simeq \hat{Q}_{2a_1-1, 2a_2+1}. $$

In addition, if $\gamma \in \hat{B}_{2a_1, 2a_2}$ corresponds to $\gamma' \in \hat{Q}_{2a_1-1, 2a_2+1}$, then each non-marked black vertex of degree $2i$ (resp. each white vertex) in $\gamma$ corresponds to a non-marked black vertex of degree $2i$ (resp. to a white vertex) in $\gamma'$.

**Proof:** Let $\gamma \in \hat{Q}_{2a_1-1, 2a_2+1}$, and let $\tau$ be the middle-part of $\gamma$. We construct $\gamma' \in \hat{B}_{2a_1, 2a_2}$ as follows. Note that $v_2$ has a black neighbour $b$ (along the branch from $v_2$ to $v_1$) and has otherwise $a_2$ white neighbours. Let $w$ be next neighbour after $b$ in counter-clockwise order around $v_2$, and let $r$ be the mobile (in $\mathcal{R}$) hanging from $w$. According to Lemma 4.1, the pair $(\tau, r)$ corresponds to some $\tau' \in \mathcal{K}$. If we replace the middle-part $\tau$ by $\tau'$ and take out the edge $\{v_2, w\}$ and the mobile $r$, we obtain some $\gamma' \in \hat{B}_{2a_1, 2a_2}$. The inverse process is easy to describe, so we obtain a bijection between $\hat{Q}_{2a_1-1, 2a_2+1}$ and $\hat{B}_{2a_1, 2a_2}$. $\square$

Lemma 4.2 (in an equivalent form) can also be found in [Cori(1975), Theo.VI p.75]. An even more precise statement (which keeps track of a certain distance-parameter) is proved in [Chapuy(2009), Prop.7.5]. We have included our own (quite shorter and completely bijective) proof for the sake of completeness.

As a corollary of Lemma 4.2, we obtain the formula of Theorem 1.1 in the quasi-bipartite case, with the exception of the case where the two odd boundaries are of length 1 (this case will be treated later, in Lemma 4.3).

**Corollary 4.1** For $r \ge 2$ and $a_1, \dots, a_r$ positive integers, the generating function $G_{2a_1-1, 2a_2+1, 2a_3, \dots, 2a_r}$ satisfies (5).

**Proof:** We first consider the case $r = 2$. Let $\hat{B}_{2a_1, 2a_2} = \hat{B}_{2a_1, 2a_2}(t; x_1, x_2, \dots)$ (resp. $B_{2a_1, 2a_2} = B_{2a_1, 2a_2}(t; x_1, x_2, \dots)$) be the generating function of $\hat{B}_{2a_1, 2a_2}$ (resp. of $B_{2a_1, 2a_2}$) where $t$ marks the number of white vertices and $x_i$ marks the number of non-marked black vertices of degree $2i$. There are $\binom{2a_i-1}{a_i}$ ways to place the buds at each marked black vertex $v_i$ ($i \in \{1, 2\}$), hence

$$ B_{2a_1, 2a_2} = \binom{2a_1-1}{a_1} \binom{2a_2-1}{a_2} \hat{B}_{2a_1, 2a_2}. $$

In addition Theorem 2.1 ensures that $G_{2a_1, 2a_2}' = 2a_1 2a_2 B_{2a_1, 2a_2}$ (the multiplicative factor being due to the choice of a marked corner in each boundary-face). Hence

$$ G_{2a_1, 2a_2}' = 4a_1 a_2 \binom{2a_1-1}{a_1} \binom{2a_2-1}{a_2} \hat{B}_{2a_1, 2a_2}. $$

Similarly, if we denote by $\hat{Q}_{2a_1-1, 2a_2+1} = \hat{Q}_{2a_1-1, 2a_2+1}(t; x_1, x_2, \dots)$ the generating function of the family $\hat{Q}_{2a_1-1, 2a_2+1}$ where $t$ marks the number of white vertices and $x_i$ marks the number of non-marked black vertices of degree $2i$, then we have

$$ G_{2a_1-1, 2a_2+1}' = (2a_1-1)(2a_2+1) \binom{2a_1-2}{a_1-1} \binom{2a_2}{a_2} \hat{Q}_{2a_1-1, 2a_2+1}. $$
Since $\hat{B}_{2a_1,2a_2} = \hat{Q}_{2a_1-1,2a_2+1}$ by Lemma 4.2, we get (with the notation $\alpha(\ell) = \frac{\ell!}{[\ell/2]![(\ell-1)/2]!}$):

$$ \alpha(2a_1 - 1) \cdot \alpha(2a_2 + 1) \cdot G_{2a_1, 2a_2} = \alpha(2a_1) \cdot \alpha(2a_2) \cdot G_{2a_1-1, 2a_2+1}. $$

In a very similar way (since the isomorphism of Lemma 4.2 preserves the degree distribution of non-marked black vertices), we have for $r \ge 2$:

$$ \alpha(2a_1 - 1) \cdot \alpha(2a_2 + 1) \cdot G_{2a_1, 2a_2, 2a_3, \dots, 2a_r} = \alpha(2a_1) \cdot \alpha(2a_2) \cdot G_{2a_1-1, 2a_2+1, 2a_3, \dots, 2a_r}. $$

Hence the fact that $G_{2a_1-1,2a_2+1,2a_3,\dots,2a_r}$ satisfies (5) follows from the fact (already proved in Corollary 3.1) that $G_{2a_1,2a_2,2a_3,\dots,2a_r}$ satisfies (5). $\square$

It remains to show the formula when the two odd boundary-faces have length 1. For that case, we have the following counterpart of Lemma 4.2:

**Lemma 4.3** Let $\mathcal{B}_2$ be the family of bipartite mobiles with a marked black vertex of degree 2, and let $\mathcal{B}_2'$ be the family of objects from $\mathcal{B}_2$ where a white vertex is marked. Then

$$ Q_{1,1} \simeq \mathcal{B}_2'. $$

In addition, if $\gamma \in \mathcal{B}_2'$ corresponds to $\gamma' \in Q_{1,1}$, then each white vertex of $\gamma$ corresponds to a white vertex of $\gamma'$, and each non-marked black vertex of degree $2i$ in $\gamma$ corresponds to a non-marked black vertex of degree $2i$ in $\gamma'$. $\square$

**Proof:** A mobile in $Q_{1,1}$ is completely reduced to its middle-part, so we have

$$ Q_{1,1} \simeq \mathcal{H} \simeq \mathcal{T}' \simeq \mathcal{R}'. $$

Consider a mobile in $\mathcal{R}'$, i.e., a bipartite mobile where a corner indicent to a white vertex is marked, and a secondary white vertex is marked. At the marked corner we can attach an edge connected to a black vertex $b$ of degree 2 (the other incident half-edge of $b$ being a bud). We thus obtain a mobile in $\mathcal{B}_2'$, and the mapping is clearly a bijection. $\square$

By Lemma 4.3 we have $2G_{1,1} = G_2'$, and similarly $2G_{1,1,2a_3,\dots,2a_r} = G_{2,2a_3,\dots,2a_r}$. Hence, again the fact that $G_{1,1,2a_3,\dots,2a_r}$ satisfies (5) follows from the fact that $G_{2,2a_3,\dots,2a_r}$ satisfies (5), which has been shown in Corollary 3.1.

## Acknowledgements

The authors are very grateful to Marie Albenque, Dominique Poulalhon, Juanjo Rué, and Gilles Schaeffer for inspiring discussions.

## References

[Aigner and Ziegler (2004)] M. Aigner and G. M. Ziegler. *Proofs from the book*, 3rd edition. Springer, 2004.

[Bernardi and Fusy (2011)] O. Bernardi and E. Fusy. Unified bijections for maps with prescribed degrees and girth, 2011. arXiv:1102.3619. To appear in *J. Combin. Theory Ser. A*.
[Bousquet-Mélou and Jehanne (2005)] M. Bousquet-Mélou and A. Jehanne. Polynomial equations with one catalytic variable, algebraic series, and map enumeration. *J. Combin. Theory Ser. B*, 96(5): 623-672, 2005.

[Bouttier et al. (2004)] J. Bouttier, P. Di Francesco, and E. Guitter. Planar maps as labeled mobiles. *Electronic J. Combin.*, 11:R69, 2004.

[Chapuy (2009)] G. Chapuy. Asymptotic enumeration of constellations and related families of maps on orientable surfaces. *Combinatorics, Probability, and Computing*, 18(4):477-516, 2009.

[Cori (1975)] R. Cori. Un code pour les graphes planaires et ses applications. *Astérisque*, 27:1-169, 1975.

[Cori (1976)] R. Cori. Planarité et algébricité. *Astérisque*, 38-39:33-44, 1976.

[Cori and Vauquelin (1981)] R. Cori and B. Vauquelin. Planar maps are well labeled trees. *Canad. J. Math.*, 33(5):1023-1042, 1981.

[Eynard (2011)] B. Eynard. *Counting surfaces*. Springer, 2011.

[Krikun (2007)] M. Krikun. Explicit enumeration of triangulations with multiple boundaries. *Electronic J. Combin.*, v14 R61, 2007.

[Pitman (1999)] J. Pitman. Coalescent random forests. *J. Comb. Theory, Ser. A*, 85(2):165-193, 1999.

[Schaeffer (1998)] G. Schaeffer. *Conjugaison d'arbres et cartes combinatoires aléatoires*. PhD thesis, Université Bordeaux I, 1998.

[Schaeffer (1997)] G. Schaeffer. Bijective census and random generation of Eulerian planar maps with prescribed vertex degrees. *Electron. J. Combin.*, 4(1):# 20, 14 pp., 1997.

[Tutte (1962)] W. T. Tutte. A census of slicings. *Canad. J. Math.*, 14:708-722, 1962.

[Tutte (1963)] W. T. Tutte. A census of planar maps. *Canad. J. Math.*, 15:249-271, 1963.