% EJC papers *must* begin with the following two lines. 
\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P1.23}{21(1)}{2014}

% Please remove all other commands that change parameters such as
% margins or pagesizes.

% only use standard LaTeX packages
% only include packages that you actually need

% we recommend these ams packages
\usepackage{amsthm,amsmath,amssymb}

% we recommend the graphicx package for importing figures
\usepackage{graphicx}

% use this command to create hyperlinks (optional and recommended)
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

% use these commands for typesetting doi and arXiv references in the bibliography
\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}

% all overfull boxes must be fixed; 
% i.e. there must be no text protruding into the margins


% declare theorem-like environments
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{claim}[theorem]{Claim}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{open}[theorem]{Open Problem}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{question}[theorem]{Question}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{note}[theorem]{Note}

\numberwithin{equation}{section}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% if needed include a line break (\\) at an appropriate place in the title

\title{\bf A note on irreducible maps\\ with several boundaries}

% input author, affilliation, address and support information as follows;
% the address should include the country, and does not have to include
% the street address 

\author{J. Bouttier$^{1,2}$ \qquad E. Guitter$^1$\\
 \small $^1$ Institut de Physique Th\'eorique\\[-0.8ex]
\small CEA, IPhT, F-91191 Gif-sur-Yvette, France\\[-0.8ex]
\small CNRS, URA 2306\\[-0.8ex]
\small $^2$ D\'epartement de Math\'ematiques et Applications\\[-0.8ex]
\small \'Ecole normale sup\'erieure, 45 rue d'Ulm, F-75231 Paris Cedex 05\\
\small\tt \{jeremie.bouttier,emmanuel.guitter\}@cea.fr
}


% \date{\dateline{submission date}{acceptance date}\\
% \small Mathematics Subject Classifications: comma separated list of
% MSC codes available from http://www.ams.org/mathscinet/freeTools.html}

\date{\dateline{Jun 7, 2013}{Jan 23, 2014}{Feb 7, 2014}\\
%\small Mathematics Subject Classifications: 
}

\begin{document}

\maketitle

% E-JC papers must include an abstract. The abstract should consist of a
% succinct statement of background followed by a listing of the
% principal new results that are to be found in the paper. The abstract
% should be informative, clear, and as complete as possible. Phrases
% like "we investigate..." or "we study..." should be kept to a minimum
% in favor of "we prove that..."  or "we show that...".  Do not
% include equation numbers, unexpanded citations (such as "[23]"), or
% any other references to things in the paper that are not defined in
% the abstract. The abstract will be distributed without the rest of the
% paper so it must be entirely self-contained.

\begin{abstract}
We derive a formula for the generating function of $d$-irreducible bipartite planar maps with
several boundaries, i.e.\ having several marked faces of controlled degrees.
It extends a formula due to Collet and Fusy for the case of arbitrary (non necessarily irreducible) bipartite planar maps, which is recovered by taking $d=0$.
As an application, we obtain an expression for the number of $d$-irreducible bipartite planar maps with a prescribed 
number of faces of each allowed degree. Very explicit expressions are given in the case of maps without multiple 
edges ($d=2$), $4$-irreducible maps and maps of girth at least $6$ ($d=4$). Our derivation is based 
on a tree interpretation of the various encountered generating functions.

  % keywords are optional
 % \bigskip\noindent \textbf{Keywords:} graph reconstruction
  %conjecture; Broglington manifold; Pipletti's classification
\end{abstract}

\section{Introduction}
\label{sec:intro}

This note is an extension of a preceding paper \cite{IRRED} on the enumeration of 
$d$-irreducible planar maps via slice decomposition. We shall use here a number of results from this
paper, which the reader is invited to consult for explicit proofs.

We recall that a {\it planar map} is a cellular embedding of a graph in the sphere, considered up to continuous deformation.
A map is {\it bipartite} if one can color its vertices in black and white so that no two adjacent vertices have the same color.
A necessary and sufficient condition for a planar map to be bipartite is that all its faces have even degrees. 
This paper deals exclusively with planar bipartite maps.

Ref.~\cite{IRRED} was mainly devoted to the enumeration of {\it maps with a single boundary}, i.e.\ maps with a distinguished oriented 
edge (the root edge) and with a control on its {\it outer degree}, i.e.\ the degree of the face lying on the right of this edge (the root face).
By first choosing the root face, then the root edge, maps with a single boundary may alternatively be defined as {\it maps 
with a distinguished face of controlled degree} and with a marked oriented edge incident to this face
whose orientation is such that the distinguished face lies on its right. In this paper, we shall extend this definition to
maps with a number $r\geq 2$ of boundaries, namely maps with $r$ distinguished faces of controlled degrees, 
and with a marked oriented edge incident to each distinguished face (again with an orientation such that the distinguished face at hand
lies on its right). The faces which have not been distinguished will be referred to as {\it inner faces}. Note that
maps with $r\geq 2$ boundaries have at least two faces, so they cannot be reduced to trees. The case of
maps with two boundaries was actually discussed already at the end of Ref.~\cite{IRRED} and we shall rely here on the
corresponding results. 

Throughout this paper, we consider $d$ some even integer larger than or equal to 2.
We set for convenience
\begin{equation}\label{eq:db}
d=2b
\end{equation}
with $b$ an integer larger than or equal to 1.
The results presented here concern the enumeration of so-called {\it $d$-irreducible} maps, as defined
now. Recall that the {\it girth} of a map is the minimal length (number of edges) of its cycles (simple closed paths). 
Note that the girth of a bipartite map is necessarily even.
A map with one or several boundaries is said {\it $d$-irreducible} if its girth is at least
$d$ and if all its cycles of length $d$ are the boundary of an inner face of degree $d$. 
Clearly, in a $d$-irreducible map with $r\geq 2$ boundaries, all inner faces 
have a degree larger than or equal to $d$ (by the girth condition) and all the boundary faces have
a degree strictly larger than $d$ (by our definition, a $d$-irreducible map with a boundary face of degree $d$ is either reduced
to a tree or has a single inner face of degree $d$ and no other boundary face).
Thus, the only non-trivial case to consider is when all 
the marked faces have a degree {\it strictly} larger than $d$.
We shall enumerate $d$-irreducible maps with a weight $z$ per $d$-valent inner face and a 
weight $x_{2j}$ per $2j$-valent inner face for $j>b$ (recall that all faces have even degree in a bipartite map),
the marked faces receiving no weight.
We then denote by 
\begin{equation}\label{eq:Fdef}
F_{2j_1,2j_2,\ldots,2j_r}^{(d)}\equiv F_{2j_1,2j_2,\ldots,2j_r}^{(d)}(z;x_{d+2},x_{d+4},\ldots )
\end{equation}
 the generating function of $d$-irreducible maps with 
$r$ boundaries whose marked faces have respective degrees $2j_1, 2j_2,\ldots,2j_r$, with $j_\ell \geq b$, $\ell=1,\ldots r$
(it vanishes as soon as $j_\ell=b$ for some $\ell$). 
The main result of this paper is a general expression for this generating function:

\begin{theorem}\label{thm:main}
For $d=2b\geq 2$ and $r\geq 2$, we have
\begin{equation}\label{eq:restwo}
F^{(d)}_{2j_1,2j_2,\ldots,2j_r} ={1\over (r-2)b +
\sum\limits_{\ell=1}^r j_\ell} \prod_{\ell=1}^r 2 j_\ell {2j_\ell-1\choose j_\ell+b}  {\partial^{r-2}\over \partial z^{r-2}} (R^{(d)})^{(r-2)b+\sum\limits_{\ell=1}^r j_\ell}
\end{equation}
where $R^{(d)}$ is the formal power series determined by
\begin{equation}\label{eq:eqforRd}
z + \sum_{\ell=0}^{b} (-1)^{b-\ell} {b+\ell \choose 2\ell} {\rm Cat}(\ell) (R^{(d)})^{b-\ell}
+ \sum_{j \geq b+1} {2j-1 \choose j+b} x_{2j} (R^{(d)})^{b+j}=0\ .
\end{equation}
In particular,  if we impose an upper bound on the degree of the faces
(i.e.\ $x_{2j}$ vanishes for $j$ large enough), then $F^{(d)}_{2j_1,2j_2,\ldots,2j_r}$ is algebraic.
\end{theorem}

Note that, if we take formally $d=0$ (i.e.\ $b=0$) in
\eqref{eq:restwo}, we recover a formula due to Collet and Fusy
\cite{CF} for the case of arbitrary (non necessarily irreducible)
bipartite planar maps, upon understanding $z$ as a weight per vertex
and identifying $R^{(0)}$ properly (beware that \eqref{eq:eqforRd} is {\it not} valid
for $d=0$), see the discussion in Section~\ref{sec:d0} below.  

The paper is organized as follows. Section~\ref{sec:genfun} presents a
proof of Theorem~\ref{thm:main}. Our starting point is a formula from \cite{IRRED} for
the generating function of $d$-irreducible maps with $r=2$ boundaries,
which we recall in Section~\ref{sec:twobound}.  We then show in
Section~\ref{sec:treerep} how to interpret the various intermediate
functions at hand as generating functions for decorated trees. The
core of the proof of Theorem~\ref{thm:main} comes in
Section~\ref{sec:multibound}: the generating function of maps with several boundaries is shown
to coincide with that of trees with several marked vertices, which are
themselves, via a construction reminiscent of that of \cite{CF}, in bijection with appropriate forests. 
Section~\ref{sec:enum} discusses applications to
enumeration, i.e.\ expressions for numbers of rooted bipartite planar
$d$-irreducible maps with a prescribed face degree distribution. A
general formula is given in Section~\ref{sec:genfor}. By taking $d=2$
and forbidding inner bivalent faces, we recover in
Section~\ref{sec:nomulti} a formula from \cite{BFb} concerning maps
without multiple edges. The cases of $4$-irreducible maps and maps of
girth at least $6$ are discussed very explicitly in the respective
Sections~\ref{sec:4irr} and \ref{sec:girth6}. Section~\ref{sec:d0}
shows how the Collet-Fusy formula is recovered by taking formally
$d=0$ in our formulas. A few concluding remarks are gathered in
Section~\ref{sec:conc}.



\section{Generating functions for $d$-irreducible maps}
\label{sec:genfun}

\subsection{The starting point: $d$-irreducible maps with two boundaries}
\label{sec:twobound}

Our starting point is a formula for the quantity \eqref{eq:Fdef} at $r=2$, namely the 
generating function $F^{(d)}_{2j_1,2j_2}$ of $d$-irreducible bipartite maps with 
two boundaries of respective lengths $2j_1$ and $2j_2$. From \cite[eq.~(9.17)]{IRRED}, it is given by
 \begin{equation}\label{eq:Ftwobound}
 F^{(d)}_{2j_1,2j_2} = 2j_1 {2j_1-1 \choose j_1+b} 2j_2 {2j_2-1 \choose j_2+b}  {(R^{(d)})^{j_1+j_2} 
\over j_1+j_2} \qquad j_1,j_2 > b ,
\end{equation}
where the function $R^{(d)}$ is a fundamental object related via
\begin{equation}\label{eq:Rd}
R^{(d)}=1+U^{(d)}_0
\end{equation}
to the first member $U^{(d)}_0$ of a family of {\it slice generating functions} $U_k^{(d)}$, $0\leq k\leq b$.
We shall not explain here what are precisely the ``slices" enumerated by $U_k^{(d)}$ and refer to \cite{IRRED} 
for such a discussion. We remind simply that slices appear as the result of a cutting of the
maps along geodesic paths, and have themselves a recursive decomposition.  As a consequence, 
the generating functions  $U_k^{(d)}$ are fully determined via a set of recursive equations
\begin{equation}\label{eq:recurU}
U_k^{(d)}=z \delta_{k,b-1}+\sum_{q\geq 1} \sum_{
k_1,\ldots,k_q \geq 1 \atop k_1+\cdots+k_q=k+1 } \prod_{i=1}^{q} U_{k_i}^{(d)} \qquad 0\leq k\leq b-1 ,
\end{equation}
which, together with \eqref{eq:Rd}, form a closed system, once completed by the relation 
\begin{equation}\label{eq:Ubd}
U_b^{(d)} = \sum_{j \geq b+1} {2j-1 \choose j+b} x_{2j} (R^{(d)})^{j+b}.
\end{equation}
Our goal is to extend formula \eqref{eq:Ftwobound} to the case of maps with $r> 2$ boundaries.
\begin{figure}
  \begin{center}
    \includegraphics[width=11.cm]{trees}
  \end{center}
\caption{Tree building rules in the case $b>1$ (see text).}
\label{fig:trees}
\end{figure}
\begin{figure}
  \begin{center}
    \includegraphics[width=12.cm]{gftrees}
  \end{center}
\caption{Interpretation of $R^{(d)}$, $U^{(d)}_k$, $1\leq k\leq b-1$ and $Z^{(d)}_j,$ $j\geq b+1$ as
generating functions for planted trees.}
\label{fig:gftrees}
\end{figure}
\subsection{The tree representation}
\label{sec:treerep}
For $b>1$, we may eliminate explicitly $U^{(d)}_0$ and $U^{(d)}_b$ from the system \eqref{eq:Rd}-\eqref{eq:Ubd} by using $U^{(d)}_0=U^{(d)}_1$ 
(as obtained from \eqref{eq:recurU} at $k=0$) and using the expression \eqref{eq:Ubd} for  $U^{(d)}_b$, resulting in the system
\begin{equation}\label{eq:Rdrecu}
\begin{split}
R^{(d)}&=1+U_1^{(d)}\\
U_k^{(d)}&=\sum_{q\geq 1} \sum_{
1\leq k_1,\ldots,k_q \leq b-1 \atop k_1+\cdots+k_q=k+1 } \prod_{i=1}^{q} U_{k_i}^{(d)} \qquad 1\leq k\leq b-2\\
U_{b-1}^{(d)}&=\sum_{q\geq 2} \sum_{
1\leq k_1,\ldots,k_q \leq b-1 \atop k_1+\cdots+k_q=b } \prod_{i=1}^{q} U_{k_i}^{(d)}+\left(z + \sum_{j \geq b+1} Z^{(d)}_j\right)\\
Z^{(d)}_j&= {2j-1 \choose j+b} x_{2j} (R^{(d)})^{j+b}\qquad j\geq b+1 .
\end{split}
\end{equation}
In view of this system, we may reinterpret $R^{(d)}$, $U_k^{(d)}$, $1\leq k \leq b-1$ and $Z_j^{(d)}$, $j\geq b+1$  as generating functions  for particular planted plane trees built according to the following rules, displayed in fig.~\ref{fig:trees}. The trees are made of
\begin{itemize}
\item four types of vertices:
\begin{itemize}
\item black inner vertices (represented by filled dots);
\item white inner vertices carrying an arbitrary integer label $j\geq b+1$ (represented as circles with the label $j$ inside);
\item leaf-vertices (represented by hexagons);
\item a univalent root-vertex (represented by the ground symbol in fig.~\ref{fig:gftrees});
\end{itemize}
\item two types of edges:
\begin{itemize}
\item bi-oriented edges, i.e.\ edges carrying an arbitrary number $k$ between $1$ and $b-1$ of outgoing arrows pointing away 
from one of their extremities, and $b-k$ outgoing arrows pointing away from the other extremity.
These bi-oriented edges connect only black inner vertices or the root;
\item mono-oriented edges, carrying $b-1$ outgoing arrows pointing away 
from one of their extremities, being necessarily a black inner vertex or the root. The other
extremity (without arrows) is necessarily a white inner vertex or a leaf-vertex;
\end{itemize}
\item with the vertex constraints:
\begin{itemize}
\item black inner vertices have arbitrary degrees larger than or equal to $2$ but a fixed {\it out-degree}
equal to $b+1$. By out-degree of a vertex, we mean the total number of outgoing arrows pointing away from it. (Note
that the out-degree constraint restricts in practice the degree of black inner vertices, which can be at most $b+1$);
\item white inner vertices are incident to mono-oriented edges and to two types of decorations:
buds (represented with a semi-circular endpoint) and blossoms (represented with a triangular endpoint).
A white inner vertex with label $j$ has total degree $2j$ (including blossoms and buds) and a number $j-b-1$ of buds.
It is weighted by $x_{2j}$;
\item leaf-vertices have degree $1$ and are weighted by $z$.
\end{itemize}
\end{itemize}

\noindent The reader will easily check that the rules above are designed so as to reproduce the
equations \eqref{eq:Rdrecu} by a {\it canonical decomposition} of the (supposedly planted) trees into descending subtrees 
by cutting them at the level of their first vertex. This vertex can be a black inner vertex of degree $q+1$ ($q\geq 1$),
reproducing the $q$-dependent terms in \eqref{eq:Rdrecu}, a white inner vertex with label $j$, reproducing the 
$j$-dependent terms in \eqref{eq:Rdrecu}, or a leaf-vertex, reproducing the $z$-dependent term in \eqref{eq:Rdrecu}.
More precisely, $R^{(d)}$, $U_k^{(d)}$, $1\leq k \leq b-1$ and $Z_j^{(d)}$, $j\geq b+1$ are easily 
identified with the generating functions for the planted trees displayed in fig.~\ref{fig:gftrees}.
Let us mention that similar trees (without leaf-vertices) were introduced in \cite{BFa,BFb} in the context of maps with
controlled girth. This is consistent with the fact that, as observed in \cite{IRRED}, enumerating such maps indeed corresponds 
to imposing $z=0$ in our setting. 
\begin{figure}
  \begin{center}
    \includegraphics[width=12cm]{treesbone}
  \end{center}
\caption{Tree building rules in the case $b=1$.}
\label{fig:treesbone}
\end{figure}

For $b=1$, eqs.~\eqref{eq:Rd}-\eqref{eq:Ubd}  simply reduce to
\begin{equation}\label{eq:Rbone}
\begin{split}
R^{(2)}&=1+z+\sum_{j \geq 2} Z^{(2)}_j\ ,\\
Z^{(2)}_j&= {2j-1 \choose j+1} x_{2j} (R^{(2)})^{j+1}\ , \qquad j\geq 2\\
\end{split}
\end{equation}
and may be viewed as generating the simpler trees of fig.~\ref{fig:treesbone} with un-oriented edges.

\subsection{A formula for the generating function of $d$-irreducible maps with $r\geq 2$ boundaries}
\label{sec:multibound}

Returning to the general case $b\geq 1$, we now consider the generating function $ F^{(d)}_{2j_1,2j_2,\ldots,2j_r}$
for maps with  $r\geq 2$ boundaries. Since $r\geq 2$, maps enumerated by $ F^{(d)}_{2j_1,2j_2,\ldots,2j_r}$ may be obtained from 
maps enumerated by $F^{(d)}_{2j_1,2j_2}$ by  a simple marking of $r-2$ extra faces of respective degrees $2j_3,2j_4,\ldots 2j_r$.
After marking, these extra faces are no longer considered as inner faces. Still the constraint that $d$-cycles must be boundaries 
of inner faces of degree $d$ is not affected by the marking upon assuming that the marked faces all have degree strictly larger than $d$
(i.e.\ we assume from now on $j_\ell>d$, $\ell=1,\ldots,r$). Note that Theorem~\ref{thm:main} is trivially true when this assumption
does not hold, for both sides of \eqref{eq:restwo} vanish.
At the level of generating function, the marking is performed via the action of derivatives with respect to $x_{2j_\ell}$ for $\ell=3,\ldots r$,
namely
\begin{equation}\label{eq:multibound}
F^{(d)}_{2j_1,2j_2,\ldots,2j_r}=\left(\prod _{\ell=3}^r 2 j_\ell {\partial\over \partial x_{2j_\ell}}\right) F^{(d)}_{2j_1,2j_2}\ ,
\qquad r\geq 2
\end{equation}
(with the usual convention that the empty product represents the identity operator). 
Here the $2j_\ell$ factors account for the choice of an oriented edge incident to each newly marked face.
\begin{figure}
  \begin{center}
    \includegraphics[width=7.cm]{specialroot}
  \end{center}
\caption{The building rule of the special vertex labeled by $j_1$ and $j_2$. It has degree $j_1+j_2+1$ 
and is incident to mono-oriented (or un-oriented if $b=1$) edges or blossoms only. The edge connecting it to the root is a 
mono-oriented edge (with thus $b-1$ arrows pointing away from the root -- it is un-oriented if $b=1$).}
\label{fig:specialroot}
\end{figure}

From \eqref{eq:Ftwobound}, we may thus write
\begin{equation}\label{eq:combin}
F^{(d)}_{2j_1,2j_2,\ldots,2j_r}=\prod_{\ell=1}^r 2 j_\ell \ \times {{2j_1-1 \choose j_1+b} {2j_2-1\choose j_2+b}\over j_1+j_2}
\times \ H^{(d)}_{2j_1,2j_2;2j_3,\ldots,2j_r}
\end{equation}
where
\begin{equation}\label{eq:Gdef}
H^{(d)}_{2j_1,2j_2;2j_3,\ldots,2j_r}= \left(\prod_{\ell=3}^r {\partial\over \partial x_{2j_\ell}} \right) 
(R^{(d)})^{j_1+j_2}\ .
\end{equation}
In the tree language, the function $H^{(d)}_{2j_1,2j_2;2j_3,\ldots,2j_r}$ can be interpreted as the generating function for planted
trees built according to the rules of fig.~\ref{fig:trees} (or of fig.~\ref{fig:treesbone} if $b=1$), whose root is adjacent to a first special vertex carrying
both labels $j_1$ and $j_2$, as 
displayed in fig.~\ref{fig:specialroot}, and with $r-2$ marked white inner vertices of respective degrees $2j_3, 2j_3,\ldots,2 j_r$.
The building rule of the special vertex is designed to reproduce the term $(R^{(d)})^{j_1+j_2}$ in \eqref{eq:Gdef}: this special 
vertex must have total degree $j_1+j_2+1$ 
and be incident to mono-oriented (or un-oriented if $b=1$) edges or blossoms only. The special vertex and the $r-2$ 
marked white inner vertices receive no weight.
Let us now show that we may write the generating function $H^{(d)}_{2j_1,2j_2;2j_3,\ldots,2j_r}$ as 
\begin{equation}\label{eq:resone}
\begin{split}
H^{(d)}_{2j_1,2j_2;2j_3,\ldots,2j_r}& =\prod_{\ell=3}^r {2j_\ell-1\choose j_\ell+b} \\
 & \times 
\sum_{p=1}^{r-2} {r-3 \choose p-1} {\partial^p \over \partial z^p} (R^{(d)})^{j_1+j_2}  {\partial^{r-p-2} \over \partial z^{r-p-2}} (R^{(d)})^{\sum\limits_{\ell=3}^r (j_\ell+b)}\ . 
\end{split}
\end{equation}
\begin{figure}
  \begin{center}
    \includegraphics[width=14.cm]{forest2}
  \end{center}
\caption{Schematic picture of the bijection between the trees enumerated by $H^{(d)}_{2j_1,2j_2;2j_3,\ldots,2j_r}$ with
a number $p$ of first generation vertices, supposedly numbered $1$ to $p$ is all possible ways (hence
the factor $p!$) and pairs made of (i) a forest of $p$ trees with roots labeled $1$ to $p$, with $(r-p-2)$ marked non-root white vertices 
and (ii) a tree with first special vertex and $p$ marked leaf-vertices labeled $1$ to $p$.
Here $p=3$ and $r=8$.}
\label{fig:foresttwo}
\end{figure}
We shall proceed in two steps: the trees enumerated by $H^{(d)}_{2j_1,2j_2;2j_3,\ldots,2j_r}$ have a number
$p\geq 1$ of ``first generation" marked white vertices, which have the special vertex as ``direct" ancestor, i.e.\ are such
that the branch from the special vertex to them does not pass via any other marked 
white vertex. We number these first generation vertices from $1$ to $p$ (in all possible ways so that each tree is counted $p!$ times -
see fig.~\ref{fig:foresttwo}, left) and cut the tree at the level of their mono-oriented incident edge in the ascendent part of the tree. The $p$ cut parts form 
a forest made of $p$ rooted trees, whose roots are incident to the $p$ first generation vertices, and are labeled $1$ to $p$
(see fig.~\ref{fig:foresttwo}, right).  This forest is equipped with a total of $(r-p-2)$ marked white vertices (those which are not
first generation). 
As for the part containing the special vertex, we may repair it by adding a leaf-vertex to each of the
cut mono-oriented edges, thus re-creating a tree satisfying the rules of fig.~\ref{fig:trees}, with root adjacent to the special vertex, and with 
now $p$ marked (and labeled) leaf-vertices. These marked leaf-vertices receive no weight, so
the generating function for such trees is simply
\begin{equation}\label{eq:firstblock}
{\partial^p\over \partial z^p} (R^{(d)})^{j_1+j_2}\ .
\end{equation}
This explains the $j_1,j_2$-dependent term in \eqref{eq:resone}. Moreover, the $p!$ to $1$ correspondence
displayed in fig.~\ref{fig:foresttwo} can be made $1$ to $1$ by simply removing the labeling of the 
tree roots in the forest part.
\begin{figure}
  \begin{center}
    \includegraphics[width=14.cm]{forest1}
  \end{center}
\caption{Schematic picture of the correspondence between forests of $p$ unlabeled trees with $(r-p-2)$ marked
non-root white vertices and forests with $(r-2)$ unlabeled trees equipped with a total of $(r-p-2)$ marked leaf-vertices
labeled $1$ to $(r-p-2)$. The correspondence is $(r-p-2)!$ to $(r-3)!/(p-1)!$ (see text). Here $p=3$ and $r=8$.}
\label{fig:forestone}
\end{figure}

In a second step, the enumeration of the complementary forest part is achieved as in \cite{CF} via a (many-to-many) correspondence between
forests of $p$ trees with a total of $(r-p-2)$ marked white non-root vertices (left side of fig.~\ref{fig:forestone}) and 
forests of $(r-2)$ trees and a total of
$(r-p-2)$ marked leaf-vertices (right side of fig.~\ref{fig:forestone}). We proceed as before by first 
labeling the $(r-p-2)$ marked white non-root vertices in all possible ways (each forest is thus counted $(r-p-2)!$ times) and cutting
the trees in the forest at the level of the mono-oriented edges leading to all these vertices. The cut mono-oriented
edges are as before completed by new added leaf-vertices in the {\it ascending part} of the trees and serve as roots
for the descending parts. The net result is a forest of $(r-2)$ trees whose roots are incident to the $(r-2)$ marked white vertices
with degrees $2j_3,\ldots,2j_r$, equipped with a total of $(r-p-2)$ marked leaf-vertices labeled $1$ to $(r-p-2)$. 
These forests are counted by 
\begin{equation}\label{eq:secondblock}
{\partial^{r-p-2} \over \partial z^{r-p-2}}\prod_{\ell=3}^r \left( {2j_\ell-1\choose j_\ell+b} 
(R^{(d)})^{j_\ell+b} \right)
\end{equation}
which explains the $(j_3\to j_r)$-dependent terms in \eqref{eq:resone}. The correspondence is not simply $(r-p-2)!$ to $1$ since, in 
\eqref{eq:secondblock}, we erased the information on how to reassemble the trees. The appropriate counting is more transparent if 
we start conversely from a forest of $(r-2)$ trees with a total of $(r-p-2)$ marked leaves: we then rebuild a forest of $p$ trees
and $(r-p-2)$ marked (and labeled) white non-root vertices by first replacing the marked leaf-vertex labeled $1$ by 
a descending subtree chosen among any of the trees in the forest which do not carry this marked leaf-vertex ($r-3$ choices),
creating a new forest {\it with one less tree}, then replacing the marked leaf-vertex labeled $2$ by 
a descending subtree formed by any of the trees in the new forest which do not carry this marked leaf-vertex ($r-4$ choices),
and continue until the $(r-p-2)$-th marked leaf-vertex in replaced by a descending subtree ($p$ choices). This leaves us with the desired forest 
with $p$ trees. Clearly, each configuration is counted $(r-3)!/(p-1)!$ times so that the correspondence is eventually
$(r-p-2)!$ to $(r-3)!/(p-1)!$, which explains the binomial factor ${r-3 \choose p-1}$ in \eqref{eq:resone}.

Now the sum in \eqref{eq:resone} may be simply evaluated through
\begin{equation}\label{eq:sumeval}
\begin{split}& 
\sum_{p=1}^{r-2} {r-3 \choose p-1} {\partial^p \over \partial z^p} (R^{(d)})^{j_1+j_2}  {\partial^{r-p-2} \over \partial z^{r-p-2}} (R^{(d)})^{\sum\limits_{\ell=3}^r (j_\ell+b)}\\ &\quad = {\partial \over \partial \zeta}\left\{
\sum_{p=1}^{r-2} {r-3 \choose p-1} {\partial^{p-1} \over \partial z^{p-1}} (R^{(d)}(z+\zeta))^{j_1+j_2}  {\partial^{r-p-2} \over \partial z^{r-p-2}} (R^{(d)}(z))^{\sum\limits_{\ell=3}^r (j_\ell+b)} \right\}_{\zeta=0}
\\ &\quad = {\partial \over \partial \zeta }\left\{ {\partial^{r-3}\over \partial z^{r-3}} \left(
(R^{(d)}(z+\zeta))^{j_1+j_2} (R^{(d)}(z))^{\sum\limits_{\ell=3}^r (j_\ell+b)} \right)\right\}_{\zeta=0}\\
 &\quad = {\partial^{r-3}\over \partial z^{r-3}}
 {\partial \over \partial \zeta }\left\{  (R^{(d)}(z+\zeta))^{j_1+j_2} (R^{(d)}(z))^{\sum\limits_{\ell=3}^r (j_\ell+b)}\right\}_{\zeta=0}
 \\
  &\quad = {\partial^{r-3}\over \partial z^{r-3}} {j_1+j_2 \over j_1+j_2+\sum\limits_{\ell=3}^r (j_\ell+b)}
 {\partial \over \partial \zeta }\left\{ (R^{(d)}(z+\zeta))^{{j_1+j_2}+\sum\limits_{\ell=3}^r (j_\ell+b)}\right\}_{\zeta=0}
 \\
 &\quad =  {j_1+j_2\over (r-2)b+\sum\limits_{\ell=1}^r j_\ell} {\partial^{r-2}\over \partial z^{r-2}}
 (R^{(d)})^{(r-2)b+\sum\limits_{\ell=1}^r j_\ell}\ .
\end{split}
\end{equation}
Here we simply used Leibniz formula to go from the second to the third
line, as well as elementary operations.  Plugging this result in
\eqref{eq:resone} and \eqref{eq:combin}, we arrive at our main formula
\eqref{eq:restwo}.  In this formula, the function $R^{(d)}$ is the
solution of eqs.~\eqref{eq:Rd}-\eqref{eq:Ubd}. As shown in
\cite{IRRED}, this system reduces after elimination to the single
equation \eqref{eq:eqforRd} for $R^{(d)}$. This completes the proof of
Theorem~\ref{thm:main}.


\section{Enumeration formulas}
\label{sec:enum}

\subsection{A general formula}
\label{sec:genfor}

A direct corollary of Theorem~\ref{thm:main} is a formula for the {\it number} $N^{(d)}_m(\{q_j\}_{j\geq b})$ of rooted bipartite planar $d$-irreducible maps
with outer degree $2m$ ($m\geq b+1$) and with $q_j$ faces of degree $2j$, $j\geq b$ (distinct from the root face if $j=m$). 
It is obtained by marking in the map {\it all the faces with degree strictly larger than $b$}, leaving the $d$-valent faces only as inner faces.
In \eqref{eq:restwo}, the function $R^{(d)}$ must therefore be evaluated at $x_{2j}=0$ for all $j>b$. We call $r^{(d)}(z)$ this function, which is obtained by solving \eqref{eq:Rdrecu} (or \eqref{eq:Rbone} if $b=1$)
at $Z^{(d)}_j=0$ for all $j$. It is determined by the equation
\begin{equation}\label{eq:eqforrd}
z + \sum_{\ell=0}^{b} (-1)^{b-\ell} {b+\ell \choose 2\ell} {\rm Cat}(\ell) (r^{(d)})^{b-\ell} = 0,
\end{equation}
as read off eq.~\eqref{eq:eqforRd} at $x_{2j}=0$, $j>b$. Eq.~\eqref{eq:restwo} translates directly into:

\begin{proposition}\label{prop:genformula}
  For $m$ and $q_b,q_{b+1},q_{b+2},\ldots$ nonnegative integers such that $m
  \geq b+1$ and $1 \leq \sum\limits_{j>b} q_j < \infty$, the number
  $N^{(d)}_m(\{q_j\}_{j\geq b})$ of rooted bipartite planar
  $d$-irreducible maps with outer degree $2m$ and with $q_j$ non-root faces of
  degree $2j$ for all $j$ reads
  \begin{equation}\label{eq:microcanonical}
    \begin{split}
      N^{(d)}_m(\{q_j\}_{j\geq b})& = (2m){2m-1 \choose m+b}
      \prod_{j>b} {1\over q_j!} {2j-1\choose j+b}^{q_j}\\ &\quad
      \times {1\over E+b(F-2-2q_b)} {(F-2)!\over q_b!} [z^{F-2}]
      (r^{(d)}(z))^{ E+b(F-2-2q_b)}
    \end{split}
  \end{equation}
  where $F$ and $E$ are the total numbers of faces and edges
  respectively, and $r^{(d)}$ is determined by \eqref{eq:eqforrd}.
\end{proposition}

Note the absence of the factors $2j$ in the product which, in \eqref{eq:restwo}, accounted for a choice of edge incident
to each marked face. Here only the root face receives such a factor. Note also the factorial factors since,
as opposed to \eqref{eq:restwo}, the marked faces are not distinguished. 
We have used the identities
\begin{equation}\label{eq:EF}
\begin{split}F&= 1+q_b+\sum_{j>b}q_j\\
E& =m+b\, q_b+\sum_{j>b}j\, q_j\\
\end{split}
\end{equation}
which lead to the identifications $r=1+\sum\limits_{j>b}q_j=F-q_b$ and $(r-2)b+\sum\limits_{\ell=1}^r j_\ell=
(r-2)b+m+\sum\limits_{j>b}j q_j=E+b(F-2-2q_b)$. Expression \eqref{eq:microcanonical} is valid for 
$F=1+q_b+\sum\limits_{j>b} q_j \geq 2+q_b$, i.e.\ with at least two faces of degree strictly larger than $b$.

\subsection{Bipartite maps without multiple edges}
\label{sec:nomulti}
A first case of interest corresponds to bipartite maps without multiple edges, i.e.\ bipartite maps
of girth at least $4$. These maps are simply obtained from $2$-irreducible maps ($b=1$) by forbidding 
bivalent faces, i.e.\ setting $q_1=0$.
Using $r^{(2)}(z)=1+z$ (as seen directly from \eqref{eq:Rbone} at $Z^{(2)}_j=0$ for all $j$), and
\begin{equation}\label{eq:caldrtow}
(F-2)! [z^{F-2}](1+z)^{E+F-2}={(E+F-2)!\over E!}
\end{equation}
we obtain from Proposition \ref{prop:genformula} that:

\begin{proposition}\label{prop:nomul}
For $m\geq 2$ and $q_{2},q_{3},\ldots$ nonnegative integers, 
the number ${\cal N}^{(4)}_m(\{q_j\}_{j\geq 2})$ ($= N^{(2)}_m(\{q_j\}_{j\geq 1})$ at $q_1=0$) of rooted bipartite planar 
maps {\it without multiple edges}, with outer degree $2m$ and with $q_j$ non-root faces of degree $2j$ for all $j$ reads
 \begin{equation}\label{eq:nnomult}
  {\cal N}^{(4)}_m(\{q_j\}_{j\geq 2}) = (2m){2m-1 \choose m+1}
  \prod_{j>1} {1\over q_j!} {2j-1\choose j+1}^{q_j} {(E+F-3)!\over E!}
 \end{equation}
where $E=m+\sum\limits_{j>1}j\, q_j$ is the total number of edges, and $F=1+\sum\limits_{j>1}q_j$ the total number
of faces. 
\end{proposition}
This expression agrees with Proposition 35 in \cite{BFb}, up to a trivial rerooting factor.
Note that our derivation of Proposition \ref{prop:nomul} from Proposition \ref{prop:genformula} requires at least two faces ($F\geq 2$) but
formula \eqref{eq:nnomult} is also correct at $F=1$ ($q_j=0$ for all $j$, hence $E=m$),  where the r.h.s.\ yields the $m$-th Catalan number, as wanted.

For instance, we may obtain the number of rooted $2m$-angulations ($m\geq 2$) without multiple edges, with $F$ faces,
by simply setting $q_j=(F-1)\delta_{j,m}$, namely
\begin{equation}\label{eq:twomang}
2m {2m-1\choose m+1} {1\over (F-1)!} {2m-1\choose m+1}^{F-1} {(E+F-3)!\over E!}=
2m {2m-1\choose m+1}^F{((m+1)F-3)!\over (F-1)!(mF)!}
\end{equation}
since $E=m F$ in this case. For $m=2$, this yields the well-known number of quadrangulations without multiple
edges \cite{TutteCPM,BrownNS,BT,SJ,DSQ}
\begin{equation}\label{eq:quadwithnomu}
4 {(3F-3)! \over (F-1)!(2F)!}= 2 {(3F-3)! \over F!(2F-1)!}
\end{equation}
in terms of the number $F$ of faces. 

\subsection{$4$-irreducible maps}
\label{sec:4irr}
Another case of interest concerns $4$-irreducible maps, which requires the knowledge of 
$r^{(4)}(z)$. From \eqref{eq:eqforrd}, we immediately obtain
\begin{equation}\label{eq:valrfour}
r^{(4)}(z)=1+{1-\sqrt{1-4z}\over 2}\ .
\end{equation}
After some straightforward algebra, we find, for $p>0$ and $s \geq 0$
\begin{equation}\label{eq:dqrfourp}
\begin{split}{s! \over p}[z^{s}] (r^{(4)})^p
& = {\delta_{s,0} \over p} + (s-1)!
\sum_{\ell=0}^{\min(p-1,s-1) }{p-1 \choose \ell} {2(s-1)-\ell \choose s-1}\\
&=  {\delta_{s,0} \over p} +{(2(s-1))!\over(s-1)! }\  {}_2F_1(1-p,1-s,2(1-s);-1)
\\
\end{split}
\end{equation}
in terms of the hypergeometric function ${}_2F_1$ (here the second term in the r.h.s. must be understood as
$0$ if $s=0$). Using this expression at $p=E+2F-4-4q_2$ and $s=F-2$,
we arrive at the formula
\begin{equation}\label{eq:Nfourl}
\begin{split}N^{(4)}_m(\{q_j\}_{j\geq 2})& = (2m){2m-1 \choose m+2}
\prod_{j>2} {1\over q_j!} {2j-1\choose j+2}^{q_j}\\ &\ \times\!
\left\{{\delta_{F,2} \over E}\!
+\!{(2(F\!-\!3))!\over q_2! (F\!-\!3)! }\  {}_2F_1(5\!-\!E\!-\!2F\!+\!4q_2,3\!-\!F,2(3\!-\!F);-1)\right\}
\ ,\\
\end{split}
\end{equation}
valid for $F\geq 2+q_2$, i.e.\ with at least two faces of degree strictly larger than $4$ (note that setting $F=2$ 
implies necessarily $q_2=0$). As before, the second term is understood as $0$ if $F=2$. 
\begin{figure}
  \begin{center}
    \includegraphics[width=8.cm]{sixsix}
  \end{center}
\caption{$4$-irreducible maps made of two hexagons and $q_2$ squares, for $q_2=0,1$ and $2$. For each
map, we indicated its multiplicity corresponding to the number of inequivalent possible choices of a root edge (not drawn here) 
incident to the outer hexagonal face.}
\label{fig:sixsix}
\end{figure}

A simple application concerns maps with exactly two faces of degree strictly larger than $4$: the root face
of degree $2m$ ($m>2$) and another face of degree $2m'$ ($m'>2$). We have in this case
$q_j=\delta_{j,m'}+q_2 \delta_{j,2}$, $E=m+m'+2 q_2$ and $F=2+q_2$, so that we find a number
of rooted $4$-irreducible maps equal two
\begin{equation}\label{eq:fourmmprime}
2m{2m-1\choose m+2} {2m'-1\choose m'+2} \left\{{\delta_{q_2,0}\over m\!+\!m'}
\!+\!{(2(q_2-1))!\over q_2!(q_2-1)!}\  {}_2F_1(1\!-\!(m\!+\!m'),1\!-\!q_2,2(1\!-\!q_2),-1) \right\}
\end{equation}
where the second term is to be understood as $0$ for $q_2=0$. For $m=m'=3$, it gives the 
sequence
\begin{equation}\label{eq:seq}
1, 6, 21, 62, 180, 540, 1683, 5418, 17901, 60390, 207207, 720954, 2537964, \
9023328
\end{equation}
whose first three terms correspond to the maps displayed in fig.~\ref{fig:sixsix}.
\subsection{Maps with girth at least $6$}
\label{sec:girth6}
If we specialize the result of the previous subsection to the case $q_2=0$, we obtain
the number of rooted maps with girth at least $6$, with outer degree $2m$ ($m\geq 3$) and with 
$q_j$ non-root faces of degree $2j$ ($j\geq 3$):
\begin{equation}\label{eq:girthsixl}
\begin{split}{\cal N}^{(6)}_m(\{q_j\}_{j\geq 3})& = (2m){2m-1 \choose m+2}
\prod_{j>2} {1\over q_j!} {2j-1\choose j+2}^{q_j}\\ &\ \times\!
\left\{{\delta_{F,2} \over E}\!
+\!{(2(F\!-\!3))!\over (F\!-\!3)! }\  {}_2F_1(5\!-\!E\!-\!2F,3\!-\!F,2(3\!-\!F);-1)\right\}
\ . \\
\end{split}
\end{equation}
If all faces have degree $6$, i.e.\ $m=3$, $q_j=(F-1)\delta_{j,3}$, and $E=3F$, we obtain the
number of rooted hexangulations of girth $6$ with $F$ faces
\begin{equation}\label{eq:hexgirthsixl}
 \delta_{F,2} 
+6 \!{(2(F\!-\!3))!\over (F\!-\!1)!(F\!-\!3)! }\  {}_2F_1(5(1-\!F),3\!-\!F,2(3\!-\!F);-1)
\end{equation}
(as before, the second term is to be understood as $0$ when $F=2$). It gives the sequence
\begin{equation}\label{eq:firsthex}
1, 3, 17, 128, 1131, 11070, 116317, 1287480, 14829188, 176250143, 2148687567
\end{equation}
corroborating the result of \cite{BFa,OEIS}.
 
\section{The case $b=0$}
\label{sec:d0}
It is interesting to include in our framework the case of general bipartite maps, without
constraints of irreducibility. Indeed, we observe that, while our derivation of Theorem \ref{thm:main} and its consequences was done 
assuming $b\geq 1$, previously known formulas for general bipartite maps may 
be recovered by taking formally $b=0$. This should not come as a surprise since 
general bipartite maps correspond indeed to $0$-irreducible bipartite maps.  Eq.~\eqref{eq:Ftwobound} at
$b=0$ matches exactly the known formula \cite{CF}
 \begin{equation}\label{eq:Ftwoboundbone}
 F_{2j_1,2j_2} = 2j_1 {2j_1-1 \choose j_1} 2j_2 {2j_2-1 \choose j_2}  {R^{j_1+j_2} 
\over j_1+j_2} \qquad j_1,j_2 > b ,
\end{equation}
for the generating function of bipartite maps with two boundaries of length $2j_1$ and $2j_2$,
if we take as $R^{(0)}$ the solution $R$ of
\begin{equation}\label{eq:Rbzero}
R =z+ \sum_{j \geq 1} Z_j, \qquad Z_j={2j-1 \choose j} x_{2j} R^{j}
\end{equation}
which replaces the system \eqref{eq:Rd}-\eqref{eq:Ubd} whenever $b=0$.
Here $z$ corresponds to a weight per {\it vertex} of the map, which again is not surprising since, in some sense, 
we may view the vertices as faces of degree $0$.
\begin{figure}
  \begin{center}
    \includegraphics[width=12.cm]{treeszero}
  \end{center}
\caption{Building rules of the trees enumerated by $R$ and $Z_j$ satisfying eq.~\eqref{eq:Rbzero}.}
\label{fig:treesbzero}
\end{figure}

The associated trees obey the rules displayed in fig.~\ref{fig:treesbzero}, and are nothing but
the well-known ``blossom trees" introduced in \cite{Schae,SchaeBCEM}, with ``buds" and ``leaves" corresponding respectively 
to our buds and our blossoms enhanced by a leaf-vertex. 
Setting $b=0$ in \eqref{eq:restwo} yields the known beautiful formula \cite{CF}
\begin{equation}\label{eq:restwozero}
F_{2j_1,2j_2,\ldots,2j_r} ={1\over
\sum\limits_{\ell=1}^r j_\ell} \prod_{\ell=1}^r 2 j_\ell {2j_\ell-1\choose j_\ell}  {\partial^{r-2}\over \partial z^{r-2}} R^{\sum\limits_{\ell=1}^r j_\ell}
\end{equation}
for the generating function of bipartite maps with multiple boundaries. 
Taking $r^{(0)}=z$ and formally $q_0=V$ and $F=2+E$ (indeed $F$ must be understood here as the number
of real faces plus that of degree-$0$ faces, i.e.\ vertices, a sum which equals $2+E$ from Euler's relation), 
eq.~\eqref{eq:microcanonical} yields
\begin{equation}\label{eq:microcanonical2}
N_m(\{q_j\}_{j\geq 1}) = (2m){2m-1 \choose m}
\prod_{j\geq 1} {1\over q_j!} {2j-1\choose j}^{q_j}\ \times {(E-1)!\over V!} 
\end{equation}
which is the well-known Tutte's formula for the number $N_m(\{q_j\}_{j\geq 1})$ of bipartite maps with root
face of degree $2m$ and with $q_j$ (non-root) faces of degree $2j$ \cite{TutteCS}. Here $E=m+\sum\limits_{j\geq 1} j q_j$
and $V=m+1+\sum\limits_{j\geq 1}(j-1)q_j$ denote the number of edges and vertices respectively.

\section{Concluding remarks}
\label{sec:conc}
Upon derivation with respect to $z$, formula \eqref{eq:restwo} yields 
\begin{equation}\label{eq:resthree}
{\partial \ \over \partial z}F^{(d)}_{2j_1,2j_2,\ldots,2j_r} ={1\over (r-2)b+
\sum\limits_{\ell=1}^r j_\ell} \prod_{\ell=1}^r 2 j_\ell {2j_\ell-1\choose j_\ell+b}  {\partial^{r-1}\over \partial z^{r-1}} (R^{(d)})^{(r-2)b+\sum\limits_{\ell=1}^r j_\ell}\ .
\end{equation}
In this form, it remains valid at $r=1$ since, as shown in \cite{IRRED}, the generating function for $d$-irreducible maps
with a single boundary of length $2j_1$ satisfies the so-called ``pointing formula" 
\begin{equation}\label{eq:Fndpointing}
{\partial F_{2j_1}^{(d)} \over \partial z} = {2j_1 \choose j_1-b} (R^{(d)})^{j_1-b}= {2j_1\over -b +j_1}{2j_1-1\choose j_1+b}
  (R^{(d)})^{-b+j_1} \qquad j_1> b .
\end{equation}
Conversely, we may use eq.~\eqref{eq:Fndpointing} as a starting point to derive eq.~\eqref{eq:resthree} from
the identity 
\begin{equation}\label{eq:multiboundone}
F^{(d)}_{2j_1,2j_2,\ldots,2j_r}=\left(\prod _{\ell=2}^r 2 j_\ell {\partial\over \partial x_{2j_\ell}}\right) F^{(d)}_{2j_1}\ ,
\qquad r\geq 1
\end{equation}
by following the same procedure as above via a decomposition of the appropriate trees with marked white vertices into
forests. Still going back from \eqref{eq:resthree} to \eqref{eq:restwo}  is not a simple matter as it requires integrating over $z$ and gives rise 
to some a priori unknown integration constant (which is $z$-independent but depends on the $j_\ell$'s). Fixing this constant 
requires knowing the value of $F^{(d)}_{2j_1,2j_2,\ldots,2j_r}$ at some particular value of $z$ (for instance at $z=0$ where it
enumerates maps with girth at least $d+2$), a problem whose difficulty might be comparable to that of the initial problem.
This is why we chose instead the generating function of maps with two boundaries as starting point.
 
Finally, we would like to stress that we used here trees as a simple tool to evaluate the wanted map generating functions
and did not recourse to any direct bijection between maps and trees. Nevertheless, we know from \cite{IRRED} that such direct bijections
do exist between the trees enumerated by $R^{(d)}$ and $U_k^{(d)}$, $k\geq 0$ and the so-called slices or $k$-slices 
(which are particular instances of $d$-irreducible maps) enumerated by the same functions. Ref.~\cite{IRRED} describes in details a direct
correspondence between trees and slices in the case $x_{2j}=0$, $j>b$, and this correspondence can easily be extended to the case
of non-vanishing $x_{2j}$'s. To obtain a direct bijection between $d$-irreducible maps with several boundaries and trees,
we would simply need a direct bijection between $d$-irreducible maps with {\it two} boundaries of lengths $2j_1$ and $2j_2$
and the trees enumerated by the r.h.s of \eqref{eq:Ftwobound}. We have not found any such bijection so far. In particular, 
eq.~\eqref{eq:Ftwobound} still awaits a direct bijective proof. This is to be contrasted with eq.~\eqref{eq:Fndpointing}, which was given in \cite{IRRED}
a direct bijective proof, which may be reformulated as a direct bijection with trees. However, as we just discussed, this formula is
not sufficient to recover our main result \eqref{eq:restwo}.

\subsection*{Acknowledgements}
The work of JB was partly supported by the ANR projects ``Cartaplus'' 12-JS02-001-01 and ``IComb'' ANR-08-JCJC-0011.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \bibliographystyle{plain} 
% \bibliography{myBibFile} 
% If you use BibTeX to create a bibliography
% then copy and past the contents of your .bbl file into your .tex file

\begin{thebibliography}{10}

\bibitem{IRRED} J. Bouttier and E. Guitter.  \newblock On irreducible maps and slices.  \newblock To appear in
{\em Combinatorics, Probability and Computing}, special issue dedicated to the Memory of Philippe Flajolet,
 \newblock arXiv:1303.3728 [math.CO].
\bibitem{CF} G. Collet and \'E. Fusy.  \newblock A simple formula for the series of bipartite and quasi-bipartite maps 
with boundaries.  \newblock {\em FPSAC 2012}, Nagoya, Japan, {\em DMTCS proc.,} AR:607-618, 2012, arXiv:1205.5215 [math.CO].
\bibitem{BFa} O. Bernardi and \'E. Fusy.  \newblock A bijection for triangulations, quadrangulations, pentagulations, etc.  \newblock {\em J.\ Combin.\ Theory Ser.\ A,} 119:218-244, 2012, arXiv:1007.1292 [math.CO].
\bibitem{BFb} O. Bernardi and \'E. Fusy.  \newblock Unified bijections for maps with prescribed degrees and girth.  \newblock {\em J.\ Combin.\ Theory Ser.\ A,} 119:1351-1387, 2012, arXiv:1102.3619 [math.CO].
\bibitem{TutteCPM} W.T. Tutte.  \newblock A Census of planar maps.  \newblock {\em Canad.\ J.\ Math.,} 
15:249-271, 1963.
\bibitem{BrownNS} W.G. Brown.  \newblock Enumeration of non-separable planar maps.  \newblock {\em Can.\ J.\ Math.,} 15:526-554, 1963.
\bibitem{BT} W.G. Brown and W.T. Tutte.  \newblock On the enumeration of rooted non-separable planar maps.  \newblock {\em Canad.\ J.\ Math.,} 16:572-577, 1964.
\bibitem{SJ} G. Schaeffer and B. Jacquard.  \newblock A bijective census of non-separable planar maps.  \newblock {\em J.\ Comb.\ Theory A,} 83:1-20, 1998.
\bibitem{DSQ} J. Bouttier and E. Guitter.  \newblock Distance statistics in quadrangulations with no multiple edges and the geometry of minbus.  \newblock {\em J.\ Phys.\ A: Math.\ Theor.,} 43:205207, 2010,
arXiv:1002.2552 [math-ph].
\bibitem{OEIS} see Sequence A179300 in {\em The On-Line Encyclopedia of Integer Sequences}, published electronically at http://oeis.org, 2010.
\bibitem{Schae} G. Schaeffer.  \newblock Conjugaison d'arbres et cartes combinatoires al\'eatoires.  \newblock PhD Thesis, Universit\'e 
Bordeaux I (1998).
\bibitem{SchaeBCEM} G. Schaeffer.  \newblock Bijective census and random generation of Eulerian planar maps.  \newblock {\em Electron.\ J.\ Combin.,}  4:R20, 1997.
\bibitem{TutteCS} W.T. Tutte.  \newblock A Census of slicings.  \newblock {\em Canad.\ J.\ Math.,} 14:708:722, 1962.
\end{thebibliography}

\end{document}

%%% Local Variables:
%%% mode: latex
%%% TeX-master: t
%%% TeX-PDF-mode: t
%%% End:
