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

HAL
open science

# On quasi-polynomials counting planar tight maps

Jérémie Bouttier, Emmanuel Guitter, Grégory Miermont

► To cite this version:

Jérémie Bouttier, Emmanuel Guitter, Grégory Miermont. On quasi-polynomials counting planar tight maps. 2022. hal-03622398

HAL Id: hal-03622398

https://hal.science/hal-03622398

Preprint submitted on 29 Mar 2022

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.
# On quasi-polynomials counting planar tight maps

Jérémie Bouttier, Emmanuel Guitter, Grégory Miermont

► To cite this version:

Jérémie Bouttier, Emmanuel Guitter, Grégory Miermont. On quasi-polynomials counting planar tight maps. Combinatorial Theory, 2024, 4 (1), pp.#12. 10.5070/C64163849. hal-03622398v2

HAL Id: hal-03622398

https://hal.science/hal-03622398v2

Submitted on 5 Jul 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

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

Distributed under a Creative Commons Attribution 4.0 International License
On quasi-polynomials counting planar
tight maps

Jérémie Bouttier*

Emmanuel Guitter*

Grégory Miermont†

March 28, 2022

A *tight map* is a map with some of its vertices marked, such that every vertex of degree 1 is marked. We give an explicit formula for the number $N_{0,n}(d_1, \dots, d_n)$ of planar tight maps with $n$ labeled faces of prescribed degrees $d_1, \dots, d_n$, where a marked vertex is seen as a face of degree 0. It is a quasi-polynomial in $(d_1, \dots, d_n)$, as shown previously by Norbury. Our derivation is bijective and based on the *slice decomposition* of planar maps. In the non-bipartite case, we also rely on enumeration results for two-type forests. We discuss the connection with the enumeration of non necessarily tight maps. In particular, we provide a generalization of Tutte's classical slicings formula to all non-bipartite maps.

<footnote>*Université Paris-Saclay, CNRS, CEA, Institut de physique théorique, 91191, Gif-sur-Yvette, France</footnote>

<footnote>†ENS de Lyon, UMPA, CNRS UMR 5669, 46 allée d'Italie, 69364 Lyon Cedex 07, France</footnote>
# ON QUASI-POLYNOMIALS COUNTING PLANAR TIGHT MAPS

Jérémie Bouttier*¹,², Emmanuel Guitter², and Grégory Miermont†³

¹Sorbonne Université and Université Paris Cité, CNRS, IMJ-PRG, F-75005 Paris, France
jeremie.bouttier@imj-prg.fr

²Université Paris-Saclay, CNRS, CEA, Institut de physique théorique, 91191, Gif-sur-Yvette, France
emmanuel.guitter@ipht.fr

³ENS de Lyon, UMPA, CNRS UMR 5669, 46 allée d'Italie, 69364 Lyon Cedex 07, France
gregory.miermont@ens-lyon.fr

June 16, 2024

**Abstract.** A *tight map* is a map with some of its vertices marked, such that every vertex of degree 1 is marked. We give an explicit formula for the number $N_{0,n}(d_1, \dots, d_n)$ of planar tight maps with $n$ labeled faces of prescribed degrees $d_1, \dots, d_n$, where a marked vertex is seen as a face of degree 0. It is a quasi-polynomial in $(d_1, \dots, d_n)$, as shown previously by Norbury. Our derivation is bijective and based on the *slice decomposition* of planar maps. In the non-bipartite case, we also rely on enumeration results for two-type forests. We discuss the connection with the enumeration of non necessarily tight maps. In particular, we provide a generalization of Tutte's classical slicings formula to all non-bipartite maps.

**Keywords.** Planar maps, bijective enumeration, slice decomposition.

**Mathematics Subject Classifications.** 05A15, 05A19.

# 1. Introduction

## 1.1. Tight maps

The main purpose of this paper is to study the enumeration problem for a class of maps, called *tight maps*.

**Definition 1.1.** A *tight map* is a connected map with some of its vertices marked, such that every vertex of degree 1 is marked. In a tight map, the faces as well as the marked vertices are called *boundaries*.

<footnote>*Supported by the Agence Nationale de la Recherche via the grants ANR-18-CE40-0033 “Dimers” and ANR-19-CE48-0011 “Combiné”.</footnote>

<footnote>†Institut Universitaire de France (IUF)</footnote>
# Contents

<table><tbody><tr><td>1. Introduction</td><td>3</td></tr><tr><td>1.1. Tight maps</td><td>3</td></tr><tr><td>1.2. Lattice count polynomials</td><td>4</td></tr><tr><td>2. Main results</td><td>6</td></tr><tr><td>2.1. Polynomials counting planar tight bipartite or quasi-bipartite maps</td><td>6</td></tr><tr><td>2.1.1. Definition and properties of the polynomials</td><td>7</td></tr><tr><td>2.1.2. Enumeration results in the bipartite case</td><td>9</td></tr><tr><td>2.1.3. Enumeration results in the quasi-bipartite case</td><td>11</td></tr><tr><td>2.2. Quasi-polynomials counting planar tight maps with more odd faces</td><td>13</td></tr><tr><td>3. Connection with the enumeration of non necessarily tight maps</td><td>15</td></tr><tr><td>3.1. Equivalence with Tutte's slicings formula in the (quasi-)bipartite case</td><td>15</td></tr><tr><td>3.2. A non-bipartite slicings formula</td><td>18</td></tr><tr><td>4. Bijective proofs in the bipartite and quasi-bipartite cases</td><td>19</td></tr><tr><td>4.1. Case of maps with one face</td><td>19</td></tr><tr><td>4.2. Case of maps with two faces</td><td>23</td></tr><tr><td>4.3. Case of pointed rooted maps via slices</td><td>28</td></tr><tr><td>4.4. General case</td><td>35</td></tr><tr><td>5. Bijective proofs for non necessarily bipartite maps</td><td>42</td></tr><tr><td>5.1. Petal trees</td><td>42</td></tr><tr><td>5.2. Petal necklaces</td><td>47</td></tr><tr><td>5.3. Tight slices</td><td>52</td></tr><tr><td>5.4. General maps</td><td>55</td></tr><tr><td>6. Conclusion</td><td>61</td></tr><tr><td>A. Enumeration of one- and two-type labeled plane forests</td><td>62</td></tr><tr><td>B. Symmetrizing the planar lattice count quasi-polynomials</td><td>66</td></tr></tbody></table>
<figure><img src="image_2.png" /><figcaption>Figure 1.1: On the left, a tight map with 9 boundaries: six faces $f_1, f_2, f_3, f_4, f_5, f_6$ with respective degrees 12, 8, 5, 4, 3, 2, and three marked vertices $v_7, v_8, v_9$, shown in white. On the right: a rooted tight map, whose opening operation gives the tight map on the left. As this figure demonstrates, a vertex incident to the root in a rooted tight map can be of degree 1 without being necessarily marked. These maps can be also seen as pointed (respectively pointed rooted) tight maps, for example by distinguishing the marked vertex $v_9$.</figcaption></figure>

Even though this definition makes sense for maps on arbitrary surfaces, we will restrict in this paper to the planar case. We refer to [Sch15] and [BGM22] for the standard definitions and terminology about maps.

Usually, we will endow a tight map with some extra structure, in particular by labeling its faces and some or all of its marked vertices, or distinguishing one marked vertex. For instance, we will call *pointed tight map* a tight map with one distinguished marked vertex. We will adopt a slightly unusual notion of *rooted tight map* compared to the well-established notion of rooting of a map: in particular, the root will be an unoriented edge. If *e* is a distinguished edge in a map *m*, there is a natural opening operation *O*(*m*, *e*) consisting in cutting along the edge, thereby creating a face of degree 2. If *m* has marked or labeled elements (vertices or faces), then *O*(*m*, *e*) naturally inherits these elements. We say that a map *m* with some of its vertices marked and a distinguished edge *e* is a *rooted tight map* if *O*(*m*, *e*) is a tight map. Note that *m* may not be a tight map itself, as the distinguished edge may be incident to an unmarked vertex of degree 1. Finally, a *pointed rooted tight map* is a rooted tight map with one distinguished marked vertex. See Figure 1.1 for examples of tight maps.

We define the *length* of a boundary in a tight map as being equal to its degree for a face, and to zero for a marked vertex. In other words, we interpret the marked vertices as boundaries of length 0.

The terminology of tight maps comes from [BGM22]. Let us discuss it in some detail. In a general map $\mathfrak{m}$, drawn on a surface $S$, and with some faces and vertices marked, let us call
# 1. Introduction

## 1.1. Tight maps

The main purpose of this paper is to study the enumeration problem for a class of maps, called *tight maps*.

**Definition 1.** A *tight map* is a map with some of its vertices marked, such that every vertex of degree 1 is marked. In a tight map, the faces as well as the marked vertices are called *boundaries*.

Even though this definition makes sense for maps on arbitrary surfaces, we will restrict in this paper to the planar case. We refer to [Sch15] and [BGM21] for the standard definitions and terminology about maps.

Usually, we will endow a tight map with some extra structure, in particular by labeling its faces and some or all of its marked vertices, or distinguishing one marked vertex. For instance, we will call *pointed tight map* a tight map with one distinguished marked vertex. We will adopt a slightly unusual notion of *rooted tight map* compared to the well-established notion of rooting of a map. If *e* is a distinguished edge in a map **m**, there is a natural opening operation $O(\mathbf{m}, e)$ consisting in cutting open the edge, thereby creating a face of degree 2. If **m** has marked or labeled elements (vertices or faces), then $O(\mathbf{m}, e)$ naturally inherits these elements. We say that a map **m** with some of its vertices marked and a distinguished edge *e* is a *rooted tight map* if $O(\mathbf{m}, *e)$ is a tight map. Note that **m** may not be a tight map itself, as the distinguished edge may be incident to an unmarked vertex of degree 1. Finally, a *pointed rooted tight map* is a rooted tight map with one distinguished marked vertex. See Figure 1 for examples of tight maps.

We define the *length* of a boundary in a tight map as being equal to its degree for a face, and to zero for a marked vertex. In other words, we interpret the marked vertices as boundaries of length 0.

The terminology of tight maps comes from [BGM21]. Let us discuss it in some detail. In a general map **m**, drawn on a surface *S*, and with some faces and vertices marked, let us call the marked elements the *boundaries*, and the unmarked elements the *internal* faces and vertices. We let *S'* be the space obtained from *S* by removing one point (i.e. creating a puncture) inside each of the boundaries of **m**. A boundary of **m** is called *tight* if its contour path has minimal possible length among all paths in the map that are freely homotopic to it in *S'*. When the map has marked vertices, then all such vertices are automatically tight boundaries, and the previous minimality condition on the contours of the boundary-faces must be understood in a slightly modified map obtained by blowing every marked vertex of degree *k* into a *k*-cycle with edges of “length 0”, hence creating a new face in the map, which we view as having degree 0, with one puncture. See Figure 2 for an example.

This being said, it is straightforward to see that a map is tight according to Definition 1, if and only if it is a map with no internal faces (i.e. all its faces are marked as boundaries), whose boundaries are all tight. Indeed, starting from a tight map, we see that all its boundaries are necessarily tight: in the modified map with every marked vertex blown
<figure><img src="image_3.png" /><figcaption>Figure 1.2: Blowing a boundary-vertex into a face of degree 0 with one puncture.</figcaption></figure>

the marked elements the *boundaries*, and the unmarked elements the *internal* faces and vertices. We let $S'$ be the space obtained from $S$ by removing one point (i.e. creating a puncture) inside each of the boundaries of $m$. A boundary of $m$ is called *tight* if its contour path has minimal possible length among all paths in the map that are freely homotopic to it in $S'$. When the map has marked vertices, then all such vertices are automatically tight boundaries, and the previous minimality condition on the contours of the boundary-faces must be understood in a slightly modified map obtained by blowing every marked vertex of degree $k$ into a $k$-cycle with edges of “length 0”, hence creating a new face in the map, which we view as having degree 0, with one puncture. See Figure 1.2 for an example.

This being said, it is straightforward to see that a map is tight according to Definition 1.1, if and only if it is a map with no internal faces (i.e. all its faces are marked as boundaries), whose boundaries are all tight. Indeed, starting from a tight map, we see that all its boundaries are necessarily tight: in the modified map with every marked vertex blown into a degree-0 face, the contour of a given face is in fact the unique non-backtracking path of edges in its free homotopy class in the punctured surface $S'$. Conversely, a map which is not tight contains an unmarked vertex $v$ of degree 1. The contour of the face $f$ incident to $v$ can be deformed into a strictly shorter path by shortcutting the edge incident to $v$, meaning that $f$ is not a tight boundary.

In fact, we view the results of the present paper as a first step towards a better (in particular, bijective) understanding of the counting problem for general maps with tight boundaries and possibly with internal faces. This problem was addressed in the case of planar maps with three boundaries in [BGM22], and remains a challenge in more complex topologies.

## 1.2. Lattice count polynomials

For any choice of nonnegative integers $d_1, d_2, \dots, d_n$ not all equal to 0 and for any nonnegative integer $g$, we let $N_{g,n}(d_1, d_2, \dots, d_n)$ be the number of tight maps of genus $g$, with $n$ labeled boundaries of respective lengths $d_1, d_2, \dots, d_n$, and where each map is weighted by its inverse number of automorphisms. In fact, the latter number is always 1 as soon as $n \ge 3$, while the only tight maps with two boundaries having a non-trivial automorphism group are (genus 0) cycles of length $p \ge 2$, with automorphism group $\mathbb{Z}/p\mathbb{Z}$ (such maps are thus weighted by $1/p$). For $n=1$, the only planar ($g=0$) example of a tight map is the (marked) vertex-map, which is excluded from the discussion since its only boundary has length 0, but in higher genera, there are many tight maps with one face, and these can have a non-trivial automorphism group.
<figure><img src="image_2.png" /><figcaption>Figure 1: On the left, a tight map with 9 boundaries: six faces $f_1, f_2, f_3, f_4, f_5, f_6$ with respective degrees 12, 8, 5, 4, 3, 2, and three marked vertices $v_7, v_8, v_9$, shown in white. On the right: a rooted tight map, whose opening operation gives the tight map on the left. As this figure demonstrates, a vertex incident to the root in a rooted tight map can be of degree 1 without being necessarily marked. These maps can be also seen as pointed (respectively pointed rooted) tight maps, for example by distinguishing the marked vertex $v_9$.</figcaption></figure>

<figure><img src="image_3.png" /><figcaption>Figure 2: Blowing a boundary-vertex into a face of degree 0 with one puncture.</figcaption></figure>

into a degree-0 face, the contour of a given face is in fact the unique non-backtracking path of edges in its free homotopy class in the punctured surface $S'$. Conversely, a map which is not tight contains an unmarked vertex $v$ of degree 1. The contour of the face $f$ incident to $v$ can be deformed into a strictly shorter path by shortcutting the edge incident to $v$, meaning that $f$ is not a tight boundary.

## 1.2. Lattice count polynomials

For any choice of nonnegative integers $d_1, d_2, \dots, d_n$ not all equal to 0 and for any non-negative integer $g$, we let $N_{g,n}(d_1, d_2, \dots, d_n)$ be the number of tight maps of genus $g$,
The numbers $N_{g,n}(d_1, \dots, d_n)$ have been extensively studied in particular by Norbury and Do [Nor10, Nor13, DN11]$^1$, in the broader context of the study of invariants of spectral curves appearing in Eynard and Orantin's topological recursion [EO07]. Norbury proved that $N_{g,n}(d_1, \dots, d_n)$ is a quasi-polynomial in the variables $d_1^2, \dots, d_n^2$, depending on their parities. This means that for every $k \in \{0, 1, \dots, n\}$, there exists a polynomial $N_{g,n}^{(k)}(x_1, \dots, x_n)$ in the variables $x_1^2, \dots, x_n^2$, symmetric under permutations of the first $k$ variables and of the last $n-k$ variables, such that, if the numbers $d_1, \dots, d_k$ are odd and the numbers $d_{k+1}, \dots, d_n$ are even, then

$$N_{g,n}(d_1, \dots, d_n) = N_{g,n}^{(k)}(d_1, \dots, d_n). \qquad (1.1)$$

For $k$ odd, these polynomials are equal to 0. In fact, the first two papers mentioned above assume that $d_1, \dots, d_n$ are all non-zero, while the third paper considers the general case where some, but not all $d_i$ may vanish. Definition 2.7 in [DN11] is indeed equivalent to our definition of tight maps, while Proposition 2.8 therein proves that the extension of the quasipolynomials to some zero values do solve the enumeration problem of tight maps with marked vertices. Norbury [Nor10] also proves that evaluating the polynomials at $(0, 0, \dots, 0)$ gives interesting geometric information, although the combinatorial meaning of this evaluation is not clear. Note that the theory of enumeration of integer points in polytopes implies that $N_{g,n}(d_1, \dots, d_n)$ is a piecewise quasi-polynomial in $d_1, \dots, d_n$, see for instance the discussion around [Bud22b, Proposition 4] (in the case $b=0$). Therefore, it is surprising that $N_{g,n}(d_1, \dots, d_n)$ is actually a genuine quasi-polynomial, furthermore in the squared variables.

The approach taken in [Nor10, Nor13, DN11] is to prove the wanted properties using recursions for these polynomials, called *lattice count polynomials*, that also allows one to effectively compute them. These recursions are in turn consequences of combinatorial recursion relations with a geometric flavor, similar to Tutte's equations used for instance in [Tut62], and to the topological recursion originating in Eynard and Orantin's work [EO07].

In this paper, focusing on the planar case $g=0$, our main goal is to show how one can obtain the above quasipolynomiality results by *bijjective* techniques, which in passing yield new explicit formulas for the lattice count polynomials. We will use two different strategies: the first one, discussed in Section 3, is based on a *substitution* approach using as an input Tutte's classical *slicings formula* [Tut62]. This formula holds however only for planar maps which are *bipartite* or *quasi-bipartite*, namely with a number of faces of odd degree equal to 0 or 2 respectively. As a consequence, the substitution approach is limited to the enumeration of planar tight bipartite and quasi-bipartite maps, corresponding to respectively $k=0$ and $k=2$ in (1.1). The second, purely *bijjective*, strategy is based on the so-called *slice decomposition* of maps introduced in [BG12], and its extensions developed in [BG14, Bou19]. We will first discuss it in Section 4 in the easier case of planar tight bipartite and quasi-bipartite maps, and then extend it in Section 5 to the general case of planar tight maps with an arbitrary number $k$ of faces of odd degree. Using then the substitution approach backwards, our general expression for tight maps allows us to extend Tutte's slicings formula to non necessarily tight maps with an arbitrary number of faces of odd degree.

<footnote>$^1$Here, we should warn the reader that these references use the notion of fatgraphs, which is different but equivalent to the language of maps used in this paper.</footnote>
with $n$ labeled boundaries of respective lengths $d_1, d_2, \dots, d_n$, and where each map is weighted by its inverse number of automorphisms. In fact, the latter number is always 1 as soon as $n \ge 3$, while the only tight maps with two boundaries having a non-trivial automorphism group are (genus 0) cycles of length $p \ge 2$, with automorphism group $\mathbb{Z}/p\mathbb{Z}$ (such maps are thus weighted by $1/p$).

The numbers $N_{g,n}(d_1, \dots, d_n)$ have been extensively studied in particular by Norbury and Do [Nor10; Nor13; DN11]$^1$. Norbury proved that $N_{g,n}(d_1, \dots, d_n)$ is a quasi-polynomial in the variables $d_1^2, \dots, d_n^2$, depending on their parities. This means that for every $k \in \{0, 1, \dots, n\}$, there exists a polynomial $N_{g,n}^{(k)}(x_1, \dots, x_n)$ in the variables $x_1^2, \dots, x_n^2$, symmetric under permutations of the first $k$ variables and of the last $n-k$ variables, such that, if the numbers $d_1, \dots, d_k$ are odd and the numbers $d_{k+1}, \dots, d_n$ are even, then

$$N_{g,n}(d_1, \dots, d_n) = N_{g,n}^{(k)}(d_1, \dots, d_n). \qquad (1)$$

For $k$ odd, these polynomials are equal to 0. In fact, the first two papers mentioned above assume that $d_1, \dots, d_n$ are all non-zero, while the third paper considers the general case where some, but not all $d_i$ may vanish. Definition 2.7 in [DN11] is indeed equivalent to our definition of tight maps, while Proposition 2.8 therein proves that the extension of the quasipolynomials to some zero values do solve the enumeration problem of tight maps with marked vertices. Norbury [Nor10] also proves that evaluating the polynomials at $(0, 0, \dots, 0)$ gives interesting geometric information, although the combinatorial meaning of this evaluation is not clear. Note that the theory of enumeration of integer points in polytopes implies that $N_{g,n}(d_1, \dots, d_n)$ is a piecewise quasi-polynomial in $d_1, \dots, d_n$, see for instance the discussion around [Bud20b, Proposition 4] (in the case $b=0$). Therefore, it is surprising that $N_{g,n}(d_1, \dots, d_n)$ is actually a genuine quasi-polynomial, furthermore in the squared variables.

The approach taken in [Nor10; Nor13; DN11] is to prove the wanted properties using recursions for these polynomials, called *lattice count polynomials*, that also allows one to effectively compute them. These recursions are in turn consequences of combinatorial recursion relations with a geometric flavor, similar to Tutte's equations used for instance in [Tut62], and to the topological recursion originating in Eynard and Orantin's work [EO07].

In this paper, focusing on the planar case $g=0$, our main goal is to show how one can obtain the above quasipolynomiality results by bijective techniques, which in passing yield new explicit formulas for the lattice count polynomials. We will use two different strategies: the first one, discussed in Section 3, is based on a *substitution* approach using as an input Tutte's classical *slicings formula* [Tut62]. This formula holds however only for planar maps which are *bipartite* or *quasi-bipartite*, namely with a number of faces of odd degree equal to 0 or 2 respectively. As a consequence, the substitution approach is limited to the enumeration of planar tight bipartite and quasi-bipartite maps, corresponding to respectively $k=0$ and $k=2$ in (1). The second, purely bijective, strategy is based on the so-called *slice decomposition* of maps introduced in [BG12], and its extensions developed

<footnote>$^1$Here, we should warn the reader that these references use the notion of fatgraphs, which is different but equivalent to the language of maps used in this paper.</footnote>
The paper is organized as follows. Section 2 provides a self-contained presentation of our main results. Section 2.1 deals with the simpler case of bipartite and quasi-bipartite tight maps: after introducing and studying in Section 2.1.1 the required basic univariate and multivariable polynomials, we state our main theorems which connect these polynomials to the numbers of planar tight bipartite maps in Section 2.1.2 (Theorem 2.3) and of planar tight quasi-bipartite maps in Section 2.1.3 (Theorem 2.8). We then state our enumeration result for general tight maps in Section 2.2 (Theorem 2.12) after introducing the appropriate univariate and multivariable quasi-polynomials. Section 3 discusses the connection with the enumeration of non necessarily tight maps by the substitution approach: Section 3.1 is devoted to the derivation of Theorems 2.3 and 2.8 from Tutte's slicings formula, and Section 3.2 uses this approach backwards to obtain from Theorem 2.12 an extension of the slicings formula to maps with an arbitrary number of faces of odd degree, see Theorem 3.2. We then discuss in Sections 4 and 5 the bijective approach based on the slice decomposition of maps. Section 4 concentrates again on the simpler bipartite and quasi-bipartite cases, discussing first tight maps with a single face (Section 4.1), tight maps with two faces (Section 4.2), pointed rooted tight maps in connection with tight slices (Section 4.3) and finally tight maps which are neither pointed nor rooted (Section 4.4) using the slice decomposition of annular maps. All these bijective results are then extended to the non-bipartite or quasi-bipartite case in Section 5, which requires the preliminary enumeration of so-called petal trees (Section 5.1), petal necklaces (Section 5.2) and non-bipartite slices (Section 5.3). Our most general enumeration result for planar tight maps with arbitrary prescribed boundary lengths is given in Section 5.4 by Theorem 5.13, which presents a single formula encompassing Theorems 2.3, 2.8 and 2.12. We gather our concluding remarks in Section 6, while a few appendices detail the derivation of some technical results.

## 2. Main results

### 2.1. Polynomials counting planar tight bipartite or quasi-bipartite maps

In this section, we provide explicit expressions for the lattice count polynomials $N_{0,n}^{(0)}$ and $N_{0,n}^{(2)}$, which correspond to planar tight bipartite and quasi-bipartite maps, respectively.

#### 2.1.1 Definition and properties of the polynomials

Let us start by introducing families of polynomials which appear in the explicit expression of $N_{0,n}^{(0)}$. Here, we concentrate on the very definitions of these polynomials and on their resulting algebraic properties. The connection with tight map enumeration will be discussed in Section 2.1.2.
in [BG14; Bou19]. We will first discuss it in Section 4 in the easier case of planar tight bipartite and quasi-bipartite maps, and then extend it in Section 5 to the general case of planar tight maps with an arbitrary number $k$ of faces of odd degree. Using then the substitution approach backwards, our general expression for tight maps allows us to extend Tutte's slicings formula to non necessarily tight maps with an arbitrary number of faces of odd degree.

The paper is organized as follows. Section 2 provides a self-contained presentation of our main results. Section 2.1 deals with the simpler case of bipartite and quasi-bipartite tight maps: after introducing and studying in Section 2.1.1 the required basic univariate and multivariable polynomials, we state our main theorems which connect these polynomials to the numbers of planar tight bipartite maps in Section 2.1.2 (Theorem 4) and of planar tight quasi-bipartite maps in Section 2.1.3 (Theorem 9). We then state our enumeration result for general tight maps in Section 2.2 (Theorem 13) after introducing the appropriate univariate and multivariable quasi-polynomials. Section 3 discusses the connection with the enumeration of non necessarily tight maps by the substitution approach: Section 3.1 is devoted to the derivation of Theorems 4 and 9 from Tutte's slicings formula, and Section 3.2 uses this approach backwards to obtain from Theorem 13 an extension of the slicings formula to maps with an arbitrary number of faces of odd degree, see Theorem 19. We then discuss in Sections 4 and 5 the bijective approach based on the slice decomposition of maps. Section 4 concentrates again on the simpler bipartite and quasi-bipartite cases, discussing first tight maps with a single face (Section 4.1), tight maps with two faces (Section 4.2), pointed rooted tight maps in connection with tight slices (Section 4.3) and finally tight maps which are neither pointed nor rooted (Section 4.4) using the slice decomposition of annular maps. All these bijective results are then extended to the non-bipartite or quasi-bipartite case in Section 5, which requires the preliminary enumeration of so-called petal trees (Section 5.1), petal necklaces (Section 5.2) and non-bipartite slices (Section 5.3). Our most general enumeration result for planar tight maps with arbitrary prescribed boundary lengths is given in Section 5.4 by Theorem 42, which presents a single formula encompassing Theorems 4, 9 and 13. We gather our concluding remarks in Section 6, while a few appendices detail the derivation of some technical results.

**Acknowledgments.** We thank Axel Bacher and Gilles Schaeffer for valuable discussions. JB acknowledges the hospitality of the Laboratoire de Physique, ENS de Lyon, and partial financial support from the Agence Nationale de la Recherche via the grants ANR-18-CE40-0033 “Dimers” and ANR-19-CE48-0011 “Combiné”.

## 2. Main results

### 2.1. Polynomials counting planar tight bipartite or quasi-bipartite maps

In this section, we provide explicit expressions for the lattice count polynomials $N_{0,n}^{(0)}$ and $N_{0,n}^{(2)}$, which correspond to planar tight bipartite and quasi-bipartite maps, respectively.
**Basic univariate polynomials.** Our first basic polynomials are functions of a single variable $m$ and are defined as follows: for any integer $k \ge 0$, we set

$$ 
\begin{aligned}
p_k(m) &:= \frac{1}{(k!)^2} \prod_{i=1}^{k} (m^2 - i^2) = \binom{m-1}{k} \binom{m+k}{k} \\
q_k(m) &:= \frac{1}{(k!)^2} \prod_{i=0}^{k-1} (m^2 - i^2) = \binom{m}{k} \binom{m+k-1}{k}
\end{aligned} 
\quad (2.1) $$

with the usual convention $p_0(m) = q_0(m) = 1$ for the empty product, and with $\binom{x}{k} = x(x - 1)\cdots(x - k + 1)/k!$ viewed as a polynomial in $x$.

Clearly, $p_k$ and $q_k$ are polynomials of degree $k$ in the variable $m^2$, and $p_k(m)$ and $q_k(m)$ are integers if $m$ is an integer. The two families of polynomials are linked by the relation

$$ q_k(m) = p_k(m) + p_{k-1}(m), \quad k \ge 0 \quad (2.2) $$

with the convention $p_{-1} := 0$. A combinatorial interpretation of this relation based on the enumeration of tight maps with a single face will be given in Section 2.1.2. We also record the identities

$$ (k+1)p_{k+1}(m) = (m-k-1)p_k(m) + \sum_{j=1}^{m-1} (2j)p_k(j) \quad (2.3) $$

$$ (k+1)q_{k+1}(m) = (m-k)q_k(m) + \sum_{j=1}^{m-1} (2j)q_k(j) \quad (2.4) $$

which are valid for $m$ a positive integer, and which may be checked by induction.

**Multivariate polynomials.** The above univariate polynomials may be extended to multivariate polynomials, functions of $n$ variables $m_1, m_2, \dots, m_n$ as follows: for any integer $k \ge 0$ and any integer $n \ge 1$, we set

$$ 
\begin{aligned}
p_k(m_1, m_2, \dots, m_n) &:= \sum_{\substack{k_1, k_2, \dots, k_n \ge 0 \\ k_1 + k_2 + \dots + k_n = k}} p_{k_1}(m_1) q_{k_2}(m_2) \cdots q_{k_n}(m_n), \\
q_k(m_1, m_2, \dots, m_n) &:= \sum_{\substack{k_1, k_2, \dots, k_n \ge 0 \\ k_1 + k_2 + \dots + k_n = k}} q_{k_1}(m_1) q_{k_2}(m_2) \cdots q_{k_n}(m_n).
\end{aligned} 
\quad (2.5) $$

(In the right-hand side of the first line, all factors except the first one are $q_{k_i}$'s.)

Clearly, $p_k$ and $q_k$ are polynomials of degree $k$ in the variables $m_1^2, m_2^2, \dots, m_n^2$. Note that the notation is consistent for $n = 1$ with (2.1). From the identity $p_k(1) = \delta_{k,0}$, we get the identification:

$$ p_k(1, m_1, m_2, \dots, m_n) = q_k(m_1, m_2, \dots, m_n) \quad (2.6) $$

and, by (2.2), we find that $q_k = p_k + p_{k-1}$ for any number of variables.
### 2.1.1. Definition and properties of the polynomials

Let us start by introducing families of polynomials which appear in the explicit expression of $N_{0,n}^{(0)}$. Here, we concentrate on the very definitions of these polynomials and on their resulting algebraic properties. The connection with tight map enumeration will be discussed in Section 2.1.2.

**Basic univariate polynomials.** Our first basic polynomials are functions of a single variable $m$ and are defined as follows: for any integer $k \ge 0$, we set

$$ 
\begin{aligned}
p_k(m) &:= \frac{1}{(k!)^2} \prod_{i=1}^{k} (m^2 - i^2) = \binom{m-1}{k} \binom{m+k}{k} \\
q_k(m) &:= \frac{1}{(k!)^2} \prod_{i=0}^{k-1} (m^2 - i^2) = \binom{m}{k} \binom{m+k-1}{k}
\end{aligned} 
\quad (2) $$

with the usual convention $p_0(m) = q_0(m) = 1$ for the empty product, and with $\binom{x}{k} = x(x-1)\cdots(x-k+1)/k!$ viewed as a polynomial in $x$.

Clearly, $p_k$ and $q_k$ are polynomials of degree $k$ in the variable $m^2$, and $p_k(m)$ and $q_k(m)$ are integers if $m$ is an integer. The two families of polynomials are linked by the relation

$$ q_k(m) = p_k(m) + p_{k-1}(m), \quad k \ge 0 \quad (3) $$

with the convention $p_{-1} := 0$. A combinatorial interpretation of this relation based on the enumeration of tight maps with a single face will be given in Section 2.1.2. We also record the identities

$$ (k+1)p_{k+1}(m) = (m-k-1)p_k(m) + \sum_{j=1}^{m-1} (2j)p_k(j) \quad (4) $$

$$ (k+1)q_{k+1}(m) = (m-k)q_k(m) + \sum_{j=1}^{m-1} (2j)q_k(j) \quad (5) $$

which are valid for $m$ a positive integer, and which may be checked by induction.

**Multivariate polynomials.** The above univariate polynomials may be extended to multivariate polynomials, functions of $n$ variables $m_1, m_2, \dots, m_n$ as follows: for any integer $k \ge 0$ and any integer $n \ge 1$, we set

$$ 
\begin{aligned}
p_k(m_1, m_2, \dots, m_n) &:= \sum_{\substack{k_1, k_2, \dots, k_n \ge 0 \\ k_1 + k_2 + \dots + k_n = k}} p_{k_1}(m_1) q_{k_2}(m_2) \cdots q_{k_n}(m_n), \\
q_k(m_1, m_2, \dots, m_n) &:= \sum_{\substack{k_1, k_2, \dots, k_n \ge 0 \\ k_1 + k_2 + \dots + k_n = k}} q_{k_1}(m_1) q_{k_2}(m_2) \cdots q_{k_n}(m_n).
\end{aligned} 
\quad (6) $$

(In the right-hand side of the first line, all factors except the first one are $q_{k_i}$'s.)
For bookkeeping purposes, let us record the explicit expressions of $p_k$ and $q_k$ for $k = 1, 2, 3$:

$$
\begin{align}
p_1(m_1, \dots, m_n) &= \left( \sum_{i=1}^{n} m_i^2 \right) - 1, \nonumber \\
p_2(m_1, \dots, m_n) &= \frac{1}{4} \left( \sum_{i=1}^{n} m_i^4 \right) + \sum_{i<j} m_i^2 m_j^2 - \frac{5}{4} \left( \sum_{i=1}^{n} m_i^2 \right) + 1, \nonumber \\
p_3(m_1, \dots, m_n) &= \frac{1}{36} \left( \sum_{i=1}^{n} m_i^6 \right) + \frac{1}{4} \left( \sum_{i \neq j} m_i^4 m_j^2 \right) + \sum_{i<j<h} m_i^2 m_j^2 m_h^2 \nonumber \\
&\quad - \frac{7}{18} \left( \sum_{i=1}^{n} m_i^4 \right) - \frac{3}{2} \left( \sum_{i<j} m_i^2 m_j^2 \right) + \frac{49}{36} \left( \sum_{i=1}^{n} m_i^2 \right) - 1, \tag{2.7} \\
q_1(m_1, \dots, m_n) &= \sum_{i=1}^{n} m_i^2, \nonumber \\
q_2(m_1, \dots, m_n) &= \frac{1}{4} \left( \sum_{i=1}^{n} m_i^4 \right) + \sum_{i<j} m_i^2 m_j^2 - \frac{1}{4} \left( \sum_{i=1}^{n} m_i^2 \right), \nonumber \\
q_3(m_1, \dots, m_n) &= \frac{1}{36} \left( \sum_{i=1}^{n} m_i^6 \right) + \frac{1}{4} \left( \sum_{i \neq j} m_i^4 m_j^2 \right) + \sum_{i<j<h} m_i^2 m_j^2 m_h^2 \nonumber \\
&\quad - \frac{5}{36} \left( \sum_{i=1}^{n} m_i^4 \right) - \frac{1}{2} \left( \sum_{i<j} m_i^2 m_j^2 \right) + \frac{1}{9} \left( \sum_{i=1}^{n} m_i^2 \right). \nonumber
\end{align}
$$

**Proposition 2.1.** For any integer $k \ge 0$, $p_k$ and $q_k$ are symmetric functions. In other words, for any integer $n \ge 1$, $p_k(m_1, m_2, \dots, m_n)$ and $q_k(m_1, m_2, \dots, m_n)$ are symmetric polynomials in $m_1, m_2, \dots, m_n$ which satisfy the consistency relation

$$
\begin{align}
p_k(m_1, m_2, \dots, m_n, 0) &= p_k(m_1, m_2, \dots, m_n), \tag{2.8} \\
q_k(m_1, m_2, \dots, m_n, 0) &= q_k(m_1, m_2, \dots, m_n). \nonumber
\end{align}
$$

*Proof.* The symmetry of $q_k(m_1, m_2, \dots, m_n)$ is apparent from its very definition in (2.5). As for $p_k(m_1, m_2, \dots, m_n)$, its symmetry is also made apparent from the following alternative and manifestly symmetric expression:

$$
p_k(m_1, m_2, \dots, m_n) = \sum_{\substack{k_0, k_1, k_2, \dots, k_n \ge 0 \\ k_0 + k_1 + k_2 + \dots + k_n = k}} \binom{n-1}{k_0} p_{k_1}(m_1) p_{k_2}(m_2) \cdots p_{k_n}(m_n). \quad (2.9)
$$

To get this latter expression, we use again the relation (2.2) to write, in the expression (2.5) for $p_k(m_1, m_2, \dots, m_n)$, each $q_{k_i}$ for $i=2$ to $n$ as the sum of $p_{k_i}$ and $p_{k_i-1}$ and distribute the two terms in the product so as to get a sum of terms of the form $p_{k'_1}(m_1)p_{k'_2}(m_2)\cdots p_{k'_n}(m_n)$ with summation variables $k'_1 = k_1$ and $k'_i = k_i$ or $k_i-1$ for $i \ge 2$. The number of terms in the sum having exactly $k_0$ indices $i$ for which $k'_i = k_i-1$ is $\binom{n-1}{k_0}$ and, for such terms, the sum rule
Clearly, $p_k$ and $q_k$ are polynomials of degree $k$ in the variables $m_1^2, m_2^2, \dots, m_n^2$. Note that the notation is consistent for $n = 1$ with (2). From the identity $p_k(1) = \delta_{k,0}$, we get the identification:

$$p_k(1, m_1, m_2, \dots, m_n) = q_k(m_1, m_2, \dots, m_n) \qquad (7)$$

and, by (3), we find that $q_k = p_k + p_{k-1}$ for any number of variables.

**Proposition 2.** For any integer $k \ge 0$, $p_k$ and $q_k$ are symmetric functions. In other words, for any integer $n \ge 1$, $p_k(m_1, m_2, \dots, m_n)$ and $q_k(m_1, m_2, \dots, m_n)$ are symmetric polynomials in $m_1, m_2, \dots, m_n$ which satisfy the consistency relation

$$ \begin{aligned} p_k(m_1, m_2, \dots, m_n, 0) &= p_k(m_1, m_2, \dots, m_n), \\ q_k(m_1, m_2, \dots, m_n, 0) &= q_k(m_1, m_2, \dots, m_n). \end{aligned} \qquad (8) $$

*Proof.* The symmetry of $q_k(m_1, m_2, \dots, m_n)$ is apparent from its very definition in (6). As for $p_k(m_1, m_2, \dots, m_n)$, its symmetry is also made apparent from the following alternative and manifestly symmetric expression:

$$ p_k(m_1, m_2, \dots, m_n) = \sum_{\substack{k_0, k_1, k_2, \dots, k_n \ge 0 \\ k_0 + k_1 + k_2 + \dots + k_n = k}} \binom{n-1}{k_0} p_{k_1}(m_1) p_{k_2}(m_2) \cdots p_{k_n}(m_n). \qquad (9) $$

To get this latter expression, we use again the relation (3) to write, in the expression (6) for $p_k(m_1, m_2, \dots, m_n)$, each $q_{k_i}$ for $i = 2$ to $n$ as the sum of $p_{k_i}$ and $p_{k_i-1}$ and distribute the two terms in the product so as to get a sum of terms of the form $p_{k'_1}(m_1)p_{k'_2}(m_2) \cdots p_{k'_n}(m_n)$ with summation variables $k'_1 = k_1$ and $k'_i = k_i$ or $k_i - 1$ for $i \ge 2$. The number of terms in the sum having exactly $k_0$ indices $i$ for which $k'_i = k_i - 1$ is $\binom{n-1}{k_0}$ and, for such terms, the sum rule $k_1 + k_2 + \dots + k_n = n$ in (6) becomes $k_0 + k'_1 + k'_2 + \dots + k'_n = n$. This leads to (9) upon renaming the summation variable $k'_i$ as $k_i$.

As for the consistency relation (8), it is a direct consequence of the identity $q_k(0) = \delta_{k,0}$ (here and in the following, we will always implicitly assume that $k$ is a non-negative integer). $\square$

Finally, let us state some recursion relations obeyed by the $p_k$'s, which we call the dilaton and string equations as we shall see later that they correspond to the recursions obtained in [Nor13] in the bipartite case.

**Proposition 3 (Dilaton and string equations).** We have the dilaton equation

$$ p_k(m_1, \dots, m_n, 1) - p_k(m_1, \dots, m_n, 0) = p_{k-1}(m_1, \dots, m_n) \qquad (10) $$

and the string equation, valid for non-negative integer $m_1, \dots, m_n$:

$$ (k+1)p_{k+1}(m_1, \dots, m_n) = (m_1 + \dots + m_n - k - 1)p_k(m_1, \dots, m_n) + \sum_{i=1}^{n} \sum_{j=1}^{m_i-1} (2j)p_k(m_1, \dots, m_{i-1}, j, m_{i+1}, \dots, m_n) \qquad (11) $$
$k_1 + k_2 + \dots + k_n = n$ in (2.5) becomes $k_0 + k'_1 + k'_2 + \dots + k'_n = n$. This leads to (2.9) upon renaming the summation variable $k'_i$ as $k_i$.

As for the consistency relation (2.8), it is a direct consequence of the identity $q_k(0) = \delta_{k,0}$ (here and in the following, we will always implicitly assume that $k$ is a non-negative integer). $\square$

Finally, let us state some recursion relations obeyed by the $p_k$'s, which we call the dilaton and string equations as we shall see later that they correspond to the recursions obtained in [Nor13] in the bipartite case.

**Proposition 2.2 (Dilaton and string equations).** We have the dilaton equation

$$p_k(m_1, \dots, m_n, 1) - p_k(m_1, \dots, m_n, 0) = p_{k-1}(m_1, \dots, m_n) \quad (2.10)$$

and the string equation, valid for non-negative integer $m_1, \dots, m_n$:

$$(k+1)p_{k+1}(m_1, \dots, m_n) = (m_1 + \dots + m_n - k - 1)p_k(m_1, \dots, m_n) + \sum_{i=1}^{n} \sum_{j=1}^{m_i-1} (2j)p_k(m_1, \dots, m_{i-1}, j, m_{i+1}, \dots, m_n) \quad (2.11)$$

*Proof.* From (2.6) and Proposition 2.1, the dilaton equation boils down to the relation $q_k = p_k + p_{k-1}$ noted above. The string equation is nothing but the multivariate extension of (2.3), and is obtained by a linear combination of it and (2.4) (precisely, we take (2.3) at $k = k_1$ and $m = m_1$ times $q_{k_2}(m_2) \cdots q_{k_n}(m_n)$ and add, for $i = 2, \dots, n$, the relation (2.4) at $k = k_i$ and $m = m_i$ times $p_{k_1}(m_1) \cdots p_{k_n}(m_n)$ with the factor $q_{k_i}(m_i)$ omitted). $\square$

### 2.1.2 Enumeration results in the bipartite case

We are now ready to state our first enumerative result:

**Theorem 2.3.** For $n \ge 3$ and for non-negative integers $m_1, m_2, \dots, m_n$ not all equal to zero, the number $N_{0,n}(2m_1, 2m_2, \dots, 2m_n)$ of planar tight bipartite maps with $n$ boundaries labeled from 1 to $n$ with respective lengths $2m_1, 2m_2, \dots, 2m_n$ is given by the polynomial

$$N_{0,n}^{(0)}(2m_1, 2m_2, \dots, 2m_n) = (n-3)! p_{n-3}(m_1, m_2, \dots, m_n). \quad (2.12)$$

For $n = 4, 5, 6$, the expression for $N_{0,n}^{(0)}$ that we obtain from (2.7) is in agreement with the polynomials given in [Bud22b, Table 1] for $g = 0$ and $b = 0$, as expected. Note that the constant term of $N_{0,n}^{(0)}$, obtained by setting all the $m_i$'s to zero, is equal to $(n-3)!p_{n-3}(0, \dots, 0) = (-1)^{n-3}(n-3)!$, and this quantity was interpreted in [Nor10] as the orbifold Euler characteristic of the moduli space $M_{0,n}$.

By combining Proposition 2.2 with Theorem 2.3, we recover the string and dilaton equations found by Norbury in [Nor10] in the planar bipartite case. Note that, in this reference, the string equation corresponds to the addition of a face of degree 2, while (2.11) for $k = n - 3$ may be interpreted as the addition of a vertex. Norbury's original equation can however be recovered by combining it with the dilaton equation. Note finally that Proposition 2.2 holds more generally
Proof. From (7) and Proposition 2, the dilaton equation boils down to the relation $q_k = p_k + p_{k-1}$ noted above. The string equation is nothing but the multivariate extension of (4), and is obtained by a linear combination of it and (5) (precisely, we take (4) at $k = k_1$ and $m = m_1$ times $q_{k_2}(m_2) \cdots q_{k_n}(m_n)$ and add, for $i = 2, \dots, n$, the relation (5) at $k = k_i$ and $m = m_i$ times $p_{k_1}(m_1) \cdots p_{k_n}(m_n)$ with the factor $q_{k_i}(m_i)$ omitted). $\square$

### 2.1.2. Enumeration results in the bipartite case

We are now ready to state our first enumerative result:

**Theorem 4.** For $n \ge 3$ and for non-negative integers $m_1, m_2, \dots, m_n$ not all equal to zero, the number $N_{0,n}(2m_1, 2m_2, \dots, 2m_n)$ of planar tight bipartite maps with $n$ boundaries labeled from 1 to $n$ with respective lengths $2m_1, 2m_2, \dots, 2m_n$ is given by the polynomial

$$ N_{0,n}^{(0)}(2m_1, 2m_2, \dots, 2m_n) = (n-3)! p_{n-3}(m_1, m_2, \dots, m_n). \quad (12) $$

Note that the constant term of $N_{0,n}^{(0)}$, obtained by setting all the $m_i$'s to zero, is equal to $(n-3)!p_{n-3}(0, \dots, 0) = (-1)^{n-3}(n-3)!$, and this quantity was interpreted in [Nor10] as the orbifold Euler characteristic of the moduli space $M_{0,n}$.

By combining Proposition 3 with Theorem 4, we recover the string and dilaton equations found by Norbury in [Nor10] in the planar bipartite case. Note that, in this reference, the string equation corresponds to the addition of a face of degree 2, while (11) for $k = n - 3$ may be interpreted as the addition of a vertex. Norbury's original equation can however be recovered by combining it with the dilaton equation. Note finally that Proposition 3 holds more generally for any $k$. When $k \ge n - 3$ we can naturally interpret it in terms of adding new marked vertices, but the combinatorial meaning of the polynomial $p_k(m_1, \dots, m_n)$ for $k < n - 3$ is more elusive.

A first derivation of Equation (12) will be presented in Section 3 below by showing that, up to some appropriate transformation accounting for the tight nature of the maps, it is actually equivalent to Tutte's celebrated slicings enumeration formula [Tut62]. We shall then present in Section 4 a direct bijective proof of Theorem 4 upon using some canonical *slice decomposition* of the maps at hand [BG12; BG14; Bou19]. As it appears, it will be convenient for that purpose to proceed gradually and first derive (12) for a number a specialized cases before addressing the result in all generality. Let us now start by discussing these specializations.

**Maps with one face.** Taking $n = k + 3$ in (12) with $m_1 = m \ne 0$ and $m_2 = \dots = m_{k+3} = 0$, we get

$$ N_{0,k+3}(2m, \underbrace{0, \dots, 0}_{k+2}) = k! p_k(m, \underbrace{0, \dots, 0}_{k+2}) = k! p_k(m), \quad k \ge 0. \quad (13) $$

Upon dividing by $k!$, which amounts to considering that all but two of the marked vertices are unlabeled, we obtain the following combinatorial interpretation of $p_k(m)$:
for any $k$. When $k \ge n-3$ we can naturally interpret it in terms of adding new marked vertices, but the combinatorial meaning of the polynomial $p_k(m_1, \dots, m_n)$ for $k < n-3$ is more elusive.

A first derivation of Equation (2.12) will be presented in Section 3 below by showing that, up to some appropriate transformation accounting for the tight nature of the maps, it is actually equivalent to Tutte's celebrated slicings enumeration formula [Tut62]. We shall then present in Section 4 a direct bijective proof of Theorem 2.3 upon using some canonical *slice decomposition* of the maps at hand [BG12, BG14, Bou19]. As it appears, it will be convenient for that purpose to proceed gradually and first derive (2.12) for a number of specialized cases (Propositions 2.4, 2.5, 2.6 and 2.7 below) before addressing the result in all generality.

**Maps with one face.** Taking $n = k+3$ in (2.12) with $m_1 = m \ne 0$ and $m_2 = \dots = m_{k+3} = 0$, we get

$$N_{0,k+3}(2m, \underbrace{0, \dots, 0}_{k+2}) = k! p_k(m, \underbrace{0, \dots, 0}_{k+2}) = k! p_k(m), \quad k \ge 0, \quad (2.13)$$

which already appeared in [Nor13, Corollary 5.6]$^2$. Upon dividing by $k!$, which amounts to considering that all but two of the marked vertices are unlabeled, we obtain the following combinatorial interpretation of $p_k(m)$:

**Proposition 2.4.** For $k \ge 0$ and $m \ge 1$, $p_k(m)$ is the number of planar tight bipartite maps with one face of degree $2m$ and $k+2$ distinct marked vertices, two of them distinguished and labeled, say as vertex 1 and vertex 2, and the remaining $k$ unlabeled.

Note that a planar map with a single face of degree $2m$ is nothing but a plane tree with $m$ edges. It is tight if and only if all its leaves are marked.

Similarly, taking $n = k+3$ in (2.12) with $m_1 = m$ and $m_2 = 1$ and $m_3 = \dots = m_{k+3} = 0$, we now get

$$N_{0,k+3}(2m, 2, \underbrace{0, \dots, 0}_{k+1}) = k! p_k(m, 1, \underbrace{0, \dots, 0}_{k+1}) = k! q_k(m, \underbrace{0, \dots, 0}_{k+1}) = k! q_k(m), \quad (2.14)$$

where we used (2.6) (and the symmetry in exchanging the variables) to switch from $p_k$ to $q_k$. Dividing by $k!$ and viewing the face of degree 2 as a split root edge, as discussed in the introduction, we obtain a combinatorial interpretation of $q_k(m)$:

**Proposition 2.5.** For $k \ge 0$ and $m \ge 1$, $q_k(m)$ is the number of pointed rooted planar tight bipartite maps with one face of degree $2m$ and $k$ additional unlabeled marked vertices (distinct from each other and from the pointed vertex).

Proofs of Propositions 2.4 and 2.5 will be presented in Section 4.1 by a direct enumeration of the trees at hand. From the above interpretations of $p_k(m)$ and $q_k(m)$, we may now understand the identity (2.2), for integer values of $m$, in a combinatorial way using the map language. Indeed, for each tree enumerated by $q_k(m)$, we may transfer the marking of its root edge into a

<footnote>$^2$Incidentally, we note that our main results (Theorems 2.3, 2.8 and 2.12) answer the question raised in the paragraph just before this corollary about finding a general formula for $N_{0,n}$.</footnote>
**Proposition 5.** For $k \ge 0$ and $m \ge 1$, $p_k(m)$ is the number of planar tight bipartite maps with one face of degree $2m$ and $k + 2$ distinct marked vertices, two of them distinguished and labeled, say as vertex 1 and vertex 2, and the remaining $k$ unlabeled.

Note that a planar map with a single face of degree $2m$ is nothing but a plane tree with $m$ edges. It is tight if and only if all its leaves are marked.

Similarly, taking $n = k+3$ in (12) with $m_1 = m$ and $m_2 = 1$ and $m_3 = \cdots = m_{k+3} = 0$, we now get

$$N_{0,k+3}(2m, 2, \underbrace{0, \dots, 0}_{k+1}) = k! p_k(m, 1, \underbrace{0, \dots, 0}_{k+1}) = k! q_k(m, \underbrace{0, \dots, 0}_{k+1}) = k! q_k(m), \quad (14)$$

where we used (7) (and the symmetry in exchanging the variables) to switch from $p_k$ to $q_k$. Dividing by $k!$ and viewing the face of degree 2 as a split root edge, as discussed in the introduction, we obtain a combinatorial interpretation of $q_k(m)$:

**Proposition 6.** For $k \ge 0$ and $m \ge 1$, $q_k(m)$ is the number of pointed rooted planar tight bipartite maps with one face of degree $2m$ and $k$ additional unlabeled marked vertices (distinct from each other and from the pointed vertex).

Proofs of Propositions 5 and 6 will be presented in Section 4.1 by a direct enumeration of the trees at hand. From the above interpretations of $p_k(m)$ and $q_k(m)$, we may now understand the identity (3), for integer values of $m$, in a combinatorial way using the map language. Indeed, for each tree enumerated by $q_k(m)$, we may transfer the marking of its root edge into a marking of that of its endpoints further away from the pointed vertex. Let us for clarity label the newly marked vertex as vertex 2 and the pointed vertex as vertex 1. Note that vertices 1 and 2 are necessarily distinct by construction, but that the vertex 2 may very well coincide with one of the $k$ additional marked vertices in the map enumerated by $q_k(m)$. The marking transformation is clearly reversible, the root edge being recovered as the only edge incident to vertex 2 that belongs to the branch from vertex 2 to vertex 1. We may thus interpret $q_k(m)$ as counting plane trees with $m$ edges, and with two distinct marked vertices 1 and 2 and $k$ other marked vertices distinct from each other and from the vertex 1. This yields a map enumerated by $p_k(m)$ when none of the $k$ marked vertices coincide with the vertex 2—note that this may happen even if the vertex 2 is a leaf since, as an endpoint of the root edge, it needs not being marked in the map enumerated by $q_k(m)$. Otherwise, it yields a map enumerated by $p_{k-1}(m)$ by ignoring the “redundant” additional marking of vertex 2. This yields the desired relation (3).

**Maps with two faces.** Taking $n = k + 3$ in (12) with $m_1, m_2 \ge 1$ and $m_3 = \cdots = m_{k+3} = 0$, we get

$$N_{0,k+3}(2m_1, 2m_2, \underbrace{0, \dots, 0}_{k+1}) = k! p_k(m_1, m_2, \underbrace{0, \dots, 0}_{k+1}) = k! p_k(m_1, m_2). \quad (15)$$

Upon dividing by $k!$ we get a combinatorial interpretation of $p_k(m_1, m_2)$:
marking of that of its endpoints further away from the pointed vertex. Let us for clarity label the newly marked vertex as vertex 2 and the pointed vertex as vertex 1. Note that vertices 1 and 2 are necessarily distinct by construction, but that the vertex 2 may very well coincide with one of the k additional marked vertices in the map enumerated by $q_k(m)$. The marking transformation is clearly reversible, the root edge being recovered as the only edge incident to vertex 2 that belongs to the branch (that is, the unique simple path) from vertex 2 to vertex 1. We may thus interpret $q_k(m)$ as counting plane trees with m edges, and with two distinct marked vertices 1 and 2 and k other marked vertices distinct from each other and from the vertex 1. This yields a map enumerated by $p_k(m)$ when none of the k marked vertices coincide with the vertex 2—note that this may happen even if the vertex 2 is a leaf since, as an endpoint of the root edge, it needs not being marked in the map enumerated by $q_k(m)$. Otherwise, it yields a map enumerated by $p_{k-1}(m)$ by ignoring the “redundant” additional marking of vertex 2. This yields the desired relation (2.2).

**Maps with two faces.** Taking $n = k+3$ in (2.12) with $m_1, m_2 \ge 1$ and $m_3 = \cdots = m_{k+3} = 0$, we get

$$N_{0,k+3}(2m_1, 2m_2, \underbrace{0, \dots, 0}_{k+1}) = k! p_k(m_1, m_2, \underbrace{0, \dots, 0}_{k+1}) = k! p_k(m_1, m_2). \quad (2.15)$$

Upon dividing by $k!$ we get a combinatorial interpretation of $p_k(m_1, m_2)$:

**Proposition 2.6.** For $k \ge 0$ and $m_1, m_2 \ge 1$, $p_k(m_1, m_2)$ is the number of planar tight bipartite maps with two faces of respective degrees $2m_1, 2m_2$ and $k+1$ distinct marked vertices, one of them distinguished and labeled, say as vertex 1, and the remaining $k$ unlabeled.

A direct bijective proof of this proposition will be presented in Section 4.2. More generally, and although we will not use it in our bijective proof in Section 4, we note the relation, valid for integers $m_1, m_2, m_3$ not all equal to 0

$$N_{0,k+3}(2m_1, 2m_2, 2m_3, \underbrace{0, \dots, 0}_{k}) = k! p_k(m_1, m_2, m_3) \quad (2.16)$$

so that $p_k(m_1, m_2, m_3)$ counts planar tight bipartite maps with three labeled boundaries with lengths $2m_1, 2m_2, 2m_3$ and $k$ unlabeled marked vertices. It is relatively straightforward to adapt the bijective proof of Proposition 2.6 to prove (2.16) directly, we leave it as an exercise to the reader.

**Pointed rooted maps.** Taking (2.12) with $n \to n+2$ and specializing to $m_{n+1} = 2$ and $m_{n+2} = 0$, we get:

**Proposition 2.7.** For $n \ge 1$, the number of pointed rooted planar tight bipartite maps with $n$ labeled boundaries of respective lengths $2m_1, \dots, 2m_n$ (in addition to the marked vertex and to the root edge) is given by

$$N_{0,n+2}^{(0)}(2m_1, 2m_2, \dots, 2m_n, 2, 0) = (n-1)! q_{n-1}(m_1, m_2, \dots, m_n). \quad (2.17)$$
**Proposition 7.** For $k \ge 0$ and $m_1, m_2 \ge 1$, $p_k(m_1, m_2)$ is the number of planar tight bipartite maps with two faces of respective degrees $2m_1, 2m_2$ and $k+1$ distinct marked vertices, one of them distinguished and labeled, say as vertex 1, and the remaining $k$ unlabeled.

A direct bijective proof of this proposition will be presented in Section 4.2. More generally, and although we will not use it in our bijective proof in Section 4, we note the relation, valid for integers $m_1, m_2, m_3$ not all equal to 0

$$N_{0,k+3}(2m_1, 2m_2, 2m_3, \underbrace{0, \dots, 0}_{k}) = k! p_k(m_1, m_2, m_3) \quad (16)$$

so that $p_k(m_1, m_2, m_3)$ counts planar tight bipartite maps with three labeled boundaries with lengths $2m_1, 2m_2, 2m_3$ and $k$ unlabeled marked vertices. It is relatively straightforward to adapt the bijective proof of Proposition 7 to prove (16) directly, we leave it as an exercise to the reader.

**Pointed rooted maps.** Taking (12) with $n \to n+2$ and specializing to $m_{n+1} = 2$ and $m_{n+2} = 0$, we get:

**Proposition 8.** For $n \ge 1$, the number of pointed rooted planar tight bipartite maps with $n$ labeled boundaries of respective lengths $2m_1, \dots, 2m_n$ (in addition to the marked vertex and to the root edge) is given by

$$N_{0,n+2}^{(0)}, (2m_1, 2m_2, \dots, 2m_n, 2, 0) = (n-1)! q_{n-1}(m_1, m_2, \dots, m_n). \quad (17)$$

*Proof.* This is a direct application of formula (12), together with the identity $p_{n-1}(m_1, m_2, \dots, m_n, 1, 0) = q_{n-1}(m_1, m_2, \dots, m_n)$ from (7). $\square$

The expression (17) will be proved bijectively in Section 4.3 by a direct decomposition of the maps into slices.

### 2.1.3. Enumeration results in the quasi-bipartite case

Recall that a planar quasi-bipartite map is a planar map whose all faces but two have even degree. To give the explicit expression of the corresponding lattice count polynomial $N_{0,n}^{(2)}$, we need to introduce the following new family of univariate polynomials: for any integer $k \ge 0$, we set

$$\tilde{p}_k(m) := \frac{1}{(k!)^2} \prod_{i=1}^{k} \left( m^2 - \left( i - \frac{1}{2} \right)^2 \right) = \binom{m - \frac{1}{2}}{k} \binom{m + k - \frac{1}{2}}{k} \quad (18)$$

with the convention $\tilde{p}_0(m) = 1$. Note that $\tilde{p}_k$ is again a polynomial of degree $k$ in $m^2$ and that $\tilde{p}_k(m)$ is an integer if $m$ is a half-integer. It satisfies the following counterpart of (4)

$$(k+1)\tilde{p}_{k+1}(m) = (m - k - \frac{1}{2})\tilde{p}_k(m) + \sum_{0 < j < m} (2j)\tilde{p}_k(j) \quad (19)$$
Proof. This is a direct application of formula (2.12), together with the identity $p_{n-1}(m_1, m_2, \dots, m_n, 1, 0) = q_{n-1}(m_1, m_2, \dots, m_n)$ from (2.6). $\square$

The expression (2.17) will be proved bijectively in Section 4.3 by a direct decomposition of the maps into slices.

### 2.1.3 Enumeration results in the quasi-bipartite case

Recall that a planar quasi-bipartite map is a planar map whose all faces but two have even degree. To give the explicit expression of the corresponding lattice count polynomial $N_{0,n}^{(2)}$, we need to introduce the following new family of univariate polynomials: for any integer $k \ge 0$, we set

$$ \tilde{p}_k(m) := \frac{1}{(k!)^2} \prod_{i=1}^{k} \left( m^2 - \left(i - \frac{1}{2}\right)^2 \right) = \binom{m - \frac{1}{2}}{k} \binom{m + k - \frac{1}{2}}{k} \quad (2.18) $$

with the convention $\tilde{p}_0(m) = 1$. Note that $\tilde{p}_k$ is again a polynomial of degree $k$ in $m^2$ and that $\tilde{p}_k(m)$ is an integer if $m$ is a half-integer. It satisfies the following counterpart of (2.3)

$$ (k+1)\tilde{p}_{k+1}(m) = \left(m - k - \frac{1}{2}\right) \tilde{p}_k(m) + \sum_{0 < j < m} (2j)\tilde{p}_k(j) \quad (2.19) $$

where it is understood that $m$ and $j$ are now half-integers.

The multivariate extension of $\tilde{p}_k$ is then defined for any integer $k \ge 0$ and any integer $n \ge 2$ as

$$ \tilde{p}_k(m_1, m_2; m_3, \dots, m_n) := \sum_{\substack{k_1, k_2, \dots, k_n \ge 0 \\ k_1 + k_2 + \dots + k_n = k}} \tilde{p}_{k_1}(m_1) \tilde{p}_{k_2}(m_2) q_{k_3}(m_3) \cdots q_{k_n}(m_n). \quad (2.20) $$

Again, we may append an arbitrary number of 0's to the arguments of $\tilde{p}_k$ without changing its value. Note that $\tilde{p}_k$ is in general not symmetric in all its variables, but only in $m_1$ and $m_2$ on the one hand, and in $m_3, \dots, m_n$ on the other hand. Note also that $\tilde{p}_k(m, 1/2) = \tilde{p}_k(m)$. The quasi-bipartite analog of Theorem 2.3 is then:

**Theorem 2.8.** For $n \ge 3$, for $m_1, m_2 \in \mathbb{Z}_{\ge 0} + \frac{1}{2}$ and $m_3, \dots, m_n \in \mathbb{Z}_{\ge 0}$, the number $N_{0,n}(2m_1, 2m_2, 2m_3, \dots, 2m_n)$ of planar tight quasi-bipartite maps with $n$ boundaries labeled from 1 to $n$ with respective lengths $2m_1, 2m_2, 2m_3, \dots, 2m_n$ is given by

$$ N_{0,n}^{(2)}(2m_1, 2m_2, 2m_3, \dots, 2m_n) = (n-3)! \tilde{p}_{n-3}(m_1, m_2; m_3, \dots, m_n). \quad (2.21) $$

In particular, for $n = k + 3$ and $m_3 = \dots = m_{k+3} = 0$, we get, for $m_1, m_2$ half-integers:

$$ N_{0,k+3}(2m_1, 2m_2, \underbrace{0, \dots, 0}_{k+1}) = k! \tilde{p}_k(m_1, m_2; \underbrace{0, \dots, 0}_{k+1}) = k! \tilde{p}_k(m_1, m_2). \quad (2.22) $$

Upon dividing by $k!$, we obtain a combinatorial interpretation of $\tilde{p}_k(m_1, m_2)$:
where it is understood that $m$ and $j$ are now half-integers.

The multivariate extension of $\tilde{p}_k$ is then defined for any integer $k \ge 0$ and any integer $n \ge 2$ as

$$ \tilde{p}_k(m_1, m_2; m_3, \dots, m_n) := \sum_{\substack{k_1, k_2, \dots, k_n \ge 0 \\ k_1 + k_2 + \dots + k_n = k}} \tilde{p}_{k_1}(m_1) \tilde{p}_{k_2}(m_2) q_{k_3}(m_3) \cdots q_{k_n}(m_n). \quad (20) $$

Again, we may append an arbitrary number of 0's to the arguments of $\tilde{p}_k$ without changing its value. Note that $\tilde{p}_k$ is in general not symmetric in all its variables, but only in $m_1$ and $m_2$ on the one hand, and in $m_3, \dots, m_n$ on the other hand. Note also that $\tilde{p}_k(m, 1/2) = \tilde{p}_k(m)$. The quasi-bipartite analog of Theorem 4 is then:

**Theorem 9.** For $n \ge 3$, for $m_1, m_2 \in \mathbb{Z}_{\ge 0} + \frac{1}{2}$ and $m_3, \dots, m_n \in \mathbb{Z}_{\ge 0}$, the number $N_{0,n}(2m_1, 2m_2, 2m_3, \dots, 2m_n)$ of planar tight quasi-bipartite maps with $n$ boundaries labeled from 1 to $n$ with respective lengths $2m_1, 2m_2, 2m_3, \dots, 2m_n$ is given by

$$ \mathbb{N}_{0,n}^{(2)}(2m_1, 2m_2, 2m_3, \dots, 2m_n) = (n-3)! \tilde{p}_{n-3}(m_1, m_2; m_3, \dots, m_n). \quad (21) $$

In particular, for $n = k + 3$ and $m_3 = \dots = m_{k+3} = 0$, we get, for $m_1, m_2$ half-integers:

$$ N_{0,k+3}(2m_1, 2m_2, \underbrace{0, \dots, 0}_{k+1}) = k! \tilde{p}_k(m_1, m_2; \underbrace{0, \dots, 0}_{k+1}) = k! \tilde{p}_k(m_1, m_2). \quad (22) $$

Upon dividing by $k!$, we obtain a combinatorial interpretation of $\tilde{p}_k(m_1, m_2)$:

**Proposition 10.** For $k \ge 0$ and $m_1, m_2 \in \mathbb{Z}_{\ge 0} + \frac{1}{2}$, $\tilde{p}_k(m_1, m_2)$ is the number of planar tight quasi-bipartite maps with two faces of odd degrees $2m_1, 2m_2$ and $k+1$ distinct marked vertices, one of them distinguished and labeled, say as vertex 1, and the remaining $k$ unlabeled.

Setting $m_2 = 1/2$, we obtain a combinatorial interpretation of the univariate polynomial $\tilde{p}_k(m) = \tilde{p}_k(m, 1/2)$, which will be given a direct bijective derivation in Section 4.1:

**Proposition 11.** For $k \ge 0$ and $m \in \mathbb{Z}_{\ge 0} + \frac{1}{2}$, $\tilde{p}_k(m)$ is the number of planar tight quasi-bipartite maps with one face of odd degree $2m$, one face of degree one, and $k+1$ distinct marked vertices, one of them distinguished and labeled, say as vertex 1, and the remaining $k$ unlabeled.

The polynomials $\tilde{p}_k$ obey the dilaton equation

$$ \tilde{p}_k(m_1, m_2; \dots, m_n, 1) - \tilde{p}_k(m_1, m_2; \dots, m_n, 0) = \tilde{p}_{k-1}(m_1, m_2; \dots, m_n) \quad (23) $$

and the string equation (for $m_i$'s as in Theorem 9)

$$ (k+1)\tilde{p}_{k+1}(m_1, m_2; \dots, m_n) = (m_1 + \dots + m_n - k - 1)\tilde{p}_k(m_1, m_2; \dots, m_n) + \sum_{i=1}^{n} \sum_{0 < j < m} (2j)\tilde{p}_k(m_1, \dots, m_{i-1}, j, m_{i+1}, \dots, m_n) \quad (24) $$

where we sum over half-integer values of $j$ for $i = 1$ and $2$ and over integer values of $j$ for $i \ge 3$. The proof is similar to that of Proposition 3 and uses now (19). Again, this corresponds to Norbury's dilaton and string equations in the planar quasi-bipartite case.
**Proposition 2.9.** For $k \ge 0$ and $m_1, m_2 \in \mathbb{Z}_{\ge 0} + \frac{1}{2}$, $\tilde{p}_k(m_1, m_2)$ is the number of planar tight quasi-bipartite maps with two faces of odd degrees $2m_1, 2m_2$ and $k+1$ distinct marked vertices, one of them distinguished and labeled, say as vertex 1, and the remaining $k$ unlabeled.

Setting $m_2 = 1/2$, we obtain a combinatorial interpretation of the univariate polynomial $\tilde{p}_k(m) = \tilde{p}_k(m, 1/2)$, which will be given a direct bijective derivation in Section 4.1:

**Proposition 2.10.** For $k \ge 0$ and $m \in \mathbb{Z}_{\ge 0} + \frac{1}{2}$, $\tilde{p}_k(m)$ is the number of planar tight quasi-bipartite maps with one face of odd degree $2m$, one face of degree one, and $k+1$ distinct marked vertices, one of them distinguished and labeled, say as vertex 1, and the remaining $k$ unlabeled.

The polynomials $\tilde{p}_k$ obey the dilaton equation

$$ \tilde{p}_k(m_1, m_2; \dots, m_n, 1) - \tilde{p}_k(m_1, m_2; \dots, m_n, 0) = \tilde{p}_{k-1}(m_1, m_2; \dots, m_n) \quad (2.23) $$

and the string equation (for $m_i$'s as in Theorem 2.8)

$$ (k+1)\tilde{p}_{k+1}(m_1, m_2; \dots, m_n) = (m_1 + \dots + m_n - k - 1)\tilde{p}_k(m_1, m_2; \dots, m_n) + \sum_{i=1}^{n} \sum_{0 < j < m} (2j)\tilde{p}_k(m_1, \dots, m_{i-1}, j, m_{i+1}, \dots, m_n) \quad (2.24) $$

where we sum over half-integer values of $j$ for $i = 1$ and $2$ and over integer values of $j$ for $i \ge 3$. The proof is similar to that of Proposition 2.2 and uses now (2.19). Again, this corresponds to Norbury's dilaton and string equations in the planar quasi-bipartite case.

**Remark 2.11.** We have the relation $\tilde{p}_k(1/2, 1/2; m_1, \dots, m_n) = q_k(m_1, \dots, m_n)$ which implies that $N_{0,n+2}(2m_1, 2m_2, 2m_3, \dots, 2m_n, 1, 1) = N_{0,n+2}(2m_1, 2m_2, 2m_3, \dots, 2m_n, 2, 0)$ for $m_1, \dots, m_n$ integers. The latter equality can be explained via a “slit-slide-sew” bijection in the spirit of [Bet20].

## 2.2. Quasi-polynomials counting planar tight maps with more odd faces

In this section, we provide explicit expressions for the lattice count polynomials $N_{0,n}^{(k)}$, enumerating planar tight maps with $k$ boundaries of odd lengths, and $n-k$ boundaries of even lengths, for an arbitrary value of $k \ge 3$.

To this end, similarly to the bipartite and quasi-bipartite cases discussed in the preceding section, we first need to introduce a two-parameter family of univariate polynomials which generalizes those introduced above: for $k$ a non-negative integer and $e \in \mathbb{Z}$, we define

$$ p_{k,e}(m) := \frac{1}{(k!)^2} \prod_{i=1}^{k} \left( m^2 - \left( i - \frac{e}{2} \right)^2 \right) = \left( m + \frac{e}{2} - 1 \right) \left( m - \frac{e}{2} + k \right). \quad (2.25) $$

We recover the polynomials $p_k$, $\tilde{p}_k$, and $q_k$ of Section 2.1 for $e = 0, 1, 2$, respectively. We will provide combinatorial interpretations of these polynomials in Section 5.
Remark 12. We have the relation $\tilde{p}_k(1/2, 1/2; m_1, \dots, m_n) = q_k(m_1, \dots, m_n)$ which implies that $N_{0,n+2}(2m_1, 2m_2, 2m_3, \dots, 2m_n, 1, 1) = N_{0,n+2}(2m_1, 2m_2, 2m_3, \dots, 2m_n, 2, 0)$ for $m_1, \dots, m_n$ integers. The latter equality can be explained via a “slit-slide-sew” bijection in the spirit of [Bet20].

## 2.2. Quasi-polynomials counting planar tight maps with more odd faces

In this section, we provide explicit expressions for the lattice count polynomials $N_{0,n}^{(k)}$, enumerating planar tight maps with $k$ boundaries of odd lengths, and $n-k$ boundaries of even lengths, for an arbitrary value of $k \ge 3$.

To this end, similarly to the bipartite and quasi-bipartite cases discussed in the preceding section, we first need to introduce a two-parameter family of univariate polynomials which generalizes those introduced above: for $k$ a non-negative integer and $e \in \mathbb{Z}$, we define

$$p_{k,e}(m) := \frac{1}{(k!)^2} \prod_{i=1}^{k} \left( m^2 - \left( i - \frac{e}{2} \right)^2 \right) = \binom{m + \frac{e}{2} - 1}{k} \binom{m - \frac{e}{2} + k}{k}. \quad (25)$$

We recover the polynomials $p_k, \tilde{p}_k$, and $q_k$ of Section 2.1 for $e = 0, 1, 2$, respectively. We will provide combinatorial interpretations of these polynomials in Section 5.

Next, let $r, s$ be non-negative integers and $\epsilon \in \mathbb{Z}$ be fixed. For $m \in \mathbb{Z}/2$, we let

$$\pi_{r,s}^{(\epsilon)}(m) := \begin{cases} \binom{r+s}{s} p_{r+s,s+1+\epsilon}(m) & \text{if } m - \frac{s+1+\epsilon}{2} \in \mathbb{Z}, \\ 0 & \text{otherwise.} \end{cases} \quad (26)$$

For every choice of $r, s, \epsilon$, this defines a quasi-polynomial in the variable $2m$. For the purposes of stating the main theorem of this section, only the cases $\epsilon \in \{0, 1\}$ will be of interest. Note that for $m = 0$ we have

$$\pi_{r,s}^{(\epsilon)}(0) = \begin{cases} \delta_{r,0}\delta_{s,0} & \text{if } \epsilon = 1, \\ 0 & \text{if } \epsilon = 0. \end{cases} \quad (27)$$

We may now state the main theorem of this section. In (29) below and later, for $\epsilon \in \{0, 1\}$, we will write $\bar{\epsilon} := 1 - \epsilon$ to lighten the notation.

**Theorem 13.** For $n \ge 3$, for $m_1, m_2, \dots, m_n \in \mathbb{Z}_{\ge 0}/2$, with at least three of the $m_i$ being half-integers, the number $N_{0,n}(2m_1, 2m_2, \dots, 2m_n)$ of planar tight maps with $n$ boundaries labeled from 1 to $n$ with respective lengths $2m_1, 2m_2, \dots, 2m_n$ is given by the symmetric quasi-polynomial

$$N_{0,n}(2m_1, 2m_2, \dots, 2m_n) = \sum_{\substack{r_1, \dots, r_n \\ s_1, \dots, s_n}} \left( \sum_{i=1}^{n} r_i \right)! \left( \sum_{i=1}^{n} \epsilon_i s_i \right) \left( \sum_{i=1}^{n} s_i - 1 \right)! \prod_{i=1}^{n} \pi_{r_i, s_i}^{(\epsilon_i)}(m_i), \quad (28)$$
Next, let $r, s$ be non-negative integers and $\epsilon \in \mathbb{Z}$ be fixed. For $m \in \mathbb{Z}/2$, we let

$$ \pi_{r,s}^{(\epsilon)}(m) := \begin{cases} \binom{r+s}{s} p_{r+s,s+1+\epsilon}(m) & \text{if } m - \frac{s+1+\epsilon}{2} \in \mathbb{Z}, \\ 0 & \text{otherwise.} \end{cases} \qquad (2.26) $$

For every choice of $r, s, \epsilon$, this defines a quasi-polynomial in the variable $2m$. For the purposes of stating the main theorem of this section (Theorem 2.12), only the cases $\epsilon \in \{0, 1\}$ will be of interest. Note that for $m = 0$ we have

$$ \pi_{r,s}^{(\epsilon)}(0) = \begin{cases} \delta_{r,0}\delta_{s,0} & \text{if } \epsilon = 1, \\ 0 & \text{if } \epsilon = 0. \end{cases} \qquad (2.27) $$

We may now state the main theorem of this section. In (2.29) below and later, for $\epsilon \in \{0, 1\}$, we will write $\bar{\epsilon} := 1 - \epsilon$ to lighten the notation.

**Theorem 2.12.** For $n \ge 3$, for $m_1, m_2, \dots, m_n \in \mathbb{Z}_{\ge 0}/2$, with at least three of the $m_i$ being half-integers, the number $N_{0,n}(2m_1, 2m_2, \dots, 2m_n)$ of planar tight maps with $n$ boundaries labeled from 1 to $n$ with respective lengths $2m_1, 2m_2, \dots, 2m_n$ is given by the symmetric quasi-polynomial

$$ N_{0,n}(2m_1, 2m_2, \dots, 2m_n) = \sum_{\substack{\epsilon_1, \dots, \epsilon_n \\ r_1, \dots, r_n \\ s_1, \dots, s_n}} \left(\sum_{i=1}^{n} r_i\right)! \left(\sum_{i=1}^{n} \epsilon_i s_i\right) \left(\sum_{i=1}^{n} s_i - 1\right)! \prod_{i=1}^{n} \pi_{r_i, s_i}^{(\epsilon_i)}(m_i), \quad (2.28) $$

where $I_n$ is the (finite) subset of $\{0, 1\}^n \times \mathbb{Z}_{\ge 0}^n \times \mathbb{Z}_{\ge 0}^n$ defined by

$$ I_n := \left\{ \begin{pmatrix} \epsilon_1, \dots, \epsilon_n \\ r_1, \dots, r_n \\ s_1, \dots, s_n \end{pmatrix} : \begin{array}{l} \displaystyle \sum_{i=1}^{n} \epsilon_i = \sum_{i=1}^{n} r_i + 1 \\ \displaystyle \sum_{i=1}^{n} \bar{\epsilon}_i = \sum_{i=1}^{n} s_i + 2 \\ \displaystyle \sum_{i=1}^{n} s_i \ge 1 \end{array} \right\}. \qquad (2.29) $$

**Remark 2.13.** We note that the right-hand side of (2.28) is equal to 0 when the number $k$ of faces of odd degree is equal to 0 or 2, so that the formula does not hold in these cases, which have been respectively dealt with above in Theorems 2.3 and 2.8. Theorem 2.12 yields a non-trivial result only when $k \ge 4$ is an even number, since a map necessarily has an even number of faces of odd degrees. As a sanity check, it is not difficult to see that the right-hand side of (2.28) vanishes when $k$ is odd. Indeed, assume without loss of generality that $2m_1, \dots, 2m_k$ are odd numbers, and that $2m_{k+1}, \dots, 2m_n$ are even. By (2.26) and (2.27), the product term in the sum (2.28) is non-zero only if $s_i + \epsilon_i$ is even for $1 \le i \le k$, and odd for $k+1 \le i \le n$. On the other hand, the constraints in the definition of the summation index implies that $\sum_{i=1}^{n}(s_i + \epsilon_i) + 2 = n$, which after reduction modulo 2, shows that $n-k$ and $n$ have the same parity, so that $k$ is necessarily even. A fully unified formula, encompassing Theorems 2.3, 2.8 and 2.12 is given in Theorem 5.13 below.
where $I_n$ is the (finite) subset of $\{0,1\}^n \times \mathbb{Z}_{\ge 0}^n \times \mathbb{Z}_{\ge 0}^n$ defined by

$$ I_n := \left\{ \begin{pmatrix} \epsilon_1, \dots, \epsilon_n \\ r_1, \dots, r_n \\ s_1, \dots, s_n \end{pmatrix} : \begin{array}{l} \displaystyle \sum_{i=1}^{n} \epsilon_i = \sum_{i=1}^{n} r_i + 1 \\ \displaystyle \sum_{i=1}^{n} \bar{\epsilon}_i = \sum_{i=1}^{n} s_i + 2 \\ \displaystyle \sum_{i=1}^{n} s_i \ge 1 \end{array} \right\}. \quad (29) $$

**Remark 14.** We note that the right-hand side of (28) is equal to 0 when the number $k$ of faces of odd degree is equal to 0 or 2, so that the formula does not hold in these cases, which have been respectively dealt with above in Theorems 4 and 9. Theorem 13 yields a non-trivial result only when $k \ge 4$ is an even number, since a map necessarily has an even number of faces of odd degrees. As a sanity check, it is not difficult to see that the right-hand side of (28) vanishes when $k$ is odd. Indeed, assume without loss of generality that $2m_1, \dots, 2m_k$ are odd numbers, and that $2m_{k+1}, \dots, 2m_n$ are even. By (26) and (27), the product term in the sum (28) is non-zero only if $s_i + \epsilon_i$ is even for $1 \le i \le k$, and odd for $k+1 \le i \le n$. On the other hand, the constraints in the definition of the summation index implies that $\sum_{i=1}^n (s_i + \epsilon_i) + 2 = n$, which after reduction modulo 2, shows that $n-k$ and $n$ have the same parity, so that $k$ is necessarily even. A fully unified formula, encompassing Theorems 4, 9 and 13 is given in Theorem 42 below.

The proof of Theorem 13 will follow an architecture similar to the bijective proof of Theorems 4 and 9, building from elementary examples of maps with explicit enumeration formulas, to construct general ones. In particular, note that (28) reduces to $\pi_{r,s}^{(1)}(m)$ if we specialize it to $n = r + s$ with $m_1 = m$, $m_2 = \dots = m_{s+3} = 1/2$ and $m_{s+4} = \dots = m_{r+s} = 0$. However, it is not a priori obvious to obtain an interpretation of $\pi_{r,s}^{(0)}(m)$ by specializing formula (28). For this reason, we will need to investigate in some depth these quasi-polynomials and relate them to the combinatorial notion of *petal trees*. This will be the object of Section 5.1, but let us record right away the definition of this notion so as to state one important result, Proposition 15, which will be used at the end of Section 3.

We call *petal* a face of degree 1. A *petal tree* is a planar map having an *exterior face* of arbitrary degree, and such that every other face is a petal. A tight petal tree is just a petal tree with marked vertices, which is tight as a map.

**Proposition 15.** For $r, s$ nonnegative integers, $m \in \mathbb{Z}_{>0}/2$, and $\epsilon \in \{-1, 0, 1\}$, the number of tight petal trees with an *exterior face* of degree $2m$, $s+1+\epsilon$ *petals*, $1+\epsilon$ of which distinguished, and $r+1-\epsilon$ marked vertices, $1-\epsilon$ of which distinguished, is equal to $\pi_{r,s}^{(e)}(m)$.

**Remark 16.** Proposition 15, which will be proved in Section 5.1, holds for $m > 0$. It can be extended to $m = 0$, provided we restrict the value of $\epsilon$ to the set $\{0, 1\}$. Indeed, in this case, (27) is consistent with Proposition 15 upon understanding the *exterior face* of degree 0 as a distinguished marked vertex. For $\epsilon = 0$ or 1, the only possible map with such a marked vertex, $s+1+\epsilon$ *petals* (and no other face) and $r+1-\epsilon$ other marked vertices is made of a single loop connecting the distinguished marked vertex and
<figure><img src="image_4.png" /><figcaption>Figure 2.1: A tight petal tree with 5 petals (displayed with yellow marks) and 7 marked vertices (shown in white).</figcaption></figure>

The proof of Theorem 2.12 will follow an architecture similar to the bijective proof of Theorems 2.3 and 2.8, building from elementary examples of maps with explicit enumeration formulas, to construct general ones. In particular, note that (2.28) reduces to $\pi_{r,s}^{(1)}(m)$ if we specialize it to $n = r + s$ with $m_1 = m$, $m_2 = \dots = m_{s+3} = 1/2$ and $m_{s+4} = \dots = m_{r+s} = 0$. However, it is not a priori obvious to obtain an interpretation of $\pi_{r,s}^{(0)}(m)$ by specializing formula (2.28). For this reason, we will need to investigate in some depth these quasi-polynomials and relate them to the combinatorial notion of *petal trees*. This will be the object of Section 5.1, but let us record right away the definition of this notion so as to state one important result, Proposition 2.14, which will be used at the end of Section 3.

We call *petal* a face of degree 1. A *petal tree* is a planar map having an *exterior* face of arbitrary degree, and such that every other face is a petal. A tight petal tree is just a petal tree with marked vertices, which is tight as a map. See Figure 2.1 for an illustration.

**Proposition 2.14.** For $r, s$ nonnegative integers, $m \in \mathbb{Z}_{>0}/2$, and $\epsilon \in \{-1, 0, 1\}$, the number of tight petal trees with an exterior face of degree $2m$, $s+1+\epsilon$ petals, $1+\epsilon$ of which distinguished, and $r+1-\epsilon$ marked vertices, $1-\epsilon$ of which distinguished, is equal to $\pi_{r,s}^{(\epsilon)}(m)$.

*Remark 2.15.* Proposition 2.14, which will be proved in Section 5.1, holds for $m > 0$. It can be extended to $m = 0$, provided we restrict the value of $\epsilon$ to the set $\{0, 1\}$. Indeed, in this case, (2.27) is consistent with Proposition 2.14 upon understanding the exterior face of degree 0 as a distinguished marked vertex. For $\epsilon = 0$ or 1, the only possible map with such a marked vertex, $s+1+\epsilon$ petals (and no other face) and $r+1-\epsilon$ other marked vertices is made of a single loop connecting the distinguished marked vertex and separating two petals. It has $s+1+\epsilon = 2$ and $r+1-\epsilon = 0$, hence $\epsilon = 1$ and $r = s = 0$ (note that the distinction of the two petals does not create any degeneracy).

*Remark 2.16.* The situation above is quite similar to the case $m = 1/2$, for which we obtain

$$ \pi_{r,s}^{(\epsilon)}\left(\frac{1}{2}\right) = \begin{cases} 0 & \text{if } \epsilon = -1, \\ \delta_{r,0}\delta_{s,0} & \text{if } \epsilon = 0, \\ 0 & \text{if } \epsilon = 1. \end{cases} \qquad (2.30) $$
separating two petals. It has $s+1+\epsilon=2$ and $r+1-\epsilon=0$, hence $\epsilon=1$ and $r=s=0$ (note that the distinction of the two petals does not create any degeneracy).

*Remark 17.* The situation above is quite similar to the case $m=1/2$, for which we obtain

$$ \pi_{r,s}^{(\epsilon)}\left(\frac{1}{2}\right) = \begin{cases} 0 & \text{if } \epsilon = -1, \\ \delta_{r,0}\delta_{s,0} & \text{if } \epsilon = 0, \\ 0 & \text{if } \epsilon = 1. \end{cases} \qquad (30) $$

This agrees with Proposition 15 since the only possible map with an exterior face of degree 1, $s+1+\epsilon$ petals and $r+1-\epsilon$ marked vertices is made of a single loop connecting a unique vertex and separating the exterior face from a unique petal. It has $s+1+\epsilon=1$ and $r+1-\epsilon \le 1$, hence $\epsilon=0$, $s=0$ and $r=0$ (note that the unique vertex is therefore marked).

# 3. Connection with the enumeration of non necessarily tight maps

## 3.1. Equivalence with Tutte's slicings formula in the (quasi-)bipartite case

One of the earliest results in map enumeration is Tutte's *slicings formula* [Tut62] which, in our current terminology, asserts that the number $M(\ell_1, \dots, \ell_n)$ of planar (non necessarily tight) *bipartite* maps with $n \ge 3$ labeled faces of prescribed even degrees $2\ell_1, \dots, 2\ell_n$ is given by

$$ M(\ell_1, \dots, \ell_n) = (\ell_1 + \dots + \ell_n - 1)_{n-3} \prod_{i=1}^{n} \binom{2\ell_i - 1}{\ell_i}, \qquad (31) $$

where $(\ell)_k := \ell(\ell-1)\cdots(\ell-k+1)$ denotes the falling factorial. Note that the faces are assumed unrooted and that the formula extends to the case where some, but not all, of the $\ell_i$ vanish, with the convention $\binom{-1}{0} = 1$, upon again understanding that a face of degree 0 is a marked vertex (planar maps with three or more labeled faces or vertices have no symmetries).

In this section, we explain how Tutte's slicings formula is related to Theorem 4 giving a formula for the number of planar *tight* bipartite maps with $n$ boundaries of prescribed lengths. As we shall see, the two formulas can be deduced from one another.

The key observation, already made in [Bud20b, Section 4], is that an arbitrary (non necessarily tight) map, possibly with marked vertices, can be bijectively decomposed into a tight map (which we call the *tight core*) and a collection of rooted plane trees (without marked vertices) attached to the corners of the tight core. See Figure 3 for an illustration. Precisely, the tight core has the same number of faces and marked vertices as the arbitrary map, and a face of degree $2\ell$ in the arbitrary map yields a face of degree $2m$ in the tight core, for some $m \le \ell$, together with a plane forest made of $2m$ trees having $\ell-m$ edges in total. The number of such plane forests is equal to

$$ A_{\ell,m} := \frac{2m}{2\ell} \binom{2\ell}{\ell-m} \qquad (32) $$
<figure><img src="image_5.png" /><figcaption>Figure 3.1: The tight core (thick red edges) of a planar bipartite map with two faces and one marked vertex (shown in white). The rest of the map consists of rooted plane trees (possibly empty) attached in the corners of the tight core.</figcaption></figure>

This agrees with Proposition 2.14 since the only possible map with an exterior face of degree 1, $s+1+\epsilon$ petals and $r+1-\epsilon$ marked vertices is made of a single loop connecting a unique vertex and separating the exterior face from a unique petal. It has $s+1+\epsilon=1$ and $r+1-\epsilon \le 1$, hence $\epsilon=0$, $s=0$ and $r=0$ (note that the unique vertex is therefore marked).

# 3. Connection with the enumeration of non necessarily tight maps

## 3.1. Equivalence with Tutte's slicings formula in the (quasi-)bipartite case

One of the earliest results in map enumeration is Tutte's *slicings formula* [Tut62] which, in our current terminology, asserts that the number $M(\ell_1, \dots, \ell_n)$ of planar (non necessarily tight) bipartite maps with $n \ge 3$ labeled faces of prescribed even degrees $2\ell_1, \dots, 2\ell_n$ is given by

$$M(\ell_1, \dots, \ell_n) = (\ell_1 + \dots + \ell_n - 1)_{n-3} \prod_{i=1}^{n} \binom{2\ell_i - 1}{\ell_i}, \quad (3.1)$$

where $(\ell)_k := \ell(\ell-1) \cdots (\ell-k+1)$ denotes the falling factorial. Note that the faces are assumed unrooted and that the formula extends to the case where some, but not all, of the $\ell_i$ vanish, with the convention $\binom{-1}{0} = 1$, upon again understanding that a face of degree 0 is a marked vertex (planar maps with three or more labeled faces or vertices have no symmetries).

In this section, we explain how Tutte's slicings formula is related to Theorem 2.3 giving a formula for the number of planar *tight* bipartite maps with $n$ boundaries of prescribed lengths. As we shall see, the two formulas can be deduced from one another.

The key observation, already made in [Bud22b, Section 4], is that an arbitrary (non necessarily tight) map, possibly with marked vertices, can be bijectively decomposed into a tight map (which we call the *tight core*) and a collection of rooted plane trees (without marked vertices) attached to the corners of the tight core. See Figure 3.1 for an illustration. Precisely, the tight core has the same number of faces and marked vertices as the arbitrary map, and a face of degree
<figure><img src="image_4.png" /><figcaption>Figure 3: The tight core (thick red edges) of a planar bipartite map with two faces and one marked vertex (shown in white). The rest of the map consists of rooted plane trees (possibly empty) attached in the corners of the tight core.</figcaption></figure>

with conventionally $A_{0,0} = 1$ and $A_{\ell,m} = 0$ for $m > \ell$. As a consequence, we have

$$M(\ell_1, \dots, \ell_n) = \sum_{m_1=0}^{\ell_1} \cdots \sum_{m_n=0}^{\ell_n} A_{\ell_1, m_1} \cdots A_{\ell_n, m_n} N_{0,n}(2m_1, \dots, 2m_n) \quad (33)$$

where $N_{0,n}$ is the number of planar tight bipartite maps with $n$ boundaries of lengths $2m_1, \dots, 2m_n$, as defined in Section 1.2. Note that the matrix $(A_{\ell,m})_{\ell,m \ge 0}$ is unitriangular, hence the formula (33) can be inverted as

$$N_{0,n}(2m_1, \dots, 2m_n) = \sum_{\ell_1=0}^{m_1} \cdots \sum_{\ell_n=0}^{m_n} B_{m_1, \ell_1} \cdots B_{m_n, \ell_n} M(\ell_1, \dots, \ell_n) \quad (34)$$

where $B$ is the inverse of $A$. This inverse is given explicitly by $B_{m,\ell} = (-1)^{m-\ell} \binom{m+\ell-1}{m-\ell}$ but we will not use its expression in the following.

Now, let us substitute Tutte's slicings formula (31) into (34). By the Chu-Vandermonde identity, we may expand the falling factorial as

$$(\ell_1 + \cdots + \ell_n - 1)_{n-3} = (n-3)! \sum_{\substack{k_1, k_2, \dots, k_n \ge 0 \\ k_1 + k_2 + \cdots + k_n = n-3}} \binom{\ell_1 - 1}{k_1} \binom{\ell_2}{k_2} \cdots \binom{\ell_n}{k_n}, \quad (35)$$

which is nothing but an equality between polynomials in $\ell_1, \dots, \ell_n$. This yields

$$N_{0,n}(2m_1, \dots, 2m_n) = (n-3)! \sum_{\substack{k_1, k_2, \dots, k_n \ge 0 \\ k_1 + k_2 + \dots + k_n = n-3}} \hat{p}_{k_1}(m_1) \hat{q}_{k_2}(m_2) \cdots \hat{q}_{k_n}(m_n) \quad (36)$$

where $\hat{p}_k(m) := \sum_{\ell=0}^{m} B_{m,\ell} \binom{\ell-1}{k} \binom{2\ell-1}{\ell}$ and $\hat{q}_k(m) := \sum_{\ell=0}^{m} B_{m,\ell} \binom{\ell}{k} \binom{2\ell-1}{\ell}$. We recover Theorem 4, with the multivariate polynomial $p_{n-3}(m_1, m_2, \dots, m_n)$ defined via (6), provided that $\hat{p}_k(m)$ and $\hat{q}_k(m)$ are respectively equal to the univariate polynomials $p_k(m)$ and $q_k(m)$ defined in (2). This is ensured by the following:
2ℓ in the arbitrary map yields a face of degree 2m in the tight core, for some m ≤ ℓ, together with a plane forest made of 2m trees having ℓ − m edges in total. The number of such plane forests is equal to

$$
A_{\ell,m} := \frac{2m}{2\ell} \binom{2\ell}{\ell-m}, \qquad (3.2)
$$

see for instance [FS09, ▷ I.38], with conventionally $A_{0,0} = 1$ and $A_{\ell,m} = 0$ for $m > \ell$. As a consequence, we have

$$
M(\ell_1, \dots, \ell_n) = \sum_{m_1=0}^{\ell_1} \dots \sum_{m_n=0}^{\ell_n} A_{\ell_1, m_1} \dots A_{\ell_n, m_n} N_{0,n}(2m_1, \dots, 2m_n) \quad (3.3)
$$

where $N_{0,n}$ is the number of planar tight bipartite maps with $n$ boundaries of lengths $2m_1, \dots, 2m_n$, as defined in Section 1.2. Note that the matrix $(A_{\ell,m})_{\ell,m \ge 0}$ is unitriangular, hence the formula (3.3) can be inverted as

$$
N_{0,n}(2m_1, \dots, 2m_n) = \sum_{\ell_1=0}^{m_1} \dots \sum_{\ell_n=0}^{m_n} B_{m_1,\ell_1} \dots B_{m_n,\ell_n} M(\ell_1, \dots, \ell_n) \quad (3.4)
$$

where $B$ is the inverse of $A$. This inverse is given explicitly by $B_{m,l} = (-1)^{m-l} \binom{m+l-1}{m-l}$ but we
will not use its expression in the following.

Now, let us substitute Tutte’s slicings formula (3.1) into (3.4). By the Chu-Vandermonde identity, we may expand the falling factorial as

$$
(\ell_1 + \cdots + \ell_n - 1)_{n-3} = (n-3)! \sum_{\substack{k_1, k_2, \ldots, k_n \ge 0 \\ k_1 + k_2 + \cdots + k_n = n-3}} \binom{\ell_1 - 1}{k_1} \binom{\ell_2}{k_2} \cdots \binom{\ell_n}{k_n}, \quad (3.5)
$$

which is nothing but an equality between polynomials in $\ell_1, \dots, \ell_n$. This yields

$$
N_{0,n}(2m_1, \dots, 2m_n) = (n-3)! \sum_{\substack{k_1, k_2, \dots, k_n \ge 0 \\ k_1 + k_2 + \dots + k_n = n-3}} \hat{p}_{k_1}(m_1) \hat{q}_{k_2}(m_2) \dots \hat{q}_{k_n}(m_n) \quad (3.6)
$$

where $\hat{p}_k(m) := \sum_{\ell=0}^m B_{m,\ell} \binom{\ell-1}{k} \binom{2\ell-1}{\ell}$ and $\hat{q}_k(m) := \sum_{\ell=0}^m B_{m,\ell} \binom{\ell}{k} \binom{2\ell-1}{\ell}$. We recover Theorem 2.3, with the multivariate polynomial $p_{n-3}(m_1, m_2, \dots, m_n)$ defined via (2.5), provided that $\hat{p}_k(m)$ and $\hat{q}_k(m)$ are respectively equal to the univariate polynomials $p_k(m)$ and $q_k(m)$ defined in (2.1). This is ensured by the following:

**Lemma 3.1.** The univariate polynomials $p_k(m)$ and $q_k(m)$ defined in (2.1) satisfy

$$
\sum_{m=0}^{\ell} A_{\ell,m} p_k(m) = \binom{\ell-1}{k} \binom{2\ell-1}{\ell}, \quad \sum_{m=0}^{\ell} A_{\ell,m} q_k(m) = \binom{\ell}{k} \binom{2\ell-1}{\ell}. \qquad (3.7)
$$

*Proof.* These hypergeometric identities can be proved using algorithmic methods, see [PWZ96]
and references therein.
**Lemma 18.** The univariate polynomials $p_k(m)$ and $q_k(m)$ defined in (2) satisfy

$$ \sum_{m=0}^{\ell} A_{\ell,m} p_k(m) = \binom{\ell-1}{k} \binom{2\ell-1}{\ell}, \qquad \sum_{m=0}^{\ell} A_{\ell,m} q_k(m) = \binom{\ell}{k} \binom{2\ell-1}{\ell}. \qquad (37) $$

*Proof.* These hypergeometric identities can be proved using algorithmic methods, see [PWZ96] and references therein.

Alternatively, a bijective proof for $\ell \ge 1$ follows from Propositions 5 and 6, themselves proved bijectively in Section 4.1. More precisely, the first identity is obtained by counting in two different ways plane trees with $\ell$ edges and $k+2$ distinct marked vertices, two of them distinguished and labeled. Namely, the left-hand side is obtained via the tight core decomposition and Proposition 5, while the right-hand side is obtained by a direct enumeration: $\binom{2\ell-1}{\ell}$ is the number of plane trees with $\ell$ edges and two distinguished labeled vertices, and $\binom{\ell-1}{k}$ is the number of ways to choose the $k$ other marked vertices. The second identity is obtained similarly by counting in two different ways plane trees with $\ell$ edges, one of them marked, and $k+1$ distinct marked vertices, one of them distinguished. $\square$

Note that, doing the above reasoning backwards, it is conversely possible to recover Tutte's slicings formula from Theorem 4, using (33). We now briefly discuss the quasi-bipartite case: let $\ell_1, \ell_2$ be positive half-integers, and $\ell_3, \dots, \ell_n$ be non-negative integers, $n \ge 3$. Then, by [Tut62, Section 6], the number $M(\ell_1, \dots, \ell_n)$ of planar quasi-bipartite maps with $n$ labeled boundaries of prescribed lengths $2\ell_1, \dots, 2\ell_n$ reads

$$ M(\ell_1, \dots, \ell_n) = (\ell_1 + \dots + \ell_n - 1)_{n-3} \binom{2\ell_1 - 1}{\ell_1 - \frac{1}{2}} \binom{2\ell_2 - 1}{\ell_2 - \frac{1}{2}} \prod_{i=3}^{n} \binom{2\ell_i - 1}{\ell_i}. \qquad (38) $$

The tight core decomposition works as before and we find that (33) still holds, upon understanding that the sums over $m_1$ and $m_2$ should be now taken over half-integer values, $A_{\ell,m}$ being still defined by (32) for $\ell, m$ half-integers. By a slight variant of the reasoning above, we may deduce Theorem 9 with the multivariate polynomial $\tilde{p}_k(m_1, m_2; m_3, \dots, m_n)$ being given by (20). Namely, we modify the expansion (35) of the falling factorial by replacing $\ell_1 - 1$ and $\ell_2$ in the right-hand side by $\ell_1 - \frac{1}{2}$ and $\ell_2 - \frac{1}{2}$, respectively, and we make use of the identity

$$ \sum_{m \in \left\{ \frac{1}{2}, \frac{3}{2}, \dots, \ell \right\}} A_{\ell, m} \tilde{p}_k(m) = \binom{\ell - \frac{1}{2}}{k} \binom{2\ell - 1}{\ell - \frac{1}{2}} \qquad (39) $$

valid for $\ell$ a positive half-integer. Again, this identity can be proved either via algorithmic methods, or via a bijective argument: it is obtained by counting in two different ways planar maps with one face of odd degree $2\ell$, one face of degree one and $k+1$ distinct marked vertices, one of them distinguished. The left-hand side is obtained by the tight-core decomposition together with Proposition 11 (which will be derived bijectively in Section 4.1). As for the right-hand side, note that, by collapsing the face of degree one,
Alternatively, a bijective proof for $\ell \ge 1$ follows from Propositions 2.4 and 2.5, themselves proved bijectively in Section 4.1. More precisely, the first identity is obtained by counting in two different ways plane trees with $\ell$ edges and $k+2$ distinct marked vertices, two of them distinguished and labeled. Namely, the left-hand side is obtained via the tight core decomposition and Proposition 2.4, while the right-hand side is obtained by a direct enumeration: $\binom{2\ell-1}{\ell}$ is the number of plane trees with $\ell$ edges and two distinguished labeled vertices, and $\binom{\ell-1}{k}$ is the number of ways to choose the $k$ other marked vertices. The second identity is obtained similarly by counting in two different ways plane trees with $\ell$ edges, one of them marked, and $k+1$ distinct marked vertices, one of them distinguished. $\square$

Note that, doing the above reasoning backwards, it is conversely possible to recover Tutte's slicings formula from Theorem 2.3, using (3.3). We now briefly discuss the quasi-bipartite case: let $\ell_1, \ell_2$ be positive half-integers, and $\ell_3, \dots, \ell_n$ be non-negative integers, $n \ge 3$. Then, by [Tut62, Section 6], the number $M(\ell_1, \dots, \ell_n)$ of planar quasi-bipartite maps with $n$ labeled boundaries of prescribed lengths $2\ell_1, \dots, 2\ell_n$ reads

$$M(\ell_1, \dots, \ell_n) = (\ell_1 + \dots + \ell_n - 1)_{n-3} \binom{2\ell_1 - 1}{\ell_1 - \frac{1}{2}} \binom{2\ell_2 - 1}{\ell_2 - \frac{1}{2}} \prod_{i=3}^{n} \binom{2\ell_i - 1}{\ell_i}. \quad (3.8)$$

The tight core decomposition works as before and we find that (3.3) still holds, upon understanding that the sums over $m_1$ and $m_2$ should be now taken over half-integer values, $A_{\ell,m}$ being still defined by (3.2) for $\ell, m$ half-integers. By a slight variant of the reasoning above, we may deduce Theorem 2.8 with the multivariate polynomial $\tilde{p}_k(m_1, m_2; m_3, \dots, m_n)$ being given by (2.20). Namely, we modify the expansion (3.5) of the falling factorial by replacing $\ell_1 - 1$ and $\ell_2$ in the right-hand side by $\ell_1 - \frac{1}{2}$ and $\ell_2 - \frac{1}{2}$, respectively, and we make use of the identity

$$\sum_{m \in \left\{ \frac{1}{2}, \frac{3}{2}, \dots, \ell \right\}} A_{\ell, m} \tilde{p}_k(m) = \binom{\ell - \frac{1}{2}}{k} \binom{2\ell - 1}{\ell - \frac{1}{2}} \quad (3.9)$$

valid for $\ell$ a positive half-integer. Again, this identity can be proved either via algorithmic methods, or via a bijective argument: it is obtained by counting in two different ways planar maps with one face of odd degree $2\ell$, one face of degree one and $k+1$ distinct marked vertices, one of them distinguished. The left-hand side is obtained by the tight-core decomposition together with Proposition 2.10 (which will be derived bijectively in Section 4.1). As for the right-hand side, note that, by collapsing the face of degree one, such maps correspond to rooted plane trees with $\ell - \frac{1}{2}$ edges: $\binom{2\ell-1}{\ell-1/2}$ is the number of such trees with one distinguished vertex, and $\binom{\ell-1/2}{k}$ is the number of ways to choose the $k$ other marked vertices.

## 3.2. A non-bipartite slicings formula

By arguing similarly, we may use Theorem 2.12 to obtain a generalization of Tutte's slicings formula counting planar maps with a prescribed degree sequence. The relevant identity to use, valid for $\ell - \frac{s+1+\epsilon}{2} \in \mathbb{Z}$ and $\epsilon \in \{0, 1\}$, is

$$\sum_{m \in \mathbb{Z}_{\ge 0}/2} A_{\ell,m} \pi_{r,s}^{(\epsilon)}(m) = \binom{2\ell-1}{\ell - \frac{s+1+\epsilon}{2}, \ell - r - \frac{s+1-\epsilon}{2}, r, s}, \quad (3.10)$$
such maps correspond to rooted plane trees with $\ell - \frac{1}{2}$ edges: $\binom{2\ell-1}{\ell-1/2}$ is the number of such trees with one distinguished vertex, and $\binom{\ell-1/2}{k}$ is the number of ways to choose the $k$ other marked vertices.

## 3.2. A non-bipartite slicings formula

By arguing similarly, we may use Theorem 13 to obtain a generalization of Tutte's slicings formula counting planar maps with a prescribed degree sequence. The relevant identity to use, valid for $\ell - \frac{s+1+\epsilon}{2} \in \mathbb{Z}$ and $\epsilon \in \{0, 1\}$, is

$$ \sum_{m \in \mathbb{Z}_{\ge 0}/2} A_{\ell,m} \pi_{r,s}^{(\epsilon)}(m) = \binom{2\ell-1}{\ell - \frac{s+1+\epsilon}{2}, \ell - r - \frac{s+1-\epsilon}{2}, r, s}, \quad (40) $$

where in the left-hand side, we observe by (26) that only the terms for which $\ell - m \in \mathbb{Z}_{\ge 0}$ contribute, and in the right-hand side, we use a multinomial coefficient notation. To understand this formula, recall from Proposition 15 that $\pi_{r,s}^{(\epsilon)}(m)$ counts tight petal trees, i.e. tight maps with an exterior face of degree $2m$, $s+1+\epsilon$ petals, $1+\epsilon$ of which are distinguished, and $r+1-\epsilon$ marked vertices, $1-\epsilon$ of which are distinguished. By applying the tight core decomposition, the left-hand side of (40) expresses the number of petal trees which are not necessarily tight, with an exterior face of degree $2\ell$, and with the same number of (distinguished) petals and (distinguished) marked vertices as described in the preceding sentence. Checking that this number equals the right-hand side of (40) is a straightforward exercise based on the methods used in Section 5.1 to prove Proposition 15, and is simpler due to the absence of the tightness condition.

Formula (33) remains unchanged if $\ell_1, \dots, \ell_n$ are allowed to take half-integer values, except that the corresponding sums should then run over half-integer $m_i$'s as well. Substituting in (33) the formula of Theorem 13 for $N_{0,n}(2m_1, \dots, 2m_n)$, we obtain the following:

**Theorem 19 (A census of non-bipartite slicings).** The number $M(\ell_1, \dots, \ell_n)$ of planar maps with $n$ labeled faces of degrees $2\ell_1, \dots, 2\ell_n$, at least four of which are odd, is given by

$$ M(\ell_1, \dots, \ell_n) = \sum_{\substack{\ell_1, \dots, \ell_n \\ r_1, \dots, r_n \\ s_1, \dots, s_n}} \binom{n}{\sum_{i=1}^{n} r_i}! \binom{n}{\sum_{i=1}^{n} \epsilon_i s_i} \binom{n}{\sum_{i=1}^{n} s_i - 1}! \\ \times \prod_{i=1}^{n} \left( \ell_i - \frac{s_i+1+\epsilon_i}{2}, \ell_i - r_i - \frac{s_i+1-\epsilon_i}{2}, r_i, s_i \right), \quad (41) $$

where $I_n$ is as in (29), and where it is understood that the multinomial coefficient vanishes whenever $\ell_i - \frac{s_i+1+\epsilon_i}{2}$ is not an integer. The formula makes sense when some $\ell_i$ vanish, upon understanding that a face of degree 0 is in fact a vertex.
where in the left-hand side, we observe by (2.26) that only the terms for which $\ell - m \in \mathbb{Z}_{\ge 0}$ contribute, and in the right-hand side, we use a multinomial coefficient notation. To understand this formula, recall from Proposition 2.14 that $\pi_{r,s}^{(\epsilon)}(m)$ counts tight petal trees, i.e. tight maps with an exterior face of degree $2m$, $s + 1 + \epsilon$ petals, $1 + \epsilon$ of which are distinguished, and $r + 1 - \epsilon$ marked vertices, $1 - \epsilon$ of which are distinguished. By applying the tight core decomposition, the left-hand side of (3.10) expresses the number of petal trees which are not necessarily tight, with an exterior face of degree $2\ell$, and with the same number of (distinguished) petals and (distinguished) marked vertices as described in the preceding sentence. Checking that this number equals the right-hand side of (3.10) is a straightforward exercise based on the methods used in Section 5.1 to prove Proposition 2.14, and is simpler due to the absence of the tightness condition.

Formula (3.3) remains unchanged if $\ell_1, \dots, \ell_n$ are allowed to take half-integer values, except that the corresponding sums should then run over half-integer $m_i$'s as well. Substituting in (3.3) the formula of Theorem 2.12 for $N_{0,n}(2m_1, \dots, 2m_n)$, we obtain the following:

**Theorem 3.2 (A census of non-bipartite slicings).** The number $M(\ell_1, \dots, \ell_n)$ of planar maps with $n$ labeled faces of degrees $2\ell_1, \dots, 2\ell_n$, at least four of which are odd, is given by

$$M(\ell_1, \dots, \ell_n) = \sum_{\left(\begin{array}{c} \epsilon_1, \dots, \epsilon_n \\ r_1, \dots, r_n \\ s_1, \dots, s_n \end{array}\right) \in I_n} \left(\sum_{i=1}^{n} r_i\right)! \left(\sum_{i=1}^{n} \epsilon_i s_i\right) \left(\sum_{i=1}^{n} s_i - 1\right)! \\ \times \prod_{i=1}^{n} \left(\ell_i - \frac{s_i+1+\epsilon_i}{2}, \ell_i - r_i - \frac{s_i+1-\epsilon_i}{2}, r_i, s_i\right), \quad (3.11)$$

where $I_n$ is as in (2.29), and where it is understood that the multinomial coefficient vanishes whenever $\ell_i - \frac{s_i+1+\epsilon_i}{2}$ is not an integer. The formula makes sense when some $\ell_i$ vanish, upon understanding that a face of degree 0 is in fact a vertex.

**Example 3.3.** For $\ell_1, \dots, \ell_4 \in \mathbb{Z}_{\ge 0} + \frac{1}{2}$, performing the sum in (3.11) yields a number of planar maps with four labeled faces of odd degrees $2\ell_1, \dots, 2\ell_4$ equal to

$$M(\ell_1, \dots, \ell_4) = (\ell_1 + \dots + \ell_4 - 2) \prod_{i=1}^{4} \binom{2\ell_i - 1}{\ell_i - \frac{1}{2}}. \quad (3.12)$$

In particular, we find $M(\frac{3}{2}, \frac{1}{2}, \frac{1}{2}, \frac{1}{2}) = 2$ which, after rooting each face, gives a number of slicings equal to 6 consistently with [Tut62, Section 6].

To our knowledge, this extension of Tutte's slicings formula for general non-bipartite planar maps with prescribed degrees is new. Note that (3.11) does not hold when the number of faces of odd degree is zero or two, see the discussion in Remark 2.13 in the tight setting. Even though we obtain Theorem 3.2 as a consequence of Theorem 2.12, the former could be proved directly by the approach of Section 5, forgetting about the tightness constraint.
*Example 20.* For $\ell_1, \dots, \ell_4 \in \mathbb{Z}_{\ge 0} + \frac{1}{2}$, performing the sum in (41) yields a number of planar maps with four labeled faces of odd degrees $2\ell_1, \dots, 2\ell_4$ equal to

$$M(\ell_1, \dots, \ell_4) = (\ell_1 + \dots + \ell_4 - 2) \prod_{i=1}^{4} \binom{2\ell_i - 1}{\ell_i - \frac{1}{2}}. \qquad (42)$$

In particular, we find $M(\frac{3}{2}, \frac{1}{2}, \frac{1}{2}, \frac{1}{2}) = 2$ which, after rooting each face, gives a number of slicings equal to 6 consistently with [Tut62, Section 6].

To our knowledge, this extension of Tutte's slicings formula for general non-bipartite planar maps with prescribed degrees is new. Note that (41) does not hold when the number of faces of odd degree is zero or two, see the discussion in Remark 14 in the tight setting. Even though we obtain Theorem 19 as a consequence of Theorem 13, the former could be proved directly by the approach of Section 5, forgetting about the tightness constraint.

# 4. Bijective proofs in the bipartite and quasi-bipartite cases

## 4.1. Case of maps with one face

In this section, we first present a combinatorial proof of Propositions 5 and 6 by a direct enumeration of the planar tight bipartite maps with one face considered in these propositions. Our approach is inspired from the bijective interpretation of Narayana numbers given in [DZ80, Section 3.2].

More precisely, we wish to enumerate planar bipartite maps with one face of degree $2m$, which are nothing but *plane trees with $m$ edges* ($m \ge 1$), endowed with a distinguished marked vertex labeled 1, and either a second distinguished marked vertex labeled 2 in the context of Proposition 5 or with a marked edge (the root edge) in the context of Proposition 6. These two situations will be referred to respectively as “case (p)” and “case (q)” in the following, to remind the reader that they concern the combinatorial interpretation of $p_k(m)$ and $q_k(m)$ respectively. The trees are finally decorated by the choice of $k$ additional unlabeled marked vertices ($k \ge 0$), with the constraint that *all the leaves of the tree are marked vertices* (either labeled or unlabeled), except possibly the endpoints of the root edge in the case (q) if it happens that such an endpoint is a leaf.

Our proof is based on the classical coding of plane trees by their contour word, here in terms of the letters $U$ (up) and $D$ (down). The following discussion is illustrated on Figure 4. Ignoring the $k$ unlabeled vertex markings for now, the coding that we use here is adapted to trees *with both a marked vertex 1 and a marked oriented edge e* whose choice in cases (p) and (q) will be discussed below. For any such tree, the contour word is obtained as follows: we start from the right of $e$ and visit all the edge sides counterclockwise around the tree. We then record a letter $U$ if we move away from vertex 1 on the tree, and a letter $D$ otherwise. After one turn around the tree, we get a word of $2m$ letters containing $m$ occurrences of $U$ and $m$ occurrences of $D$, since the two sides of any given edge give rise to exactly one $U$ and one $D$. Viewing the successive $U$'s and $D$'s as successive up and down steps, the coding may alternatively be represented
<figure><img src="image_6.png" /><figcaption>Figure 4.1: The coding of planar tight maps with one face with degree 2$m$ (here $m = 11$) by dressed words with letters $U, D_\circ$ and $D_\bullet$. Left: in the context of Proposition 2.4, such a map has $k+2$ (here $k=7$) marked vertices (represented as white, as in Figure 1.1), two of them distinguished as vertex 1 and 2 (represented by a bigger red circle). The associated word, indicated under the map, starts with a $D_\circ$. Right: in the context of Proposition 2.5, the map has $k+1$ marked vertices, one of them distinguished as vertex 1, and a root edge (represented in thick red). The associated word ends with a $U$. We indicated under each word its visualization as a lattice path, where the vertex markings have been transferred to descending steps (as indicated by circles). We also indicated the starting oriented edge $e$ for the contour word of each map.</figcaption></figure>

# 4. Bijective proofs in the bipartite and quasi-bipartite cases

## 4.1. Case of maps with one face

In this section, we first present a combinatorial proof of Propositions 2.4 and 2.5 by a direct enumeration of the planar tight bipartite maps with one face considered in these propositions. Our approach is inspired from the bijective interpretation of Narayana numbers given in [DZ80, Section 3.2].

More precisely, we wish to enumerate planar bipartite maps with one face of degree $2m$, which are nothing but *plane trees with $m$ edges* ($m \ge 1$), endowed with a distinguished marked vertex labeled 1, and either a second distinguished marked vertex labeled 2 in the context of Proposition 2.4 or with a marked edge (the root edge) in the context of Proposition 2.5. These two situations will be referred to respectively as “case (p)” and “case (q)” in the following, to remind the reader that they concern the combinatorial interpretation of $p_k(m)$ and $q_k(m)$ respectively. The trees are finally decorated by the choice of $k$ additional unlabeled marked vertices ($k \ge 0$), with the constraint that *all the leaves of the tree are marked vertices* (either labeled or unlabeled), except possibly the endpoints of the root edge in the case (q) if it happens that such an endpoint is a leaf.
<figure><img src="image_5.png" /><figcaption>Figure 4: The coding of planar tight maps with one face with degree 2m (here m = 11) by dressed words with letters U, D◦ and D•. Left: in the context of Proposition 5, such a map has k + 2 (here k = 7) marked vertices (represented as white, as in Figure 1), two of them distinguished as vertex 1 and 2 (represented by a bigger red circle). The associated word, indicated under the map, starts with a D◦. Right: in the context of Proposition 6, the map has k + 1 marked vertices, one of them distinguished as vertex 1, and a root edge (represented in thick red). The associated word ends with a U. We indicated under each word its visualization as a lattice path, where the vertex markings have been transferred to descending steps (as indicated by circles). We also indicated the starting oriented edge e for the contour word of each map.</figcaption></figure>

as a lattice path of length 2m starting and ending at the same height (a so-called bridge
in the lattice path terminology) and whose nodes correspond to the successive visited
corners around the tree. In this representation, the corners at vertex 1 are associated
with the nodes with minimal height. Setting the minimal height to 0, the height of a
node is nothing but the graph distance to vertex 1 of the vertex incident to the associated
corner. The above coding by words/paths is clearly bijective.

To use this coding in the context of Propositions 5 and 6 where the trees already have
a distinguished vertex 1, we need a canonical prescription for the choice of the oriented
edge *e* at which we start the contour. In case (p) where the tree is endowed with a second
distinguished vertex 2, we take for *e* the first edge of the branch between vertex 2 and
vertex 1, oriented towards 1. Clearly the knowledge of *e* and that of the vertex 2 are
equivalent, but we note that, by construction, the associated word necessarily *starts with*
a *D* in case (p).

In case (q), we first orient the root edge away from vertex 1 and take for *e* the edge
following it along the counterclockwise contour around the tree. The edge *e* is therefore
incident to the endpoint of the root edge further away from vertex 1 and we orient it away
Our proof is based on the classical coding of plane trees by their contour word, here in
terms of the letters U (up) and D (down). The following discussion is illustrated on Figure 4.1.
Ignoring the k unlabeled vertex markings for now, the coding that we use here is adapted to trees
with both a marked vertex 1 and a marked oriented edge e whose choice in cases (p) and (q) will
be discussed below. For any such tree, the contour word is obtained as follows: we start from the
right of e and visit all the edge sides counterclockwise around the tree. We then record a letter U
if we move away from vertex 1 on the tree, and a letter D otherwise. After one turn around the
tree, we get a word of 2m letters containing m occurrences of U and m occurrences of D, since
the two sides of any given edge give rise to exactly one U and one D. Viewing the successive
U's and D's as successive up and down steps, the coding may alternatively be represented as a
lattice path of length 2m starting and ending at the same height (a so-called bridge in the lattice
path terminology) and whose nodes correspond to the successive visited corners around the tree.
In this representation, the corners at vertex 1 are associated with the nodes with minimal height.
Setting the minimal height to 0, the height of a node is nothing but the graph distance to vertex
1 of the vertex incident to the associated corner. The above coding by words/paths is clearly
bijective.

To use this coding in the context of Propositions 2.4 and 2.5 where the trees already have a
distinguished vertex 1, we need a canonical prescription for the choice of the oriented edge *e* at
which we start the contour. In case (p) where the tree is endowed with a second distinguished
vertex 2, we take for *e* the first edge of the branch between vertex 2 and vertex 1, oriented towards
1. Clearly the knowledge of *e* and that of the vertex 2 are equivalent, but we note that, by
construction, the associated word necessarily *starts with a D* in case (p).

In case (q), we first orient the root edge away from vertex 1 and take for *e* the edge following
it along the counterclockwise contour around the tree. The edge *e* is therefore incident to the
endpoint of the root edge further away from vertex 1 and we orient it away from that vertex<fnref n="3" />.
Clearly the knowledge of *e* and that of the root edge are equivalent, but we note that, by con-
struction, the last visited edge side in the contour is that of the root edge itself, going away from
vertex 1, hence the associated coding word necessarily *ends with a U* in case (q).

It remains to introduce the *k* additional vertex markings. The markings may be recorded in
the coding word as follows: every vertex *v* distinct from vertex 1 may be associated bijectively
with a letter *D* of the coding word. Indeed *v* is bijectively associated with the edge *e(v)* incident
to *v* that belongs to the branch between *v* and the vertex 1 and exactly one of the two sides of *e(v)*
is coded by the letter *D*. If *v* is a marked vertex, we transfer its marking to the associated letter
*D*, which we denote by *D<sub>o</sub>* to record the marking. If *v* is not a marked vertex, the associated
letter *D* will be denoted by *D<sub>•</sub>*; so that the letter *D* eventually appears in two flavors *D<sub>o</sub>* and *D<sub>•</sub>*.
leading to dressed words made of the three letters *U*, *D<sub>o</sub>* and *D<sub>•</sub>*. In case (p), we also transfer
the marking of vertex 2, so that the first letter (which we know is originally a *D*) is now a *D<sub>o</sub>*.
The numbers of *U*, *D<sub>o</sub>* and *D<sub>•</sub>* letters are therefore, respectively, *m*, *k+1* and *m-k-1* in case
(p) and *m*, *k* and *m-k* in case (q).

Apart from possibly vertex 2 (which is marked anyway) in case (p) or possibly an endpoint
of the root edge (which needs not being marked) in case (q), any leaf in the tree corresponds

<footnote n="3">³Note that it may happen that the edge *e* be identical to the root edge itself, but with the opposite orientation, in which case the first letter of the word is a *D*. In all other cases the first letter is a *U*.</footnote>
from that vertex<fnref n="2" />. Clearly the knowledge of e and that of the root edge are equivalent, but we note that, by construction, the last visited edge side in the contour is that of the root edge itself, going away from vertex 1, hence the associated coding word necessarily ends with a U in case (q).

It remains to introduce the k additional vertex markings. The markings may be recorded in the coding word as follows: every vertex v distinct from vertex 1 may be associated bijectively with a letter D of the coding word. Indeed v is bijectively associated with the edge e(v) incident to v that belongs to the branch between v and the vertex 1 and exactly one of the two sides of e(v) is coded by the letter D. If v is a marked vertex, we transfer its marking to the associated letter D, which we denote by D◦ to record the marking. If v is not a marked vertex, the associated letter D will be denoted by D•, so that the letter D eventually appears in two flavors D◦ and D•, leading to dressed words made of the three letters U, D◦ and D•. In case (p), we also transfer the marking of vertex 2, so that the first letter (which we know is originally a D) is now a D◦. The numbers of U, D◦ and D• letters are therefore, respectively, m, k + 1 and m − k − 1 in case (p) and m, k and m − k in case (q).

Apart from possibly vertex 2 (which is marked anyway) in case (p) or possibly an endpoint of the root edge (which needs not being marked) in case (q), any leaf in the tree corresponds to a sequence UD in the associated word. Requiring that all leaves be marked boils down to demanding that any D following a U be marked, i.e. the sequence UD• is not allowed in the dressed words.

Altogether, a word coding for a tree in case (p) has the canonical form

$$
D_{\circ} D_{\bullet}^{a_1} U^{b_1} D_{\circ} D_{\bullet}^{a_2} U^{b_2} \cdots D_{\circ} D_{\bullet}^{a_{k+1}} U^{b_{k+1}} \quad (43)
$$

where the $a_i$ and $b_i$ are nonnegative integers such that $a_1 + a_2 + \cdots + a_{k+1} = m - k - 1$
and $b_1 + b_2 + \cdots + b_{k+1} = m$. In other words, the $a_i$ and $b_i$ form weak compositions of
$m - k - 1$ and $m$, respectively, into $k + 1$ summands. There are respectively $\binom{m-1}{k}$ and
$\binom{m+k}{k}$ such compositions, hence the number of trees in case (p) is $\binom{m-1}{k} \binom{m+k}{k} = p_k(m)$
as wanted.

Similarly, a word coding for a tree in case (q) has the canonical form

$$
D_{\bullet}^{a_1} U^{b_1} D_{\circ} D_{\bullet}^{a_2} U^{b_2} D_{\circ} \cdots D_{\bullet}^{a_k} U^{b_k} D_{\circ} D_{\bullet}^{a_{k+1}} U^{b_{k+1}} U \quad (44)
$$

where the $a_i$ and $b_i$ form weak compositions of $m-k$ and $m-1$, respectively, into
$k+1$ summands<fnref n="3" />. There are respectively $\binom{m}{k}$ and $\binom{m+k-1}{k}$ such compositions, hence the
number of trees in case (q) is $\binom{m}{k}\binom{m+k-1}{k} = q_k(m)$ as wanted.

This ends the combinatorial proof of Propositions 5 and 6.

<footnote n="2">²Note that it may happen that the edge e be identical to the root edge itself, but with the opposite orientation, in which case the first letter of the word is a D. In all other cases the first letter is a U.</footnote>

<footnote n="3">³Note that the case $a_1 = b_1 = 0$ corresponds to a word starting with a $D_\circ$ which, cyclically, comes after the last letter $U$. This situation corresponds to the case where the endpoint of the root edge further away from vertex 1 is a leaf and is marked. The case $a_1 > 0$ corresponds to the case where this vertex is a leaf and is unmarked and, finally, the case $a_1 = 0, b_1 > 0$ corresponds to the case where this vertex is not a leaf.</footnote>
to a sequence *UD* in the associated word. Requiring that all leaves be marked boils down to demanding that any *D* following a *U* be marked, i.e. the sequence *UD*<sub>•</sub> is not allowed in the dressed words.

Altogether, a word coding for a tree in case (p) has the canonical form

$$
D_{\circ} D_{\bullet}^{a_1} U^{b_1} D_{\circ} D_{\bullet}^{a_2} U^{b_2} \cdots D_{\circ} D_{\bullet}^{a_{k+1}} U^{b_{k+1}} \quad (4.1)
$$

where the $a_i$ and $b_i$ are nonnegative integers such that $a_1 + a_2 + \cdots + a_{k+1} = m-k-1$ and $b_1 + b_2 + \cdots + b_{k+1} = m$. In other words, the $a_i$ and $b_i$ form weak compositions of $m-k-1$ and $m$, respectively, into $k+1$ summands. There are respectively $\binom{m-1}{k}$ and $\binom{m+k}{k}$ such compositions, hence the number of trees in case (p) is $\binom{m-1}{k} \binom{m+k}{k} = p_k(m)$ as wanted.

Similarly, a word coding for a tree in case (q) has the canonical form

$$
D_{\bullet}^{a_1} U^{b_1} D_{\circ} D_{\bullet}^{a_2} U^{b_2} D_{\circ} \cdots D_{\bullet}^{a_k} U^{b_k} D_{\circ} D_{\bullet}^{a_{k+1}} U^{b_{k+1}} U \quad (4.2)
$$

where the $a_i$ and $b_i$ form weak compositions of $m-k$ and $m-1$, respectively, into $k+1$ summands<fnref n="4" />. There are respectively $\binom{m}{k}$ and $\binom{m+k-1}{k}$ such compositions, hence the number of trees in case (q) is $\binom{m}{k} \binom{m+k-1}{k} = q_k(m)$ as wanted.

This ends the combinatorial proof of Propositions 2.4 and 2.5.

**Quasi-bipartite case.** The proof of Proposition 2.10 is obtained along similar lines, see Figure 4.2 for an example. Indeed, we may transform bijectively a planar map with one face of odd degree $2m$ ($m \in \mathbb{Z}_{\ge 0} + 3/2$), one face of degree 1 and a distinguished vertex 1 into a plane tree with $m - 1/2$ edges with both a marked vertex 1 and a marked oriented edge $e$. This is done by considering the unique vertex incident to the loop formed by the degree 1 face, by marking its incident edge $e$ lying immediately to the left of that loop, with $e$ oriented away from the vertex and finally erasing the loop. We can now use our coding of such pointed rooted trees by words with $2m - 1$ letters. Taking the markings into account gives rise to a dressed word with exactly $k$ occurrences of $D_{\circ}$, $m - 1/2 - k$ occurrences of $D_{\bullet}$ and $m - 1/2$ occurrences of $U$, with no occurrence of the sequence $UD_{\bullet}$, hence with canonical form

$$
D_{\bullet}^{a_1} U^{b_1} D_{\circ} D_{\bullet}^{a_2} U^{b_2} \cdots D_{\circ} D_{\bullet}^{a_{k+1}} U^{b_{k+1}} \quad (4.3)
$$

where the $a_i$ and $b_i$ are nonnegative integers such that $a_1 + a_2 + \cdots + a_{k+1} = m - k - 1/2$
and $b_1 + b_2 + \cdots + b_{k+1} = m - 1/2$. In other words, the $a_i$ and $b_i$ form weak compositions of
$m - k - 1/2$ and $m - 1/2$, respectively, into $k+1$ summands. There are respectively $\binom{m-1/2}{k}$ and
$\binom{m+k-1/2}{k}$ such compositions, hence the number of maps at hand is $\binom{m-1/2}{k} \binom{m+k-1/2}{k} = \tilde{p}_k(m)$
as announced. This holds for $m \ge 3/2$. For $m = 1/2$, the value $\tilde{p}_k(1/2) = \delta_{k,0}$ is consistent
with the fact that there is a unique planar map with two (distinguished) faces of degree 1 and
one marked vertex labeled 1, which is its unique vertex so that the map cannot host any other
marked vertices when $k > 0$.

<footnote n="4">⁴Note that the case $a_1 = b_1 = 0$ corresponds to a word starting with a $D_{\circ}$ which, cyclically, comes after the last letter $U$. This situation corresponds to the case where the endpoint of the root edge further away from vertex 1 is a leaf and is marked. The case $a_1 > 0$ corresponds to the case where this vertex is a leaf and is unmarked and, finally, the case $a_1 = 0, b_1 > 0$ corresponds to the case where this vertex is not a leaf.</footnote>
<figure><img src="image_6.png" /><figcaption>Figure 5: The coding of planar tight maps with one face with odd degree $2m$ (here $m = 23/2$) and one face of degree 1 by dressed words with letters $U$, $D_\circ$ and $D_\bullet$. As in Proposition 11 the map has $k+1$ (here $k=7$) marked vertices, one of them distinguished as vertex 1. We indicated under the map the associated word, of length $2m-1$, and its visualization as a lattice path. We also indicated on the map the starting oriented edge $e$ for the contour word.</figcaption></figure>

**Quasi-bipartite case.** The proof of Proposition 11 is obtained along similar lines, see Figure 5 for an example. Indeed, we may transform bijectively a planar map with one face of odd degree $2m$ ($m \in \mathbb{Z}_{\ge 0} + 3/2$), one face of degree 1 and a distinguished vertex 1 into a plane tree with $m - 1/2$ edges with both a marked vertex 1 and a marked oriented edge $e$. This is done by considering the unique vertex incident to the loop formed by the degree 1 face, by marking its incident edge $e$ lying immediately to the left of that loop, with $e$ oriented away from the vertex and finally erasing the loop. We can now use our coding of such pointed rooted trees by words with $2m-1$ letters. Taking the markings into account gives rise to a dressed word with exactly $k$ occurrences of $D_\circ$, $m - 1/2 - k$ occurrences of $D_\bullet$ and $m - 1/2$ occurrences of $U$, with no occurrence of the sequence $UD_\bullet$, hence with canonical form

$$D_{\bullet}^{a_1} U^{b_1} D_{\circ} D_{\bullet}^{a_2} U^{b_2} \cdots D_{\circ} D_{\bullet}^{a_{k+1}} U^{b_{k+1}} \quad (45)$$

where the $a_i$ and $b_i$ are nonnegative integers such that $a_1 + a_2 + \cdots + a_{k+1} = m - k - 1/2$ and $b_1 + b_2 + \cdots + b_{k+1} = m - 1/2$. In other words, the $a_i$ and $b_i$ form weak compositions of $m - k - 1/2$ and $m - 1/2$, respectively, into $k+1$ summands. There are respectively $\binom{m-1/2}{k}$ and $\binom{m+k-1/2}{k}$ such compositions, hence the number of maps at hand is $\binom{m-1/2}{k} \binom{m+k-1/2}{k} = \tilde{p}_k(m)$ as announced. This holds for $m \ge 3/2$. For $m = 1/2$, the value $\tilde{p}_k(1/2) = \delta_{k,0}$ is consistent with the fact that there is a unique planar map with two (distinguished) faces of degree 1 and one marked vertex labeled 1, which is its unique vertex so that the map cannot host any other marked vertices when $k > 0$.
<figure><img src="image_7.png" /><figcaption>Figure 4.2: The coding of planar tight maps with one face with odd degree $2m$ (here $m = 23/2$) and one face of degree 1 by dressed words with letters $U, D_\circ$ and $D_\bullet$. As in Proposition 2.10 the map has $k+1$ (here $k=7$) marked vertices, one of them distinguished as vertex 1. We indicated under the map the associated word, of length $2m-1$, and its visualization as a lattice path. We also indicated on the map the starting oriented edge $e$ for the contour word.</figcaption></figure>

**4.2. Case of maps with two faces**

Let us now provide a bijective proof of Proposition 2.6. To this end, we will first need to reinterpret slightly the objects counted by $p_k(m)$, $q_k(m)$ that were discussed in the preceding section.

**Definition 4.1.** For given integers $a \ge 1$ and $b \ge 0$, an $(a, b)$-forest is a tight map with exactly two faces $f, f_*$, such that:

• $f_*$ is a simple face<fnref n="5" /> of degree $a+b$ and one distinguished incident vertex $v_*$,

• the $a$ vertices following and including $v_*$ in counterclockwise order around $f_*$ are not marked.

We call the $a$ vertices referred to above as the *unmarkable* vertices, and the other $b$ vertices are called the *markable* vertices. In the illustrating figures, starting with Figure 4.3, the latter will be represented by white squares, while the former will be represented by crosses. Equivalently, by removing the $a+b$ edges incident to $f_*$, we may view an $(a, b)$-forest as a linearly ordered collection of $a+b$ rooted plane trees starting from the one rooted at $v_*$, whose leaves (non-root vertices of degree 1) are all marked, and such that the roots of the first $a$ trees are unmarked while those of the remaining $b$ trees may be marked or not.

The size of an $(a, b)$-forest is the degree of the face $f$. If we view it as a collection of trees as above, then this size is equal to $2e + a + b$ where $e$ is the total number of edges in the trees composing the forest.

<footnote n="5">⁵We say that a face is *simple* if its contour is a simple cycle, i.e. does not visit a same vertex several times.</footnote>
## 4.2. Case of maps with two faces

Let us now provide a bijective proof of Proposition 7. To this end, we will first need to reinterpret slightly the objects counted by $p_k(m)$, $q_k(m)$ that were discussed in the preceding section.

**Definition 21.** For given integers $a \ge 1$ and $b \ge 0$, an $(a, b)$-forest is a tight map with exactly two faces $f, f_*$, such that:

* $f_*$ is a simple face of degree $a+b$ and one distinguished incident vertex $v_*$,

* the $a$ vertices following and including $v_*$ in counterclockwise order around $f_*$ are not marked.

We call the $a$ vertices referred to above as the *unmarkable vertices*, and the other $b$ vertices are called the *markable vertices*. In the illustrating figures, starting with Figure 6, the latter will be represented by white squares, while the former will be represented by crosses. Equivalently, by removing the $a+b$ edges incident to $f_*$, we may view an $(a, b)$-forest as a linearly ordered collection of $a+b$ rooted plane trees starting from the one rooted at $v_*$, whose leaves (non-root vertices of degree 1) are all marked, and such that the roots of the first $a$ trees are unmarked while those of the remaining $b$ trees may be marked or not.

The size of an $(a, b)$-forest is the degree of the face $f$. If we view it as a collection of trees as above, then this size is equal to $2e + a + b$ where $e$ is the total number of edges in the trees composing the forest.

We now describe two simple bijections, illustrated on Figure 7, linking the numbers $p_k(m)$ and $q_k(m)$ to the forests discussed above. First, recall from Proposition 5 the interpretation of $p_k(m)$ as counting tight bipartite planar maps with one face $f$ of degree $2m$ and $k+2$ distinct marked vertices, of which exactly two are labeled as 1 and 2. There is a natural operation consisting in cutting open the branch $\gamma$ linking the distinguished vertices, into a simple face $f_*$ of degree $2d$, where $d \ge 1$ is the graph distance between these vertices. In doing so, we duplicate the vertices lying on the path $\gamma$, except its extremities, into “left and right” copies, and in case some of these vertices are marked, we always decide to transfer the mark to the left copy. The vertex initially distinguished and labeled as 1 is then renamed as $v_*$ and seen as unmarked, while we remove the mark and label on the vertex initially labeled 2. The result is then a $(d+1, d-1)$-forest. Conversely, given a $(d+1, d-1)$-forest for some $d \ge 1$, we can glue together the $r$-th edge of $f_*$ in counterclockwise order starting from $v_*$ with the opposite $(2d-r+1)$-th one, for $r \in \{1, 2, \dots, d\}$, relabel $v_*$ as vertex 1 and the diametrally opposite vertex of $f_*$, lying at distance $d$ from $v_*$, as vertex 2, and finally, after gluing the vertices in pairs along the contour of $f_*$, transferring to the newly created vertices the marks carried by all markable vertices. By construction, every markable vertex is matched to an unmarkable vertex, and this operation is the inverse of the cutting procedure described above. Finally, these operations preserve the number $k$ of marked (unlabeled) vertices, and are size-preserving in the sense that the degree $2m$ of the unique face of the map to be cut corresponds to the size of the resulting forest.
<figure><img src="image_8.png" /><figcaption>Figure 4.3: Left: an example of a (4, 2)-forest, with 9 marked vertices and size 28. The marked vertices are represented as white, as in Figure 1.1. Note that none of the first 4 vertices arriving in counterclockwise order after $v_*$ are marked, while the following 2 comprise one marked and one unmarked vertex. Right: a schematic, generic representation of a (4, 2)-forest, where the grey blobs represent tree components (that may be reduced to a single root vertex) and white squares represent markable roots, while crosses represent unmarkable roots.</figcaption></figure>

We now describe two simple bijections, illustrated on Figure 4.4, linking the numbers $p_k(m)$ and $q_k(m)$ to the forests discussed above. First, recall from Proposition 2.4 the interpretation of $p_k(m)$ as counting tight bipartite planar maps with one face $f$ of degree $2m$ and $k+2$ distinct marked vertices, of which exactly two are labeled as 1 and 2. There is a natural operation consisting in cutting open the branch $\gamma$ linking the distinguished vertices, into a simple face $f_*$ of degree $2d$, where $d \ge 1$ is the graph distance between these vertices. In doing so, we duplicate the vertices lying on the path $\gamma$, except its extremities, into “left and right” copies (upon orienting $\gamma$ from vertex 1 to vertex 2), and in case some of these vertices are marked, we always decide to transfer the mark to the left copy. The vertex initially distinguished and labeled as 1 is then renamed as $v_*$ and seen as unmarked, while we remove the mark and label on the vertex initially labeled 2. The result is then a $(d+1, d-1)$-forest. Conversely, given a $(d+1, d-1)$-forest for some $d \ge 1$, we can glue together the $r$-th edge of $f_*$ in counterclockwise order starting from $v_*$ with the opposite $(2d-r+1)$-th one, for $r \in \{1, 2, \dots, d\}$, relabel $v_*$ as vertex 1 and the diametrally opposite vertex of $f_*$, lying at distance $d$ from $v_*$, as vertex 2, and finally, after gluing the vertices in pairs along the contour of $f_*$, transferring to the newly created vertices the marks carried by all markable vertices. By construction, every markable vertex is matched to an unmarkable vertex, and this operation is the inverse of the cutting procedure described above. Finally, these operations preserve the number $k$ of marked (unlabeled) vertices, and are size-preserving in the sense that the degree $2m$ of the unique face of the map to be cut corresponds to the size of the resulting forest.

Similarly, recall from Proposition 2.5 that $q_k(m)$ enumerates rooted tight bipartite planar maps with one face $f$ of degree $2m$ and $k+1$ distinct marked vertices, exactly one of them being distinguished and labeled as vertex 1. Let $v$ be the vertex incident to the root edge of such
<figure><img src="image_7.png" /><figcaption>Figure 6: Left: an example of a (4, 2)-forest, with 9 marked vertices and size 28. The marked vertices are represented as white, as in Figure 1. Note that none of the first 4 vertices arriving in counterclockwise order after $v_*$ are marked, while the following 2 comprise one marked and one unmarked vertex. Right: a schematic, generic representation of a (4, 2)-forest, where the grey blobs represent tree components (that may be reduced to a single root vertex) and white squares represent markable roots, while crosses represent unmarkable roots.</figcaption></figure>

Similarly, recall from Proposition 6 that $q_k(m)$ enumerates rooted tight bipartite planar maps with one face $f$ of degree $2m$ and $k+1$ distinct marked vertices, exactly one of them being distinguished and labeled as vertex 1. Let $v$ be the vertex incident to the root edge of such a map, and which is further away from vertex 1. Again, we cut open along the branch from vertex 1 to $v$, with length $d \ge 1$ say, creating a simple face $f_*$ of degree $2d$. We transfer the marks along this path to the left copies of the vertices created in the cutting operation, and if $v$ happens to be marked, we keep this mark. Finally, we remove the mark on vertex 1 and rename it as $v_*$. This results in a $(d, d)$-forest, since now the vertex diametrically opposite to $v_*$ in $f_*$ is a markable vertex. This operation is clearly invertible by a similar gluing operation as above, and it preserves the number of marked unlabeled vertices as well as the degree of $f$. We may conclude with the following statement.

**Proposition 22.** For integers $m \ge 1$ and $k \ge 0$, the number $p_k(m)$ (resp. $q_k(m)$) is the cardinality of the set of $(d+1, d-1)$-forests (resp. $(d, d)$-forests) with size $2m$ and $k$ marked unlabeled vertices, where $d$ can take any value in $\mathbb{Z}_{>0}$.

Our bijective proof of Proposition 7 will consist in showing that a tight map with two faces $f_1, f_2$ of respective degrees $2m_1, 2m_2$, and with $k$ unlabeled marked vertices and one extra distinguished marked vertex with label 1 can be decomposed uniquely and bijectively into a pair of tight maps consisting in

* a $(d_1 + 1, d_1 - 1)$-forest with $k_1$ marked vertices
<figure><img src="image_9.png" /><figcaption>Figure 4.4: The cutting operation turning tight maps with one face into forests. On the left, tight maps counted by $p_k(m)$ are cut into $(d+1, d-1)$ forests, and on the right, rooted tight maps counted by $q_k(m)$ become $(d, d)$-forests.</figcaption></figure>

a map, and which is further away from vertex 1. Again, we cut open along the branch from vertex 1 to $v$, with length $d \ge 1$ say, creating a simple face $f_*$ of degree $2d$. We transfer the marks along this path to the left copies of the vertices created in the cutting operation, and if $v$ happens to be marked, we keep this mark. Finally, we remove the mark on vertex 1 and rename it as $v_*$. This results in a $(d, d)$-forest, since now the vertex diametrically opposite to $v_*$ in $f_*$ is a markable vertex. This operation is clearly invertible by a similar gluing operation as above, and it preserves the number of marked unlabeled vertices as well as the degree of $f$. We may conclude with the following statement.

**Proposition 4.2.** For integers $m \ge 1$ and $k \ge 0$, the number $p_k(m)$ (resp. $q_k(m)$) is the cardinality of the set of $(d+1, d-1)$-forests (resp. $(d, d)$-forests) with size $2m$ and $k$ marked unlabeled vertices, where $d$ can take any value in $\mathbb{Z}_{>0}$.

Our bijective proof of Proposition 2.6 will consist in showing that a tight map with two faces $f_1, f_2$ of respective degrees $2m_1, 2m_2$, and with $k$ unlabeled marked vertices and one extra distinguished marked vertex with label 1 can be decomposed uniquely and bijectively into a pair of tight maps consisting in

* a $(d_1 + 1, d_1 - 1)$-forest with $k_1$ marked vertices

* a $(d_2, d_2)$-forest with $k_2$ marked vertices

where $d_1, d_2 \ge 1$ and $k_1 + k_2 = k$. By Proposition 4.2 and the definition (2.5) of $p_k(m_1, m_2)$, this immediately implies Proposition 2.6.

Given an $(a, b)$-forest and an integer $c$ such that $1 \le c \le \min(a-1, b)$, the *c-partial gluing* of the forest is the map obtained by gluing the $r$-th edge following $v_*$ in counterclockwise order around $f_*$ with the opposite $(a+b+1-r)$-th one, for $r \in \{1, 2, \dots, c\}$, and transferring any
<figure><img src="image_8.png" /><figcaption>Figure 7: The cutting operation turning tight maps with one face into forests. On the left, tight maps counted by $p_k(m)$ are cut into $(d+1, d-1)$ forests, and on the right, rooted tight maps counted by $q_k(m)$ become $(d, d)$-forests.</figcaption></figure>

• a $(d_2, d_2)$-forest with $k_2$ marked vertices

where $d_1, d_2 \ge 1$ and $k_1 + k_2 = k$. By Proposition 22 and the definition (6) of $p_k(m_1, m_2)$, this immediately implies Proposition 7.

Given an $(a, b)$-forest and an integer $c$ such that $1 \le c \le \min(a-1, b, (a+b-1)/2)$, the *c-partial gluing* of the forest is the map obtained by gluing the $r$-th edge following $v_*$ in counterclockwise order around $f_*$ with the opposite $(a+b-r+1)$-th one, for $r \in \{1, 2, \dots, c\}$, and transferring any mark on the markable vertices to the resulting glued vertices. The vertex inherited from $v_*$ in the new map is distinguished and labeled as vertex 1, while the last vertex to be glued, lying at distance $c$ from $v_*$, is distinguished and called $v_{**}$. By the assumption that $c \le (a+b-1)/2$, the resulting map still has two faces which we call $f, f_{**}$, where $f_{**}$ is the “remnant” of $f_*$, of degree $a+b-2c$, and we do not change the name for the exterior face since it has the same contour information as the original face. Moreover, the assumption that $c \le \min(a-1, b)$ implies that every markable vertex is glued to an unmarkable vertex.

The obtained map is then an $(a', b')$*-forest* with $a' = a-c-1$ and $b' = b-c+1$, according to the following definition, similar to Definition 21:

**Definition 23.** For integers $a \ge 0$ and $b \ge 1$, an $(a, b)$*-forest* is a tight map with exactly two faces $f, f_{**}$, such that:

• $f_{**}$ is a simple face of degree $a+b$,

• there is an extra distinguished vertex labeled 1 incident to the face $f$, and we let $v_{**}$ be the vertex incident to $f_{**}$ that is closest to 1,

• the $a$ vertices following and excluding $v_{**}$ in counterclockwise order around $f_{**}$ are not marked.
<figure><img src="image_10.png" /><figcaption>Figure 4.5: The 2-partial gluing of a (5, 3)-forest yielding a (2, 2)*-forest.</figcaption></figure>

mark on the markable vertices to the resulting glued vertices. The vertex inherited from $v_*$ in the new map is distinguished and labeled as vertex 1, while the last vertex to be glued, lying at distance $c$ from $v_*$, is distinguished and called $v_{**}$. Since $c \le \min(a-1, b)$, some edges remain unglued, and the resulting map still has two faces which we call $f$, $f_{**}$, where $f_{**}$ is the “remnant” of $f$, of degree $a+b-2c$, and we do not change the name for the exterior face since it has the same contour information as the original face. Moreover, the assumption that $c \le \min(a-1, b)$ implies that every markable vertex is glued to an unmarkable vertex.

The obtained map is then an $(a', b')^*$-forest with $a' = a-c-1$ and $b' = b-c+1$, according to the following definition, similar to Definition 4.1:

**Definition 4.3.** For integers $a \ge 0$ and $b \ge 1$, an $(a, b)^*$-forest is a tight map with exactly two faces $f, f_{**}$, such that:

* $f_{**}$ is a simple face of degree $a+b$,

* there is an extra distinguished vertex labeled 1 incident to the face $f$, and we let $v_{**}$ be the vertex incident to $f_{**}$ that is closest to 1,

* the $a$ vertices following and excluding $v_{**}$ in counterclockwise order around $f_{**}$ are not marked.

The partial gluing operation is clearly invertible, by cutting along the simple path of length $c$ from $v_{**}$ to the distinguished labeled vertex 1. See Figure 4.5 for an illustration.

*Proof of Proposition 2.6.* Let $m_1, m_2, d_1, d_2$ be positive integers, and $k_1, k_2$ be non-negative integers. Suppose we are given a $(d_1+1, d_1-1)$ forest $f_1$ with size $2m_1$ and $k_1$ marked vertices, and a $(d_2, d_2)$ forest $f_2$ with size $2m_2$ and $k_2$ marked vertices. We let $v_{*,1}, v_{*,2}$ be the distinguished vertices in these maps. As explained above, we wish to use these pieces to build a planar tight map with two faces of degrees $2m_1, 2m_2$, with $k = k_1 + k_2$ marked unlabeled vertices, and with one extra distinguished vertex. There are three possible situations, illustrated in Figure 4.6.
<figure><img src="image_9.png" /><figcaption>Figure 8: The 2-partial gluing of a (5, 3)-forest yielding a (2, 2)*-forest.</figcaption></figure>

The partial gluing operation is clearly invertible, by cutting along the simple path of
length $c$ from $v_{**}$ to the distinguished labeled vertex 1. See Figure 8 for an illustration.

*Proof of Proposition 7.* Let $m_1, m_2, d_1, d_2$ be positive integers, and $k_1, k_2$ be non-negative integers. Suppose we are given a $(d_1+1, d_1-1)$ forest $f_1$ with size $2m_1$ and $k_1$ marked vertices, and a $(d_2, d_2)$ forest $f_2$ with size $2m_2$ and $k_2$ marked vertices. We let $v_{*,1}, v_{*,2}$ be the distinguished vertices in these maps. As explained above, we wish to use these pieces to build a planar tight map with two faces of degrees $2m_1, 2m_2$, with $k = k_1 + k_2$ marked unlabeled vertices, and with one extra distinguished vertex. There are three possible situations, illustrated in Figure 9.

Suppose first that $d_1 = d_2 = d$. Then we can glue together the two simple boundaries of $\mathbf{f}_1$ and $\mathbf{f}_2$, in such a way that $v_{*,1}$ and $v_{*,2}$ are glued together into a single distinguished vertex labeled 1. The next $d$ unmarkable vertices after $v_{*,1}$ (resp. the last $d-1$ markable vertices) of $\mathbf{f}_1$ are then glued to the last $d$ markable vertices (resp. the $d-1$ unmarkable vertices following $v_{*,2}$) of $\mathbf{f}_2$. The result is a tight map with two faces of degrees $2m_1, 2m_2$, and with $k_1 + k_2$ marked unlabeled vertices as well as a distinguished marked vertex labeled 1 lying on the boundary of both faces.

Suppose next that $d_1 > d_2$. In this case, we first perform the $(d_1 - d_2)$-partial gluing of $\mathbf{f}_1$, resulting in a $(d_2, d_2)^*$-forest (with distinguished vertex called $v_{*,1}$), which we glue along the simple face of $\mathbf{f}_2$ by identifying $v_{*,1}$ and $v_{*,2}$. Note that each of the $d_2$ markable vertices on either side of the gluing is matched with an unmarkable vertex on the other side. The resulting map has a distinguished labeled vertex incident to $f_1$ but not to $f_2$.

Finally, the case $d_2 > d_1$ is similar, except that we now perform the $(d_2 - d_1)$-partial gluing of $\mathbf{f}_2$ first, resulting in a $(d_1 - 1, d_1 + 1)^*$-forest, whose $d_1 + 1$ markable vertices and $d_1 - 1$ unmarkable vertices are matched with the $d_1 + 1$ unmarkable vertices and $d_1 - 1$ markable vertices of $\mathbf{f}_1$. The resulting map has a distinguished labeled vertex incident to $f_2$ but not to $f_1$.

The above construction can clearly be inverted by the following cutting operation.
Start from a tight map **m** with two faces $f_1, f_2, k$ marked vertices and one extra distin-
Suppose first that $d_1 = d_2 = d$. Then we can glue together the two simple boundaries of $f_1$ and $f_2$, in such a way that $v_{*,1}$ and $v_{*,2}$ are glued together into a single distinguished vertex labeled 1. The next $d$ unmarkable vertices after $v_{*,1}$ (resp. the last $d-1$ markable vertices) of $f_1$ are then glued to the last $d$ markable vertices (resp. the $d-1$ unmarkable vertices following $v_{*,2}$) of $f_2$. The result is a tight map with two faces of degrees $2m_1, 2m_2$, and with $k_1 + k_2$ marked unlabeled vertices as well as a distinguished marked vertex labeled 1 lying on the boundary of both faces.

Suppose next that $d_1 > d_2$. In this case, we first perform the $(d_1 - d_2)$-partial gluing of $f_1$, resulting in a $(d_2, d_2)^*$-forest (with distinguished vertex called $v_{*,1}$), which we glue along the simple face of $f_2$ by identifying $v_{*,1}$ and $v_{*,2}$. Note that each of the $d_2$ markable vertices on either side of the gluing is matched with an unmarkable vertex on the other side. The resulting map has a distinguished labeled vertex incident to $f_1$ but not to $f_2$.

Finally, the case $d_2 > d_1$ is similar, except that we now perform the $(d_2 - d_1)$-partial gluing of $f_2$ first, resulting in a $(d_1 - 1, d_1 + 1)^*$-forest, whose $d_1 + 1$ markable vertices and $d_1 - 1$ unmarkable vertices are matched with the $d_1 + 1$ unmarkable vertices and $d_1 - 1$ markable vertices of $f_1$. The resulting map has a distinguished labeled vertex incident to $f_2$ but not to $f_1$.

The above construction can clearly be inverted by the following cutting operation. Start from a tight map $\mathfrak{m}$ with two faces $f_1, f_2, k$ marked vertices and one extra distinguished vertex labeled 1. We observe that such a map is unicyclic, and therefore contains a unique simple cycle $\gamma$, of length $2d \ge 2$ say. We cut along this cycle, separating $f_1$ and $f_2$. Formally, this means that we associate with $\mathfrak{m}$ the two maps $\mathfrak{m}_1, \mathfrak{m}_2$ respectively obtained by removing all edges and vertices that are incident to $f_2$ but not $f_1$ on the one hand, and $f_1$ but not $f_2$ on the other hand. Note that for $i \in \{1, 2\}$, $\mathfrak{m}_i$ is made of the initial face $f_i$ and has an “exterior” simple face $f_{*,i}$ which is the remnant of the face $f_{3-i}$. All marked vertices of $\mathfrak{m}$ that are not on $\gamma$ are naturally transferred to either $\mathfrak{m}_1$ or $\mathfrak{m}_2$, and we need a convention to transfer the marked vertices lying on $\gamma$.

To this end, we distinguish the cases as above depending on whether the vertex labeled 1 is incident to both $f_1, f_2$, to $f_1$ but not $f_2$, or to $f_2$ but not $f_1$. In the first case, the cutting operation splits the labeled vertex 1 into two copies $v_{*,1}, v_{*,2}$, respectively belonging to $\mathfrak{m}_1$ and $\mathfrak{m}_2$, that we declare unmarkable. The $d$ vertices following $v_{*,1}$ in counterclockwise order around $f_{*,1}$ are declared unmarkable, as well as the $d-1$ vertices following $v_{*,2}$ in counterclockwise order around $f_{*,2}$, and all other vertices incident to $f_{*,1}$ and $f_{*,2}$ are declared markable. In this way, every vertex of $\gamma$ has been split into a a markable/unmarkable pair in $\mathfrak{m}_1$ and $\mathfrak{m}_2$. We then transfer the marks that were located on the vertices $\gamma$ to the unique associated markable duplicate. This gives the wanted pair $(f_1, f_2) = (\mathfrak{m}_1, \mathfrak{m}_2)$ of $(d+1, d-1)$- and $(d, d)$-forests, of sizes $2m_1$ and $2m_2$, which receive $k_1$ and $k_2$ marked unlabeled vertices with $k_1 + k_2 = k$.

In the second case, we let $v_{**}$ be the vertex incident to $f_2$ that is closest to the distinguished vertex 1. When cutting along the cycle $\gamma$, this vertex is separated into two copies, one called $v_{**,1}$ is incident to $f_{*,1}$ and is declared markable, as well as the $d-1$ vertices preceding it around $f_{*,1}$, the other called $v_{*,2}$ is incident to $f_{2,*}$ and is declared unmarkable, as well as the $d-1$ vertices following it around $f_{*,2}$. The map $\mathfrak{m}_2 =: f_2$ is then a $(d, d)$-forest, while we further cut $\mathfrak{m}_1$ along the simple path of length $d' \ge 1$ from $v_{**,1}$ to the distinguished vertex 1, hence creating a $(d+d'+1, d+d'-1)$-forest $f_1$, attributing the marked vertices in the natural way (this operation is the reverse of the $d'$-partial gluing of the resulting forest).
guished vertex labeled 1. We observe that such a map is unicyclic, and therefore contains a unique simple cycle $\gamma$, of length $2d \ge 2$ say. We cut along this cycle, separating $f_1$ and $f_2$. Formally, this means that we associate with $\mathbf{m}$ the two maps $\mathbf{m}_1, \mathbf{m}_2$ respectively obtained by removing all edges and vertices that are incident to $f_2$ but not $f_1$ on the one hand, and $f_1$ but not $f_2$ on the other hand. Note that for $i \in \{1, 2\}$, $\mathbf{m}_i$ is made of the initial face $f_i$ and has an "exterior" simple face $f_{*,i}$ which is the remnant of the face $f_{3-i}$. All marked vertices of $\mathbf{m}$ that are not on $\gamma$ are naturally transferred to either $\mathbf{m}_1$ or $\mathbf{m}_2$, and we need a convention to transfer the marked vertices lying on $\gamma$.

To this end, we distinguish the cases as above depending on whether the vertex labeled 1 is incident to both $f_1, f_2$, to $f_1$ but not $f_2$, or to $f_2$ but not $f_1$. In the first case, the cutting operation splits the labeled vertex 1 into two copies $v_{*,1}, v_{*,2}$, respectively belonging to $\mathbf{m}_1$ and $\mathbf{m}_2$, that we declare unmarkable. The $d$ vertices following $v_{*,1}$ in counterclockwise order around $f_{*,1}$ are declared unmarkable, as well as the $d-1$ vertices following $v_{*,2}$ in counterclockwise order around $f_{*,2}$, and all other vertices incident to $f_{*,1}$ and $f_{*,2}$ are declared markable. In this way, every vertex of $\gamma$ has been split into a a markable/unmarkable pair in $\mathbf{m}_1$ and $\mathbf{m}_2$. We then transfer the marks that were located on the vertices $\gamma$ to the unique associated markable duplicate. This gives the wanted pair $(\mathbf{f}_1, \mathbf{f}_2) = (\mathbf{m}_1, \mathbf{m}_2)$ of $(d+1, d-1)$- and $(d, d)$-forests, of sizes $2m_1$ and $2m_2$, which receive $k_1$ and $k_2$ marked unlabeled vertices with $k_1 + k_2 = k$.

In the second case, we let $v_{**}$ be the vertex incident to $f_2$ that is closest to the distinguished vertex 1. When cutting along the cycle $\gamma$, this vertex is separated into two copies, one called $v_{**1}$ is incident to $f_{*,1}$ and is declared markable, as well as the $d-1$ vertices preceding it around $f_{*,1}$, the other called $v_{*,2}$ is incident to $f_{2,*}$ and is declared unmarkable, as well as the $d-1$ vertices following it around $f_{*,2}$. The map $\mathbf{m}_2 =: \mathbf{f}_2$ is then a $(d, d)$-forest, while we further cut $\mathbf{m}_1$ along the simple path of length $d' \ge 1$ from $v_{**1}$ to the distinguished vertex 1, hence creating a $(d+d'+1, d+d'-1)$-forest $\mathbf{f}_1$, attributing the marked vertices in the natural way (this operation is the reverse of the $d'$-partial gluing of the resulting forest).

The situation in the third case is similar, with a slightly different convention for the markable and unmarkable vertices, as illustrated in Figure 9. $\square$

**Quasi-bipartite case.** We now consider the quasi-bipartite case where one assumes that $m_1, m_2 \in \mathbb{Z}_{\ge 0} + 1/2$, that is, $2m_1$ and $2m_2$ are odd integers, and aim at proving Proposition 10. A discussion parallel to the above applies, except that the separating cycle between the two faces of a tight map with faces of degrees $2m_1$ and $2m_2$ will have an odd length, say $2d-1$ for some $d \ge 1$.

In this situation, unfolding the above argument *mutatis mutandis*, there is now a canonical decomposition of a planar tight map with two faces of degrees $2m_1, 2m_2$, with $k$ marked unlabeled vertices and one extra distinguished vertex labeled 1 into a pair formed of a $(d_1, d_1-1)$-forest and a $(d_2, d_2-1)$-forest, for some $d_1, d_2 \ge 1$, respectively with sizes $2m_1$ and $2m_2$ and with $k_1$ and $k_2$ marked vertices, where $k_1 + k_2 = k$. The situation is therefore more symmetric since the glued forests are of the same nature and have the same numbers of markable vertices.
The situation in the third case is similar, with a slightly different convention for the markable and unmarkable vertices, as illustrated in Figure 4.6. □

**Quasi-bipartite case.** We now consider the quasi-bipartite case where one assumes that $m_1, m_2 \in \mathbb{Z}_{\ge 0} + 1/2$, that is, $2m_1$ and $2m_2$ are odd integers, and aim at proving Proposition 2.9. A discussion parallel to the above applies, except that the separating cycle between the two faces of a tight map with faces of degrees $2m_1$ and $2m_2$ will have an odd length, say $2d-1$ for some $d \ge 1$.

In this situation, unfolding the above argument *mutatis mutandis*, there is now a canonical decomposition of a planar tight map with two faces of degrees $2m_1, 2m_2$, with $k$ marked unlabeled vertices and one extra distinguished vertex labeled 1 into a pair formed of a $(d_1, d_1-1)$-forest and a $(d_2, d_2-1)$-forest, for some $d_1, d_2 \ge 1$, respectively with sizes $2m_1$ and $2m_2$ and with $k_1$ and $k_2$ marked vertices, where $k_1 + k_2 = k$. The situation is therefore more symmetric since the glued forests are of the same nature and have the same numbers of markable vertices.

By performing the $(d_i-1)$-partial gluing of the $(d_i, d_i-1)$-forest of size $2m_i$ with $k_i$ marked vertices, we see that such objects are in bijection with tight maps with one face of degree $2m_i$, one face of degree 1, and $k_i$ marked vertices, which are precisely counted by $\tilde{p}_{k_i}(m_i)$, as discussed in Section 4.1. Together with the above, this shows that $\tilde{p}_k(m_1, m_2)$ indeed enumerates the wanted quasi-bipartite planar tight maps with two faces, as stated in Proposition 2.9.

**4.3. Case of pointed rooted maps via slices**

We now aim at proving Proposition 2.7, interpreting $(n-1)! q_{n-1}(m_1, m_2, \dots, m_n)$ as the number of pointed rooted planar tight bipartite maps with $n$ labeled boundaries of respective lengths $2m_1, \dots, 2m_n$, where $m_1, \dots, m_n$ are integers not all equal to zero. To this end, we will need the slice decomposition developed in [BG12, BG14]. Here, we follow closely the presentation of [Bou19, Section 2.2] and adapt it to the tight setting.

A *slice* is a planar map with one distinguished *exterior face*, whose contour carries three distinguished (but not necessarily distinct) corners *A*, *B* and *C* appearing in this counterclockwise order around the map, that split the contour in three parts:

• the contour segment *AB*, called the *left boundary*<fnref n="6" />, which is a geodesic path,

• the contour segment *AC*, called the *right boundary*, which is the unique geodesic path between its two endpoints, and intersects the left boundary only at *A*,

• the contour segment *BC*, called the *base*.

The length of the base (i.e. the number of edges on the corresponding contour segment, counted with multiplicity) is called the *width* of the slice. The length of the left boundary is called the *depth*, and the depth minus the length of the right boundary is called the *tilt*. The corner *A* is called the *apex*.

<footnote n="6">⁶Note that, in the accepted denominations “left boundary” and “right boundary”, the term “boundary” has a meaning different from that in the rest of the paper.</footnote>
By performing the $(d_i - 1)$-partial gluing of the $(d_i, d_i - 1)$-forest of size $2m_i$ with $k_i$ marked vertices, we see that such objects are in bijection with tight maps with one face of degree $2m_i$, one face of degree 1, and $k_i$ marked vertices, which are precisely counted by $\tilde{p}_{k_i}(m_i)$, as discussed in Section 4.1. Together with the above, this shows that $\tilde{p}_k(m_1, m_2)$ indeed enumerates the wanted quasi-bipartite planar tight maps with two faces, as stated in Proposition 10.

### 4.3. Case of pointed rooted maps via slices

We now aim at proving Proposition 17, interpreting $(n-1)!q_{n-1}(m_1, m_2, \dots, m_n)$ as the number of pointed rooted planar tight bipartite maps with $n$ labeled boundaries of respective lengths $2m_1, \dots, 2m_n$, where $m_1, \dots, m_n$ are integers not all equal to zero. To this end, we will need the slice decomposition developed in [BG12; BG14]. Here, we follow closely the presentation of [Bou19, Section 2.2] and adapt it to the tight setting.

A *slice* is a planar map with one distinguished *exterior face*, whose contour carries three distinguished (but not necessarily distinct) corners *A*, *B* and *C* appearing in this counterclockwise order around the map, that split the contour in three parts:

• the contour segment *AB*, called the *left boundary*<fnref n="4" />, which is a geodesic path,

• the contour segment *AC*, called the *right boundary*, which is the unique geodesic path between its two endpoints, and intersects the left boundary only at *A*,

• the contour segment *BC*, called the *base*.

The length of the base (i.e. the number of edges on the corresponding contour segment, counted with multiplicity) is called the *width* of the slice. The length of the left boundary is called the *depth*, and the depth minus the length of the right boundary is called the *tilt*. The corner *A* is called the *apex*.

A slice of width 1 is called *elementary*. The tilt of an elementary slice is necessarily in {1, 0, -1}. By the uniqueness property of the right boundary, there is a unique elementary slice of tilt -1, called the *trivial slice*, which consists of a single edge with extremities *A* = *B* and *C*. The trivial slice differs from the *empty slice* consisting in a single edge with extremities *B* and *A* = *C*, which has tilt +1. If we restrict our attention to bipartite maps, as is the case in this section, there are no slices with tilt 0.

Finally, a *tight slice* is a slice, elementary or not, that carries some marked vertices, in such a way that

• all vertices of degree 1 distinct from those incident to *A*, *B* and *C* are marked,

• the *right boundary* carries no marked vertices.

Note that the vertex incident to *B* may possibly be marked, but not those incident to *A* and *C*, even if those vertices have degree one. In particular, the empty slice comes with

<footnote n="4">⁴Note that, in the accepted denominations “left boundary” and “right boundary”, the term “boundary” has a meaning different from that in the rest of the paper.</footnote>
<figure><img src="image_11.png" /><figcaption>Figure 4.6: Decomposition of a tight map with two faces $f_1, f_2$, $k$ marked unlabeled vertices and one extra distinguished labeled vertex, into two forests. The top left, top right, and bottom pictures represent respectively the situations where the distinguished labeled vertex belongs to the common boundary of $f_1$ and $f_2$, is incident to $f_1$ but not $f_2$, and is incident to $f_2$ but not $f_1$. We denote by $2d$ the length of the cycle separating $f_1$ and $f_2$. In the first case, the map is decomposed into a $(d+1, d-1)$ forest glued to a $(d, d)$ forest. In the second case, the map is decomposed into the $(d_1-d)$-partial gluing of a $(d_1+1, d_1-1)$-forest with a $(d, d)$-forest, and in the third case, it is instead a $(d+1, d-1)$-forest glued to the $(d_2-d)$-partial gluing of a $(d_2, d_2)$-forest. Note that, on this picture, the counterclockwise order along the face $f_{*,2}$, which is the “exterior” simple face of $m_2$, appears to be clockwise, since $f_{*,2}$ is the unbounded face in the plane embedding.</figcaption></figure>
<figure><img src="image_10.png" /><figcaption>Figure 9: Decomposition of a tight map with two faces $f_1, f_2, k$ marked unlabeled vertices and one extra distinguished labeled vertex, into two forests. The top left, top right, and bottom pictures represent respectively the situations where the distinguished labeled vertex belongs to the common boundary of $f_1$ and $f_2$, is incident to $f_1$ but not $f_2$, and is incident to $f_2$ but not $f_1$. We denote by $2d$ the length of the cycle separating $f_1$ and $f_2$. In the first case, the map is decomposed into a $(d+1, d-1)$ forest glued to a $(d, d)$ forest. In the second case, the map is decomposed into the $(d_1-d)$-partial gluing of a $(d_1+1, d_1-1)$-forest with a $(d, d)$-forest, and in the third case, it is instead a $(d+1, d-1)$-forest glued to the $(d_2-d)$-partial gluing of a $(d_2, d_2)$-forest. Note that, on this picture, the counterclockwise order along the face $f_{*,2}$, which is the "exterior" simple face of $m_2$, appears to be clockwise, since $f_{*,2}$ is the unbounded face in the plane embedding.</figcaption></figure>
<figure><img src="image_12.png" /><figcaption>Figure 4.7: The different types of tight elementary slices, with marked vertices shown in white. Left: the trivial slice. Center: the empty slice, in its unmarked and marked versions. Right: a non-empty tight elementary slice</figcaption></figure>

A slice of width 1 is called *elementary*. The tilt of an elementary slice is necessarily in {1, 0, -1}. By the uniqueness property of the right boundary, there is a unique elementary slice of tilt -1, called the *trivial slice*, which consists of a single edge with extremities $A = B$ and $C$. The trivial slice differs from the *empty slice* consisting in a single edge with extremities $B$ and $A = C$, which has tilt +1. If we restrict our attention to bipartite maps, as is the case in this section, there are no slices with tilt 0.

Finally, a *tight slice* is a slice, elementary or not, that carries some marked vertices, in such a way that

• all vertices of degree 1 distinct from those incident to $A$, $B$ and $C$ are marked,

• the right boundary carries no marked vertices.

Note that the vertex incident to $B$ may possibly be marked, but not those incident to $A$ and $C$, even if those vertices have degree one. In particular, the empty slice comes with two tight versions, depending on whether the vertex incident to $B$ is marked or not, and we will call the marked version the *marked empty slice*, which will play an important role later on. See Figure 4.7 for an illustration of the different types of tight elementary slices.

**Pointed rooted maps and elementary slices.** There is a simple one-to-one correspondence between pointed rooted planar bipartite maps on the one hand$^7$, and non-empty, bipartite elementary slices of tilt 1 on the other hand. Starting from a pointed rooted bipartite map $m$ with root $e$ and distinguished vertex $v$, we can perform the opening operation $O(m, e)$ that opens the

<footnote>$^7$Here, as for tight maps, we use the slightly unusual convention that a rooted map is a map with a distinguished, non oriented edge.</footnote>
<figure><img src="image_11.png" /><figcaption>Figure 10: The different types of tight elementary slices, with marked vertices shown in white. Left: the trivial slice. Center: the empty slice, in its unmarked and marked versions. Right: a non-empty tight elementary slice</figcaption></figure>

two tight versions, depending on whether the vertex incident to $B$ is marked or not, and we will call the marked version the *marked empty slice*, which will play an important role later on. See Figure 10 for an illustration of the different types of tight elementary slices.

**Pointed rooted maps and elementary slices.** There is a simple one-to-one correspondence between pointed rooted planar bipartite maps on the one hand<fnref n="5" />, and non-empty, bipartite elementary slices of tilt 1 on the other hand. Starting from a pointed rooted bipartite map **m** with root **e** and distinguished vertex **v**, we can perform the opening operation $O(\mathbf{m}, \mathbf{e})$ that opens the edge **e** into an exterior face of degree 2. We let **b** and **c** be the two corners incident to this new face, where **c** is closest from **v**. We then cut open the map along the leftmost geodesic<fnref n="6" /> $\gamma$ from **c** to **v**, hence enlarging the exterior face. The resulting map is an elementary bipartite slice of tilt 1, if we let $B$ be the corner inherited from **b**, $A$ be the unique corner of the exterior face incident to **v**, and $C$ be the corner immediately following $B$ as we walk with the exterior face on the right (so that $C$ is one of the two duplicates of **c** created after cutting). The fact that the right boundary $AC$ is the unique geodesic between these two extremities comes from the fact that $\gamma$ was chosen to be leftmost, and the slice is non-empty because it has at least one inner face, inherited from the map we started with. Conversely, starting from a non-empty elementary bipartite slice of tilt 1, we may glue “isometrically” together the left and right

<footnote n="5">⁵Here, as for tight maps, we use the slightly unusual convention that a rooted map is a map with a distinguished, non oriented edge.</footnote>

<footnote n="6">⁶See for instance [Bou19, Figure 2.1] for a careful definition of the leftmost geodesic from a corner to a vertex.</footnote>
edge *e* into an exterior face of degree 2. We let *b* and *c* be the two corners incident to this new face, where *c* is closest from *v*. We then cut open the map along the leftmost geodesic$^8 \gamma$ from *c* to *v*, hence enlarging the exterior face. The resulting map is an elementary bipartite slice of tilt 1, if we let *B* be the corner inherited from *b*, *A* be the unique corner of the exterior face incident to *v*, and *C* be the corner immediately following *B* as we walk with the exterior face on the right (so that *C* is one of the two duplicates of *c* created after cutting). The fact that the right boundary *AC* is the unique geodesic between these two extremities comes from the fact that $\gamma$ was chosen to be leftmost, and the slice is non-empty because it has at least one inner face, inherited from the map we started with. Conversely, starting from a non-empty elementary bipartite slice of tilt 1, we may glue "isometrically" together the left and right boundaries starting from the apex. This results in a bipartite map pointed at the vertex *v* incident to the apex, and with a face of degree 2 whose contour is made of the base and of the first edge of the left boundary incident to *B*, which are necessarily distinct since the slice is non-empty. We may finally glue these two edges together into a single edge *e*, at which we root the resulting map.

These two operations are inverse of one another. They specialize to a correspondence be-
tween pointed rooted planar *tight* bipartite maps and non-empty *tight* bipartite slices of tilt 1,
if we take the convention that the marks of marked vertices in $\mathfrak{m}$ that belong to the leftmost
geodesic $\gamma$ considered above should systematically be transferred to the left boundary of the
slice.

**Decomposing a slice into a path decorated with elementary slices.** Next, we discuss the decomposition of a bipartite slice $s$ of width $w \in \mathbb{Z}_{>0}$ and tilt $t \in \mathbb{Z}$ into a collection of elementary slices. We list the corners of the base as $c_0 = B, c_1, \dots, c_w = C$, walking with the exterior face on the right. We let $\ell_i = d(c_0, A) - d(c_i, A)$ for $i \in \{0, 1, \dots, w\}$, where $d$ is the graph distance in $s$, and the distance between two corners is defined as the distance between their incident vertices. In particular, $\ell_w = t$ is the tilt of $s$, and $L = (\ell_0, \ell_1, \dots, \ell_w)$ is a walk on $\mathbb{Z}$ with increments $\ell_i - \ell_{i-1} \in \{-1, +1\}$, that we will systematically identify with the lattice path made of the union of segments $[(i-1, \ell_{i-1}), (i, \ell_i)]$, $1 \le i \le n$ in the plane.

For every $i \in \{0, 1, \dots, w\}$, we let $\gamma_i$ be the leftmost geodesic from $c_i$ to the apex $A$. In particular, $\gamma_0$ and $\gamma_w$ are respectively the left and right boundary of $s$. For $i \in \{1, 2, \dots, w\}$, we let $v_i'$ be the first vertex common to $\gamma_{i-1}$ and $\gamma_i$. Then the map $s_i'$ delimited by these two geodesics is an elementary bipartite slice with base $c_{i-1}c_i$, with apex $A_i'$ incident to $v_i'$, and with tilt $t_i = \ell_i - \ell_{i-1}$. If $t_i = -1$, in which case we say that $i$ is a *down step*, then $s_i'$ is trivial, while if $t_i = +1$, in which case we call $i$ an *up step*, then $s_i'$ is non-trivial. It may however be the empty slice, precisely when the geodesic $\gamma_{i-1}$ starts by following the base edge from $c_{i-1}$ to $c_i$.

With a bipartite slice $s$ with width $w$ and tilt $t$, we have associated a lattice path $L$ from $(0, 0)$ to $(w, t)$ with increments $\pm 1$, where each of the $(w+t)/2$ up steps $i$ is decorated with a bipartite elementary slice $s'_i$ of tilt 1, while all the $(w-t)/2$ down steps are decorated with the trivial slice, so that these last decorations are in fact irrelevant and can be omitted.

We can invert this decomposition: given a lattice path from (0, 0) to (w, t) whose up steps i are decorated with bipartite elementary slices s'_i of tilt 1 (and where s'_i is the trivial slice if i is a down step), we may associate a slice of width w in the following way. For every down step i, we

<footnote n="8">⁸See for instance [Bou19, Figure 2.1] for a careful definition of the leftmost geodesic from a corner to a vertex.</footnote>
boundaries starting from the apex. This results in a bipartite map pointed at the vertex $v$ incident to the apex, and with a face of degree 2 whose contour is made of the base and of the first edge of the left boundary incident to $B$, which are necessarily distinct since the slice is non-empty. We may finally glue these two edges together into a single edge $e$, at which we root the resulting map.

These two operations are inverse of one another. They specialize to a correspondence between pointed rooted planar *tight* bipartite maps and non-empty *tight* bipartite slices of tilt 1, if we take the convention that the marks of marked vertices in $\mathbf{m}$ that belong to the leftmost geodesic $\gamma$ considered above should systematically be transferred to the left boundary of the slice.

**Decomposing a slice into a path decorated with elementary slices.** Next, we discuss the decomposition of a bipartite slice $\mathbf{s}$ of width $w \in \mathbb{Z}_{>0}$ and tilt $t \in \mathbb{Z}$ into a collection of elementary slices. We list the corners of the base as $c_0 = B, c_1, \dots, c_w = C$, walking with the exterior face on the right. We let $\ell_i = d(c_0, A) - d(c_i, A)$ for $i \in \{0, 1, \dots, w\}$, where $d$ is the graph distance in $\mathbf{s}$, and the distance between two corners is defined as the distance between their incident vertices. In particular, $\ell_w = t$ is the tilt of $\mathbf{s}$, and $L = (\ell_0, \ell_1, \dots, \ell_w)$ is a walk on $\mathbb{Z}$ with increments $\ell_i - \ell_{i-1} \in \{-1, +1\}$, that we will systematically identify with the lattice path made of the union of segments $[(i-1, \ell_{i-1})), (i, \ell_i)]$, $1 \le i \le n$ in the plane.

For every $i \in \{0, 1, \dots, w\}$, we let $\gamma_i$ be the leftmost geodesic from $c_i$ to the apex $A$. In particular, $\gamma_0$ and $\gamma_w$ are respectively the left and right boundary of $\mathbf{s}$. For $i \in \{1, 2, \dots, w\}$, we let $v'_i$ be the first vertex common to $\gamma_{i-1}$ and $\gamma_i$. Then the map $\mathbf{s}'_i$ delimited by these two geodesics is an elementary bipartite slice with base $c_{i-1}c_i$, with apex $A'_i$ incident to $v'_i$, and with tilt $t_i = \ell_i - \ell_{i-1}$. If $t_i = -1$, in which case we say that $i$ is a *down step*, then $\mathbf{s}'_i$ is trivial, while if $t_i = +1$, in which case we call $i$ an *up step*, then $\mathbf{s}'_i$ is non-trivial. It may however be the empty slice, precisely when the geodesic $\gamma_{i-1}$ starts by following the base edge from $c_{i-1}$ to $c_i$.

With a bipartite slice $\mathbf{s}$ with width $w$ and tilt $t$, we have associated a lattice path $L$ from $(0,0)$ to $(w,t)$ with increments $\pm 1$, where each of the $(w+t)/2$ up steps $i$ is decorated with a bipartite elementary slice $\mathbf{s}'_i$ of tilt 1, while all the $(w-t)/2$ down steps are decorated with the trivial slice, so that these last decorations are in fact irrelevant and can be omitted.

We can invert this decomposition: given a lattice path from $(0,0)$ to $(w,t)$ whose up steps $i$ are decorated with bipartite elementary slices $\mathbf{s}'_i$ of tilt 1 (and where $\mathbf{s}'_i$ is the trivial slice if $i$ is a down step), we may associate a slice of width $w$ in the following way. For every down step $i$, we identify the segment $s_i = [(i-1, \ell_{i-1})), (i, \ell_i)]$ of the lattice path with the associated trivial slice $\mathbf{s}'_i$, hence color it in red as in Figure 10. Next, for every up step $i$, we consider an embedding of $\mathbf{s}'_i$ in the plane in which the base edge is the segment $s_i$, and so that the left boundary (resp. the right boundary) is represented as a curve, monotone in its two coordinates, that starts from $(i-1, \ell_{i-1})$ (resp. $(i, \ell_i)$), is entirely contained in $[i-1, i] \times [\ell_{i-1}, \infty)$ (resp. $[i-1, i] \times [\ell_i, \infty))$, and such that its $r$-th vertex, starting from the base, has its ordinate equal to $\ell_{i-1} + r - 1$ (resp. $\ell_i + r - 1$).
identify the segment $s_i = [(i-1, \ell_{i-1}), (i, \ell_i)]$ of the lattice path with the associated trivial slice $s'_i$, hence color it in red as in Figure 4.7. Next, for every up step $i$, we consider an embedding of $s'_i$ in the plane in which the base edge is the segment $s_i$, and so that the left boundary (resp. the right boundary) is represented as a curve, monotone in its two coordinates, that starts from $(i-1, \ell_{i-1})$ (resp. $(i, \ell_i)$), is entirely contained in $[i-1, i] \times [\ell_{i-1}, \infty)$ (resp. $[i-1, i] \times [\ell_i, \infty)$), and such that its $r$-th vertex, starting from the base, has its ordinate equal to $\ell_{i-1} + r - 1$ (resp. $\ell_i + r - 1$). By convention, the edges of the left boundaries of the slices $s'_i$ are declared blue, while the edges of the right boundaries are declared red. Note that if $s'_i$ is an empty slice, then the above operation simply consists in coloring the segment $s_i$ in blue. Then, every red element (either an edge lying on the right boundary of some slice, or the segment associated with a down step of the lattice path), lying in some square $[i-1, i] \times [\ell-1, \ell]$, attempts to be matched to the first available blue edge in some square $[j-1, j] \times [\ell-1, \ell]$ for some $j > i$, and all matched edges are glued together. After this gluing is performed, we obtain a bipartite slice of width $w$ and tilt $t$, where the unmatched edges, i.e. the blue edges which are not preceded by red edges at the same ordinate, and the red edges that are not followed by a blue edge at the same ordinate, form respectively the left and right boundaries.

Let us now discuss how this decomposition behaves with respect to the tightness constraint. We first observe that it associates with a *tight* bipartite slice $s$ of width $w \ge 1$ and tilt $t$ a lattice path $L$ from $(0, 0)$ to $(w, t)$ with $\pm 1$ steps decorated with *tight* elementary bipartite slices. The only ambiguity that should be lifted is how we transfer the marks of marked vertices that belong to the union of leftmost geodesics $\gamma_i$ defined above to exactly one of their duplicates. We choose the duplicate that belongs to the left boundary of the slice $s'_i$, where $i$ is the maximal index such that the marked vertex at hand belongs to $\gamma_{i-1}$. Note that such a maximal index $i$ always exists, since, by definition, tight slices carry no marked vertices on their right boundaries, and that the duplicate of the vertex is different from the apex of $s'_i$ by maximality of $i$. With these conventions, all the slices $s'_i$, $1 \le i \le w$, with transferred marks, are tight slices.

Moreover, there is an additional restriction on the family $L$, $(s'_i, 1 \le i \le w)$ that guarantees that the original slice be tight, i.e. that it contains no undesired unmarked vertices of degree 1. Observe that, in the above correspondence, the vertex incident to a corner $c_i$, $i \in \{1, \dots, w-1\}$ of the base distinct from the extremities will have degree 1 precisely in the situation where $i$ is a down step and $i+1$ is an up step decorated with the empty slice. Indeed, if the vertex $v_i$ incident to $c_i$ has degree 1, then the vertices $v_{i-1}$ and $v_{i+1}$ incident to the corners $c_{i-1}$ and $c_{i+1}$ are the same vertex, and therefore the geodesics $\gamma_i$ and $\gamma_{i+1}$ delimit the empty slice, since $\gamma_i$ meets $\gamma_{i+1}$ after one single step. Conversely, in the gluing procedure, if a down step $i$ is immediately followed by an up step $i+1$, then the “red” segment $[(i-1, \ell_{i-1}), (i, \ell_{i-1}-1)]$ associated with the down-step $i$ will be matched to the first edge of the left boundary of the slice $s'_{i+1}$. This will result in a vertex of degree 1 precisely when this first edge is equal to the base edge, and the only elementary slice of tilt 1 with this property is the empty slice. Consequently, in a tight slice, every such up step $i+1$ is decorated with a slice $s'_i$ that is either non-empty, or is the *marked empty slice*, that is the empty slice with marked base vertex $B$.

By forgetting the redundant information of up steps that are decorated with unmarked empty slices, that is, by letting $(s_j, 1 \le j \le k)$ be the sequence $(s'_i, 1 \le i \le w)$ whose trivial and unmarked empty elements have been removed, we obtain the following result.
By convention, the edges of the left boundaries of the slices $s'_i$ are declared blue, while the edges of the right boundaries are declared red. Note that if $s'_i$ is an empty slice, then the above operation simply consists in coloring the segment $s_i$ in blue. Then, every red element (either an edge lying on the right boundary of some slice, or the segment associated with a down step of the lattice path), lying in some square $[i-1, i] \times [\ell-1, \ell]$, attempts to be matched to the first available blue edge in some square $[j-1, j] \times [\ell-1, \ell]$ for some $j > i$, and all matched edges are glued together. After this gluing is performed, we obtain a bipartite slice of width $w$ and tilt $t$, where the unmatched edges, i.e. the blue edges which are not preceded by red edges at the same ordinate, and the red edges that are not followed by a blue edge at the same ordinate, form respectively the left and right boundaries.

Let us now discuss how this decomposition behaves with respect to the tightness constraint. We first observe that it associates with a *tight* bipartite slice $\mathbf{s}$ of width $w \ge 1$ and tilt $t$ a lattice path $L$ from $(0, 0)$ to $(w, t)$ with $\pm 1$ steps decorated with *tight* elementary bipartite slices. The only ambiguity that should be lifted is how we transfer the marks of marked vertices that belong to the union of leftmost geodesics $\gamma_i$ defined above to exactly one of their duplicates. We choose the duplicate that belongs to the left boundary of the slice $s'_i$, where $i$ is the maximal index such that the marked vertex at hand belongs to $\gamma_{i-1}$. Note that such a maximal index $i$ always exists, since, by definition, tight slices carry no marked vertices on their right boundaries, and that the duplicate of the vertex is different from the apex of $s'_i$ by maximality of $i$. With these conventions, all the slices $s'_i$, $1 \le i \le w$, with transferred marks, are tight slices.

Moreover, there is an additional restriction on the family $L$, $(s'_i, 1 \le i \le w)$ that guarantees that the original slice be tight, i.e. that it contains no undesired unmarked vertices of degree 1. Observe that, in the above correspondence, the vertex incident to a corner $c_i, i \in \{1, \dots, w-1\}$ of the base distinct from the extremities will have degree 1 precisely in the situation where $i$ is a down step and $i+1$ is an up step decorated with the empty slice. Indeed, if the vertex $v_i$ incident to $c_i$ has degree 1, then the vertices $v_{i-1}$ and $v_{i+1}$ incident to the corners $c_{i-1}$ and $c_{i+1}$ are the same vertex, and therefore the geodesics $\gamma_i$ and $\gamma_{i+1}$ delimit the empty slice, since $\gamma_i$ meets $\gamma_{i+1}$ after one single step. Conversely, in the gluing procedure, if a down step $i$ is immediately followed by an up step $i+1$, then the “red” segment $[(i-1, \ell_{i-1}), (i, \ell_{i-1}-1)]$ associated with the down-step $i$ will be matched to the first edge of the left boundary of the slice $s'_{i+1}$. This will result in a vertex of degree 1 precisely when this first edge is equal to the base edge, and the only elementary slice of tilt 1 with this property is the empty slice. Consequently, in a tight slice, every such up step $i+1$ should never be decorated with the empty slice $s'_i$, unless its base vertex $B$ is marked, i.e. it may be decorated with the *marked empty slice*.

By forgetting the redundant information of up steps that are decorated with unmarked empty slices, that is, by letting $(s_j, 1 \le j \le k)$ be the sequence $(s'_i, 1 \le i \le w)$ whose trivial and unmarked empty elements have been removed, we obtain the following result.

**Proposition 24.** *There is a one-to-one correspondence between tight bipartite slices of width $w$ and tilt $t$ on the one hand, and pairs of the form $(L, (s_j, 1 \le j \le k))$ on the other hand, where:*
**Proposition 4.4.** There is a one-to-one correspondence between tight bipartite slices of width $w$ and tilt $t$ on the one hand, and pairs of the form $(L, (s_j, 1 \le j \le k))$ on the other hand, where:

* $L$ is a lattice path from $(0,0)$ to $(w,t)$ with $\pm 1$ steps, that has $k$ marked up steps, in such a way that every up step immediately following a down step is marked,

* for $1 \le j \le k$, $s_j$ is either the marked empty slice or a tight bipartite elementary slice with at least one inner face.

Now observe that if $s$ is a non-empty bipartite slice with tilt $1$, then the base edge is incident to an inner face. Calling $2m > 0$ the degree of this face, and after removing the base edge, we obtain a bipartite slice with width $2m - 1$ and tilt $1$. This simple operation preserves the tight characters of the maps at hand, which implies the following:

**Corollary 4.5.** There is a one-to-one correspondence between non-trivial, non-empty tight bipartite elementary slices, whose inner face incident to the base edge has degree $2m > 0$ on the one hand, and pairs of the form $(L, (s_j, 1 \le j \le k))$ on the other hand, where $k$ is some non-negative integer and:

* $L$ is a lattice path from $(0,0)$ to $(2m-1, 1)$ with $\pm 1$ steps, that has $k$ marked up steps, in such a way that every up step immediately following a down step is marked,

* for $1 \le j \le k$, $s_j$ is either the marked empty slice or a tight bipartite elementary slice with at least one inner face.

Finally, by convention, we extend the above correspondence by associating with the marked empty slice the pair $((0,0), \emptyset)$ consisting of the trivial lattice path of length zero, with no marks.

By iterating the decomposition of this corollary, i.e. inductively replacing each non-empty elementary slice in the above decomposition by a lattice path with some marked up steps, and an ordered family of as many elementary slices, we obtain a plane tree (where the plane order is induced by the order of the up steps to which the slices are connected). See Figure 4.9 for an illustration. For integers $m_1, \dots, m_n$ not all equal to 0, let $\mathcal{T}(m_1, \dots, m_n)$ be the family of pairs $(\mathbf{t}, (L_i)_{1 \le i \le n})$ where:

* $\mathbf{t}$ is a rooted plane tree with vertices labeled by $\{1, 2, \dots, n\}$, and, denoting by $k_i$ the number of children of the vertex labeled $i$ in $\mathbf{t}$,

* if $m_i > 0$ then $L_i$ is a lattice path from $(0,0)$ to $(2m_i - 1, 1)$ with $k_i$ marked up steps, such that all up steps immediately following a down step are marked,

* if $m_i = 0$ then $L_i$ is the trivial path $((0,0))$, in which case necessarily $k_i = 0$.

**Corollary 4.6.** For any non-negative integers $m_1, \dots, m_n$ not all equal to 0, the iterated slice decomposition yields a one-to-one correspondence between pointed rooted planar tight maps with $n$ labeled boundaries of respective lengths $2m_1, \dots, 2m_n$, and the set $\mathcal{T}(m_1, \dots, m_n)$.
* $L$ is a lattice path from $(0,0)$ to $(w,t)$ with $\pm 1$ steps, that has $k$ marked up steps, in such a way that every up step immediately following a down step is marked,

* for $1 \le j \le k$, $s_j$ is either the marked empty slice or a tight bipartite elementary slice with at least one inner face.

Now observe that if $s$ is a non-empty bipartite slice with tilt 1, then the base edge is incident to an inner face. Calling $2m > 0$ the degree of this face, and after removing the base edge, we obtain a bipartite slice with width $2m-1$ and tilt 1. This simple operation preserves the tight characters of the maps at hand, which implies the following:

**Corollary 25.** There is a one-to-one correspondence between non-trivial, non-empty tight bipartite elementary slices, whose inner face incident to the base edge has degree $2m > 0$ on the one hand, and pairs of the form $(L, (s_j, 1 \le j \le k))$ on the other hand, where $k$ is some non-negative integer and:

* $L$ is a lattice path from $(0,0)$ to $(2m-1,1)$ with $\pm 1$ steps, that has $k$ marked up steps, in such a way that every up step immediately following a down step is marked,

* for $1 \le j \le k$, $s_j$ is either the marked empty slice or a tight bipartite elementary slice with at least one inner face.

Finally, by convention, we extend the above correspondence by associating with the marked empty slice the pair $((0,0)), \emptyset$) consisting of the trivial lattice path of length zero, with no marks.

By iterating the decomposition of this corollary, i.e. inductively replacing each non-empty elementary slice in the above decomposition by a lattice path with some marked up steps, and an ordered family of as many elementary slices, we obtain a plane tree (where the plane order is induced by the order of the up steps to which the slices are connected). See Figure 12 for an illustration. For integers $m_1, \dots, m_n$ not all equal to 0, let $\mathcal{T}(m_1, \dots, m_n)$ be the family of pairs $(\mathbf{t}, (L_i)_{1 \le i \le n})$ where:

* $\mathbf{t}$ is a rooted plane tree with vertices labeled by $\{1,2,\dots,n\}$, and, denoting by $k_i$ the number of children of the vertex labeled $i$ in $\mathbf{t}$,

* if $m_i > 0$ then $L_i$ is a lattice path from $(0,0)$ to $(2m_i-1,1)$ with $k_i$ marked up steps, such that all up steps immediately following a down step are marked,

* if $m_i = 0$ then $L_i$ is the trivial path $((0,0))$, in which case necessarily $k_i = 0$.

**Corollary 26.** For every choice of non-negative integers $m_1, \dots, m_n$ not all equal to 0, the iterated slice decomposition yields a one-to-one correspondence between pointed rooted planar tight maps with $n$ labeled boundaries of respective lengths $2m_1, \dots, 2m_n$, and the set $\mathcal{T}(m_1, \dots, m_n)$.
<figure><img src="image_13.png" /><figcaption>Figure 4.8: Illustration of the decomposition of a non-empty elementary tight slice of tilt 1 into a lattice path decorated with elementary slices. The middle picture shows the decomposition along the leftmost geodesics started from the corners of the inner face incident to the base. The right-hand side shows the result of the decomposition. Note that the trivial and empty slices $s'_2, s'_4$ and $s'_5$ may be discarded, at the price of transferring their color to the corresponding step of the lattice path, while the two other slices are non-empty and therefore correspond to marked up steps. Note also that the second up step, which is consecutive to the first down step, is marked, as is required.</figcaption></figure>

We are now in position to prove Proposition 2.7. Note that the number of lattice paths of length $2m-1$ from 0 to 1 that has exactly $k$ marked up steps, including all up steps immediately following down steps, is precisely the number $q_k(m)$. Indeed, they are exactly counted by the words discussed in Section 4.1, with $m-1$ letters $U$, $m-k$ letters $D_\bullet$ and $k$ letters $D_\circ$, with forbidden subword $UD_\bullet$ (up to flipping upside down the lattice paths to better match the interpretation of the letters $U, D$). In fact, this even holds for $m=k=0$ since in this case $q_k(0) = \delta_{k0}$, so we interpret $q_0(0)$ combinatorially as counting the unique marked empty slice.

We now proceed to enumerating the elements of the set $T(m_1, \dots, m_n)$. By [BM14, Section 5, Equation (18)], for a given $n$-uple $(k_1, \dots, k_n)$ of non-negative integers, if $k_1+\dots+k_n = n-1$ then there are exactly $(n-1)!$ rooted labeled plane trees on the vertex set $\{1, 2, \dots, n\}$ such that vertex $i$ has $k_i$ children for all $i = 1, \dots, n$, and there are no such tree otherwise. For any such tree $t$, there are $\prod_{i=1}^n q_{k_i}(m_i)$ possible choices of marked lattice paths $L_i$, $1 \le i \le n$ such that
<figure><img src="image_12.png" /><figcaption>Figure 11: Illustration of the decomposition of a non-empty elementary tight slice of tilt 1 into a lattice path decorated with elementary slices. The middle picture shows the decomposition along the leftmost geodesics started from the corners of the inner face incident to the base. The right-hand side shows the result of the decomposition. Note that the trivial and empty slices $s'_2, s'_4$ and $s'_5$ may be discarded, at the price of transferring their color to the corresponding step of the lattice path, while the two other slices are non-empty and therefore correspond to marked up steps. Note also that the second up step, which is consecutive to the first down step, is marked, as is required.</figcaption></figure>

We are now in position to prove Proposition 17. Note that the number of lattice paths of length $2m-1$ from $0$ to $1$ that has exactly $k$ marked up steps, including all up steps immediately following down steps, is precisely the number $q_k(m)$. Indeed, they are exactly counted by the words discussed in Section 4.1, with $m-1$ letters $U$, $m-k$ letters $D_\bullet$ and $k$ letters $D_\circ$, with forbidden subword $UD_\bullet$ (up to flipping upside down the lattice paths to better match the interpretation of the letters $U, D$). In fact, this even holds for $m=k=0$ since in this case $q_k(0) = \delta_{k0}$, so we interpret $q_0(0)$ combinatorially as counting the unique marked empty slice.

We now proceed to enumerating the elements of the set $T(m_1, \dots, m_n)$. By [BM14, Section 5, Equation (18)], for a given $n$-uple $(k_1, \dots, k_n)$ of non-negative integers, if $k_1 + \dots + k_n = n-1$ then there are exactly $(n-1)!$ rooted labeled plane trees on the vertex set $\{1, 2, \dots, n\}$ such that vertex $i$ has $k_i$ children for all $i = 1, \dots, n$, and there are no such tree otherwise. For any such tree $t$, there are $\prod_{i=1}^n q_{k_i}(m_i)$ possible choices of marked lattice paths $L_i$, $1 \le i \le n$ such that $(t, (L_i)_{1\le i\le n})$ belongs to $T(m_1, \dots, m_n)$.
<figure><img src="image_14.png" /><figcaption>Figure 4.9: Iterating the slice decomposition yields a plane tree whose vertices are decorated by marked paths. On this picture, we do not represent the lattice paths, but encode them using a color code on polygons drawn around the vertices of t, where black/blue correspond to marked/unmarked up steps and red to down steps. Note that some of the terminal nodes of t correspond to non-trivial paths with no marked steps, while some others correspond to the trivial path, represented as white dots, and are associated in turn to the marked vertices of the original tight slice.</figcaption></figure>

$(t, (L_i)_{1 \le i \le n})$ belongs to $\mathcal{T}(m_1, \dots, m_n)$. This finally explains the wanted formula

$$ 
\begin{align} 
N_{0,n+2}(2m_1, \dots, 2m_2, 2, 0) &= (n-1)! \sum_{\substack{k_1, \dots, k_n \ge 0 \\ k_1 + \dots + k_n = n-1}} \prod_{i=1}^{n} q_{k_i}(m_i) \tag{4.4} \\ 
&= (n-1)! q_{n-1}(m_1, \dots, m_n), 
\end{align} 
$$

which concludes the proof.

## 4.4. General case

We will now prove Theorem 2.3 in all generality, as well as its quasi-bipartite analog, Theorem 2.8. As the case of maps with one face was already treated in Section 4.1, it suffices to treat the case where the first and second boundaries are faces, that is when $m_1, m_2 > 0$. To this end, we will combine the ideas of Sections 4.2 and 4.3 via the following:

**Proposition 4.7.** Let $m_1, m_2$ be positive integers or half-integers and let $m_3, \dots, m_n$ be non-negative integers ($n \ge 3$). Then, there is a bijection between the set of planar tight maps with $n$
<figure><img src="image_13.png" /><figcaption>Figure 12: Iterating the slice decomposition yields a plane tree whose vertices are decorated by marked paths. On this picture, we do not represent the lattice paths, but encode them using a color code on polygons drawn around the vertices of t, where black/blue correspond to marked/unmarked up steps and red to down steps. Note that some of the terminal nodes of t correspond to non-trivial paths with no marked steps, while some others correspond to the trivial path, represented as white dots, and are associated in turn to the marked vertices of the original tight slice.</figcaption></figure>

This finally explains the wanted formula

$$ 
\begin{aligned}
N_{0,n+2}(2m_1, \dots, 2m_2, 2, 0) &= (n-1)! \sum_{\substack{k_1, \dots, k_n \ge 0 \\ k_1 + \dots + k_n = n-1}} \prod_{i=1}^{n} q_{k_i}(m_i) \\
&= (n-1)! q_{n-1}(m_1, \dots, m_n),
\end{aligned} 
\quad (46) 
$$

which concludes the proof.

## 4.4. General case

We will now prove Theorem 4 in all generality, as well as its quasi-bipartite analog, Theorem 9. As the case of maps with one face was already treated in Section 4.1, it suffices to treat the case where the first and second boundaries are faces, that is when $m_1, m_2 > 0$. To this end, we will combine the ideas of Sections 4.2 and 4.3 via the following:
boundaries labeled from 1 to $n$ with respective lengths $2m_1, 2m_2, \dots, 2m_n$, and the set of pairs $(\mathbf{m}_{12}, \mathbf{s})$ such that there exists $k \in \{0, \dots, n-3\}$ for which:

• $\mathbf{m}_{12}$ is a planar tight two-face map, with two faces of respective degrees $2m_1$ and $2m_2$, and $k+1$ distinct marked vertices, one of them distinguished,

• $\mathbf{s} = (\mathbf{s}_1, \dots, \mathbf{s}_{k+1})$ is a $(k+1)$-tuple of slices such that:

- for each $j = 1, \dots, k+1$, $\mathbf{s}_j$ is either the marked empty slice or a tight bipartite elementary slice with at least one inner face, whose inner faces and marked vertices are labeled by integers in $\{3, \dots, n\}$,

- each $i \in \{3, \dots, n\}$ appears in exactly one $\mathbf{s}_i$ and labels an inner face of degree $2m_i$ for $m_i > 0$, or a marked vertex for $m_i = 0$,

- the label 3 appears in the first slice $\mathbf{s}_1$.

Before proving this proposition, let us see how it implies Theorems 2.3 and 2.8. We start with the former: our purpose is to enumerate the pairs $(\mathbf{m}_{12}, \mathbf{s})$ of the proposition when $m_1$ and $m_2$ are integers. For a fixed $k \in \{0, \dots, n-3\}$, the number of possible maps $\mathbf{m}_{12}$ is equal to $p_k(m_1, m_2)$ by Proposition 2.6, which we proved in Section 4.2. As for the number of possible $\mathbf{s}$, it is given by a slight variant of the reasoning in Section 4.3. Indeed, by recursively decomposing each slice $\mathbf{s}_j$ into a tree of lattice paths, we see that the set of possible $(k+1)$-tuples $\mathbf{s}$ is in bijection with the set $\mathcal{F}_{k+1}(m_3, \dots, m_n)$ defined as the set of pairs $(\mathbf{f}, (L_i)_{3 \le i \le n})$ where:

• $\mathbf{f}$ is a plane forest with $k+1$ connected components, i.e. a $(k+1)$-tuple of rooted plane trees, whose vertices are labeled by $\{3, \dots, n\}$, the label 3 appearing in the first component,

• denoting by $k_i$ the number of children of the vertex labeled $i$ in $\mathbf{f}$:

- if $m_i > 0$ then $L_i$ is a lattice path from $(0, 0)$ to $(2m_i - 1, 1)$ with $k_i$ marked up steps, such that all up steps immediately following a down step are marked,

- if $m_i = 0$ then $L_i$ is the trivial path $\{(0, 0)\}$, in which case necessarily $k_i = 0$.

Note that $\mathcal{F}_1(m_3, \dots, m_n)$ is nothing but the set $\mathcal{T}(m_3, \dots, m_n)$ as defined in Section 4.3. By Proposition A.1 of Appendix A below, for a given $n$-uple $(k_3, \dots, k_n)$, if $k_3 + \dots + k_n = n-3-k$ then there are exactly $(n-3)!$ plane forests on the vertex set $\{3, \dots, n\}$ with $k+1$ components, the first of which contains the label 3, and such that vertex $i$ has $k_i$ children for all $i = 3, \dots, n$, and there are no such forests otherwise. For any such forest $\mathbf{f}$, there are $\prod_{i=3}^n q_{k_i}(m_i)$ possible choices of marked lattice paths $L_i$, $3 \le i \le n$ such that $(\mathbf{f}, (L_i)_{3 \le i \le n})$ belongs to $\mathcal{F}_{k+1}(m_3, \dots, m_n)$. This gives

$$ \begin{align} \mathrm{Card} (\mathcal{F}_{k+1}(m_3, \dots, m_n)) &= (n-3)! \sum_{\substack{k_3, \dots, k_n \ge 0 \\ k_3 + \dots + k_n = n-3-k}} \prod_{i=3}^{n} q_{k_i}(m_i) \tag{4.5} \\ &= (n-3)! q_{n-3-k}(m_3, \dots, m_n). \end{align} $$