\documentclass[finalversion]{FPSAC2024}
\articlenumber{39}

% symbols definitions
\input{defs.tex}

\title{Tamari intervals and blossoming trees}

\author{Wenjie Fang\thanks{\href{mailto:wenjie.fang@univ-eiffel.fr}{wenjie.fang@univ-eiffel.fr}. Partially supported by ANR-21-CE48-0007 (IsOMA) and ANR-21-CE48-0020 (PAGCAP).}\addressmark{1}, 
\'Eric Fusy\thanks{\href{mailto:eric.fusy@univ-eiffel.fr}{eric.fusy@univ-eiffel.fr}. Partially supported by ANR-19-CE48-0011 (COMBIN\'E).}\addressmark{1}, 
\and Philippe Nadeau\thanks{\href{nadeau@math.univ-lyon1.fr}{nadeau@math.univ-lyon1.fr}. Partially supported by ANR-19-CE48-0011 (COMBIN\'E).}\addressmark{2}
}

\address{
\addressmark{1}LIGM, CNRS, Universit\'e Gustave Eiffel, Champs-sur-Marne, France\\ 
\addressmark{2}Institut Camille Jordan, CNRS,  Universit\'e Claude Bernard Lyon 1, France}

\received{\today}

%% leave this blank until submitting a revised version
%\revised{}

\abstract{
  We introduce a simple bijection between Tamari intervals and the blossoming trees (Poulalhon and Schaeffer, 2006) encoding planar triangulations, using a new meandering representation of such trees. Its specializations to the families of synchronized, Kreweras, new/modern, and infinitely modern intervals give a combinatorial proof of the counting formula for each family. Compared to (Bernardi and Bonichon, 2009), our bijection behaves well with the duality of Tamari intervals, enabling also the counting of self-dual intervals.
}

%\abstract{Tamari intervals have attracted recent attention due to their connections in algebraic combinatorics. Several families of Tamari intervals are enumerated using bijections to planar maps, but done in a case-by-case fashion. We here present a bijection between Tamari intervals to blossoming trees, which gives a unified approach to enumeration of Tamari intervals, including self-dual ones. We also discover an involution of Tamari intervals that maps Kreweras intervals to infinitely-modern intervals.}

%% put your French abstract here, or comment this out if you don't have one
\resume{Nous donnons une nouvelle bijection simple entre les intervalles de Tamari et les arbres bourgeonnants (Poulalhon et Schaeffer, 2006) qui encodent les triangulations planaires, en passant par une nouvelle représentation méandrique de ces arbres. Les spécialisations aux familles des intervalles synchrones, Kreweras, nouveaux/modernes, et infiniment modernes donnent des preuves combinatoires des formules de comptage pour ces familles. Par rapport à (Bernardi et Bonichon, 2009), notre bijection se comporte bien vis-à-vis de la dualité des intervalles de Tamari, nous permettant de compter les intervalles auto-duaux.}


\keywords{Tamari intervals, blossoming trees, enumeration, duality}

\usepackage[backend=bibtex]{biblatex}
\addbibresource{tam_short.bib}
%% note the \printbibliography command at the end of the file which goes with these biblatex commands

\begin{document}
\maketitle

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

The Tamari lattice $\mathrm{Tam}_n$ is a well-known poset on Catalan objects of size $n$, that plays an important role in several domains, such as representation theory~\cite{Bergeron2012,bousquet2011number},  polyhedral combinatorics and Hopf algebras~\cite{bostan23,loday-ronco}. Partially motivated by such links, the enumeration of intervals in the Tamari lattice was first considered by Chapoton~\cite{chapoton06} who discovered the beautiful formula 
\begin{equation}\label{eq:tam}
I_n=\frac{2}{n(n+1)}\binom{4n+1}{n-1}
\end{equation}
for the number of intervals in $\mathrm{Tam}_n$. The subject has attracted much attention since then, with strikingly simple counting formulas found for several other families~\cite{bousquet2013representation,bousquet2011number,fang17}.  

Regarding combinatorial proofs, Bernardi and Bonichon~\cite{bernardi09} gave a bijection from Tamari intervals to planar (simple) triangulations via Schnyder woods. Then, a bijection by Poulalhon and Schaeffer~\cite{PS06} encodes the same triangulations by a class of blossoming trees, which yields~\eqref{eq:tam}. The bijection in~\cite{bernardi09} can be specialized to some subfamilies of Tamari intervals, such as Kreweras intervals~\cite{bernardi09} and synchronized Tamari intervals~\cite{fusy19}. Another strategy, for instance in~\cite{fang17}, is to construct bijections between Tamari intervals and planar maps inspired by their recursive decompositions.

In this extended abstract, we present a more direct bijection between Tamari intervals and the blossoming trees from~\cite{PS06}. Readers are referred to \cite{full-version} for the full version. Our construction, presented in \Cref{sec:tamari,sec:blossoming}, starts from a suitable planar representation of an interval as a pair of binary trees. With simple local operations, we get a ``meandering representation'' of the interval, closely related to interval-posets of Ch\^atel and Pons~\cite{ChatelPons15}. Such a representation can be seen as a folded version of a blossoming tree. When unfolded, the blossoming tree is characterized by local conditions as in~\cite{PS06}. We also find it convenient to give a certain bicoloring to half-edges in blossoming trees, which breaks symmetries.

Due to its simplicity, our bijection is also well-suited for specializations to known subfamilies of Tamari intervals, by characterizing the blossoming trees in each case (\Cref{theo:special}). In addition to synchronized intervals, whose specialization is much simpler than that in~\cite{fusy19}, and 
Kreweras intervals, already given in \cite{bernardi09}, our bijection also specializes to new/modern intervals~\cite{chapoton06,rognerud18} and infinitely modern intervals~\cite{rognerud18}. Compared to~\cite{bernardi09}, our bijection has also the advantage that it transfers the duality involution on Tamari intervals in a simple way, 
which amounts to a color-switch in blossoming trees (\Cref{prop:dual}). Self-dual intervals thus correspond to blossoming trees with a half-turn symmetry, which are easy to count for each family we consider (see \Cref{table:self_dual}), leading to  counting formulas that are new to our knowledge, except for Kreweras intervals, for which it is known. 

The following statement summarizes our main results.
\begin{theo}
  There is a bijection $\inttoblom$ between intervals in $\Tam_n$ and bicolored blossoming trees of size $n$ that sends self-dual intervals to blossoming trees with a half-turn symmetry. Its specialization to synchronized, Kreweras, modern/new, and infinitely modern intervals yields combinatorial proofs
of counting formulas for intervals and self-dual intervals in each case, see \Cref{table:self_dual}.
\end{theo}

Finally, besides color switch, another natural involution on blossoming trees is to apply a reflection. This yields a new involution on Tamari intervals with interesting properties, see~\Cref{rem:reflection}.

\section{Tamari intervals and their meandering representation}\label{sec:tamari}

Let $\bintree_n$ be the set of rooted binary trees with $n$ nodes. Recall that the Tamari lattice $\Tam_n$ is the poset $(\bintree_n, \leq)$ whose covering relations are given by right rotations, i.e., changing a subtree of the form $((T_1,T_2),T_3))$ into $(T_1,(T_2,T_3))$. An \emph{interval} in $\Tam_n$ is a pair $(T, T')$ such that $T \leq T'$. Let $\pair_n = \bintree_n \times \bintree_n$, and $\tamint_n \subseteq \pair_n$ the set of intervals in $\Tam_n$. In the following, we denote by $[n]$ the set $\{1, \ldots, n\} \subset \mathbb{N}$.

\begin{figure}[!ht]
\begin{center}
\includegraphics[width=0.9\textwidth]{drawingsupper}
\end{center}
\caption{A binary tree $T$ with its canonical drawing and smooth drawing.}
\label{fig:drawings}
\end{figure}

We first review some representations and encodings of binary trees. For $T \in \bintree_n$, the \tdef{canonical drawing} of $T$ is the crossing-free drawing of $T$ with its $n + 1$ leaves placed from left to right at the points of abscissas $0, \ldots, n$ on the $x$-axis, its nodes in the upper half-plane, and its left (resp. right) branches being segments of slope $1$ (resp. $-1$). \cacher{For every node $v$ of $T$, the \tdef{wedge} of $v$ is the concatenation of the segment of slope $+1$ from $v$ to the leftmost leaf in the subtree $T_v$ rooted at $v$ and of the segment of slope $-1$ from $v$ to the rightmost leaf in $T_v$. The \tdef{smooth drawing} of $T$ is obtained from the canonical drawing by replacing every node and associated wedge by a semi-circle (in the upper half-plane) connecting the two incident leaves, see \Cref{fig:drawings}.} The \tdef{smooth drawing} of $T$ is obtained by removing all lines, then for each node $u$, adding a semi-circle in the upper half-plane linking the leftmost and the rightmost leaves of the subtree induced by $u$, see \Cref{fig:drawings}. For $t \in [n]$, let $A_t$ be the unique arc covering the unit-segment $[t-1,t]$ and visible from it, see the left-part of~\Cref{fig:diagramdrawing}.

%\begin{rem}
 % A smooth drawing of a binary tree also corresponds to an \emph{alternating layout} of a plane tree with $n$ edges, where \emph{alternating} means that all neighbours of a vertex are on the same side, either all to the left or all to the right (we will not use this characterization here).
%\end{rem}

\begin{figure}[!ht]
\begin{center}
\includegraphics[width=\textwidth]{diagramdrawing}
\end{center}
\caption{Construction of the diagram-drawing from the smooth drawing, with its degree-vector.}
\label{fig:diagramdrawing}
\end{figure}

%\begin{defn}
%An \tdef{upper diagram-drawing} of size $n$ is an arc-diagram with $2n+1$ points at abscissas $0,\tfrac{1}{2},1,\ldots,n-\tfrac{1}{2},n$ on the $x$-axis, the $n+1$ (resp. $n$) points of integer (resp. half-integer) abscissa being colored black (resp. white), such that all arcs are (semi-circles) in the upper half-plane and have a black (resp. white) as left (resp. right) extremity, and such that  each white point is incident to a single arc.  
%\end{defn}

For $T \in \bintree_n$, the \tdef{diagram-drawing} $\widehat{T}$ of $T$ is obtained from the smooth drawing of $T$ as follows. For each $t \in [n]$, we add a white point at $t-\tfrac{1}{2}$, and we replace $A_t$ by an arc from this white point to the black point at the left end of $A_t$, see \Cref{fig:diagramdrawing}. To recover the smooth drawing from $\widehat{T}$, for each white point $w$ of $\widehat{T}$, its \tdef{right-attachment point} $b$ is the black point at $x = n$ if there is no arc above $w$, and is the black point to the left of $w'$ if $w$ is covered by an arc $b' \to w'$. 
%In other words, the rightmost black point $b$ in the region enclosed by arcs and some parts of the $x$-axis containing that from $w$ to the black point on it right. 
Then, to obtain the smooth drawing of $T$, each arc $b \to w$ in $\widehat{T}$ is replaced by an arc connecting $b$ to the right-attachment point of $w$.

%The mapping to recover the smooth drawing of 
%$T$ from its diagram-drawing  $\hat{T}$ is as follows: for each white point $w$ of $\hat{T}$, define the \tdef{right-attachment point} of $w$ as the rightmost black point $b$ that can be reached
%from $w$ by traveling in the upper half-plane without crossing an arc, i.e., $b$ is the black point at $x=n$ if there is no arc above $w$, and if $w$ is covered by an arc $b'\to w'$
%then $b$ is the black point to the left of $w'$.  Then, for each arc $b\to w$ in $\hat{T}$, the corresponding arc in the smooth drawing of $T$ connects $b$ to the right-attachment point of 
%$w$. It is also easy to check that, starting from any upper diagram-drawing, this mapping yields a valid smooth drawing (satisfying the conditions of \Cref{lem:smooth}), so that
%it actually gives a bijection from upper diagram-drawings of size $n$ to $\bintree_n$ (via smooth drawings).

%\begin{defn}
%A \tdef{degree-vector} of size $n$ is a vector $(d_0,\ldots,d_{n})\in\mathbb{N}^{n+1}$ satisfying $\sum_{j=0}^{n} d_j =n$, and $\sum_{j=0}^i d_j >i$ for each $0\leq i<n$
%(i.e., the sequence of steps $(d_i-1)_{0\leq i\leq n}$ gives a Łukasiewicz walk). 
%\end{defn}

For $T\in\bintree_n$, the \tdef{degree-vector} of $T$ is the vector $\dne(T) = (d_0,\ldots,d_{n})$ such that $d_i$ is the number of arcs incident to the black point $b$ at $x = i$ in the diagram-drawing $\widehat{T}$ for $0 \leq i \leq n$. We see that $d_i$ is also the right-degree of $b$ in the smooth drawing of $T$, and is the length of the left branch of $T$ ending at the leaf at abscissa $i$ in the canonical drawing. The diagram-drawing of $T$ is easily recovered from its degree-vector.
%This correspondence is a bijection between degree-vectors of size $n$ and $\bintree_n$.

\begin{figure}%[!ht]
\begin{center}
\includegraphics[width=0.7\textwidth]{bracket_both}
\end{center}
\caption{A binary tree $T$, its bracket-vector $\bvec(T)$ and dual bracket-vector $\dualbvec(T)$.}
\label{fig:bracket}
\end{figure}

Finally, we recall the bracket-vector and dual bracket-vector encoding of a binary tree $T\in\bintree_n$. We label the nodes of $T$ by left-to-right infix order, with $v_i$ the node of label $i \in [n]$. Let $a_i$ (resp. $b_i)$ be the size of the right (resp. left) subtree of $v_i$. The \tdef{bracket-vector} of $T$ is $\bvec(T) = (a_1, \ldots, a_n)$, and the \tdef{dual bracket-vector} of $T$ is $\dualbvec(T) = (b_1, \ldots, b_n)$, see \Cref{fig:bracket} for an illustration. These vectors can also be specified by inequality constraints, which we do not reproduce here, see~\cite{huangtamari}. The bracket-vector encoding is convenient to characterize Tamari intervals. For $(T, T')\in\pair_n$, it is known~\cite{huangtamari} that $(T, T') \in \tamint_n$ if and only if $\mathbf{V}(T) \leq \mathbf{V}(T')$ componentwise, or equivalently, $\dualbvec(T) \geq \dualbvec(T')$ componentwise.

\begin{rem}\label{rk:dualbracket}
  The dual bracket-vector is closely related to the diagram drawing. For $T \in \bintree_n$ and $t \in [n]$, the unique arc at the white point $t - \tfrac1{2}$ is connected to the black vertex at $x = t - 1 - b_t$. 
\end{rem}

\begin{figure}[!ht]
\begin{center}
\includegraphics[width=0.9\textwidth]{drawingpair}
\end{center}
\caption{A pair $(T,T')$ of binary trees of the same size, its canonical drawing, and its smooth drawing.}
\label{fig:drawingpair}
\end{figure}

The \tdef{mirror} of a binary tree $T$, denoted by $\mir(T)$, is the mirror image of $T$ exchanging left and right. The \tdef{mirror canonical drawing} (resp. \tdef{mirror smooth drawing}) of $T$ is the canonical drawing (resp. smooth drawing) of $\mir(T)$ rotated by a half-turn, which preserves the left-to-right order of leaves of $T$.

For $X = (T,T') \in \pair_n$, the \tdef{canonical drawing} (resp. \tdef{smooth drawing}) of $X$ is the superimposition of the canonical (resp. smooth) drawing of $T'$ with the mirror canonical (resp. smooth) drawing of $T$, see \Cref{fig:drawingpair}. In this case, the \tdef{upper diagram-drawing} of $X$ is the diagram-drawing of $T'$, while the \tdef{lower diagram-drawing} of $X$ is the diagram-drawing of $\mir(T)$ rotated by a half-turn. 
%We note that the leaves of the lower diagram-drawing of $X$ have the same order as that in the canonical drawing of $T$, since they undergo two left-to-right mirrors, the second one due to the half-turn. 
The \tdef{diagram-drawing} of $X$ is the superimposition of the upper and lower diagram-drawings of $X$. As a convention, in each of the 3 representations of $X$, the arcs are blue (resp. red) in the upper (resp. lower) part. Let \tdef{$\treestobil$} be the mapping that sends $X\in\pair_n$ to its diagram-drawing, see \Cref{fig:phi}. 

\begin{defn}\label{def:meandering}
  A \tdef{meandering diagram} of size $n$ is a non-crossing arc-diagram $M$ with $2n + 1$ points, at $0, \tfrac{1}{2}, 1, \ldots, n-\tfrac{1}{2}, n$ on the $x$-axis, colored black for integral points and white for half-integral ones, with all upper (resp. lower) arcs having a black (resp. white) left end and a white (resp. black) right end, such that each white point is incident to exactly one upper (resp. lower) arc. The \tdef{underlying graph} of $M$ is the graph with black points as vertices, where each white point yields an edge connecting the black endpoints of its incident upper and lower arcs. A \tdef{meandering tree} is a meandering diagram whose underlying graph is a tree. Let $\mdiag_n$ (resp. $\mtree_n$) be the set of meandering diagrams (resp. meandering trees) of size $n$.
\end{defn}

%The \tdef{diagram-drawing} $M$ of $X=(T,T')$ is the superimposition of the upper diagram-drawing and lower diagram-drawing of $X$. 
%Clearly the diagram-drawing of $X$ is the planar meandric representation of a bilabeled graph $G\in\bilabelpl_n$. 
 
\begin{figure}
\begin{center}
\includegraphics[width=0.8\textwidth]{phi_compact}
\end{center}
\vspace{-.4cm}
\caption{Left: The action of $\treestobil$ on each segment of consecutive points on the $x$-axis of the smooth drawing of $X \in \pair_n$ (the shorter blue and red arcs in the left drawing may be reduced to a point). 
	Right: the diagram-drawing $M = \treestobil(X)$ for the pair $X$ in \Cref{fig:drawingpair}, which is a meandering tree, meaning $X \in \tamint_n$ by \Cref{prop:phi}.}
\label{fig:phi}
\end{figure}
%
%\begin{figure}
%\begin{center}
%%\includegraphics[width=12cm]{local_op_phi}
%\end{center}
%\caption{Operations of the inverse mapping $\psi$ associating a pair $(T,T')\in\bintree_n\times\bintree_n$ to a graph $G\in\bilabelpl_n$.
% The arcs of the smooth drawing of $T'$ are constructed from the upper arcs of $\hG$ (each upper arc of $\hG$ yields an arc of the smooth drawing of $T$ that encloses it and 
% has same left extremity), as shown. Symmetrically, the arcs
% of the smooth drawing of $T$ are constructed from the lower arcs of~$\hG$.}
%\label{fig:local_op_psi}
%\end{figure}

\begin{prop}\label{prop:phi}
For $n \geq 1$, the mapping $\treestobil$ is a bijection between $\pair_n$ and $\mdiag_n$. It specializes to a bijection between $\tamint_n$ and $\mtree_n$. 
\end{prop}
%\begin{proof}
 %The first statement is clear, given the fact that the meandric representation of a graph in $\bilabelpl_n$ is made of an upper part that is an arbitrary upper diagram-drawing of size $n$,
% and (independently) a lower part that is the half-turn of an arbitrary upper diagram-drawing of size $n$. 
 
%  Regarding the second statement, it is a consequence of the property that, for $I = (T,T')$ a Tamari interval of size $n$ and $P = \alpha(X)$ the associated interval-poset under the Châtel-Pons bijection, for $t\in[n]$ the minimal (resp. maximal) value of the interval $\{s\in[n];\ s\preceq_P t\}$ is the label of the leftmost (resp. rightmost) node in the subtree of $T'$ (resp. $T$) rooted at the node of label $t$. This property directly follows from \Cref{rk:relations}. 
%\end{proof}

\begin{figure}[!ht]
\begin{center}
\includegraphics[width=10cm]{transfer_faulty}
\end{center}
\caption{The forbidden pattern for $X \in \pair_n$ to be in $\tamint_n$ (left) corresponds via $\treestobil$ to the forbidden pattern for $M\in\mdiag_n$ to be in $\mtree_n$ (right).}
\label{fig:transfer_flawed}
\end{figure}

\begin{proof}[Sketch of proof] % Let us give a few elements of the proof.
  For the first statement, the inverse $\biltotrees$ of $\treestobil$ is obtained by the equivalence between the representations of binary trees discussed above. For $M \in \mdiag_n$, we consider the upper part of $M$ as an upper diagram-drawing, from which we compute the corresponding smooth drawing, and turn it into the canonical drawing of a binary tree $T'$. We do the same for the half-turn of the lower diagram-drawing, yielding a binary tree, with $T$ its mirror. Then we take $\psi(M) = (T, T')$.
  
  For the second statement, we use the fact that $X \in \pair_n$ is in $\tamint_n$ if and only if its smooth drawing has no pair of arcs as on the left side of \Cref{fig:transfer_flawed}, which follows from the bracket-vector characterization of Tamari intervals, and is closely related to the Tamari diagrams in~\cite{combe2019cubic}. We then show that 
  %$M = \treestobil(X)$ 
 $M\in \mdiag_n$ is in $\mtree_n$ if and only if it has no pair of arcs as on the right side of \Cref{fig:transfer_flawed}, and that these patterns are in correspondence via~$\treestobil$.
\end{proof}

\begin{rem}\label{rk:int_poset}
  Each diagram $M\in\mdiag_n$ yields a relation $R$ on integers in $[n]$ where $i\,R\,j$ if the edge $\{a_j, b_j\}$ of the underlying graph in~\Cref{def:meandering} associated to the white point $j - \tfrac{1}{2}$ satisfies $[i-1, i] \subseteq [a_j, b_j]$. It can be shown that $R$ defines a poset if and only if $M\in\mtree_n$. In this case, by construction, $([n], R)$ is an interval-poset defined in~\cite{ChatelPons15}. Let $I=\psi(M)$, by \Cref{prop:phi}, we have $I \in \tamint_n$. We checked that $([n], R)$ is the interval-poset of $I$ under the bijection in~\cite{ChatelPons15}. 
\end{rem}

%\begin{rem}
 % In this formulation, our bijection $\treestobil$ has somehow a similar flavor as the Bernardi--Bonichon bijection~\cite{bernardi09}, the natural domain for the  construction being an extended family ($\bintree_n\times\bintree_n$ here, non-crossing pairs of Dyck walks of length $2n$ in the Bernardi--Bonichon bijection). The two constructions are, however, fundamentally different: this is witnessed by the fact that, for instance --as we will see in \Cref{sec:duality}-- our bijection commutes in a simple way with the duality involution on Tamari intervals, which is not true for the Bernardi--Bonichon bijection.
%\end{rem}

Recalling \Cref{rk:dualbracket}, the mapping $\treestobil$ can be formulated simply in terms of the bracket-vector of $T$ and dual bracket-vector of $T'$.

\begin{prop} \label{prop:shortcut-interval-bijection}
  Let $(T, T') \in \pair_n$, $\bvec(T) = (a_1, \ldots, a_n)$, and $\dualbvec(T') = (b_1, \ldots, b_n)$. Then $\treestobil(X)$ is given by its lower arcs $(t - \tfrac{1}{2}, t+a_t)$ and upper arcs $(t - \tfrac{1}{2}, t-b_t-1)$ for all $t \in [n]$.
\end{prop}

\section{Blossoming trees and their meandering representation}\label{sec:blossoming}

We consider the following trees, which are in bijection with simple triangulations~\cite{PS06}.

\begin{defn} \label{defn:blossoming-tree}
  A \tdef{blossoming tree} $B$ is an unrooted plane tree such that each \tdef{node}, that is, vertex of degree at least $2$, has exactly two neighbors that are \tdef{leaves}, which are vertices of degree $1$. We only consider such trees with at least two nodes. Edges incident to leaves are called \tdef{buds}, drawn as an outgoing arrow, and all other edges are called \tdef{plain edges}. The \tdef{size} of $B$ is its number of plain edges, which is also its number of nodes minus $1$.
\end{defn}

A blossoming tree is \tdef{bicolored} if each plain edge has one half-edge colored red and the other blue, such that the half-edges at each node are separated by the two incident buds into a group of blue and a group of red, one of the groups being possibly empty. See~\Cref{fig:closure}(a) for an example. We note that a blossoming tree yields at most two bicolored blossoming trees, since the bicoloring is uniquely determined once the color of a  half-edge is fixed. It yields just one if and only if it possesses the half-turn symmetry. We denote by $\blossoming_n$ the set of bicolored blossoming trees of size~$n$.

\begin{figure}[!ht]
\begin{center}
\includegraphics[width=\textwidth]{opening}
\end{center}
\caption{A meandering tree and the corresponding bicolored blossoming tree.}
\label{fig:opening}
\end{figure}
 
For $M \in \mtree_n$, we construct $B \in \blossoming_n$ by adding a ``left'' and a ``right'' bud at each black point along the $x$-axis, while keeping the colors of arcs, which are turned into half-edges of plain edges in $B$, see \Cref{fig:opening}. Let \tdef{$\bijbilblom$} be the mapping sending $M$ to $B$. 

Conversely, given a bicolored blossoming tree $B$, its \tdef{closure}, denoted by $\oB$, is constructed as follows, see \Cref{fig:closure}. For each plain edge $e$, we insert an \tdef{edge-vertex} $v_e$ in its middle, and we attach to $v_e$ two unmatched half-edges called \tdef{legs}, one on each side of $e$. The \ccw-contour of $B$ yields a cyclic word of parentheses, whose opening (resp. closing) ones are given by buds (resp. legs). We then match buds and legs in a planar way, see \Cref{fig:closure}(b).
%This is done by matching closest unmatched buds and legs at each step in the \ccw-contour distance. 
%By the minimality of distance, each leg can be matched to a bud, and the unmatched buds and legs are always on the outer face. 
Since $B$ has $2n+2$ buds and $2n$ legs, two buds are left unmatched. %The object we obtain (a planar map with two dangling buds in the outer face) is the closure $\oB$ of $B$. 
It is easily checked that the two unmatched buds of the closure $\oB$ are at distinct vertices, which are called the \tdef{extremal vertices} of $\oB$.
%Vertices of $\oB$ are of two types: tree-vertices (those in $B$) and edge-vertices (those in the middle of edges)

\begin{figure}[!ht]
\begin{center}
\includegraphics[width=\linewidth]{closure}
\end{center}
\caption{(a) A bicolored blossoming tree $B$; (b) the matching of buds with legs; (c) the closure $\oB$ of $B$, where the meandric path is shown in bold; (d) the meandering tree $M = \bijblombil(B)$ obtained by stretching the meandric path\cacher{with the blue (resp. red) arcs in the upper (resp. lower) half-plane}.}
\label{fig:closure}
\end{figure}

\begin{lemma}\label{lem:meandric_cycle}
  For $B\in\blossoming_n$, let $\oB$ be the closure of $B$, and $\pi$ the subgraph of $\oB$ induced by all closure-edges, that is, those obtained by matching a bud with a leg. Then
  \begin{itemize}%[noitemsep,nolistsep]
  \item $\pi$ is a Hamiltonian path of $\oB$ whose ends are the two extremal vertices;
  \item $\pi$ splits half-edges of $B$ by color;
  \item For any edge $e = \{u,v\}$ of $\oB$ corresponding to a half-edge of plain edge of $B$, with $v$ the edge-vertex end, let $\pi_e$ be the unique subpath of $\pi$ from $u$ to $v$, and $\sigma_e = \pi_e \cup \{e\}$, which is a cycle. Then, the interior of $\sigma_e$ is on the right of $e$ traversed from $u$ to $v$.
  \end{itemize}
\end{lemma}
%\begin{proof}
 % For the first point, we proceed by induction on $n$. The base case $n = 1$ can be easily checked. Suppose that all closure-edges in the closure $\oB'$ of every $B' \in \blossoming_{n-1}$ form a Hamiltonian path. Let $B \in \blossoming_n$ and $\oB$ its closure. There are thus $n$ edge-vertices and $n+1$ tree-vertices in $\oB$. We then observe that, if a bud in $\oB$ is not directly succeeded by another bud of the same vertex in the \ccw-direction, then it is matched with the next leg from the next adjacent edge-vertex, with contour distance 1. We say that they form a \emph{short pair}, and clearly among the two buds of a tree-vertex, at least one is in a short pair. There are thus at least $n+1$ short pairs, while there are only $n$ edge-vertices in $\oB$, meaning that there is some edge-vertex $v_e$ of $\oB$, corresponding to some edge $e = \{u, u'\}$ in $B$, whose both legs are in short pairs with two buds $b, b'$, with $b$ on $u$ and $b'$ on $u'$. Let $B' \in \blossoming_{n-1}$ be the tree obtained from $B$ by contracting $e$ in $B$ into a new vertex $u_0$ and removing $b, b'$. By induction hypothesis, the closure-edges of $\oB'$ form a Hamiltonian path $\pi'$. It is clear that expanding the occurrence of $u_0$ in $\pi'$ into the path from $u$ to $v_e$ to $u'$ via the short pairs of $b$ and $b'$ gives a Hamiltonian path in $\oB$. We thus conclude the induction. 
  
  %The second point comes from the fact that, by construction, the two half-edges of an edge in $B$, which are of different colors, are on different sides of $\pi$, and half-edges of a vertex in $B$ are split by its buds, through which $\pi$ goes, into monochromatic clusters. The third point is simply the consequence that we match buds with legs in \ccw-direction.
%\end{proof}

The Hamiltonian path $\pi$ of $\oB$ in \Cref{lem:meandric_cycle} is called the \tdef{meandric path} of $\oB$. From the first statement of \Cref{lem:meandric_cycle}, for $B\in\blossoming_n$, we may stretch the meandric path of $\oB$ into the horizontal segment $\{0\leq x\leq n,y=0\}$ with $2n+1$ equally-spaced vertices, along with arcs as semi-circles. By the second statement of \Cref{lem:meandric_cycle}, this can be done in a unique way with the blue (resp. red) half-edges of $B$ turned into the arcs above (resp. below) the segment. Let $M$ be the arc-diagram thus obtained, then the third statement of \Cref{lem:meandric_cycle} ensures that $M \in \mtree_n$. We define \tdef{$\bijblombil$} as the mapping that sends $B$ to $M$.
  
  %such a drawing is the meandric representation $\hC$ of some (minimal, by \Cref{prop:minimal_characterization}) tree $C\in\bilabelmin_n$. We denote by $\bijblombil$ the mapping sending $B$ to $C$, and it is illustrated in \Cref{fig:closure}.
 

%To show that $\bijblombil$ is a bijection, we need the following definitions. The \tdef{closure-map} $\oC$ associated to $C$ is the plane bipartite map with black (resp. white) vertices at the black (resp. white) points of $\hC$, and with two types of edges, \tdef{tree-edges} that correspond to the arcs, and the path $[0..n]$ on the horizontal axis, which yields $2n$ edges that are called \tdef{closure-edges}.

% \begin{lemma}\label{lem:cycle_meandric}
%   Let $C\in\bilabelmin_n$ and $B = \bijbilblom(C)$. Let $\oB$ be the closure of $B$. For every closure-edge $e$ of $\oB$, let $\pi_e$ be the unique path of tree-edges  connecting the two end points of $e$, and let $\sigma_e$ be the cycle formed by the concatenation of $\pi_e$ with $e$. Then, when traversing $e$ from its tree-vertex extremity to its edge-vertex extremity, the interior of $\sigma_e$ is on the right of $e$.  
%  \end{lemma}
%  \begin{proof}
%  \EF{Maybe establish the existence of at least one short edge (label $[i,i+1]$ and extremities $i,i+1$), and then induction on the number of edges.} 
%  \end{proof}

\begin{prop} \label{prop:gamma-bijection}
  For $n \geq 1$, the mapping $\bijbilblom$ is a bijection from $\mtree_n$ to $\blossoming_n$, with $\bijblombil$ its inverse.
\end{prop}
%\begin{proof}
% The fact that $\bijblombil$ and $\bijbilblom$ are mappings between $\blossoming_n$ and $\bilabelmin_n$ is ensured by \Cref{lem:meandric_cycle}. We clearly have $\bijbilblom(\bijblombil(B))=B$ for $B\in\blossoming_n$. To show that $\bijblombil(\bijbilblom(C)) = C$ for $C\in\bilabelmin_n$, let $\hC$ be its meandric representation. We notice that $\hC$ clearly gives a closure of $\bijbilblom(C)$, with the colors preserved, while the closure of a bicolored blossoming tree is unique. We thus have $\bijblombil(\bijbilblom(C))=C$.
%\end{proof}


\section{The main bijection: properties and enumeration results}

Combining \Cref{prop:phi,prop:gamma-bijection}, we obtain the following.

\begin{theo}\label{theo:main}
The mapping $\inttoblom := \bijbilblom \circ \treestobil$ is a bijection from $\tamint_n$ to $\blossoming_n$.  Its inverse is $\blomtoint := \biltotrees \circ \bijblombil$.
\end{theo}

%\begin{figure}[!ht]
%\begin{center}
%\includegraphics[width=\linewidth]{canopy_types_compact}
%\end{center}
%\caption{(a) A bicolored blossoming tree $B$; (b) the matching of buds with legs; (c) the closure $\oB$ of $B$, where the meandric path (the concatenation of the closure-edges) is shown bolder; (d) the meandering tree $M=\bijblombil(B)$ obtained by stretching the meandric path so that the blue (resp. red) arcs are in the upper (resp. lower) half-plane.}
%\label{fig:closure}
%\end{figure}

It is possible to track several parameters via the bijection. For $X = (T,T') \in \pair_n$ given as it canonical drawing, and for $0 \leq i \leq n$, the \tdef{bi-degree} of $X$ at $i$ is the pair $(d, d')$ such that the right branch of $T$ (resp. left branch of $T'$) ending at $i$ on the horizontal axis has $d$ (resp. $d'$) nodes. In other words, $\dne(T')_i = d'$ and $\dne(\mir(T))_{n-i} = d$. The \tdef{canopy-type} of $X$ at $i$ is ${s \brack r}$, where $s = \mathbb{1}_{d'>0}$ and $r = \mathbb{1}_{d=0}$ are given by indicator functions. We note that, if $X \in \tamint_n$, then the canopy-type ${0 \brack 1}$ can not occur. For $B \in \blossoming_n$, the \tdef{bi-degree} of a node $v \in B$ is the pair $(d, d')$ such that $d$ (resp. $d'$) is the number of red (resp. blue) half-edges at $v$, and the \tdef{canopy-type} of $v$ is ${s \brack r}$ where $s = \mathbb{1}_{d'>0}$ and $r = \mathbb{1}_{d=0}$. 

\begin{prop}
For $X\in\tamint_n$ and $B=\inttoblom(X)$, each index $0 \leq i \leq n$ corresponds to a node $v \in B$ of same bi-degree, and thus same canopy-type.
\end{prop}

\begin{rem}
It seems harder to read the lengths of left branches of $T$ and right branches of $T'$. A clear way to read these lengths could yield bijective proofs of the counting formulas for $m$-Tamari intervals~\cite{bousquet2011number} (via~\cite[Prop.72]{Pons19}) and for labeled Tamari intervals~\cite{bousquet2013representation}. %(counted by $2^n(n+1)^{n-2}$). 
\end{rem}

The number of entries of each canopy-type is then easy to track in bicolored blossoming trees using a root-decomposition, yielding the following counting formulas.

\begin{coro}\label{coro:trivariate}
%  Let $I_{i,j,m}$ be the number of Tamari intervals with $i,j,m$ canopy-entries of types $\canoo, \canzz, \canoz$ respectively. Let $A \equiv A(x, y, z)$ and $B \equiv B(x, y, z)$ be the trivariate series defined by
We denote by $J_{i,j}(n)$ the number of Tamari intervals of size $n$ with $i+1$ canopy-entries $\canoo$ and $j+1$ canopy-entries $\canzz$, and thus $n-1-i-j$ canopy-entries $\canoz$. Let $A \equiv A(t;x, y)$ and $B \equiv B(t;x, y)$ be the trivariate series specified by
  \begin{equation} \label{eq:defn-canopy-series}
    A = \frac{t}{(1 - B)^2} \left(y + \frac{A}{1-A} \right), \quad B = \frac{t}{(1 - A)^2} \left(x + \frac{B}{1-B} \right).
  \end{equation}
  Then we have
  \begin{equation}\label{eq:first_exp_canopy}
   J_{i,j}(n) =\frac1{n}[t^{n+1}x^{i+1}y^{j+1}] A B.
  \end{equation}
  %\begin{equation}\label{eq:second_exp_canopy}
  %   \sum_{n,i,j} J_{i,j}(n) t^nx^iy^j = \frac{xA}{1 - A} + \frac{yB}{1 - B} + \frac{AB}{(1 - A) (1 - B)} - AB.
  %\end{equation}
  In particular, using Lagrange inversion, the coefficients $S_{i,j}:=J_{i,j}(i+j+1)$ and $J_k(n):=\sum_{i+j=k}J_{i,j}(n)$ are given by %(applying the Lagrange inversion formula)
  \begin{equation}\label{eq:counting}
    S_{i,j} = \frac{1}{(i + 1)(j + 1)} \binom{2i+j+1}{j} \binom{2j+i+1}{i}, \quad \!\!\! J_k(n)=\frac{2}{n(n + 1)} \binom{3n}{k - 2} \binom{n + 1}{k},
  \end{equation}
  where $S_{i,j}$ counts \tdef{synchronized Tamari intervals}, i.e., those with no canopy-entry of type $\canoz$ (\textit{cf.} \cite[Section~2]{fang17}).
\end{coro}
The expression of $S_{i,j}$ in \Cref{eq:counting} can be obtained using bijections in~\cite{fang17} or in~\cite{fusy19} to planar non-separable maps counted by vertices and faces. On the other hand, the coefficients $J_k(n)$ count Tamari intervals by size and number of synchronized entries (type $\canoo$ or $\canzz$), and it has been recently computed in~\cite{bostan23} by solving functional equations, and via the Bernardi-Bonichon bijection building upon~\cite{fusy19}. The derivation with our bijection is however more direct.

Besides synchronized intervals, % (for which the corresponding blossoming trees are characterized as having the two buds consecutive at each node),  
the bijection $\inttoblom$ can also be specialized to other known families of Tamari intervals, as listed in \Cref{table:self_dual}, namely: 
\begin{itemize}%[noitemsep,nolistsep]
\item modern intervals~\cite{rognerud18}, i.e., intervals $I = (T, T')$ whose ``rise'' $((T, \epsilon), (\epsilon, T'))$ is also a Tamari interval. In this case, the rise is a ``new'' Tamari interval defined in~\cite{chapoton06},
\item infinitely modern intervals~\cite{rognerud18}, i.e., intervals such that all iterated rises are also Tamari intervals,
\item Tamari intervals corresponding to Kreweras intervals (\textit{cf.} \cite{bernardi09} and references therein) under the standard bijection from binary trees to non-crossing partitions: the parts are given by right branches of the binary tree with nodes labeled by infix order. 
\end{itemize}

\begin{theo}\label{theo:special}
For each of the following families of Tamari intervals, the associated bicolored blossoming trees given by $\inttoblom$ are characterized by the following conditions:
\begin{itemize}%[noitemsep,nolistsep]
\item {\bf Synchronized}: for each node, its two incident buds are consecutive in cyclic order.
\item {\bf Modern}: for every plain edge, at least one end is followed by a bud in clockwise order.
\item {\bf Infinitely modern}: for every path of plain edges, at least one end is followed by a bud in \cw-order.
\item {\bf Kreweras}: for every path of plain edges, at least one end is followed by a bud in counterclockwise order.
\end{itemize}
These conditions amount to forbidding in bicolored blossoming trees the patterns illustrated in \Cref{fig:forbidden-pattern}. 
In each case, a decomposition of the corresponding trees yields a combinatorial proof of the known counting formula, given by the first column in \Cref{table:self_dual}.
\end{theo}

\begin{figure}[!ht]
  \centering
  \includegraphics[page=1,width=0.6\textwidth]{fig-ipe.pdf}
  \caption{Forbidden patterns of blossoming trees for subfamilies of Tamari intervals.}
  \label{fig:forbidden-pattern}
\end{figure}

\begin{table}
\cacher{\small
\begin{tabular}{cccccc}
\toprule
\textbf{Size} & general & synchronized & \begin{tabular}{c}modern \\ /new (Size$-\!$1) \end{tabular} & \begin{tabular}{c}modern \& \\ synchronized \end{tabular} & \begin{tabular}{c}inf. modern \\ / Kreweras \end{tabular} \\
\midrule
\textbf{$\boldsymbol{n}$} & $\frac{2}{n(n+1)}\binom{4n+1}{n-1}$ & $\frac{2}{n(n+1)}\binom{3n}{n-1}$ & $\frac{3\cdot 2^{n-1}}{(n+1)(n+2)}\binom{2n}{n}$ & $\frac{1}{n+1}\binom{2n}{n}$ & $\frac1{2n+1}\binom{3n}{n}$ \\[.1cm] 
  \midrule
  \midrule
\textbf{$\boldsymbol{2m}$} & $\frac{1}{3m+1}\binom{4m}{m}$ & $0$ & $\frac{2^{m-1}}{m+1}\binom{2m}{m}$ & $0$ & $\frac1{2m+1}\binom{3m}{m}$ \\[.1cm] 
\midrule
\textbf{$\boldsymbol{2m+1}$} & $\frac1{m+1}\binom{4m+2}{m}$ & $\frac1{m+1}\binom{3m+1}{m}$ & $\frac{2^m}{m+1}\binom{2m}{m}$ &$\frac1{m+1}\binom{2m}{m}$ & $\frac1{m+1}\binom{3m+1}{m}$ \\[.1cm]
\bottomrule
\end{tabular}
}
  \centering
  \begin{tabular}{cccc}
    \toprule
    \textbf{Types} & All, size $n$ & Self-dual, size $2m$ & Self-dual, size $2m+1$ \\
    \midrule
    \textbf{General} & $\displaystyle \frac{2}{n(n+1)}\binom{4n+1}{n-1}$ & $\displaystyle \frac{1}{3m+1}\binom{4m}{m}$ & $\displaystyle \frac1{m+1}\binom{4m+2}{m}$ \\ \midrule
    \textbf{Synchronized} & $\displaystyle \frac{2}{n(n+1)}\binom{3n}{n-1}$ & $\displaystyle 0$ & $\displaystyle \frac1{m+1}\binom{3m+1}{m}$ \\ \midrule
    \textbf{\begin{tabular}{c}Modern \\ / New (for size-1)\end{tabular}} & $\displaystyle \frac{3\cdot 2^{n-1}}{(n+1)(n+2)}\binom{2n}{n}$ & $\displaystyle \frac{2^{m-1}}{m+1}\binom{2m}{m}$ & $\displaystyle \frac{2^m}{m+1}\binom{2m}{m}$ \\ \midrule
    \textbf{\begin{tabular}{c}Modern and \\ synchronized\end{tabular}} & $\displaystyle \frac{1}{n+1}\binom{2n}{n}$ & $\displaystyle 0$ & $\displaystyle \frac1{m+1}\binom{2m}{m}$ \\ \midrule
    \textbf{\begin{tabular}{c}Inf. modern \\ / Kreweras\end{tabular}} & $\displaystyle \frac1{2n+1}\binom{3n}{n}$ & $\displaystyle \frac1{2m+1}\binom{3m}{m}$ & $\displaystyle \frac1{m+1}\binom{3m+1}{m}$ \\
    \bottomrule
  \end{tabular}
\caption{Counting formulas for Tamari intervals and self-dual ones.}
\label{table:self_dual}
\end{table}

We define $\mir(X)$ for $X = (T,T') \in \pair_n$ as $\mir(X) = (\mir(T'),\mir(T))$. We call $\mir$ the \tdef{duality} on $\pair_n$, it is an involution on $\pair_n$ and on $\tamint_n$. Its name comes from the fact that $\mir$ on binary trees is the duality map for $\Tam_n$.

\begin{prop}\label{prop:dual}
  For $I \in \tamint_n$, we obtain $\inttoblom(\mir(I))$ by switching colors of half-edges in $\inttoblom(I)$. Hence, self-dual intervals are mapped by $\inttoblom$ to blossoming trees with half-turn symmetry.
\end{prop}

For each of the families in \Cref{table:self_dual}, one can easily count the corresponding blossoming trees that are half-turn symmetric. This yields the formulas shown in the second and the third column in \Cref{table:self_dual}, which are new to our knowledge, except for Kreweras.

\begin{rem} \label{rem:reflection}
  We define the \tdef{reflection} of a blossoming tree to be its mirror image. It is clear that reflection commutes with color switch on blossoming trees, and it is transferred by $\blomtoint$ to an involution on Tamari intervals. Combined with \Cref{theo:special}, with forbidden patterns illustrated in \Cref{fig:forbidden-pattern}, we see that synchronized intervals are stable by this new involution, while infinitely modern intervals are matched with Kreweras intervals.

  It was previously known that both infinitely modern intervals and Kreweras intervals are equinumerous to ternary trees \cite{rognerud18}, but they seem to have very different structures. Our involution somehow relates these two families. We plan to further explore properties of this new involution.
\end{rem}

\begin{rem} \label{rem:q-analogue}
  Regarding the counting formulas for self-dual intervals in \Cref{table:self_dual}, %various families (see \Cref{table:self_dual}), 
  one observes that, in the cases of general and synchronized intervals, they are given by a simple $q$-analogue of the formula for all intervals taken at $q=-1$.  
  It would be nice to have a natural explanation of this fact. This may come from a combinatorial analysis of blossoming trees.
\end{rem}

\acknowledgements{We thank Vic Reiner for the initial observation of \Cref{rem:q-analogue} in the case of general Tamari intervals. We also thank Frédéric Chapoton, Vincent Pilaud and Gilles Schaeffer for interesting discussions.}

\cacher{
\begin{rem}
Via bicolored blossoming trees we can introduce a new involution on Tamari intervals: two Tamari intervals are matched if their associated bicolored blossoming trees are mirror of each
other. This involution clearly commutes with duality. By \Cref{prop:special}, it preserves the property of being synchronized, and it matches infinitely modern intervals with Kreweras intervals. 
\end{rem}
}

%\acknowledgements{}

%% if you use biblatex then this generates the bibliography
%% if you use some other method then remove this and do it your own way
\printbibliography



\end{document}
