# On quasi-polynomials counting planar tight maps

Jérémie Bouttier Université Paris-Saclay, CNRS, CEA, Institut de physique
théorique, 91191, Gif-sur-Yvette, France Emmanuel Guitter11footnotemark: 1
Grégory Miermont ENS de Lyon, UMPA, CNRS UMR 5669, 46 allée d’Italie, 69364
Lyon Cedex 07, France

###### 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},\ldots,d_{n})$ of planar tight maps with $n$ labeled faces of
prescribed degrees $d_{1},\ldots,d_{n}$, where a marked vertex is seen as a
face of degree $0$. It is a quasi-polynomial in $(d_{1},\ldots,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.

###### Contents

  1. 1 Introduction
    1. 1.1 Tight maps
    2. 1.2 Lattice count polynomials
  2. 2 Main results
    1. 2.1 Polynomials counting planar tight bipartite or quasi-bipartite maps
      1. 2.1.1 Definition and properties of the polynomials
      2. 2.1.2 Enumeration results in the bipartite case
      3. 2.1.3 Enumeration results in the quasi-bipartite case
    2. 2.2 Quasi-polynomials counting planar tight maps with more odd faces
  3. 3 Connection with the enumeration of non necessarily tight maps
    1. 3.1 Equivalence with Tutte’s slicings formula in the (quasi-)bipartite case
    2. 3.2 A non-bipartite slicings formula
  4. 4 Bijective proofs in the bipartite and quasi-bipartite cases
    1. 4.1 Case of maps with one face
    2. 4.2 Case of maps with two faces
    3. 4.3 Case of pointed rooted maps via slices
    4. 4.4 General case
  5. 5 Bijective proofs for non necessarily bipartite maps
    1. 5.1 Petal trees
    2. 5.2 Petal necklaces
    3. 5.3 Tight slices
    4. 5.4 General maps
  6. 6 Conclusion
  7. A Enumeration of one- and two-type labeled plane forests
  8. B Symmetrizing the planar lattice count quasi-polynomials

##  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 $\mathbf{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 $\mathbf{m}$ has marked or labeled
elements (vertices or faces), then $O(\mathbf{m},e)$ naturally inherits these
elements. We say that a map $\mathbf{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 $\mathbf{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.

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}$.

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 $\mathbf{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^{\prime}$ be
the space obtained from $S$ by removing one point (i.e. creating a puncture)
inside each of the boundaries of $\mathbf{m}$. A boundary of $\mathbf{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^{\prime}$. 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.

Figure 2: Blowing a boundary-vertex into a face of degree $0$ with one
puncture.

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 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^{\prime}$.
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},\ldots,d_{n}$ not all
equal to $0$ and for any nonnegative integer $g$, we let
$N_{g,n}(d_{1},d_{2},\ldots,d_{n})$ be the number of tight maps of genus $g$,
with $n$ labeled boundaries of respective lengths $d_{1},d_{2},\ldots,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\geq 3$, while the only
tight maps with two boundaries having a non-trivial automorphism group are
(genus $0$) cycles of length $p\geq 2$, with automorphism group
$\mathbb{Z}/p\mathbb{Z}$ (such maps are thus weighted by $1/p$).

The numbers $N_{g,n}(d_{1},\ldots,d_{n})$ have been extensively studied in
particular by Norbury and Do [Nor10, Nor13, DN11]111Here, 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.. Norbury proved
that $N_{g,n}(d_{1},\ldots,d_{n})$ is a quasi-polynomial in the variables
$d_{1}^{2},\ldots,d_{n}^{2}$, depending on their parities. This means that for
every $k\in\\{0,1,\ldots,n\\}$, there exists a polynomial
$\mathsf{N}^{(k)}_{g,n}(x_{1},\ldots,x_{n})$ in the variables
$x_{1}^{2},\ldots,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},\ldots,d_{k}$ are odd and the numbers $d_{k+1},\ldots,d_{n}$ are even,
then

$N_{g,n}(d_{1},\ldots,d_{n})=\mathsf{N}^{(k)}_{g,n}(d_{1},\ldots,d_{n})\,.$
(1)

For $k$ odd, these polynomials are equal to $0$. In fact, the first two papers
mentioned above assume that $d_{1},\ldots,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,\ldots,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},\ldots,d_{n})$ is a piecewise quasi-polynomial in
$d_{1},\ldots,d_{n}$, see for instance the discussion around [Bud20a,
Proposition 4] (in the case $b=0$). Therefore, it is surprising that
$N_{g,n}(d_{1},\ldots,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 in 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 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 multivariate 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 $\mathsf{N}^{(0)}_{0,n}$ and $\mathsf{N}^{(2)}_{0,n}$, 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 $\mathsf{N}^{(0)}_{0,n}$. 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\geq 0$, we set

$\begin{split}&p_{k}(m):=\frac{1}{(k!)^{2}}\,\prod_{i=1}^{k}\left(m^{2}-i^{2}\right)=\binom{m-1}{k}\binom{m+k}{k}\\\
&q_{k}(m):=\frac{1}{(k!)^{2}}\,\prod_{i=0}^{k-1}\left(m^{2}-i^{2}\right)=\binom{m}{k}\binom{m+k-1}{k}\\\
\end{split}$ (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),\qquad k\geq 0$ (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

$\displaystyle(k+1)p_{k+1}(m)$
$\displaystyle=(m-k-1)p_{k}(m)+\sum_{j=1}^{m-1}(2j)p_{k}(j)$ (4)
$\displaystyle(k+1)q_{k+1}(m)$
$\displaystyle=(m-k)q_{k}(m)+\sum_{j=1}^{m-1}(2j)q_{k}(j)$ (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},\ldots,m_{n}$ as follows: for any
integer $k\geq 0$ and any integer $n\geq 1$, we set

$\begin{split}&p_{k}(m_{1},m_{2},\ldots,m_{n}):=\sum_{k_{1},k_{2},\ldots,k_{n}\geq
0\atop k_{1}+k_{2}+\cdots+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},\ldots,m_{n}):=\sum_{k_{1},k_{2},\ldots,k_{n}\geq 0\atop
k_{1}+k_{2}+\cdots+k_{n}=k}q_{k_{1}}(m_{1})q_{k_{2}}(m_{2})\cdots
q_{k_{n}}(m_{n}).\\\ \end{split}$ (6)

(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},\ldots,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},\ldots,m_{n})=q_{k}(m_{1},m_{2},\ldots,m_{n})$ (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\geq 0$, $p_{k}$ and $q_{k}$ are symmetric functions. In
other words, for any integer $n\geq 1$, $p_{k}(m_{1},m_{2},\ldots,m_{n})$ and
$q_{k}(m_{1},m_{2},\ldots,m_{n})$ are symmetric polynomials in
$m_{1},m_{2},\ldots,m_{n}$ which satisfy the consistency relation

$\begin{split}&p_{k}(m_{1},m_{2},\ldots,m_{n},0)=p_{k}(m_{1},m_{2},\ldots,m_{n}),\\\
&q_{k}(m_{1},m_{2},\ldots,m_{n},0)=q_{k}(m_{1},m_{2},\ldots,m_{n}).\\\
\end{split}$ (8)

###### Proof.

The symmetry of $q_{k}(m_{1},m_{2},\ldots,m_{n})$ is apparent from its very
definition in (6). As for $p_{k}(m_{1},m_{2},\ldots,m_{n})$, its symmetry is
also made apparent from the following alternative and manifestly symmetric
expression:

$p_{k}(m_{1},m_{2},\ldots,m_{n})=\sum_{k_{0},k_{1},k_{2},\ldots,k_{n}\geq
0\atop k_{0}+k_{1}+k_{2}+\cdots+k_{n}=k}{n-1\choose
k_{0}}p_{k_{1}}(m_{1})p_{k_{2}}(m_{2})\cdots p_{k_{n}}(m_{n}).$ (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},\ldots,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^{\prime}_{1}}(m_{1})p_{k^{\prime}_{2}}(m_{2})\cdots
p_{k^{\prime}_{n}}(m_{n})$ with summation variables $k^{\prime}_{1}=k_{1}$ and
$k^{\prime}_{i}=k_{i}$ or $k_{i}-1$ for $i\geq 2$. The number of terms in the
sum having exactly $k_{0}$ indices $i$ for which $k^{\prime}_{i}=k_{i}-1$ is
${n-1\choose k_{0}}$ and, for such terms, the sum rule
$k_{1}+k_{2}+\cdots+k_{n}=n$ in (6) becomes
$k_{0}+k^{\prime}_{1}+k^{\prime}_{2}+\cdots+k^{\prime}_{n}=n$. This leads to
(9) upon renaming the summation variable $k^{\prime}_{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). ∎

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},\ldots,m_{n},1)-p_{k}(m_{1},\ldots,m_{n},0)=p_{k-1}(m_{1},\ldots,m_{n})$
(10)

and the string equation, valid for non-negative integer $m_{1},\ldots,m_{n}$:

$(k+1)p_{k+1}(m_{1},\ldots,m_{n})=(m_{1}+\cdots+m_{n}-k-1)p_{k}(m_{1},\ldots,m_{n})+\\\
\sum_{i=1}^{n}\sum_{j=1}^{m_{i}-1}(2j)p_{k}(m_{1},\ldots,m_{i-1},j,m_{i+1},\ldots,m_{n})$
(11)

###### 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,\ldots,n$, the
relation (5) at $k=k_{i}$ and $m=m_{i}$ times $p_{k_{1}}(m_{1})\cdots
q_{k_{n}}(m_{n})$ with the factor $q_{k_{i}}(m_{i})$ omitted). ∎

####  2.1.2 Enumeration results in the bipartite case

We are now ready to state our first enumerative result:

######  Theorem 4.

For $n\geq 3$ and for non-negative integers $m_{1},m_{2},\ldots,m_{n}$ not all
equal to zero, the number $N_{0,n}(2m_{1},2m_{2},\ldots,2m_{n})$ of planar
tight bipartite maps with $n$ boundaries labeled from $1$ to $n$ with
respective lengths $2m_{1},2m_{2},\ldots,2m_{n}$ is given by the polynomial

$\mathsf{N}^{(0)}_{0,n}(2m_{1},2m_{2},\ldots,2m_{n})=(n-3)!\,p_{n-3}(m_{1},m_{2},\ldots,m_{n}).$
(12)

Note that the constant term of $\mathsf{N}^{(0)}_{0,n}$, obtained by setting
all the $m_{i}$’s to zero, is equal to
$(n-3)!p_{n-3}(0,\ldots,0)=(-1)^{n-3}(n-3)!$, and this quantity was
interpreted in [Nor10] as the orbifold Euler characteristic of the moduli
space $\mathcal{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\geq 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},\ldots,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\neq 0$ and $m_{2}=\cdots=m_{k+3}=0$, we
get

$N_{0,k+3}(2m,\underbrace{0,\ldots,0}_{k+2})=k!\,p_{k}(m,\underbrace{0,\ldots,0}_{k+2})=k!\,p_{k}(m),\qquad
k\geq 0.$ (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)$:

######  Proposition 5.

For $k\geq 0$ and $m\geq 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,\ldots,0}_{k+1})=k!\,p_{k}(m,1,\underbrace{0,\ldots,0}_{k+1})=k!\,q_{k}(m,\underbrace{0,\ldots,0}_{k+1})=k!\,q_{k}(m),$
(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\geq 0$ and $m\geq 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}\geq 1$ and $m_{3}=\cdots=m_{k+3}=0$,
we get

$N_{0,k+3}(2m_{1},2m_{2},\underbrace{0,\ldots,0}_{k+1})=k!\,p_{k}(m_{1},m_{2},\underbrace{0,\ldots,0}_{k+1})=k!\,p_{k}(m_{1},m_{2}).$
(15)

Upon dividing by $k!$ we get a combinatorial interpretation of
$p_{k}(m_{1},m_{2})$:

######  Proposition 7.

For $k\geq 0$ and $m_{1},m_{2}\geq 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,\ldots,0}_{k})=k!\,p_{k}(m_{1},m_{2},m_{3})$
(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\geq 1$, the number of pointed rooted planar tight bipartite maps with
$n$ labeled boundaries of respective lengths $2m_{1},\ldots,2m_{n}$ (in
addition to the marked vertex and to the root edge) is given by

$\mathsf{N}_{0,n+2}^{(0)},(2m_{1},2m_{2},\dots,2m_{n},2,0)=(n-1)!\,q_{n-1}(m_{1},m_{2},\ldots,m_{n}).$
(17)

###### Proof.

This is a direct application of formula (12), together with the identity
$p_{n-1}(m_{1},m_{2},\allowbreak\ldots,m_{n},1,0)=q_{n-1}(m_{1},m_{2},\ldots,m_{n})$
from (7). ∎

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 $\mathsf{N}^{(2)}_{0,n}$, we need to introduce the
following new family of univariate polynomials: for any integer $k\geq 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}\\\
$ (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)=\left(m-k-\tfrac{1}{2}\right)\tilde{p}_{k}(m)+\sum_{0<j<m}(2j)\tilde{p}_{k}(j)$
(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\geq 0$ and any integer $n\geq 2$ as

$\tilde{p}_{k}(m_{1},m_{2};m_{3},\ldots,m_{n}):=\sum_{k_{1},k_{2},\ldots,k_{n}\geq
0\atop
k_{1}+k_{2}+\cdots+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}).$ (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},\ldots,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\geq 3$, for $m_{1},m_{2}\in\mathbb{Z}_{\geq 0}+\frac{1}{2}$ and
$m_{3},\ldots,m_{n}\in\mathbb{Z}_{\geq 0}$, the number
$N_{0,n}(2m_{1},2m_{2},2m_{3},\ldots,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},\ldots,2m_{n}$ is given by

$\mathsf{N}_{0,n}^{(2)}(2m_{1},2m_{2},2m_{3},\ldots,2m_{n})=(n-3)!\,\tilde{p}_{n-3}(m_{1},m_{2};m_{3},\ldots,m_{n}).$
(21)

In particular, for $n=k+3$ and $m_{3}=\cdots=m_{k+3}=0$, we get, for
$m_{1},m_{2}$ half-integers:

$N_{0,k+3}(2m_{1},2m_{2},\underbrace{0,\ldots,0}_{k+1})=k!\,\tilde{p}_{k}(m_{1},m_{2};\underbrace{0,\ldots,0}_{k+1})=k!\,\tilde{p}_{k}(m_{1},m_{2}).$
(22)

Upon dividing by $k!$, we obtain a combinatorial interpretation of
$\tilde{p}_{k}(m_{1},m_{2})$:

######  Proposition 10.

For $k\geq 0$ and $m_{1},m_{2}\in\mathbb{Z}_{\geq 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\geq 0$ and $m\in\mathbb{Z}_{\geq 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};\ldots,m_{n},1)-\tilde{p}_{k}(m_{1},m_{2};\ldots,m_{n},0)=\tilde{p}_{k-1}(m_{1},m_{2};\ldots,m_{n})$
(23)

and the string equation (for $m_{i}$’s as in Theorem 9)

$(k+1)\tilde{p}_{k+1}(m_{1},m_{2};\ldots,m_{n})=(m_{1}+\cdots+m_{n}-k-1)\tilde{p}_{k}(m_{1},m_{2};\ldots,m_{n})+\\\
\sum_{i=1}^{n}\sum_{0<j<m}(2j)\tilde{p}_{k}(m_{1},\ldots,m_{i-1},j,m_{i+1},\ldots,m_{n})$
(24)

where we sum over half-integer values of $j$ for $i=1$ and $2$ and over
integer values of $j$ for $i\geq 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.

######  Remark 12.

We have the relation
$\tilde{p}_{k}(1/2,1/2;m_{1},\ldots,m_{n})=q_{k}(m_{1},\ldots,m_{n})$ which
implies that
$N_{0,n+2}(2m_{1},2m_{2},2m_{3},\ldots,2m_{n},1,1)=N_{0,n+2}(2m_{1},2m_{2},2m_{3},\ldots,2m_{n},2,0)$
for $m_{1},\ldots,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 $\mathsf{N}^{(k)}_{0,n}$, enumerating planar tight maps with $k$
boundaries of odd lengths, and $n-k$ boundaries of even lengths, for an
arbitrary value of $k\geq 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}.$
(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}$
(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}$ (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\geq 3$, for $m_{1},m_{2},\ldots,m_{n}\in\mathbb{Z}_{\geq 0}/2$, with at
least three of the $m_{i}$ being half-integers, the number
$N_{0,n}(2m_{1},2m_{2},\ldots,2m_{n})$ of planar tight maps with $n$
boundaries labeled from $1$ to $n$ with respective lengths
$2m_{1},2m_{2},\ldots,2m_{n}$ is given by the symmetric quasi-polynomial

$N_{0,n}(2m_{1},2m_{2},\ldots,2m_{n})=\\\
\sum_{\left(\begin{subarray}{c}\epsilon_{1},\ldots,\epsilon_{n}\\\
r_{1},\ldots,r_{n}\\\ s_{1},\ldots,s_{n}\end{subarray}\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)!\prod_{i=1}^{n}\pi_{r_{i},s_{i}}^{(\epsilon_{i})}(m_{i}),$
(28)

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

$I_{n}:=\left\\{\left(\begin{array}[]{c}\epsilon_{1},\ldots,\epsilon_{n}\\\
r_{1},\ldots,r_{n}\\\
s_{1},\ldots,s_{n}\end{array}\right):\begin{array}[]{l}\sum\limits_{i=1}^{n}\epsilon_{i}=\sum\limits_{i=1}^{n}r_{i}+1\\\
\sum\limits_{i=1}^{n}\bar{\epsilon}_{i}=\sum\limits_{i=1}^{n}s_{i}+2\end{array}\,,\sum_{i=1}^{n}s_{i}\geq
1\right\\}\,.$ (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\geq 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},\ldots,2m_{k}$ are odd numbers, and that $2m_{k+1},\ldots,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\leq i\leq k$, and odd for $k+1\leq i\leq
n$. On the other hand, the contraints 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}=\cdots=m_{s+3}=1/2$ and $m_{s+4}=\cdots=m_{r+s}=0$. However,
it is not a priori obvious to obtain an interpretation of $\pi^{(0)}_{r,s}(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}^{(\epsilon)}(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 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}$ (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\leq 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},\ldots,\ell_{n})$ of planar (non necessarily tight) _bipartite_
maps with $n\geq 3$ labeled faces of prescribed even degrees
$2\ell_{1},\ldots,2\ell_{n}$ is given by

$M(\ell_{1},\ldots,\ell_{n})=(\ell_{1}+\cdots+\ell_{n}-1)_{n-3}\prod_{i=1}^{n}\binom{2\ell_{i}-1}{\ell_{i}},$
(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.

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.

The key observation, already made in [Bud20a, 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\leq\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}$ (32)

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

$M(\ell_{1},\ldots,\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},\ldots,2m_{n})$ (33)

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

$N_{0,n}(2m_{1},\ldots,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},\ldots,\ell_{n})$ (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_{k_{1},k_{2},\ldots,k_{n}\geq
0\atop
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}},$
(35)

which is nothing but an equality between polynomials in
$\ell_{1},\ldots,\ell_{n}$. This yields

$N_{0,n}(2m_{1},\ldots,2m_{n})=(n-3)!\sum_{k_{1},k_{2},\ldots,k_{n}\geq 0\atop
k_{1}+k_{2}+\cdots+k_{n}=n-3}\hat{p}_{k_{1}}(m_{1})\hat{q}_{k_{2}}(m_{n})\cdots\hat{q}_{k_{n}}(m_{n})$
(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},\ldots,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:

######  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}.$
(37)

###### Proof.

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

Alternatively, a bijective proof for $\ell\geq 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. ∎

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},\ldots,\ell_{n}$ be non-negative integers, $n\geq 3$.
Then, by [Tut62, Section 6], the number $M(\ell_{1},\ldots,\ell_{n})$ of
planar quasi-bipartite maps with $n$ labeled boundaries of prescribed lengths
$2\ell_{1},\ldots,2\ell_{n}$ reads

$M(\ell_{1},\ldots,\ell_{n})=(\ell_{1}+\cdots+\ell_{n}-1)_{n-3}\binom{2\ell_{1}-1}{\ell_{1}-\tfrac{1}{2}}\binom{2\ell_{2}-1}{\ell_{2}-\tfrac{1}{2}}\prod_{i=3}^{n}\binom{2\ell_{i}-1}{\ell_{i}}.$
(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},\ldots,\allowbreak 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}-\tfrac{1}{2}$ and $\ell_{2}-\tfrac{1}{2}$, respectively, and we make
use of the identity

$\sum_{m\in\\{\frac{1}{2},\frac{3}{2},\ldots,\ell\\}}A_{\ell,m}\tilde{p}_{k}(m)=\binom{\ell-\tfrac{1}{2}}{k}\binom{2\ell-1}{\ell-\tfrac{1}{2}}$
(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, 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}_{\geq
0}/2}A_{\ell,m}\pi^{(\epsilon)}_{r,s}(m)=\binom{2\ell-1}{\ell-\frac{s+1+\epsilon}{2}\,,\,\ell-r-\frac{s+1-\epsilon}{2}\,,\,r\,,\,s}\,,$
(40)

where in the left-hand side, we observe by (26) that only the terms for which
$\ell-m\in\mathbb{Z}_{\geq 0}$ contribute, and in the right-hand side, we use
a multinomial coefficient notation. To understand this formula, recall from
Proposition 15 that $\pi^{(\epsilon)}_{r,s}(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},\ldots,\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},\ldots,2m_{n})$, we obtain the following:

######  Theorem 19 (A census of non-bipartite slicings).

The number $M(\ell_{1},\ldots,\ell_{n})$ of planar maps with $n$ labeled faces
of degrees $2\ell_{1},\ldots,2\ell_{n}$, at least four of which are odd, is
given by

$M(\ell_{1},\ldots,\ell_{n})=\sum_{\left(\begin{subarray}{c}\epsilon_{1},\ldots,\epsilon_{n}\\\
r_{1},\ldots,r_{n}\\\ s_{1},\ldots,s_{n}\end{subarray}\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}\binom{2\ell_{i}-1}{\ell_{i}-\frac{s_{i}+1+\epsilon_{i}}{2},\ell_{i}-r_{i}-\frac{s_{i}+1-\epsilon_{i}}{2},r_{i},s_{i}}\,,$
(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.

######  Example 20.

For $\ell_{1},\ldots,\ell_{4}\in\mathbb{Z}_{\geq 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},\ldots,2\ell_{4}$ equal to

$M(\ell_{1},\ldots,\ell_{4})=(\ell_{1}+\cdots+\ell_{4}-2)\prod_{i=1}^{4}\binom{2\ell_{i}-1}{\ell_{i}-\frac{1}{2}}.$
(42)

In particular, we find
$M\left(\frac{3}{2},\frac{1}{2},\frac{1}{2},\frac{1}{2}\right)=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\geq 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\geq 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 4: The coding of planar tight maps with one face with degree $2m$ (here
$m=11$) by dressed words with letters $U$, $D_{\circ}$ and $D_{\bullet}$.
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_{\circ}$. 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.

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 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 from that vertex222Note 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$.. 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_{\circ}$ to record the marking. If $v$ is not a marked vertex, the
associated letter $D$ will be denoted by $D_{\bullet}$, so that the letter $D$
eventually appears in two flavors $D_{\circ}$ and $D_{\bullet}$, leading to
dressed words made of the three letters $U$, $D_{\circ}$ and $D_{\bullet}$. 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_{\circ}$. The numbers of $U$,
$D_{\circ}$ and $D_{\bullet}$ 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_{\bullet}$ 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}}$ (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$ (44)

where the $a_{i}$ and $b_{i}$ form weak compositions of $m-k$ and $m-1$,
respectively, into $k+1$ summands333Note 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.. 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.

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.

##### 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}_{\geq 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}}$ (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\geq 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$.

###  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\geq 1$ and $b\geq 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.

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.

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\geq 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\geq 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,\ldots,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 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.

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\geq 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\geq 1$ and $k\geq 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

  * •

a $(d_{2},d_{2})$-forest with $k_{2}$ marked vertices

where $d_{1},d_{2}\geq 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\leq
c\leq\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,\ldots,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\leq(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\leq\min(a-1,b)$ implies that every markable vertex is
glued to an unmarkable vertex.

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

######  Definition 23.

For integers $a\geq 0$ and $b\geq 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 8 for an illustration.

Figure 8: The $2$-partial gluing of a $(5,3)$-forest yielding a
$(2,2)^{*}$-forest.

###### 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
$\mathbf{f}_{1}$ with size $2m_{1}$ and $k_{1}$ marked vertices, and a
$(d_{2},d_{2})$ forest $\mathbf{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 $\mathbf{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\geq 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 tranfer 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^{\prime}\geq 1$ from $v_{**,1}$ to the distinguished vertex $1$,
hence creating a $(d+d^{\prime}+1,d+d^{\prime}-1)$-forest $\mathbf{f}_{1}$,
attributing the marked vertices in the natural way (this operation is the
reverse of the $d^{\prime}$-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. ∎

##### Quasi-bipartite case.

We now consider the quasi-bipartite case where one assumes that
$m_{1},m_{2}\in\mathbb{Z}_{\geq 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\geq 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}\geq 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 10.

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
$\mathbf{m}_{2}$, appears to be clockwise, since $f_{*,2}$ is the unbounded
face in the plane embedding.

###  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},\ldots,m_{n})$ as the number of pointed rooted
planar tight bipartite maps with $n$ labeled boundaries of respective lengths
$2m_{1},\ldots,2m_{n}$, where $m_{1},\ldots,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 boundary444Note 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., 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 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.

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

##### Pointed rooted maps and elementary slices.

There is a simple one-to-one correspondence between pointed rooted planar
bipartite maps on the one hand555Here, as for tight maps, we use the slightly
unusual convention that a rooted map is a map with a distinguished, non
oriented edge., and non-empty, bipartite elementary slices of tilt $1$ on the
other hand. Starting from a pointed rooted bipartite map $\mathbf{m}$ with
root $e$ and distinguished vertex $v$, we can perform the opening operation
$O(\mathbf{m},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 geodesic666See
for instance [Bou19, Figure 2.1] for a careful definition of the leftmost
geodesic from a corner to a vertex. $\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 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},\ldots,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,\ldots,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},\ldots,\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\leq i\leq n$ in the plane.

For every $i\in\\{0,1,\ldots,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,\ldots,w\\}$, we let $v^{\prime}_{i}$ be the first vertex common
to $\gamma_{i-1}$ and $\gamma_{i}$. Then the map $\mathbf{s}^{\prime}_{i}$
delimited by these two geodesics is an elementary bipartite slice with base
$c_{i-1}c_{i}$, with apex $A^{\prime}_{i}$ incident to $v^{\prime}_{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}^{\prime}_{i}$ is trivial, while if
$t_{i}=+1$, in which case we call $i$ an up step, then
$\mathbf{s}^{\prime}_{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}^{\prime}_{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}^{\prime}_{i}$ of tilt $1$ (and where $\mathbf{s}^{\prime}_{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}^{\prime}_{i}$, hence color it in red as
in Figure 10. Next, for every up step $i$, we consider an embedding of
$\mathbf{s}^{\prime}_{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 $\mathbf{s}^{\prime}_{i}$ are declared blue,
while the edges of the right boundaries are declared red. Note that if
$\mathbf{s}^{\prime}_{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\geq 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
$\mathbf{s}^{\prime}_{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 $\mathbf{s}^{\prime}_{i}$ by maximality of $i$. With these
conventions, all the slices $\mathbf{s}^{\prime}_{i},1\leq i\leq w$, with
transferred marks, are tight slices.

Moreover, there is an additional restriction on the family
$L,(\mathbf{s}^{\prime}_{i},1\leq i\leq 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,\ldots,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
$\mathbf{s}^{\prime}_{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 $\mathbf{s}^{\prime}_{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 $(\mathbf{s}_{j},1\leq j\leq k)$ be
the sequence $(\mathbf{s}^{\prime}_{i},1\leq i\leq 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,(\mathbf{s}_{j},1\leq j\leq 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\leq j\leq k$, $\mathbf{s}_{j}$ is either the marked empty slice or a
tight bipartite elementary slice with at least one inner face.

Now observe that if $\mathbf{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,(\mathbf{s}_{j},1\leq
j\leq 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\leq j\leq k$, $\mathbf{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)\\},\varnothing)$ consisting of the
trivial lattice path of length zero, with no marks.

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
$\mathbf{s}^{\prime}_{2},\mathbf{s}^{\prime}_{4}$ and
$\mathbf{s}^{\prime}_{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.

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},\ldots,m_{n}$ not all equal to $0$, let
$\mathcal{T}(m_{1},\ldots,m_{n})$ be the family of pairs
$(\mathbf{t},(L_{i})_{1\leq i\leq n})$ where:

  * •

$\mathbf{t}$ is a rooted plane tree with vertices labeled by
$\\{1,2,\ldots,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$.

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 $\mathbf{t}$, where black/blue correspond to marked/unmarked
up steps and red to down steps. Note that some of the terminal nodes of
$\mathbf{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.

######  Corollary 26.

For every choice of non-negative integers $m_{1},\ldots,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},\ldots,2m_{n}$, and the set
$\mathcal{T}(m_{1},\ldots,m_{n})$.

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 immediatly 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
$\mathcal{T}(m_{1},\ldots,m_{n})$. By [BM14, Section 5, Equation (18)], for a
given $n$-uple $(k_{1},\ldots,k_{n})$ of non-negative integers, if
$k_{1}+\cdots+k_{n}=n-1$ then there are exactly $(n-1)!$ rooted labeled plane
trees on the vertex set $\\{1,2,\ldots,n\\}$ such that vertex $i$ has $k_{i}$
children for all $i=1,\ldots,n$, and there are no such tree otherwise. For any
such tree $\mathbf{t}$, there are $\prod_{i=1}^{n}q_{k_{i}}(m_{i})$ possible
choices of marked lattice paths $L_{i},1\leq i\leq n$ such that
$(\mathbf{t},(L_{i})_{1\leq i\leq n})$ belongs to
$\mathcal{T}(m_{1},\ldots,m_{n})$. This finally explains the wanted formula

$\begin{split}N_{0,n+2}(2m_{1},\ldots,2m_{2},2,0)&=(n-1)!\sum_{\begin{subarray}{c}k_{1},\ldots,k_{n}\geq
0\\\ k_{1}+\cdots+k_{n}=n-1\end{subarray}}\prod_{i=1}^{n}q_{k_{i}}(m_{i})\\\
&=(n-1)!\,q_{n-1}(m_{1},\ldots,m_{n})\,,\end{split}$ (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:

######  Proposition 27.

Let $m_{1},m_{2}$ be positive integers or half-integers and let
$m_{3},\ldots,m_{n}$ be non-negative integers ($n\geq 3$). Then, there is a
bijection between the set of planar tight maps with $n$ boundaries labeled
from $1$ to $n$ with respective lengths $2m_{1},2m_{2},\ldots,2m_{n}$, and the
set of pairs $(\mathbf{m}_{12},\mathbf{s})$ such that there exists
$k\in\\{0,\ldots,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},\ldots,\mathbf{s}_{k+1})$ is a $(k+1)$-tuple of
slices such that:

    * –

for each $j=1,\ldots,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,\ldots,n\\}$,

    * –

each $i\in\\{3,\ldots,n\\}$ appears in exactly one $\mathbf{s}_{j}$ 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 4 and 9.
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,\ldots,n-3\\}$, the number of possible maps
$\mathbf{m}_{12}$ is equal to $p_{k}(m_{1},m_{2})$ by Proposition 7, 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},\ldots,m_{n})$ defined as the set of pairs
$(\mathbf{f},(L_{i})_{3\leq i\leq 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,\ldots,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},\ldots,m_{n})$ is nothing but the set
$\mathcal{T}(m_{3},\ldots,m_{n})$ as defined in Section 4.3. By Proposition 44
of Appendix A below, for a given $n$-uple $(k_{3},\ldots,k_{n})$, if
$k_{3}+\cdots+k_{n}=n-3-k$ then there are exactly $(n-3)!$ plane forests on
the vertex set $\\{3,\ldots,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,\ldots,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\leq i\leq n$ such that
$(\mathbf{f},(L_{i})_{3\leq i\leq n})$ belongs to
$\mathcal{F}_{k+1}(m_{3},\ldots,m_{n})$. This gives

$\begin{split}\mathrm{Card}\left(\mathcal{F}_{k+1}(m_{3},\ldots,m_{n})\right)&=(n-3)!\sum_{\begin{subarray}{c}k_{3},\ldots,k_{n}\geq
0\\\ k_{3}+\cdots+k_{n}=n-3-k\end{subarray}}\prod_{i=3}^{n}q_{k_{i}}(m_{i})\\\
&=(n-3)!\,q_{n-3-k}(m_{3},\ldots,m_{n}).\end{split}$ (47)

Thus, multiplying by $p_{k}(m_{1},m_{2})$, summing over $k$ and using (6), we
get

$\begin{split}N_{0,n}(2m_{1},2m_{2},2m_{3}\ldots,2m_{n})&=(n-3)!\sum_{k=0}^{n-3}p_{k}(m_{1},m_{2})q_{n-3-k}(m_{3},\ldots,m_{n})\\\
&=(n-3)!\,p_{n-3}(m_{1},m_{2},m_{3},\ldots,m_{n})\end{split}$ (48)

as wanted. This concludes the proof of Theorem 4 assuming Proposition 27.

If we now assume that $m_{1},m_{2}$ are half-integers, the only change we have
to do in the above reasoning is that, for a fixed $k$, the number of possible
maps $\mathbf{m}_{12}$ is now equal to $\tilde{p}_{k}(m_{1},m_{2})$ by
Proposition 10 (also proved in Section 4.2). Thus, by (6) and (20), we now
have

$\begin{split}N_{0,n}(2m_{1},2m_{2},2m_{3}\ldots,2m_{n})&=(n-3)!\sum_{k=0}^{n-3}\tilde{p}_{k}(m_{1},m_{2})q_{n-3-k}(m_{3},\ldots,m_{n})\\\
&=(n-3)!\,\tilde{p}_{n-3}(m_{1},m_{2};m_{3},\ldots,m_{n})\end{split}$ (49)

which establishes Theorem 9.

The remainder of this section is devoted to the proof of Proposition 27. It
uses the slice decomposition of annular maps which was introduced in [BG14,
Section 9.3], see also [Bou19, Section 2.2] for another exposition. Here we
will give yet another, modernized, exposition which, following [BGM21], makes
use of the key notion of _Busemann function_.

##### Decomposing an annular map into a pair of paths decorated with
elementary slices.

Figure 13: Sketch of an annular map $\mathbf{m}$ (left) and of its universal
cover $\tilde{\mathbf{m}}$ (right). The external face $1$ and the central face
$2$ of $\mathbf{m}$ lift respectively to the lower face $\tilde{1}$ and to the
upper face $\tilde{2}$ of $\tilde{\mathbf{m}}$, which have infinite degrees
(marked corners are represented by arrows). All the other faces form the grey
region. The innermost minimal separating cycle $\gamma$ lifts to a biinfinite
geodesic $\tilde{\gamma}$.

Let $\mathbf{m}$ be an _annular_ map, that is a planar map with two
distinguished faces labeled $1$ and $2$. For now, we do not assume that
$\mathbf{m}$ is a tight map, but we assume that every face other than $1$ and
$2$ has even degree. Denoting by $2m_{1}$ and $2m_{2}$ the respective degrees
of $1$ and $2$, $\mathbf{m}$ is either bipartite when $m_{1}$ and $m_{2}$ are
integers, or quasi-bipartite when they are half-integers.

Let us choose a representation of $\mathbf{m}$ in the complex plane such that
face $1$ is the unbounded face, and such that the origin (point of affix zero)
lies in face $2$. We then consider the preimage $\tilde{\mathbf{m}}$ of
$\mathbf{m}$ by the mapping $z\mapsto\exp(2i\pi z)$: it is an infinite map
which we call the _universal cover_ of $\mathbf{m}$ (upon viewing $0$ and
$\infty$ as “punctures”). We refer to [BGM21] for a detailed discussion of the
properties of the universal cover of a map drawn on the triply-punctured
sphere, it can be adapted without difficulty to the simpler case considered
here of a map drawn on the doubly-punctured sphere. For our purposes, we
simply note that the faces $1$ and $2$ lift in $\tilde{\mathbf{m}}$ to unique
faces $\tilde{1}$ and $\tilde{2}$, which have infinite degrees, while all the
other faces and vertices of $\mathbf{m}$ lift to infinitely many preimages in
$\tilde{\mathbf{m}}$ with the same finite degree. In particular,
$\tilde{\mathbf{m}}$ is bipartite. See Figure 13 for an illustration.

Let $s$ denote the _separating girth_ of $\mathbf{m}$, that is the minimal
length (number of edges) of a closed path in $\mathbf{m}$ winding around the
origin. We call such path a _separating cycle_ and say that it is _minimal_ if
it has length $s$. Let then $\gamma$ be the _innermost_ minimal separating
cycle, which is defined as the contour of the intersection of the interiors of
all minimal separating cycles. We consider the path
$\tilde{\gamma}=(\tilde{\gamma}(t))_{t\in\mathbb{Z}}$ obtained by following
$\gamma$ counterclockwise infinitely many times and lifting this biinfinite
path in $\tilde{\mathbf{m}}$. The parametrization of $\tilde{\gamma}$ depends
on a choice of a vertex $\tilde{\gamma}(0)$ whose projection belongs to
$\gamma$, but we will see that the outcome of our construction does not depend
on it. By [CE10, Proposition 2.5], $\tilde{\gamma}$ is a _biinfinite geodesic_
in $\tilde{\mathbf{m}}$, i.e. we have

$\tilde{d}(\gamma(t),\gamma(t^{\prime}))=|t-t^{\prime}|$ (50)

for any $t,t^{\prime}\in\mathbb{Z}$, where $\tilde{d}$ denotes the graph
distance in $\tilde{\mathbf{m}}$. We now define the _Busemann function_
$B_{\tilde{\gamma}}$ from the vertex set $\tilde{V}$ of $\tilde{\mathbf{m}}$
to $\mathbb{Z}$ by

$B_{\tilde{\gamma}}(v):=\lim_{t\to\infty}\tilde{d}(v,\gamma(t))-t,\qquad
v\in\tilde{V}.$ (51)

By the triangle inequality, one easily checks that the limit indeed exists and
is attained for $t$ large enough. Furthermore, for any two adjacent vertices
$v,v^{\prime}$ we have
$B_{\tilde{\gamma}}(v)-B_{\tilde{\gamma}}(v^{\prime})=\pm 1$ (since
$\tilde{\mathbf{m}}$ is bipartite), and every vertex $v$ has a neighbor
$v^{\prime}$ for which this difference is $+1$ (i.e. $B_{\tilde{\gamma}}$ has
no local minimum). Let us denote by $T$ the automorphism of
$\tilde{\mathbf{m}}$ corresponding to the translation $z\mapsto z+1$ of the
complex plane (it corresponds to making one turn counterclockwise around the
origin in $\mathbf{m}$): we then have
$B_{\tilde{\gamma}}(Tv)=B_{\tilde{\gamma}}(v)-s$ as a consequence of the
relation $T\tilde{\gamma}(t)=\tilde{\gamma}(t+s)$.

Now, let us denote by $(c_{i})_{i\in\mathbb{Z}}$ and
$(c^{\prime}_{i})_{i\in\mathbb{Z}}$ the successive corners incident to the
faces $\tilde{1}$ and $\tilde{2}$, respectively, as we follow their contours
walking with the face at hand to the right. This depends on a choice for the
corners $c_{0}$ and $c^{\prime}_{0}$, whose influence will be discussed later.
We have $Tc_{i}=c_{i+2m_{1}}$ and $Tc^{\prime}_{i}=c^{\prime}_{i-2m_{2}}$ for
all $i$.

We then set, for any $i\in\mathbb{Z}$,
$\ell_{i}:=B_{\tilde{\gamma}}(c_{0})-B_{\tilde{\gamma}}(c_{i})$ and
$\ell^{\prime}_{i}:=B_{\tilde{\gamma}}(c^{\prime}_{0})-B_{\tilde{\gamma}}(c^{\prime}_{i})$
(these differences do not depend on the choice of $\tilde{\gamma}(0)$, as
claimed). Observe that the definition of $\ell_{i}$ is analogous to that used
in Section 4.3 for the decomposition of a slice into a path decorated with
elementary slices: the distance to the apex $d(\cdot,A)$ is just replaced by
the Busemann function $B_{\tilde{\gamma}}(\cdot)$. The sequences
$\ell=(\ell_{i})_{i\in\mathbb{Z}}$ and
$\ell^{\prime}=(\ell^{\prime}_{i})_{i\in\mathbb{Z}}$ form infinite lattice
paths (with increments $\pm 1$) which are periodic: indeed, we have
$\ell_{i+2m_{1}}=\ell_{i}+s$ and
$\ell^{\prime}_{i+2m_{2}}=\ell^{\prime}_{i}-s$ for all $i$. Thus, these
sequences are entirely determined by their data in a fundamental domain:
$L:=(\ell_{0},\ell_{1},\ldots,\ell_{2m_{1}})$ and
$L^{\prime}:=(\ell^{\prime}_{0},\ell^{\prime}_{1},\ldots,\ell^{\prime}_{2m_{2}})$
form lattice paths connecting $(0,0)$ to respectively $(2m_{1},s)$ and
$(2m_{2},-s)$.

With each corner $c_{i}$, we associate the _leftmost_ infinite geodesic
$\gamma_{i}=(\gamma_{i}(t))_{t\geq 0}$ defined inductively as follows. We let
$\gamma_{i}(0)$ be the vertex incident to $c_{i}$ and, assuming that
$\gamma_{i}(t)$ is known, we let $\gamma_{i}(t+1)$ be the leftmost vertex such
that
$B_{\tilde{\gamma}}(\gamma_{i}(t+1))=B_{\tilde{\gamma}}(\gamma_{i}(t))-1$,
using the edge $\gamma_{i}(t-1)\gamma_{i}(t)$ (or the corner $c_{i}$ for
$t=0$) as a reference. We define in the same way the leftmost infinite
geodesic $\gamma^{\prime}_{i}$ starting at $c^{\prime}_{i}$. We may check that
each of these leftmost geodesics eventually merges with $\tilde{\gamma}$ (for
$\gamma^{\prime}_{i}$, this uses the fact that we chose $\gamma$ to be the
innermost minimal separating cycle).

Figure 14: Sketch of the decomposition of the universal cover of an annular
map into slices. The leftmost infinite geodesics (shown in dotted lines)
eventually merge with the biinfinite geodesic $\tilde{\gamma}$ (shown in
dashed lines). These geodesics delimit slices $\boldsymbol{\sigma}_{i}$ and
$\boldsymbol{\sigma}^{\prime}_{i}$, $i\in\mathbb{Z}$. In the situation
displayed here, the slices $\boldsymbol{\sigma}_{2}$,
$\boldsymbol{\sigma}_{7}$, $\boldsymbol{\sigma}^{\prime}_{1}$, etc, are
trivial slices (reduced to an edge).

Let $\boldsymbol{\sigma}_{i}$ (resp. $\boldsymbol{\sigma}^{\prime}_{i}$) be
the map delimited by $\gamma_{i-1}$ and $\gamma_{i}$ (resp.
$\gamma^{\prime}_{i-1}$ and $\gamma^{\prime}_{i}$), which we stop at their
first common vertex $v_{i}$ (resp. $v^{\prime}_{i}$). It is an elementary
bipartite slice with base $c_{i-1}c_{i}$ (resp.
$c^{\prime}_{i-1}c^{\prime}_{i}$). As in Section 4.3, the slice is trivial
whenever $i$ corresponds to a down step of $\ell$ (resp. $\ell^{\prime}$), and
is non-trivial otherwise (but may be empty). By periodicity, we have
$\boldsymbol{\sigma}_{i}=\boldsymbol{\sigma}_{i+2m_{1}}$ and
$\boldsymbol{\sigma}^{\prime}_{i}=\boldsymbol{\sigma}^{\prime}_{i-2m_{2}}$ (in
the sense of equality as maps). Note that every finite face, edge and vertex
of $\tilde{\mathbf{m}}$ belongs to exactly one slice $\boldsymbol{\sigma}_{i}$
or $\boldsymbol{\sigma}^{\prime}_{i}$ deprived of its right boundary.

Let us finally discuss the roles of the reference corners $c_{0}$ and
$c^{\prime}_{0}$. Changing the reference corner $c_{0}$ amounts to translating
the lattice path $\ell$, and to reparametrizing the sequence
$\boldsymbol{\sigma}=(\boldsymbol{\sigma}_{i})_{i\in\mathbb{Z}}$ by a
translation of $i$. In particular, both $\ell$ and $\boldsymbol{\sigma}$ are
invariant if we change $c_{0}$ into one its translates $T^{k}c_{0}$, thus they
only depend on the choice of a corner incident to face $1$ in $\mathbf{m}$.
Similarly, $\ell^{\prime}$ and
$\boldsymbol{\sigma}^{\prime}=(\boldsymbol{\sigma}^{\prime}_{i})_{i\in\mathbb{Z}}$
only depend on the choice of a corner incident to face $2$ in $\mathbf{m}$.

If we assume that the map $\mathbf{m}$ has a third distinguished element
(face, edge or vertex) labeled $3$, which will be the case in our application,
then it is possible to choose corners incident to faces $1$ and $2$ in a
canonical way. Namely, we pick a preimage $\tilde{3}$ of $3$ in
$\tilde{\mathbf{m}}$: $\tilde{3}$ belongs to precisely one slice
$\boldsymbol{\sigma}_{i}$ or $\boldsymbol{\sigma}^{\prime}_{i}$ deprived of
its right boundary. If $\tilde{3}$ belongs to a $\boldsymbol{\sigma}_{i}$,
then by changing the reference corner $c_{0}$ we can ensure that it belongs to
$\boldsymbol{\sigma}_{1}$. Then, we choose $c^{\prime}_{0}$ in such way that
$B_{\tilde{\gamma}}(c^{\prime}_{0})=B_{\tilde{\gamma}}(c_{0})$: this is
possible because the function $B_{\tilde{\gamma}}(\cdot)$ has $\pm 1$
increments along the contour of $\tilde{2}$ and decreases by $s$ over a
translation $T$, hence it is surjective. There might exist several such
$c^{\prime}_{0}$, in which case we may pick, say, the “rightmost” one. If
$\tilde{3}$ belongs to a $\boldsymbol{\sigma}^{\prime}_{i}$, we proceed in the
same way upon exchanging the roles of $c_{0}$ and $c^{\prime}_{0}$.

######  Lemma 28.

The above construction is a bijection between:

  * •

the set of maps $\mathbf{m}$ with two marked faces of degrees
$2m_{1},2m_{2}\in\mathbb{Z}_{>0}$ and all other faces of even degree, and
separating girth $s\in\mathbb{Z}_{>0}$,

  * •

the set of quadruples
$(L,L^{\prime},\boldsymbol{\sigma},\boldsymbol{\sigma}^{\prime})$, where $L$
and $L^{\prime}$ are lattice paths connecting $(0,0)$ to respectively
$(2m_{1},s)$ and $(2m_{2},-s)$, where $\boldsymbol{\sigma}$ and
$\boldsymbol{\sigma}^{\prime}$ are sequences of elementary slices of
respective periods $2m_{1}$ and $2m_{2}$, such that for every
$i=1,\ldots,2m_{1}$ (resp. $i=1,\ldots,2m_{2}$) the tilt of
$\boldsymbol{\sigma}_{i}$ and (resp. $\boldsymbol{\sigma}^{\prime}_{i}$) is
equal to $\ell_{i}-\ell_{i-1}$ (resp.
$\ell^{\prime}_{i}-\ell^{\prime}_{i-1}$).

To prove this lemma, we now describe the inverse procedure which consists in
assembling an annular map $\mathbf{m}$ from a quadruple
$(L,L^{\prime},\boldsymbol{\sigma},\boldsymbol{\sigma}^{\prime})$.

##### Assembling an annular map from a pair of paths decorated with elementary
slices.

Using the lattice path $L$ and the sequence of slices $\boldsymbol{\sigma}$
restricted to a period, we may use the inverse of the decomposition described
in Section 4.3 to obtain a slice $\boldsymbol{\Sigma}$ of width $2m_{1}$ and
tilt $s$. We then perform the operation described in [BG14, Section 7.1] and
called _wrapping_ in [Bou19, Section 2.2]. It consists in gluing
“isometrically” the left and right boundaries of $\boldsymbol{\Sigma}$
together, but unlike the gluing performed in Section 4.3 to obtain a pointed
rooted map, we now start from the two endpoints of the base of
$\boldsymbol{\Sigma}$ which we identify together, and perform the gluing from
there (see the illustrations in the aforementioned references). As the tilt
$s$ is positive, the $s$ edges of the left boundary closest to the apex remain
unglued. This produces an annular map $\mathbf{m}_{1}$ whose two distinguished
faces have respective degrees $2m_{1}$ and $s$, the latter resulting from the
unglued edges, the former resulting from the base, whose two identified
endpoints yield a distinguished corner denoted $c$.

Similarly, the lattice path $L^{\prime}$ and the sequence of slices
$\boldsymbol{\sigma}^{\prime}$ yield a slice $\boldsymbol{\Sigma}^{\prime}$ of
width $2m_{2}$ and tilt $-s$, whose wrapping produces an annular map
$\mathbf{m}_{2}$ with two distinguished faces of respective degrees $2m_{2}$
and $s$ (since the tilt of $\boldsymbol{\Sigma}^{\prime}$ is negative, it is
now the $s$ edges closest to the apex on the _right_ boundary that form this
latter face), the former having a distinguished corner denoted $c^{\prime}$.

The annular map $\mathbf{m}$ is then obtained by gluing the two annular maps
$\mathbf{m}_{1}$ and $\mathbf{m}_{2}$ together along the contours of their
distinguished faces of degree $s$. The contour then becomes a separating cycle
$\gamma$, which can be shown to have minimal length. Note that there are a
priori $s$ ways to glue $\mathbf{m}_{1}$ and $\mathbf{m}_{2}$ together,
however only one way is compatible with the prescription that, in the
universal cover $\tilde{\mathbf{m}}$ of $\mathbf{m}$, the corners $c$ and
$c^{\prime}$ admit respective lifts $c_{0}$ and $c^{\prime}_{0}$ such that
$B_{\tilde{\gamma}}(c_{0})=B_{\tilde{\gamma}}(c^{\prime}_{0})$ where
$\tilde{\gamma}$ is the infinite geodesic constructed by lifting $\gamma$.

We may check that the assembling procedure is indeed the inverse of the
decomposition described above. The most subtle point is to show that any
quadruple $(L,L^{\prime},\boldsymbol{\sigma},\boldsymbol{\sigma}^{\prime})$ is
left invariant if we assemble it then decompose the resulting annular map.
This requires to check that the boundaries of the slices become, in the
annular map, precisely the leftmost geodesics that we use in the
decomposition. More details can be found in [BG14, Section 7].

##### Application to tight maps and end of the proof of Proposition 27.

So far, all our discussion holds without the assumption that $\mathbf{m}$ is
tight. Adding this constraint amounts to two restrictions on the corresponding
quadruple $(L,L^{\prime},\boldsymbol{\sigma},\boldsymbol{\sigma}^{\prime})$,
which are similar to those encountered in Section 4.3. First, every
$\boldsymbol{\sigma}_{i}$ and $\boldsymbol{\sigma}^{\prime}_{i}$ must be a
tight elementary slice. Here, we use the natural convention that the mark of a
marked vertex is transferred to its copy in the unique slice deprived of its
right boundary that contains it (in particular, marked vertices lying on the
separating cycle $\gamma$ have their marks transferred to
$\boldsymbol{\sigma}_{i}$’s and not to $\boldsymbol{\sigma}^{\prime}_{i}$’s).
Second, the lattice paths $\ell$ and $\ell^{\prime}$ (which are the periodic
extensions of $L$ and $L^{\prime}$) must be such that every up step
immediately following a down step cannot be decorated with an unmarked empty
slice.

To complete the proof of Proposition 27, we assume that $\mathbf{m}$ has
$n\geq 3$ boundaries, labeled $1$ to $n$. By the slice decomposition, the
labels $3,\ldots,n$ get distributed among the $\boldsymbol{\sigma}_{i}$ and
$\boldsymbol{\sigma}^{\prime}_{i}$. Let $i_{1}\leq\cdots\leq i_{j}$ be the
indices $i$ between $1$ and $2m_{1}$ such that $\boldsymbol{\sigma}_{i}$ is
neither the unmarked empty slice nor the trivial slice, i.e. contains at least
one label. Let $i^{\prime}_{1}\leq\cdots\leq i^{\prime}_{j^{\prime}}$ be
similarly the indices $i$ between $1$ and $2m_{2}$ such that
$\boldsymbol{\sigma}^{\prime}_{i}$ contains at least one label. We set
$k=j+j^{\prime}-1$ and note that $0\leq k\leq n-3$ since there are $n-2$
labels in total to distribute among the slices. Recall that, by the
aforementioned prescription for choosing the reference corners, the label $3$
is either in $\boldsymbol{\sigma}_{1}$ or $\boldsymbol{\sigma}^{\prime}_{1}$.
If it is in $\boldsymbol{\sigma}_{1}$, we set
$(\mathbf{s}_{1},\ldots,\mathbf{s}_{k+1}):=(\boldsymbol{\sigma}_{i_{1}=1},\ldots,\boldsymbol{\sigma}_{i_{j}},\boldsymbol{\sigma}^{\prime}_{i^{\prime}_{1}},\ldots,\boldsymbol{\sigma}^{\prime}_{i^{\prime}_{j^{\prime}}})$.
Otherwise, we set
$(\mathbf{s}_{1},\ldots,\mathbf{s}_{k+1}):=(\boldsymbol{\sigma}^{\prime}_{i^{\prime}_{1}=1},\ldots,\boldsymbol{\sigma}^{\prime}_{i^{\prime}_{j^{\prime}}},\boldsymbol{\sigma}_{i_{1}},\ldots,\boldsymbol{\sigma}_{i_{j}})$.
This defines the $(k+1)$-tuple of slices $\mathbf{s}$ of the proposition.

As for the two-face map $\mathbf{m}_{12}$, it is obtained as follows. Let
$\boldsymbol{\omega}$ and $\boldsymbol{\omega}^{\prime}$ be the sequences
obtained from respectively $\boldsymbol{\sigma}$ and
$\boldsymbol{\sigma}^{\prime}$ by replacing every slice different from the
unmarked empty slice and from the trivial slice with the marked empty slice.
Then, $\mathbf{m}_{12}$ is the annular map obtained by assembling the
quadruple $(L,L^{\prime},\boldsymbol{\omega},\boldsymbol{\omega}^{\prime})$.
It is by construction a tight two-face map with $k+1$ marked vertices, and we
distinguish the marked vertex coming from the marked empty slice which
replaces the slice containing the label $3$.

We check that the mapping $\mathbf{m}\mapsto(\mathbf{m}_{12},\mathbf{s})$ is a
bijection by exhibiting the inverse bijection. Let
$(\mathbf{m}_{12},\mathbf{s})$ be a pair as in the proposition, and let
$(L,L^{\prime},\boldsymbol{\omega},\boldsymbol{\omega}^{\prime})$ be the
quadruple obtained by decomposing the two-face map $\mathbf{m}_{12}$, its
distinguished marked vertex playing the role of the third distinguished
element labeled $3$ used in the construction of page 4.4. By construction the
sequences $\boldsymbol{\omega}$ and $\boldsymbol{\omega}^{\prime}$ consist
only of empty or trivial slices, with a number $k+1$ of marked empty slices.
Replacing these marked empty slices with
$\mathbf{s}_{1},\ldots,\mathbf{s}_{k+1}$, we obtain two sequences
$\boldsymbol{\sigma}$ and $\boldsymbol{\sigma}^{\prime}$ such that the
assembling of the quadruple
$(L,L^{\prime},\boldsymbol{\sigma},\boldsymbol{\sigma}^{\prime})$ gives the
tight map $\mathbf{m}$ we are looking for. This ends the proof of Proposition
27. ∎

######  Remark 29.

It might seem a priori more direct to attempt to enumerate the quadruples
$(L,L^{\prime},\boldsymbol{\sigma},\boldsymbol{\sigma}^{\prime})$. But, since
the paths $L$ and $L^{\prime}$ have a height variation depending on the
separating girth $s$, this leads to an expression involving a sum over $s$.
The trick of “recombining” $L$ and $L^{\prime}$ into a two-face map allows to
circumvent this issue.

##  5 Bijective proofs for non necessarily bipartite maps

In this section, we explain how the bijective approach of Section 4 may be
extended so as to enumerate planar tight maps which are not necessarily
bipartite.

Recall from Section 2.2 that a _petal_ is a face of degree one. The key idea
to extend our construction to the non bipartite case is to realize that petals
play a role very similar to marked vertices. Mimicking the organization of
Section 4, we will first enumerate tight maps with a single non-petal face in
Section 5.1, then tight maps with just two non-petal faces in Section 5.2, and
finally tight maps with an arbitrary number of non-petal faces in Section 5.4.
A prerequisite to this latter enumeration will be that of tight non
necessarily bipartite slices in Section 5.3.

Before we start our discussion, let us recall from Section 2.2 the definition
of the polynomials

$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}$
(52)

for $k\in\mathbb{Z}_{\geq 0}$. For $m-\frac{e}{2}\in\mathbb{Z}$, we may
interpret $p_{k,e}(m)$ as counting words of the form (43) where the $a_{i}$
and $b_{i}$ are nonnegative integers such that
$a_{1}+a_{2}+\cdots+a_{k+1}=m+\frac{e}{2}-k-1$ and
$b_{1}+b_{2}+\cdots+b_{k+1}=m-\frac{e}{2}$ (i.e. the word has length $2m$,
$k+1$ occurrences of $D_{\circ}$ and $e$ more $D$’s than $U$’s). This
interpretation holds a priori only for
$m\geq\max\left(k+1-\frac{e}{2},\frac{e}{2}\right)$ but this domain may be
extended to $m\geq\max\left(1-\frac{e}{2},\frac{e}{2}-k\right)$ since
$p_{k,e}(m)$ vanishes in the additional domain.

######  Remark 30.

Even though we will not use it in the sequel, let us mention that, by a
variation of the arguments of Section 4.1, we may show that, for $m$ as above,
$p_{k,e}(m)$ is the number of two-face tight maps with one face of degree
$2m$, one simple face of degree $|e|$ and $k+1$ marked vertices, one of them
distinguished, with the condition that for $e<0$ no marked vertex is incident
to the face of degree $e$. Note that such maps are closely related with the
notion of $(a,b)^{*}$-forests of Definition 23: for $e>0$, $p_{k,e}(m)$ counts
$(0,e)^{*}$-forests with size $2m$ and $k+1$ marked vertices including the
distinguished vertex.

###  5.1 Petal trees

We recall that 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.

We also recall, for $r,s\in\mathbb{Z}_{\geq 0}$, $\epsilon\in\mathbb{Z}$ and
$m\in\mathbb{Z}/2$, the definition of the quasi-polynomial

$\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}$
(53)

Our goal in this section is to prove Proposition 15, showing that, for
$m\in\mathbb{Z}_{>0}/2$ and $\epsilon\in\\{-1,0,1\\}$,
$\pi^{(\epsilon)}_{r,s}(m)$ enumerates tight petal trees with one exterior
face of degree $2m$, $s+1+\epsilon$ petals (excluding the exterior face when
$m=1/2$), $1+\epsilon$ of which are distinguished, and $r+1-\epsilon$ marked
vertices, $1-\epsilon$ of which are distinguished. The reason for the
$\epsilon$-dependence in the statement is that we must distinguish two
elements among marked vertices and petals. For this reason, there are three
situations to consider: we may distinguish two marked vertices
($\epsilon=-1$), two petals ($\epsilon=1$), or one of each type
($\epsilon=0$).

We note that, upon “labeling” the undistinguished elements, Proposition 15 is
equivalent to the more symmetric statement:

######  Proposition 31.

For $0\leq e\leq k+2$ and $m\in\mathbb{Z}_{>0}/2$, the number of tight petal
trees with an exterior face of degree $2m$, with $e$ petals and $k+2-e$ marked
vertices, all labeled, is given by:

$N_{0,k+3}(2m,\underbrace{1,\ldots,1}_{e},\underbrace{0,\ldots,0}_{k+2-e})=\begin{cases}k!p_{k,e}(m)&\text{if
$m-\frac{e}{2}\in\mathbb{Z}$,}\\\ 0&\text{otherwise.}\end{cases}$ (54)

More precisely, Proposition 31 is recovered from Proposition 15 by setting
$k=r+s$ and $e=s+1+\epsilon$ (hence $k+2-e=r+1-\epsilon$). The petal trees
considered in Proposition 15 have $s$ (repectively $r$) non-distinguished
petals (respectively marked vertices) which we may label in $s!$ (repectively
$r!$) ways. Using $s!r!\binom{r+s}{s}=(r+s)!=k!$, we obtain (54) for
$1+\epsilon\leq e\leq k+1+\epsilon$, hence for the whole range $0\leq e\leq
k+2$ by letting in $\epsilon$ vary in $\\{-1,0,1\\}$.

###### Proof of Proposition 15.

Let us first discuss how we may code petal trees using words, or equivalently
lattice paths, as we did in Section 4.1 for ordinary trees. Note first that
petal trees have two types of edges: _“tree-type”_ edges whose both sides are
incident to the exterior face and _“petal-type”_ edges with one edge side
incident to a petal and the other to the exterior face. In particular, the
tree-type edges have distinct endpoints and they form a plane tree (i.e. a map
with a single face), which we call the _“wood”_ of the petal tree. Here the
coding that we shall use applies to _rooted_ petal trees, i.e. petal trees
where we distinguish a corner (the root corner) _in the exterior face_ (note
that this also induces a rooting of the wood tree). Starting from this root
corner and following the contour of the exterior face going counterclockwise
around the tree (i.e. with the exterior face on the right), we record a letter
$U$ (respectively $D$) for each tree-type edge visited while going away from
(respectively towards) the root and a letter $E$ for each visited petal-type
edge. The obtained three-letter word may alternatively be visualized as a
lattice path with three types of elementary steps: up, down and horizontal,
associated respectively to the letters $U$, $D$ and $E$. This path is a
Motzkin path of length equal to the degree $2m^{\prime}$ of the exterior face,
i.e. it goes from $(0,0)$ to $(2m^{\prime},0)$ and _stays above the $x$-axis_.
Indeed, the ordinates of the path record graph distances to the _root vertex_
incident to the root corner. The number $s^{\prime}$ of occurrences of the
letter $E$ in the coding word is nothing but the number of petals, and is such
that $m^{\prime}-\frac{s^{\prime}}{2}$, which is the number of $U$’s (or
equivalently of $D$’s), is a nonnegative integer.

Let us now consider a rooted petal tree with marked vertices, _where the root
vertex is unmarked_ , and such that all non-root leaves are marked. Every non-
root vertex being bijectively associated with its parent tree-type edge in the
wood tree, hence with a letter $D$, we record the markings as in Section 4.1
by replacing each $D$ by a $D_{\circ}$ if the associated vertex is marked and
by a $D_{\bullet}$ otherwise. We end up with a word made of four letters, $U$,
$D_{\circ}$, $D_{\bullet}$ and $E$, associated with a “dressed” Motzkin path,
with $k^{\prime}$ occurrences of $D_{\circ}$ and
$m^{\prime}-\frac{s^{\prime}}{2}-k^{\prime}$ occurrences of $D_{\bullet}$ if
the petal tree has $k^{\prime}$ marked vertices. As before, requiring that all
non-root leaves be marked simply amounts to forbidding the sequence
$UD_{\bullet}$ in the coding words.

Figure 15: Schematic picture of the decomposition of a lattice path of length
$2m-1$, height difference $-\epsilon$, and minimal height $-\ell$ into a
sequence of $2\ell+1-\epsilon$ Motzkin paths, where the squares indicate that
the underlying descending step may be marked (if associated with a
$D_{\circ}$) or not (if associated with a $D_{\bullet}$). For
$j=1,2,\cdots,\ell$, the $j$-th Motzkin path is followed by the first
elementary down step reaching height $-j$. These $\ell$ Motzkin paths code for
an ordered set $\mathcal{F}_{\square}$ of $\ell$ rooted petal trees whose root
vertex are marked or not according to the nature of the following elementary
down step. For $j=\ell+2,\ell+3,\cdots,2\ell+1-\epsilon$, the $j$-th Motzkin
path is preceded by the last elementary up step reaching height $j-1-2\ell$.
Together with the $(\ell+1)$-th Motzkin path, these Motzkin paths code for an