%% if you are submitting an initial manuscript then you should have submission as an option here
%% if you are submitting a revised manuscript then you should have revision as an option here
%% otherwise options taken by the article class will be accepted
\documentclass[final]{FPSAC2022}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

%% note that the class file already loads {amsmath, amsthm, amssymb}

%\emergencystretch=1em
\newtheorem{thm}{Theorem}
\newtheorem{prop}{Proposition}

\newtheorem{lem}{Lemma}

\theoremstyle{definition}
\newtheorem{definition}{Definition}%[subsection]


%\usepackage{lipsum}
\usepackage{mathtools}
%\usepackage{float}
%\usepackage[skip=0.1pt]{caption}



\newcommand{\DP}{\mathsf{DP}} % Dyck paths
\newcommand{\D}{\mathcal{D}} % Dyck paths (new)
\newcommand{\ltype}{\opname{ltype}}
\newcommand{\rtype}{\opname{rtype}}
\newcommand{\type}{\opname{type}}

\newcommand{\opname}[1]{\operatorname{\textup{\textsf{#1}}}}
\newcommand{\contI}{\opname{cont}}
\newcommand{\deltaI}{\delta_{\mathcal{I}}}
\newcommand{\deltaF}{\delta_{\mathcal{F}}}
\newcommand{\DeltaI}{\Delta_{\mathcal{I}}}
\newcommand{\DeltaF}{\Delta_{\mathcal{F}}}
\newcommand{\piI}{\pi_{\mathcal{I}}}
\newcommand{\piF}{\pi_{\mathcal{F}}}
\newcommand{\PiI}{\Pi_{\mathcal{I}}}
\newcommand{\PiF}{\Pi_{\mathcal{F}}}
\newcommand{\oplusI}{\oplus_{\mathcal{I}}}
\newcommand{\oplusF}{\oplus_{\mathcal{F}}}
\newcommand{\hdI}{\operatorname{hd}_{\mathcal{I}}}
\newcommand{\tlI}{\operatorname{tl}_{\mathcal{I}}}
\newcommand{\hdF}{\operatorname{hd}_{\mathcal{F}}}
\newcommand{\tlF}{\operatorname{tl}_{\mathcal{F}}}
\newcommand{\size}{\opname{size}}

\newcommand{\oc}{\opname{Occ}}
\newcommand{\Area}{\opname{Area}}




\newcommand{\Conj}{\opname{Conj}}
\newcommand{\ConjD}{\Conj_{\D}}
\newcommand{\ConjI}{\Conj_{\mathcal{I}}}


\newcommand{\F}{\mathcal{F}}
\newcommand{\ConjF}{\Conj_{\mathcal{F}}}

\newcommand{\lat}{\opname{lat}}
\newcommand{\Long}{\opname{long}}

\newcommand{\FF}{\opname}

\newcommand{\ljaw}{\opname{jaw}}
\newcommand{\ujaw}{\opname{ujaw}}

\newcommand{\Val}{\opname{Val}}
\newcommand{\Peak}{\opname{Peak}}
\newcommand{\DR}{\opname{DR}}
\newcommand{\DD}{\opname{DD}}
\newcommand{\Drun}{\mathbf{D}}
\renewcommand{\d}{\mathrm{d}}
\newcommand{\Cont}{\mathbf{C}}
\renewcommand{\c}{\mathrm{c}}
\newcommand{\Rise}{\mathbf{R}}
\renewcommand{\r}{\mathrm{r}}
\newcommand{\Type}{\mathbf{T}}
\renewcommand{\t}{\mathrm{t}}
\renewcommand{\L}{\opname{d}}
\newcommand{\bra}{\mathbf{\opname{b}}}
\newcommand{\Bra}{\mathbf{B}}




%% define your title in the usual way
\title{Bijections Between Fighting Fish, Planar Maps, and Tamari Intervals}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author[E.~Duchi and C.~Henriet]{Enrica Duchi\thanks{\href{mailto:duchi@irif.fr}{duchi@irif.fr}. Partially supported by Grant ANR COMBIN\'e.}\addressmark{1} \and Corentin Henriet\thanks{\href{mailto:henriet@irif.fr}{henriet@irif.fr}}\addressmark{1}}
%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}IRIF, Universit\'e de Paris}

%% put the date of submission here
\received{\today}

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

%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)
\abstract{We introduce two models of classes of walks in the quarter plane defined by simple rewriting rules: \emph{generalized fighting fish} and \emph{extended fighting fish}. They are two generalizations in different directions of the recently introduced fighting fish of (Duchi, Guerrini, Rinaldi, Schaeffer 2017), that were shown to  be equinumerated with rooted non-separable planar maps and synchronized Tamari intervals. We explain these equinumeration results by presenting two direct and more general bijections: one between generalized fighting fish and rooted planar maps, and the other between extended fighting fish and Tamari intervals.}

%% put your French abstract here, or comment this out if you don't have one
%\resume{A écrire}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{bijective combinatorics, fighting fish, planar maps, Tamari intervals}

%% you can include your bibliography however you want, but using an external .bib file is STRONGLY RECOMMENDED and will make the editor's life much easier
%% regardless of how you do it, please use numerical citations, ie. [xx, yy] in the text

%% this sample uses biblatex, which (among other things) takes care of URLs in a more flexible way than bibtex
%% but you can use bibtex if you want
\usepackage[backend=bibtex]{biblatex}
\addbibresource{fpsac022.bib}
%% note the \printbibliography command at the end of the file which goes with these biblatex commands

\begin{document}

\maketitle

%% note that you DO NOT have to put your abstract here -- it is generated by \maketitle and the \abstract and \resume commands above
%\section{Generalized fish heads}
\section{Introduction}\label{sec0}

Fighting fish is a relatively new class of combinatorial objects that has been introduced in~\cite{ff} by Duchi \textit{et al.} Roughly speaking, a fighting fish is a branched surface that is obtained by gluing together flexible unit squares along their edges in a directed way, resulting into independent branches that can overlap. These objects can be indifferently viewed as branched surfaces or as words describing their boundary followed counterclockwise, but it is more convenient to define their growth operations in terms of the latter:

\begin{definition}
	The class of \emph{fighting fish}, denoted $\mathcal{FF}$ is the set of words inductively defined from the word $ENWS$, called the \emph{Head}, with the help of the following two operations:
	\begin{itemize}
		\item \textbf{operation $\bigtriangledown_k$, $k\geq 1$}: replace a subword $N^k$ by $EN^kW$.
		\item\textbf{operation $\bigtriangleup_k$, $k\geq 1$}: replace a subword $W^k$ by $NW^kS$.
	\end{itemize}
	The \emph{size} of a fighting fish is half of its length minus 1.
\end{definition}


These words on the alphabet $\{N,S,E,W\}$ can also be considered as paths confined to the positive quadrant (up to a 45° tilting of the $x$ and $y$ axes), by embedding each letter $N,S,E,W$ to its respective corresponding step $(0,1)$, $(0,-1)$, $(1,0)$, $(-1,0)$.
%% Given a word $w$ on the alphabet $\Sigma$ we define its height $h$ as
%% $|w|_N+|w|_W+ 2|w|_V-|w|_S-|w|_E$

%% our generalized fish heads as words on the alphabet $\Sigma=\{N,S,W,E,
%% V\}$, or equivalently as paths in the plane, where $N$ ({\em
%%   resp. S,W,E,V}) corresponds to the step $(1,1)$ ({\em
%%   resp. $(-1,-1)$, $(-1,1)$,$(1,-1)$,$(0,2)$}). In the special cases
%% corresponding to \ref{DGRS}, our path describes the border of the fish
%% tail in counterclockwise direction starting from the head. Given a word $w$ on the alphabet $\Sigma$ we define its height $h$ as
%% $|w|_N+|w|_W+ 2|w|_V-|w|_S-|w|_E$ (see Figure~\label{fig:fishTail} for
%% a pictorial representation of the operations).


%\vspace{-.5em}
\begin{figure}[t]
	\centering
	\includegraphics[page=15,width=0.6\textwidth]{figures-these}
	\caption{Operations $\bigtriangleup_k$ and $\bigtriangledown_k$ and an example of fighting fish.}
	\label{fig:construction}\label{fig:FightingFish}
\end{figure}
%\vspace{-.5em}


%% \begin{definition}
%% The class of \emph{generalized fish
%% heads}, denoted $\mathcal{GFH}$ is the set of paths inductively defined as follows:
%% \begin{description}
%% \item[Basis.] The empty generalized fish head is the empty path corresponding to a fish head of size 0.
%% \vspace{0.5em}
%% \item[Inductive step.] Given a fish head $t$ of size $n$, we create a fish tail of size $n+1$ by applying one of the following operations:
%% \begin{description}
%% \item[operation $\bigtriangledown_k$, $k\geq 0$] replace a subword equal to $N^k$ by $EN^kW$.
%% \item[operation $\bigtriangleup_k$, $k\geq 0$] replace a subword equal to $W^k$ by $NW^kS$.
%% \item[operation $\triangleleft$] replace a subword equal to $WN$ by $V$.
%% \end{description}
%% \end{description}
%% \end{definition}
%
%Notice that these operations are easy to describe but do not provide a unique construction of each object. We actually can give a non ambiguous decomposition for the class $\mathcal{GFH}$ that generalizes the slice decomposition described in~\cite{ff} for fish tails. This decomposition gives us a system of polynomial functional equations with a catalytic variable that we can solve to obtain an algebraic equation satisfied by their generating function.
%
%However, in this extended abstract we concentrate on the bijective links between $\mathcal{GFH}$ and some of its subclasses and other combinatorial objects

Fighting fish are closely related to the well studied combinatorial structures known as \emph{non-separable planar maps}~\cite{Brown}, \emph{synchronized Tamari intervals}~\cite{PRV,FPR}, \emph{two stack sortable permutations}~\cite{Zeilb,West,Bona}, and \emph{left ternary trees}~\cite{DDP,JS}: for all these structures, the number of objects of size $n$ is \[\frac{2}{(n+1)(2n+1)}{3n\choose n}.\]

In~\cite{ff2}, the authors explored further the remarkable
enumerative properties of fighting fish and proposed a new decomposition extending the classical wasp-waist decomposition of polyominoes. Moreover, they proved that the number of fighting fish with $i$ left lower free edges and $j$ right
lower free edges is $\frac1{ij}{2i+j-2\choose j-1}{2j+i-2\choose i-1}$, confirming the apparently close relation of fighting fish with the above combinatorial structures. In particular, these authors proved analytically that fighting fish and left-ternary trees share the same formula with respect to one additional parameter,  the \emph{fin length} for the fish and the \emph{core} for the trees. However, to our knowledge, there is no known bijection involving these two classes that would explain this equidistribution.

More generally, until now, the only bijective proof involving fighting fish is the recursive one given by Fang in~\cite{FangFish} with two-stack sortable permutations, obtained using a new recursive decomposition of this class isomorphic to the one given in~\cite{ff2} for fighting fish. It connects fighting fish bijectively to the other above mentioned combinatorial structures, but only indirectly because the recursive structure is different from previously known bijections. 

In this paper we explore further the bijective world of fighting fish by introducing two bijections involving rooted planar maps and Tamari intervals. For this purpose, we present two new classes of fish, each one encapsulating the model of fighting fish, either by generalizing it with an extra value $k=0$ for $\bigtriangledown_k$ and $\bigtriangleup_k$, or by extending it with an additional operation that involves a new letter $V$ corresponding to the step $(-1,1)$:
\begin{itemize}
	\item the class of \emph{generalized fighting fish} $\mathcal{GFF}$ is the set of words obtained from the empty word with the operations $\bigtriangledown_k$ and $\bigtriangleup_k$, with $k \geq 0$.
	\item the class of \emph{extended fighting fish} $\mathcal{EFF}$ is the set of words obtained from the Head using the operations $\bigtriangledown_k$ and $\bigtriangleup_k$ with $k \geq 1$ and the new operation $\triangleleft$ consisting in replacing an occurrence of $WN$ by $V$.
\end{itemize}

Our new constructions imply in particular that fighting fish are exactly the Mullin codes of non-separable planar maps endowed with  their unique rightmost depth first search tree, and that the area of fighting fish corresponds to the length of longest chain in the associated synchronized Tamari interval.



In Section~\ref{sec1} we shortly define planar maps and give a bijection between generalized fighting fish with size $n$ and rooted planar maps with $n$ edges that specializes into a bijection between fighting fish and non-separable planar maps. In section~\ref{sec2} we give a decomposition for the class of extended fighting fish which specializes to the class of fighting fish and that inspired the bijections presented in this paper, we shortly define Tamari intervals and its subclass of synchronized intervals and give a bijection between extended fighting fish of size $n$ and Tamari intervals of size $n$ that specializes into a bijection between fighting fish and synchronized intervals.  

\section{Planar maps and generalized fighting fish}\label{sec1}

\subsection{Planar maps}
\begin{definition}
A \emph{planar map} is a proper embedding of a connected graph on the plane, defined up to continuous deformations. A planar map splits the plane into edges, vertices and faces. As usual, we consider \emph{rooted planar maps}, where an edge on the boundary of the infinite face is distinguished and oriented in such a way that the infinite face is on its right.  This edge is called the root, while the face on its right is called the root face. We denote by $\mathcal{M}$ the class of rooted planar maps (see Figure~\ref{Fig:AllMaps}$(a)$) for an example). For a planar map with $n$ edges, $i+1$ vertices and $j+1$ faces, the Euler relation reads $n=i+j$.
\end{definition}

\begin{figure}[t]
	\centering
	\includegraphics[scale=.7]{AllMaps}
	\caption{$(a)$ A rooted planar map; $(b)$ a rooted loopless planar map; $(c)$ a rooted bridgeless planar map; $(d)$ a rooted non-separable planar map.}
	\label{Fig:AllMaps}
\end{figure}
%\vspace{-2em}

\begin{definition} \mbox{}
  \begin{itemize}
       \item A \emph{loopless planar map} is a planar
       map without loops, \textit{i.e.}, edges that start and end at the same vertex (see Figure~\ref{Fig:AllMaps}$(b)$ for an example). %% We denote by $\mathcal{LM}$ the class of loopless planar maps.
     \item A \emph{bridgeless planar map} is a planar
       map without bridges, \textit{i.e.}, edges whose deletion disconnects the map (see Figure~\ref{Fig:AllMaps}$(c)$ for an example). %% We denote by $\mathcal{BM}$ the class of bridgeless planar maps.
\item A \emph{non-separable planar map} is a rooted loopless planar map with at least two edges without {separable vertices}, \textit{i.e.}\ vertices whose deletion disconnects the map (see Figure~\ref{Fig:AllMaps}$(d)$ for an example). %% We denote by $\mathcal{NS}$ the class of non-separable planar maps.

  \end{itemize}
\end{definition}

%%  \begin{figure}
%% \centering
%% \includegraphics[width=0.3\textwidth]{FightingFish}
%% \caption{A fighting fish and the branched surface bordered by the path.}
%% \label{fig:FightingFish}
%% \end{figure}

%We denote by ${ff}_n= |\mathcal{FF}_n|$  the number of fighting fish with size $n$. Moreover,  we denote by  ${ff}_{i,j}=|\mathcal{FF}_{i,j}|$ the number of fighting fish with $i$ $E$ steps (or $i$ $W$ steps) and $j$ $N$ steps (or $j$ $S$ steps).  
%
%\vspace{-.5em}
%\begin{figure}[h]
%	\centering
%	\includegraphics[scale=0.6]{AllFish}
%	\caption{$(a)$ A generalized fighting fish. $(b)$ A generalized fighting fish without up bridges. $(c)$  A generalized fighting fish without down bridges.}
%	\label{Fig:AllFish}
%\end{figure}
%\vspace{-2em}
%
%The class of \emph{generalized fighting fish without up (resp. down) bridges}, denoted $\mathcal{UF}$ (resp. $\mathcal{DF}$) consists of the generalized fish heads obtained from the empty path using only operations $\bigtriangledown_k$ with $k \geq 0$ (resp. $k \geq 1$) and $\bigtriangleup_\ell$ with $\ell \geq 1$ (resp. $\ell \geq 0$). (See Figure~\ref{Fig:AllFish})
%
%
%
%
%We denote by ${gf}_n=|\mathcal{GF}_{n}|$  the number of generalized fighting fish with size $n$ and by ${gf}_{i,j}=|\mathcal{GF}_{i,j}|$ the number of generalized fighting fish with $i$ $E$ steps (or $i$ $W$ steps) and $j$ $N$ steps (or $j$ $S$ steps).




\subsection{A bijection between rooted planar maps and generalized fighting fish}
In this section we will show that combining depth first search with the Mullin encoding of tree-rooted maps (see~\cite{chapterMaps} for more details),  gives a bijection between  rooted planar maps with $n$ edges and generalized fighting fish of size $n$. This bijection has the nice property that it specializes in bijections between the various subclasses of rooted planar maps and generalized fighting fish already introduced. 

\paragraph{From generalized fighting fish to decorated trees.}
Given a generalized fighting fish $\opname{F}$ of size $n$, we are going to construct a decorated tree by reading $\opname{F}$ from left to right and constructing the associated tree  while moving on its border. The decorated tree will be constituted of $i$ edges (\textit{i.e.} $i+1$ vertices) and $2j$ half-edges, \textit{i.e.}\ oriented half-edges, called \emph{closing half-edges} or \emph{opening half-edges} respectively if the half-edge is oriented toward its vertex or away from it (see Figure~\ref{Fig:MapBij}). During the construction of the tree we maintain an active corner on the left hand side of the leftmost branch of the tree. We start with a single vertex with its unique corner as active corner and repeat for all letters of $\FF{F}$:
\begin{itemize}
\item [\emph{(E)}] If we read a step \emph{E}, we create an edge at the active corner on the tree and then move the active corner forward to the other endpoint of this new edge. 
\item[{\em(W)}] If we read a step \emph{W}, then we move the active corner counterclockwise around the tree, backward along the only edge returning to the root from its current position.
\item[\emph{(N)}] If we read a step \emph{N}, then we insert an opening half-edge at the active corner, and we move the active corner around it counterclockwise to the newly created corner at the same vertex.
\item[\emph{(S)}] If we read a step \emph{S}, then we insert a closing half-edge at the  active corner, and we move the active corner around it counterclockwise to the newly created corner at the same vertex. This closing half-edge is matched with the last unmatched opening half-edge inserted on the tree.
\end{itemize}

Finally, at the end of the construction the active corner has returned to its initial position and we root the tree there. The resulting tree is balanced in the sense of~\cite[Theorem 6]{chapterMaps} (omitted proof).

%\vspace{-1em}
\begin{figure}[t]
	\centering
	\includegraphics[scale=0.7]{MapBij}
	\caption{A map with its rightmost depth-first search spanning tree and its opening, and the corresponding generalized fighting fish.}
	\label{Fig:MapBij}
\end{figure}
%\vspace{-2em}


\paragraph{From decorated trees to rooted planar maps.}
Given a rooted decorated tree with $i+1$ vertices and $j+1$ opening (and therefore closing) half-edges, we bijectively obtain a rooted planar map endowed with its unique rightmost dept-first search spanning tree, by merging matched opening and closing half-edges into edges. This closure corresponds to the one described in~\cite[Theorem 6]{chapterMaps}.

The combined construction starting from a generalized fighting fish to the closure of the associated tree is essentially equivalent to a specialization of Mullin bijection between shuffles of two parentheses words and tree-rooted planar maps, described in~\cite[Theorem 4]{chapterMaps}.  

\begin{prop}
  The Mullin map specializes to a bijection between generalized
  fighting fish of size $n$ and tree-rooted planar maps with
  $n$ edges endowed with their (unique) rightmost depth-first search
  spanning tree. Upon forgetting the spanning tree to keep only the
  underlying rooted planar map, this yields a bijection with rooted
  planar maps with $n$ edges.
\end{prop}
\begin{proof}
The reverse bijection consists in taking the planar map $M$, endow it with its unique rightmost depth-first search spanning tree and split the edges that are not in the spanning tree. Then we can read the generalized fighting fish path by moving around the tree in counterclockwise order. The proof that the two mapping are inverse is omitted but follows from the comparison of two recursive decompositions: the standard root edge deletion decomposition of maps and a isomorphic decomposition that we found on generalized fighting fish. 
\end{proof}

\begin{prop}
  The previous bijection preserves the following statistics:
  \begin{itemize}
  \item By construction we have that the number of $E$ steps (or $W$ steps) in  $\FF{GF}$ is equal to the number of vertices minus $1$ in $M$ and that the number of $N$ steps (or $S$ steps) in  $\FF{GF}$ is equal to the number of faces of $M$ minus $1$.
  \item The number of down (resp. up) bridges in the generalized fighting fish $\FF{F}$, \emph{\textit{i.e.}} the number of ways $F$ can be decomposed as $\FF{F}=\FF{F}_1 E \FF{G} W \FF{F}_2$ (resp. $\FF{F}=\FF{F}_1 N \FF{G} S \FF{F}_2$) where $\FF{F}_1 \FF{F}_2$ and $\FF{G}$ are generalized fighting fish, corresponds to the number of bridges (resp. loops) in the planar map $M$. 
  \end{itemize}
\end{prop}


\begin{prop}
  The previous bijection specializes into a bijection between generalized fighting fish of size $n$ without down (resp. up) bridges and bridgeless (resp. loopless) planar maps with $n$ edges, and into a bijection between fighting fish of size $n$ and non-separable planar maps with $n$ edges.  
  %% The previous bijection specializes into the following bijection between $\mathcal{UF}_n$ and $\mathcal{LM}_n$, between $\mathcal{BF}_n$ and $\mathcal{BM}_n$, and between $\mathcal{FF}_n$ and $\mathcal{NS}_n$.
\end{prop}
We point out that the length of the \emph{jaw} of the fighting fish, that is the length of the first sequence of $E$ steps, gives the number of edges of the infinite face minus $1$. Another nice property of the bijection is that the notion of duality in maps is translated into the natural notion of symmetry for generalized fighting fish: exchange the operations $\bigtriangleup_k$ and $\bigtriangledown_k$ during the construction.

\section{Bijection between Tamari intervals and extended fighting fish}\label{sec2}


\subsection{A decomposition for extended fighting fish}


We now describe a decomposition of extended fighting fish introduced in section \ref{sec0}. Let us recall that even we describe them as words, we can also see them as gluings of cells and the correspondence being made by a counterclockwise tour of the boundary.


\begin{definition}
	Let $\FF{F}$ be an extended fighting fish.
%
	The \emph{size} of $\FF{F}$ is half of the number of its steps that are not $V$ minus 1, that is $\size(\FF{F}) = \frac{1}{2} (|\FF{F}|_E+|\FF{F}|_N+|\FF{F}|_W+|\FF{F}|_S) - 1$.
%
	The \emph{jaw} $\ljaw(\FF{F})$ of $\FF{F}$ is the maximal integer $k$ such that $E^{k}$ is a prefix of $\FF{F}$.
%
	The \emph{area} $\Area(\FF{F})$ of $\FF{F}$ is the number of full squares included in $\FF{F}$. It can be expressed as $\Area(\FF{F}) = \sum_{i=1}^m (y_i(\FF{F}) - y_{i-1}(\FF{F}))x_i(\FF{F})$, where $m$ is the length of $\FF{F}$ and $(x_i(\FF{F}), y_i(\FF{F}))$ are the coordinates of the point following the $i^{\rm{th}}$ step of the quadrant walk corresponding to $\FF{F}$.
%
	A \emph{pointed extended fighting fish} is an extended fighting fish $\FF{F}$ where a prefix $E^{i-1}$ with $1 \leq i \leq \ljaw(\FF{F}) + 1$ of the jaw is distinguished, which we write $\FF{F}^{\bullet i}$. There are $\ljaw(\FF{F}) +1$ ways to point an extended fighting fish $\FF{F}$.
%
	A \emph{properly pointed fighting fish} is a pointed fighting fish $\FF{F}^{\bullet i}$ such that $i \leq \ljaw(\FF{F})$.
\end{definition}

\begin{figure}[h]
	\centering
	\includegraphics[page=3,scale=0.5]{figures-these}
	\caption{All extended fighting fish of size $n+1$ for $n = 1,2,3$, with fighting fish in red boxes.}
	\label{fig:heads-decomp}
\end{figure}

We denote by $\mathcal{EFF}^\bullet_n$ the set of pointed extended fighting fish of size $n$ and by $\mathcal{EFF}^\bullet = \bigcup_{n \geq 1} \mathcal{EFF}^\bullet_n$ the set of all pointed extended fighting fish.  In the following, we also consider the word $EVS$ to be an extended fighting fish belonging to $\mathcal{EFF}$ and we will refer to it as the \emph{empty fish} and denote it $\varepsilon$, it has by convention size, area and jaw all equal to 0.

Let us now present a decomposition of extended fighting fish that encapsulates a decomposition for fighting fish. 

\begin{prop}
	Let $\FF{F}^{\bullet i}$ be a pointed extended fighting fish of size $n_1$ with $k_1 = \ljaw(\FF{F}_1)$ and $1 \leq i \leq k_1 +1$ and $\FF{F}_2$ be an extended fighting fish of size $n_2$ with $k_2 = \ljaw(\FF{F}_2)+1$. We construct a new extended fighting fish $\FF{F}$ from $\FF{F}_1$ and $\FF{F}_2$ (see Figure~\ref{fig:heads-decomp} for an example):
	\begin{itemize}
		\item if $\FF{F}_1$ and $\FF{F}_2$ are both empty, $\FF{F}$ is the Head;
		\item if $\FF{F}_1$ is empty and $\FF{F}_2$ is not, we write $\FF{F}_2 = E^{k_2} N \FF{G}_2$ and set $\FF{F} = E^{k_2+1} NW \FF{G}_2$;
		\item if $\FF{F}_2$ is empty and $\FF{F}_1$ is not, we write $\FF{F}_1^{\bullet i} \hspace{-.3pt} = \hspace{-.3pt} E^{i-1} E^{k_1-i+1} N \FF{G}_1$ and set
		$\FF{F} = E^i N E^{k_1-i} N \FF{G}_1 S$ if $1 \leq i \leq k_1$ and $\FF{F} = E^{k_1 +1} N V \FF{G}_1 S$ if $i = k_1 +1$;
		\item if $\FF{F}_1$ and $\FF{F}_2$ are both non-empty, we write $\FF{F}_1^{\bullet i} = E^{i-1} E^{k_1-i+1} N \FF{G}_1$, $\FF{F}_2 = E^{k_2} N \FF{G}_2$ and set $\FF{F} = E^{k_2} E^i N E^{k_1-i} N \FF{G}_1 \FF{G}_2$ if $1 \leq i \leq k_1$ and $\FF{F} = E^{k_2} E^{k_1 +1} N V \FF{G}_1 \FF{G}_2$ if $i = k_1 +1$;
	\end{itemize}	
	Then $\FF{F}$ is an extended fighting fish of size $n_1 + n_2+1$ with $\ljaw(\FF{F}) = \ljaw(\FF{F}_2)+i$ and $\Area(\FF{F}) = \Area(\FF{F}_1)+\Area(\FF{F}_2)+i$. We set $\oplusF(\FF{F}_1^{\bullet i},\FF{F}_2) = F$ to be the \emph{composition} of $\FF{F}_1^{\bullet i}$ and $\FF{F}_2$. Reciprocally, every non-empty extended fighting fish $\FF{F}$ can be decomposed in a unique way as $\oplusF(\FF{F}_1^{\bullet i},\FF{F}_2)$, with $\FF{F}_1^{\bullet i} \in \F^\bullet$ and $\FF{F}_2 \in \F$, \textit{i.e.} $\oplusF$ is a bijection from $\mathcal{EFF}^\bullet \times \mathcal{EFF}$ to $\mathcal{EFF} - \{\varepsilon\}$. Its restriction to fighting fish induces a bijection from $\mathcal{FF}^\bullet \times \mathcal{FF}$ to $\mathcal{FF}-\{\varepsilon\}$.
\end{prop}

To sketch the proof of this proposition, we remark that if $\FF{F}$ is a non-empty extended fighting fish, we can find its decomposition as $\oplusF(\FF{F}_1^{\bullet i},\FF{F}_2)$ by cutting $\FF{F}= E^k E^\ell N \FF{G}_1 \FF{G}_2$ such that $\FF{G}_1$ has a $x$-coordinate variation equal to 0 and contains no proper prefix having a 0 $x$-coordinate variation, $\ell =\Long(\FF{G}_1)$, then distinguishing cases whether $k=0$ or not and whether $\FF{G}_1$ starts with a $W$, a $V$ or a letter among $\{N, E\}$.

%\vspace{0em}
\begin{figure}[h]
	\centering
	\includegraphics[page=5,scale=0.6]{figures-these}
	\caption{Examples of decompositions of extended fighting fish.}
	\label{fig:heads-decomp}
\end{figure}
%\vspace{-1em}

\subsection{Tamari intervals}

We define now intervals in Tamari lattices, that have the same enumeration sequence as extended fighting fish (see~\cite{cha06}). Tamari lattices have a rich algebraic structure that we cannot explore in its all depth here, interested reader may find more details on it in~\cite{PRV,FPR,Pons19,BMFPR11}.

\paragraph{The Tamari lattice on Dyck paths}

\begin{definition}
	A \emph{Dyck path} of size $n$ is a finite walk on $\mathbb{Z}^2$ starting at (0,0) that consists of $n$ up steps $u=(1,1)$, $n$ down steps $d=(1,-1)$ and that stay above the $x$-axis.	A \emph{peak} of $P$ is a point of $P$ preceded by an up step and followed by a down step. A \emph{valley} of $P$ is a point of $P$ preceded by a down step and followed by an up step. A \emph{double rise} (resp. \emph{double descent}) of $P$ is a point of $P$ between two up steps (resp. between two down steps). A \emph{contact} of $P$ is a point of $P$ lying on the $x$-axis.
\end{definition}

Note that every non-empty Dyck path $P$ can be decomposed uniquely $P = u P_1 d P_2$ with $P_1$ and $P_2$ being Dyck paths, by cutting it in two parts at its first return to the $x$-axis. We will denote by $\mathcal{D}_n$ the set of Dyck paths of size $n$, by $\mathcal{D} = \bigcup_{n \geq 0} \mathcal{D}_n$ the set of all Dyck paths, and by $\Val(P)$, $\Peak(P)$, $\DR(P)$ and $\DD(P)$ the number of valleys, of peaks, of double rises and of double descents of a Dyck path $P$ respectively. Note that we always have $\Val(P)+1 = \Peak(P)$, $\DR(P)=\DD(P)$ and $\Val(P)+\DR(P)=n-1$.\\

We define a covering relation on $\mathcal{D}_n$. Let $P$ be an element of $\mathcal{D}_n$ that can be written (as a word) as $P = V d P_1 W$, where $V,W$ are words on the alphabet $\{u,d\}$ and $P_1$ is a Dyck path that returns to the $x$-axis only at the end. We then construct $P' = V P_1 d W$, which is also a Dyck path, and we say that $P$ covers $P'$ and that $P'$ can be obtained from $P$ by \emph{right rotation} (see Figure~\ref{fig:rightrotation}). The \emph{Tamari lattice} $(\mathcal{D}_n, \preceq)$ of order $n$ is given by the transitive closure $\preceq$ of the covering relation we just defined: $P \preceq P'$ if $P'$ can be obtained from $P$ through a (possibly empty) series of right rotations. %The Tamari lattice of order $n$ interpreted in terms of ballot paths is exactly the $(NE)^n$-Tamari lattice.%\\
%\vspace{-.5em}
\begin{figure}[h]
	\centering
	\includegraphics[page=10,scale=0.5]{figures-these}
	\caption{Example of right rotation on a Dyck path.}
	\label{fig:rightrotation}
\end{figure}
%\vspace{-.5em}
We present now the conjugation of Dyck paths which is a slight variation of the involution defined by Deutsch on Dyck paths. We refer to subsection $4.4$ of~\cite{FMN} for an extended version of results presented here. Conjugation of Dyck paths is an anti-isomorphism $\ConjD$ of Tamari lattices, that is a bijection on every $\D_n$ such that for all $P,Q \in \D_n$, we have $P \preceq Q$ if and only if $\ConjD(Q) \preceq \ConjD(P)$. Let us define recursively
\[
\ConjD(\bullet) = \bullet, \hspace{20pt}  \ConjD(P_1 u P_2 d) = \ConjD(P_2) u \ConjD(P_1) d.
\]

\begin{prop}
	$\ConjD$ is an anti-isomorphism and an involution of the Tamari lattice $\D_n$.
\end{prop}

Tamari lattices are then self-dual via the operation of conjugation, and we introduce now some vectors that behave nicely with respect to this conjugation.

\begin{definition}
	Let $P$ be a Dyck path of size $n$.
	The \emph{descent vector} of $P$ is the vector of nonnegative integers $\Drun(P)=(\d_0(P),\ldots,\d_n(P))$ such that $P = d^{\d_n(P)}ud^{\d_{n-1}(P)}u \cdots ud^{\d_0(P)}$.
	The \emph{contact vector} of $P$ is the vector of nonnegative integers $\Cont(P)=(c_0(P),\ldots,c_n(P))$ such that $c_0(P)$ is the number of non-initial contacts of $P$ and $c_i(P)$ is the number of non-initial contacts of the Dyck path following the $i^{\rm{th}}$ rise of $P$.
	The \emph{type} of $P$ is the binary vector $\Type(P) = (\t_0(P),\ldots,\t_n(P))$ such that $t_i(P)=0$ if $c_i(P)=0$.
\end{definition}

Note that a Dyck path is fully determined by the data of its descent vector (and also by its contact vector).

\begin{prop}
	For every Dyck path $P$, we have $\Cont(P) = \Drun(\Conj_\D(P))$.
\end{prop}
%\vspace{-.5em}
\begin{figure}[h]
	\centering
	\includegraphics[page=9,scale=0.6]{figures-these.pdf}
	\caption{A Dyck path and its descent and contact vectors, and its type.}
	\label{fig:dyck-vectors}
\end{figure}
%\vspace{-1em}

\paragraph{Recursive decomposition of Tamari intervals}

\begin{definition}
	A \emph{Tamari interval} of size $n\geq 0$ is an interval in the Tamari lattice $(\mathcal{D}_n, \preceq)$ of order $n$, that is a pair of comparable Dyck paths $[P, Q]$ with $P \preceq Q$. For such an interval $I=[P,Q]$, we define its contact vector $\Cont(I)=\Cont(P)$, its descent vector $\Drun(I)=\Drun(Q)$, its conjugate $\ConjI(I)=[\ConjD(Q),\ConjD(P)]$, and its \emph{Tamari distance} $\L(I)$ to be the length of the longest strictly increasing chain from $P$ to $Q$ in the Tamari lattice.\\
	We say that a Tamari interval is \emph{synchronized} if $P$ and $Q$ have the same type, and we set $\type(I)=\type(P)=\type(Q)$.\\
	A \emph{pointed Tamari interval} is an interval $[P,Q]$ with a distinguished contact of the lower path $P$, which we write as $[P^\ell {\bullet} P^r,Q]$, where $P=P^\ell P^r$ is split by the distinguished contact into two Dyck subpaths $P^\ell$ and $P^r$ (that can be empty). We also write $[P, Q]^{\bullet i}$ for some $1 \leq i \leq \c_0(I)+1$ to denote the pointed interval obtained from $[P,Q]$ by distinguishing the $i^{\rm{th}}$ contact from right to left of $P$. A \emph{properly pointed synchronized interval} is a pointed synchronized interval $[P^\ell {\bullet} P^r,Q]$ such that $P^\ell$ is non-empty.
\end{definition}

We denote by $\mathcal{I}_n$ (resp. $\mathcal{SI}_n$) the set of Tamari intervals (resp. synchronized intervals) of size $n$ and by $\mathcal{I}^\bullet_n$ (resp. $\mathcal{SI}^\bullet_n$) the set of pointed Tamari intervals (resp. properly pointed synchronized intervals) of size $n$.

With this definition of pointed intervals, we are now able to give a decomposition of Tamari intervals proved in~\cite{BMFPR11} and specialized to synchronized intervals in~\cite{FPR}:

\begin{thm}[\cite{BMFPR11,FPR}]
	Let $I^{\bullet i}_1 = [P_1^\ell {\bullet} P_1^r,Q_1]$ be a pointed Tamari interval of size $n_1$ with $1\leq i \leq \c_0(I_1)+1$ and $I_2 = [P_2, Q_2]$ be a Tamari interval of size $n_2$. We define the \emph{composition} of $I^{\bullet i}_1$ and $I_2$ as (see Figure~\ref{fig:int-decomp} for an example):
	\[\oplusI(I^{\bullet i}_1, I_2) = [u P_1^\ell d P_1^r P_2, u Q_1 d Q_2].\]
	Then $\oplusI(I^{\bullet i}_1, I_2)$ is a Tamari interval of size $n_1+n_2+1$ and we have:\\
	$\begin{cases*}
	\Cont(\oplusI(I^{\bullet i}_1, I_2))=(\c_0(I_2)+i,\c_0(I_1)-i+1,\c_1(I_1),\ldots,\c_n(I_1),\c_1(I_2),\ldots,\c_n(I_2)),\\
	\Drun(\oplusI(I^{\bullet i}_1, I_2))=(\d_0(I_2),\ldots,\d_{n-1}(I_2),\d_n(I_2)+1+\d_0(I_1),\d_1(I_1),\ldots,\d_n(I_1),0).
	\end{cases*}$\\
	In particular, $\c_0(\oplusI(I^{\bullet i}_1, I_2))=\c_0(I_2)+i$. We have also $\L(\oplusI(I^{\bullet i}_1, I_2)) = \L(I_1) + \L(I_2) + i -1$.
	Furthermore, the map $\oplusI$ is a bijection from $\mathcal{I}^\bullet \times \mathcal{I}$ to $\mathcal{I} - \{[\bullet,\bullet]\}$, \textit{i.e.} every Tamari interval $I=[P,Q]$ of size $n \geq 1$ can be decomposed in a unique way as $\oplusI(I^{\bullet i}_1, I_2)$, with $I_1^{\bullet i}$ being a pointed Tamari interval and $I_2$ being a Tamari interval. Its restriction to synchronized intervals induces a bijection between $\mathcal{SI}^\bullet \times \mathcal{SI}$ and $\mathcal{SI} - \{[\bullet,\bullet]\}$.
\end{thm}

%\vspace{-0.5em}
\begin{figure}[h]
	\centering
	\includegraphics[page=13,scale=0.65]{figures-these.pdf}
	\caption{Decomposition of Tamari intervals.}
	\label{fig:int-decomp}
\end{figure}
%\vspace{-1em}



	

\subsection{Bijection between Tamari intervals and extended fighting fish}

We are now able to recursively define a bijection $\Phi$ from Tamari intervals to extended fighting fish. We set
\begin{align*}
\Phi([\bullet, \bullet]) & = \epsilon,\\
\Phi(\oplusI(I_1^{\bullet i},I_2)) & = \oplusF(\Phi(I_1)^{\bullet i},\Phi(I_2)) \text{ for all } (I_1^{\bullet i},I_2) \in \mathcal{I}^\bullet \times \mathcal{I}.
\end{align*}

\begin{thm}
	$\Phi$ is a bijection from Tamari intervals to extended fighting fish such that for every Tamari interval $I$ of size $n \geq 0$, $\Phi(I)$ is of size $n$ and we have $\ljaw(\Phi(I)) = \c_0(I)$.
	Moreover, the restriction of $\Phi$ to synchronized intervals induces a bijection from synchronized intervals to fighting fish.
\end{thm}

To see that $\Phi$ is well-defined and it is a bijection, we have to prove by induction on the size $n$ of intervals that for every Tamari interval $I$ of size $n$, $\Phi(I)$ has size $n$ and can be pointed by exactly the same integers, that is to say $\c_0(I)=\ljaw(\Phi(I))$. Those conditions are true at every step of the induction because they are true for $I = [\bullet,\bullet]$ and composition relations for size and for $\c_0$ and $\ljaw$ imply the inductive step.

We have actually a direct description of the bijection proved using isomorphic decompositions of the two classes (see Figure~\ref{fig:example-bij-tamari} for an example):

\begin{thm}
	Let $I=[P,Q]$ be a Tamari interval of size $n \geq 0$, with $\Cont(I)=\Cont(P)$ and $\Drun(I)=(\d_n(Q), \ldots,\d_0(Q))$ its contact and descent vectors. For $0 \leq i \leq n$, we define
	\[
	w_i = \begin{cases} E^{\c_i(P)-1}N &\text{ if } \c_i(P) \geq 1 \text{ and } \d_{n-i}(Q) = 0,\\
	WS^{\d_{n-i}(Q)-1} &\text{ if } \c_i(P) =0 \text{ and } \d_{n-i}(Q) \geq 1,\\
	V &\text{ if } \c_i(P) =0 \text{ and } \d_{n-i}(Q) = 0.
    \end{cases}
	\]
	Then the word $Ew_0w_1 \cdots w_nS$ is the extended fighting fish $\Phi(I)$. The parameters $|\Phi(I)|_E$, $|\Phi(I)|_W$, $|\Phi(I)|_N$ and $|\Phi(I)|_S$ match respectively $\Val(P)+1$, $\Val(Q)+1$, $\DR(P)+1$ and $\DR(Q)+1$. Moreover,
	$\begin{cases*}
	\L(I) = \Area(\Phi(I)) - n,\\
	\Phi(\ConjI(I))=\ConjF(\Phi(I)).
	\end{cases*}$
\end{thm}


\begin{figure}[h]
	\centering
	\includegraphics[page=14,scale=0.6]{figures-these.pdf}
	\caption{An example of the bijection $\Phi$.}
	\label{fig:example-bij-tamari}
\end{figure}
%\vspace{-1.5em}

\section{Conclusion}

With these two bijections that specialize nicely into subclasses of the considered objects, we hope to create bridges between the different worlds where generalized extended fighting fish, planar maps and Tamari intervals live.  Our bijections preserves the structure of the objects, as shown by the conservation of symmetry properties and the equinumeration of statistics, and we aim to a deeper study of these results. We also want to point out that the link between Tamari distance of intervals and area of extended fighting fish brings a new combinatorial interpretation of the Tamari distance, which is closely related to algebraic combinatorics (see ~\cite{bergeron2011higher}). 

\printbibliography

\end{document}

