%% 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[finalversion]{FPSAC2025}
\articlenumber{142}
%% 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}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\theoremstyle{definition}
\newtheorem{example}[theorem]{Example}

\usepackage{hyperref,resizegather,enumitem}
\usepackage[linesnumbered,ruled,vlined]{algorithm2e}
	\DontPrintSemicolon
	\SetAlgoSkip{medskip}

% Functions

\newcommand{\len}[1]{\ensuremath{\mathopen{}\left\lvert #1 \right\rvert\mathclose{}}} % for |x|
\newcommand{\set}[1]{\ensuremath{\mathopen{}\left\lbrace #1 \right\rbrace\mathclose{}}} % for {x}
\newcommand{\sqt}[1]{\ensuremath{\mathopen{}\left\lbrack #1 \right\rbrack\mathclose{}}} % for [x]
\newcommand{\prts}[1]{\ensuremath{\mathopen{}\left( #1 \right)\mathclose{}}} % for (x)
\newcommand{\setd}[2]{\ensuremath{\mathopen{}\left\lbrace #1\,\middle\vert\,#2 \right\rbrace\mathclose{}}} % for {x|r}
\newcommand{\cont}[1]{\mathrm{cont}\prts{#1}} % for cont(x)
\newcommand{\supp}[1]{\mathrm{supp}\prts{#1}} % for supp(x)

% Assorted letters

\newcommand{\bbN}{\mathbb{N}}
\newcommand{\calR}{\mathcal{R}}
\newcommand{\calX}{\mathcal{X}}
\newcommand{\uord}{\mathbf{u}}
\newcommand{\vord}{\mathbf{v}}
\newcommand{\word}{\mathbf{w}}

% Plactic-like symbols

\newcommand{\hypo}[1][]{\ensuremath{\mathsf{hypo}_{#1}}}
\newcommand{\sylv}[1][]{\ensuremath{\mathsf{sylv}_{#1}}}
\newcommand{\sylvh}[1][]{\ensuremath{\mathsf{sylvh}_{#1}}}
\newcommand{\rst}[1][]{\ensuremath{\mathsf{rSt}_{#1}}}
\newcommand{\lst}[1][]{\ensuremath{\mathsf{lSt}_{#1}}}
\newcommand{\rtg}[1][]{\ensuremath{\mathsf{rTg}_{#1}}}
\newcommand{\ltg}[1][]{\ensuremath{\mathsf{lTg}_{#1}}}
\newcommand{\mtg}[1][]{\ensuremath{\mathsf{mTg}_{#1}}}
\newcommand{\jtg}[1][]{\ensuremath{\mathsf{jTg}_{#1}}}

% Generic P symbols
\newcommand{\plr}{\ensuremath{\mathrm{P}^\rightarrow}}
\newcommand{\prl}{\ensuremath{\mathrm{P}^\leftarrow}}
\newcommand{\psymb}{\ensuremath{\mathrm{P}}}

% Generic Q symbols
\newcommand{\qlr}{\ensuremath{\mathrm{Q}^\rightarrow}}
\newcommand{\qrl}{\ensuremath{\mathrm{Q}^\leftarrow}}
\newcommand{\qsymb}{\ensuremath{\mathrm{Q}}}

% P symbol functions
\newcommand{\pltg}[1]{\ensuremath{\plr_{\ltg}\prts{#1}}}
\newcommand{\prtg}[1]{\ensuremath{\prl_{\rtg}\prts{#1}}}
\newcommand{\pmtg}[1]{\ensuremath{\psymb_{\mtg}\prts{#1}}}

% Q symbol functions
\newcommand{\qltg}[1]{\ensuremath{\qlr_{\ltg}\prts{#1}}}
\newcommand{\qrtg}[1]{\ensuremath{\qrl_{\rtg}\prts{#1}}}
\newcommand{\qmtg}[1]{\ensuremath{\qsymb_{\mtg}\prts{#1}}}

% TikZ configuration
\usepackage{tikz}
\usetikzlibrary{shapes.misc}

\tikzset{
	bst/.style={
		standard/.style={
			font=\small,
			draw=black,
			rounded rectangle,
			minimum width=4.5mm,
			minimum height=4.5mm,
			inner xsep=0.5mm,
			inner ysep=1mm,
			outer sep=0mm,
			line width=.5pt,
		},
		crossed/.style={
			standard,
			path picture={
				\draw[thick]
				(path picture bounding box.south east) -- (path picture bounding box.north west)
				(path picture bounding box.south west) -- (path picture bounding box.north east);
			}
		},
		every node/.style={standard},
		every child/.style={draw=black,line width=.6pt},
		level distance=10mm,
		level 1/.style={sibling distance=60mm},
		level 2/.style={sibling distance=30mm},
		level 3/.style={sibling distance=15mm},
	},
	tinybst/.style={
		bst,
		level distance=5.5mm,
		level 1/.style={sibling distance=8mm},
		level 2/.style={sibling distance=8mm},
		level 3/.style={sibling distance=8mm},
		every node/.append style={
			font=\footnotesize,
		},
	},
	microbst/.style={
		bst,
		standard/.append style={
			font=\scriptsize,
			minimum width=3mm,
			minimum height=3mm,
			inner ysep=1.5mm,
		},
		level distance=5.5mm,
		level 1/.style={sibling distance=10mm},
		level 2/.style={sibling distance=10mm},
		level 3/.style={sibling distance=10mm},
	},
}

%% define your title in the usual way
\title[The meet-taiga and join-taiga monoids]{Plactic-like monoids arising from meets and joins of taiga congruences}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
%% for more than 3 names, use the Oxford comma: One Author, Two Author, Red Author, \and Blue Author
\author{\texorpdfstring{Thomas Aird\thanks{\href{mailto:thomas.aird@manchester.ac.uk}{thomas.aird@manchester.ac.uk}. Thomas Aird's work was supported by the London Mathematical Society, the Heilbronn Institute for Mathematical Research, and NOVA University Lisbon.}\addressmark{1} \and Duarte Ribeiro\thanks{\href{mailto:duarte.ribeiro.math@gmail.com}{duarte.ribeiro.math@gmail.com}. Duarte Ribeiro's work was supported by National Funds through the FCT -- Funda\c{c}\~{a}o para a Ci\^{e}ncia e a Tecnologia, I.P., under the scope of the projects PTDC/MAT-PUR/31174/2017, UIDB/04621/2020 and UIDP/04621/2020 (Center for Computational and Stochastic Mathematics), and UIDB/00297/2020 (\url{https://doi.org/10.54499/UIDB/00297/2020}) and UIDP/00297/2020 (\url{https://doi.org/10.54499/UIDP/00297/2020}) (Center for Mathematics and Applications).}\addressmark{2}}{Thomas Aird and Duarte Ribeiro}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Department of Mathematics, The University of Manchester, Alan Turing Building, Oxford Rd, Manchester, M13 9PL, UK \\ \addressmark{2}Center for Mathematics and Applications (NOVA Math), FCT NOVA, 2829-516 Caparica, Portugal}

%% put the date of submission here
\received{November 14, 2025}

%% leave this blank until submitting a revised version
\revised{March 31, 2025}

%% 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 study algebraic and combinatorial properties of plactic-like monoids arising from the meets and joins of taiga congruences. We construct combinatorial objects associated with the meet-taiga monoid, establish a Robinson--Schensted-like correspondence and give extraction and iterative insertion algorithms for said objects. Finally, we obtain `hook-length'-like formulas for the various taiga monoids.}

%% put your French abstract here, or comment this out if you don't have one
% \resume{\lipsum[2]}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{Taiga monoid, binary trees with multiplicities, Robinson--Schensted correspondence, extraction algorithm, iterative insertion algorithm, hook-length formula}

%% 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; i.e., [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, giveninits]{biblatex}
\addbibresource{ribeiro_taiga_monoids.bib}
\appto\bibfont{\setlength{\emergencystretch}{.5em}}
%% 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{Introduction} \label{section:Introduction}

Plactic-like monoids are an informal class of monoids that share the interesting property of their elements being uniquely identified with combinatorial objects, thus giving these monoids a fundamental role in algebraic combinatorics. The namesake of this family is the plactic monoid, also known as the monoid of Young tableaux \cite{LS1978}. It has been widely applied in several areas of mathematics such as representation theory, symmetric functions and crystal bases. Other plactic-like monoids  have since arisen in the context of combinatorial Hopf algebras whose bases are indexed by combinatorial objects.

The Baxter monoid was introduced by Giraudo \cite{giraudo_baxter} as the analogue of the plactic monoid for Hopf algebras indexed by Baxter permutations. Its defining congruence was shown to be the meet of the sylvester congruence and its dual, in the lattice of congruences on the free monoid. Thus, its combinatorial objects are pairs of twin binary search trees, that is, pairs of combinatorial objects of the sylvester monoid and its dual, that satisfy certain restrictions. On the other hand, it is also known that the join of the sylvester congruence and its dual is the hypoplactic congruence \cite{novelli_hypoplactic}.

The (right-) taiga monoid was defined by Priez \cite{priez_binary_trees} as the quotient of the free monoid by the join of the sylvester and (right-) stalactic congruences. Its associated combinatorial objects are binary search trees with multiplicities. Due to their similarity to the sylvester monoids, it is natural to ask what are the combinatorial properties of the `Baxter' and `hypoplactic' analogues of the taiga monoids.

In this extended abstract, we study such analogues, which we call the meet- and join-taiga monoids. These were introduced by the authors in \cite{aird_ribeiro_meet_join}, where one can find detailed proofs, as well as analogous results on the meet- and join-stalactic monoids. 

The necessary background is given in \Cref{section:Background}. We introduce the meet- and join-taiga congruences in \Cref{section:meets_and_joins_of_taiga_congruences}, for which we give several equivalent characterisations.

\Cref{section:Robinson_Schensted_like_correspondence} focuses on the combinatorial objects associated with the meet-taiga monoid. We define $\psymb$-symbols by taking pairs of binary search trees with multiplicities satisfying certain restrictions. We similarly define $\qsymb$-symbols, and use them to establish Robinson--Schensted-like correspondences. We then give algorithms to extract words from $\psymb$-symbols, as well as iterative versions of the insertion algorithms, allowing us to easily compute the concatenation of words under the meet-taiga congruence.

In \Cref{section:Counting_in_the_taiga_monoids}, we provide explicit `hook-length'-like formulas for the sizes of the left-, right- and join-taiga congruence classes. The meet-taiga case is equivalent to counting the number of linear extensions in specific posets, for which we state its time complexity. Finally, we give bounds for the number of binary search trees with multiplicities which form a pair of twin binary search trees with multiplicities with a given one.

\section{Background} \label{section:Background}

For background on monoids, congruences and presentations, see \cite[Chapter~1]{howie1995fundamentals}. Let $\bbN = \set{1,2,\dots}$ denote the set of natural numbers, without zero. For $a,b \in \bbN$, we denote by $\sqt{a}$ the set $\set{1 < \cdots < a}$, and by $\sqt{a,b}$ the set $\setd{k \in \bbN}{a \leq k \leq b}$, when $a<b$.

\subsection{Words} \label{subsection:Words}

For any non-empty set $\calX$, we denote by $\calX^*$ the free monoid generated by $\calX$, that is, the set of all words over $\calX$ under concatenation. We denote the empty word by $\varepsilon$, and refer to $\calX$ as an \emph{alphabet}, and to its elements as \emph{letters}. For a word $\word \in \calX^*$, its \emph{restriction} to a subset $\mathcal{S}$ of $\calX$, denoted by $\word\sqt{S}$, is the word obtained from $\word$ by removing any letter not in $\mathcal{S}$. We denote the length of $\word$ by $\len{\word}$ and, for each $x \in \calX$, we denote the number of occurrences of $x$ in $\word$ by $\len{\word}_x$. If $\len{\word}_x = 1$, we say $x$ is a \emph{simple letter} of $\word$, and we denote the restriction of $\word$ to its simple letters by $\overline{\word}$.

The subset of $\calX$ of letters that occur in $\word$ is called the \emph{support} of $\word$, denoted by $\supp{\word}$, and the function from $\calX$ to $\bbN_0$ given by $x \mapsto \len{\word}_x$ is called the \emph{content} of $\word$, denoted by $\cont{\word}$. Clearly, two words that share the same content also share the same support.

\subsection{Binary trees with multiplicities and binary search trees with multiplicities} \label{subsection:binary_trees_with_multiplicities_and_binary_search_trees_with_multiplicities}

For background on right strict, left strict and pairs of twin binary search trees, see \cite{giraudo_baxter}. Empty combinatorial objects are denoted by $\perp$. We refer to the underlying unlabelled objects of labelled objects as their \emph{shapes}.

A \emph{binary tree with multiplicities} (BTM) is a rooted planar binary tree where each node is labelled by a positive integer, called a \emph{multiplicity}. A \emph{binary search tree with multiplicities} (BSTM) is a BTM where each node is further labelled by a letter of $\bbN$, such that the letter of the left (resp. right) child of any node is strictly less than (resp. strictly greater than) the letter of said node. We consider the \emph{label} of a node of a BSTM to be the pair consisting of the letter and multiplicity that labels the node. For ease of notation, we write multiplicities as superscripts. Examples of BSTMs are the following:

\begin{equation*}
	\label{example:bstm}
	\begin{tikzpicture}[tinybst,baseline=-8mm]
		\node{$4^3$}
		child { node{$1^2$} 
			child[missing]
			child { node{$2^2$}
				child[missing]
				child { node{$3^1$} }
			}
		}
		child[missing]
		child { node{$5^1$} };
	\end{tikzpicture}
	\quad \text{and} \quad
	\begin{tikzpicture}[tinybst,baseline=-6mm]
		\node{$2^2$}
		child { node{$1^2$} }
		child { node{$4^3$}
			child { node{$3^1$} }
			child { node{$5^1$} }
		};
	\end{tikzpicture}
\end{equation*}

Algorithm \hyperref[alg:TaigaLeafInsertion]{\textsf{TgLI}} allows one to insert a letter into a BSTM, either by a new leaf labelled by it or by increasing the multiplicity of a node labelled by it, and still obtain a BSTM. Using this algorithm, one can compute a unique BSTM from a word $\word$: starting from the empty tree, read $\word$ from right to left (resp. left to right) and insert its letters one-by-one into the tree. The resulting tree is denoted by $\prtg{\word}$ (resp. $\pltg{\word}$).

\begin{algorithm}[ht] \label{alg:TaigaLeafInsertion}
	\DontPrintSemicolon
	\KwIn{A BSTM $T$, a letter $a \in \bbN$.}
	\KwOut{A BSTM $T \uparrow a$.}
	\BlankLine
	\lIf{$T$ is empty}{add a node labelled $a$ with multiplicity $1$.}
	\Else{
		let $b$ be the letter that labels the root node of $T$;\\
		\lIf{$a < b$}{recursively insert $a$ into the left subtree of the root node;}
		\lElseIf{$a > b$}{recursively insert $a$ into the right subtree of the root node;}
		\lElse{increment by 1 the multiplicity of the root node;}
	}
	\Return the resulting tree $T \uparrow a$.
	\caption{\textit{Taiga Leaf Insertion} (\textsf{TgLI}).}
\end{algorithm}

\begin{example}
	\label{example:insertion_alg_prtg}
	Computing $\prtg{451423412}$:
	\begin{gather*}  
		\begin{tikzpicture}[tinybst, baseline=-1mm]
			\node{$2^1$};
		\end{tikzpicture}
		\quad\xrightarrow{1}\quad
		\begin{tikzpicture}[tinybst, baseline=-4mm]
			\node{$2^1$}
			child { node{$1^1$} }
			child[missing];
		\end{tikzpicture}
		\quad\xrightarrow{4}\quad
		\begin{tikzpicture}[tinybst, baseline=-4mm]
			\node{$2^1$}
			child { node{$1^1$} }
			child { node{$4^1$} };
		\end{tikzpicture}
		\quad\xrightarrow{3}\quad
		\begin{tikzpicture}[tinybst, baseline=-6mm]
			\node{$2^1$}
			child { node{$1^1$} }
			child { node{$4^1$}
				child { node{$3^1$} }
				child [missing]
			};
		\end{tikzpicture}
		\quad\xrightarrow{2}\quad		
		\begin{tikzpicture}[tinybst, baseline=-6mm]
			\node{$2^2$}
			child { node{$1^1$} }
			child { node{$4^1$}
				child { node{$3^1$} }
				child [missing]
			};
		\end{tikzpicture}
		\quad\xrightarrow{4}\\[10pt]
		\xrightarrow{4}\quad
		\begin{tikzpicture}[tinybst, baseline=-6mm]
			\node{$2^2$}
			child { node{$1^1$} }
			child { node{$4^2$}
				child { node{$3^1$} }
				child [missing]
			};
		\end{tikzpicture}
		\quad\xrightarrow{1}\quad
		\begin{tikzpicture}[tinybst, baseline=-6mm]
			\node{$2^2$}
			child { node{$1^2$} }
			child { node{$4^2$}
				child { node{$3^1$} }
				child [missing]
			};
		\end{tikzpicture}
		\quad\xrightarrow{5}\quad
		\begin{tikzpicture}[tinybst, baseline=-6mm]
			\node{$2^2$}
			child { node{$1^2$} }
			child { node{$4^2$}
				child { node{$3^1$} }
				child { node{$5^1$} }
			};
		\end{tikzpicture}
		\quad\xrightarrow{4}\quad
		\begin{tikzpicture}[tinybst, baseline=-6mm]
			\node{$2^2$}
			child { node{$1^2$} }
			child { node{$4^3$}
				child { node{$3^1$} }
				child { node{$5^1$} }
			};
		\end{tikzpicture}
	\end{gather*}
\end{example}

An \emph{increasing} (resp. \emph{decreasing}) \emph{binary tree} is an $\bbN$-labelled rooted planar binary tree, such that the label of each node is less than (resp. greater than) the label of its children, and no two nodes have the same label. 

For a word $\word$ with no repeated letters, algorithm \hyperref[alg:RecursiveIncreasingBinaryTreeAlgorithm]{\textsf{RiBTA}} allows one to compute an increasing binary tree $\mathrm{incr}(\word)$ obtained from $\word$. We define a \emph{Recursive Decreasing Binary Tree Algorithm} (\hyperref[alg:RecursiveIncreasingBinaryTreeAlgorithm]{\textsf{RdBTA}}) algorithm by replacing ``\textrm{incr}'' with ``\textrm{decr}'' and ``least'' with ``greatest'' in \hyperref[alg:RecursiveIncreasingBinaryTreeAlgorithm]{\textsf{RiBTA}}.

\begin{algorithm}[ht] \label{alg:RecursiveIncreasingBinaryTreeAlgorithm}
	\DontPrintSemicolon
	\KwIn{A word $\word \in \bbN^*$ with no repeated letters.}
	\KwOut{An increasing binary tree $\mathrm{incr}(\word)$.}
	\BlankLine
	let $\mathrm{incr}(\word) := \perp$; \\
	\lIf{$\len{\word} \geq 1$}{write $\word = \uord a \vord$, where $a$ is the least letter of $\word$, label the root node of $\mathrm{incr}(\word)$ by $a$ and recursively compute its left subtree $\mathrm{incr}(\uord)$ and right subtree $\mathrm{incr}(\vord)$;}
	\Return the resulting tree $\mathrm{incr}(\word)$.
	\caption{\textit{Recursive Increasing Binary Tree Algorithm} (\textsf{RiBTA}).}
\end{algorithm}

We say that a binary tree whose labels are non-intersecting subsets of $\bbN$ is an \emph{increasing} (resp. \emph{decreasing}) \emph{binary tree over sets} (BTS) if the binary tree obtained by replacing each set with its minimum (resp. maximum) element is an increasing (resp. decreasing) binary tree. Examples of increasing and decreasing binary trees over sets are the following:
\begin{equation*}
	\label{example:increasing_decreasing_binary_trees_over_sets}
	\begin{tikzpicture}[microbst,baseline=-8mm]
		\node{$1,4,7$}
		child { node{$3,8$} 
			child[missing]
			child { node{$5,9$}
				child[missing]
				child { node{$6$} }
			}
		}
		child[missing]
		child { node{$2$} };
	\end{tikzpicture}
	\quad \text{and} \quad
	\begin{tikzpicture}[microbst, baseline=-6mm]
		\node{$5,9$}
		child { node{$3,8$} }
		child { node{$1,4,7$}
			child { node{$6$} }
			child { node{$2$} }
		};
	\end{tikzpicture}
\end{equation*}

Using Algorithm \hyperref[alg:RecursiveIncreasingBinaryTreeAlgorithm]{\textsf{RiBTA}} (resp. \hyperref[alg:RecursiveIncreasingBinaryTreeAlgorithm]{\textsf{RdBTA}}), one can compute a unique increasing (resp. decreasing) BTS from a word $\word$:
Let $\supp{\word} = \set{x_1 < \dots < x_k}$. For each $i \in \sqt{k}$, consider the set $W_i$ of all $j \in \sqt{\len{\word}}$ such that $x_i$ is the $j$-th letter of $\word$, when reading $\word$ from left to right. Let $\vord = v_1\cdots v_k$ be the word where $v_i = \min(W_i)$ (resp. $v_i = \max(W_i)$). Now, apply \hyperref[alg:RecursiveIncreasingBinaryTreeAlgorithm]{\textsf{RiBTA}} (resp. \hyperref[alg:RecursiveIncreasingBinaryTreeAlgorithm]{\textsf{RdBTA}}), to $\vord$ to obtain an increasing (resp. decreasing) binary tree. Finally, for each $i \in \sqt{k}$ replace the label $v_i$ in the tree with the set $W_i$. The resulting tree is denoted $\qltg{\word}$ (resp. $\qrtg{\word}$).

\begin{example}
	Computing $\qrtg{451423412}$: Let $\word = 451423412$. Then, $W_1 = \set{3,8}$, $W_2 = \set{5,9}$, $W_3 = \set{6}$, $W_4 = \set{1,4,7}$ and $W_5 = \set{2}$ and, as such, $\vord = 89672$.
	
	\begin{gather*}  
		\begin{tikzpicture}[microbst, baseline=-1mm]
			\node{$9$};
		\end{tikzpicture}
		\quad\xrightarrow{8,7}\quad
		\begin{tikzpicture}[microbst, baseline=-4mm]
			\node{$9$}
			child { node{$8$} }
			child { node{$7$} };
		\end{tikzpicture}
		\quad\xrightarrow{6,2}\quad
		\begin{tikzpicture}[microbst, baseline=-6mm]
			\node{$9$}
			child { node{$8$} }
			child { node{$7$}
				child { node{$6$} }
				child { node{$2$} }
			};
		\end{tikzpicture}
		\quad\rightarrow\quad
		\begin{tikzpicture}[microbst, baseline=-6mm]
			\node{$5,9$}
			child { node{$3,8$} }
			child { node{$1,4,7$}
				child { node{$6$} }
				child { node{$2$} }
			};
		\end{tikzpicture}
	\end{gather*}
\end{example}

Ley $\word$ be a word with support $\set{x_1 < \dots < x_k}$. Then, $\pltg{\word}$ (resp. $\prtg{\word}$) and $\qltg{\word}$ (resp. $\qrtg{\word}$) have the same underlying binary tree shape. Furthermore, for each $i \in \sqt{k}$, the letters $x_i$ have their positions in $\word$ given by the label of the $i$-th node of $\qltg{\word}$ (resp. $\qrtg{\word}$). From this, we have an analogue of the Robinson--Schensted correspondence for pairs of BSTMs and BTSs, first stated in \cite{priez_binary_trees}. We give the result for the right-insertion algorithm case:

\begin{theorem} \label{theorem:robinson_right_taiga}
	The map $\word \mapsto (\prtg{\word}, \qrtg{\word})$ is a bijection between the elements of $\bbN^*$ and the set formed by the pairs $(T,S)$ where
	\begin{enumerate}[label={(\roman*)}]
		\item $T$ is a BSTM;
		\item $S$ is a decreasing BTS such that the union of the sets labelling $S$ is the interval $\sqt{m}$, where $m$ is the sum of the multiplicities of $T$;
		\item $T$ and $S$ have the same underlying binary tree shape;
		\item the multiplicity of the $i$-th node of $T$ is the cardinality of the set labelling the $i$-th node of $S$.
	\end{enumerate}
\end{theorem}

\subsection{The right- and left-taiga monoids} \label{subsection:the_right_and_left_taiga_monoids}

For background on the hypoplactic, sylvester and stalactic monoids, see \cite{novelli_hypoplactic}, \cite{hivert_sylvester} and \cite{hnt_stalactic}, respectively. 

The \emph{right-taiga congruence} $\equiv_{\rtg}$ on $\bbN^*$ is defined in the following way: for $\uord,\vord \in \bbN^*$,
\[ \uord \equiv_{\rtg} \vord \Leftrightarrow \prtg{\uord} = \prtg{\vord}. \]

The factor monoid $\bbN^*/{\equiv_{\rtg}}$ is the (infinite-rank) \emph{right-taiga monoid}, denoted by $\rtg$. It follows from the definition of $\rtg$ that any element $\sqt{\word}_{\rtg}$ can be uniquely identified with the BSTM $\prtg{\word}$. All words in each $\equiv_{\rtg}$-class share the same content (and therefore the same support), hence, we extend these definitions to $\equiv_{\rtg}$-classes and BSTMs in a natural way. The left-taiga congruence $\equiv_{\ltg}$ and monoid $\ltg$ are defined analogously.

Recall that the sylvester and \#-sylvester congruences are generated, respectively, by the relations
\begin{align*}
	\calR_{\sylv} &= \setd{(ca \uord b,ac \uord b)}{a \leq b < c, \uord \in \bbN^*} \; \text{and} \\ 
	\calR_{\sylvh} &= \setd{(b \uord ac,b \uord ca)}{a < b \leq c, \uord \in \bbN^*},
\end{align*}
and the right- and left-stalactic congruences are generated, respectively, by the relations
\begin{align*}
	\calR_{\rst} &= \setd{(ba \uord b,ab \uord b)}{a,b \in \bbN, \uord \in \bbN^*} \; \text{and} \\ 
	\calR_{\lst} &= \setd{(b \uord ab,b \uord ba)}{a,b \in \bbN, \uord \in \bbN^*}.
\end{align*}

\begin{proposition}[{\cite[Proposition 4]{priez_binary_trees}}]
	The right- and left-taiga congruences are generated, respectively, by the relations
	\[
	\calR_{\rtg} = \calR_{\sylv} \cup \calR_{\rst} \quad \text{and} \quad \calR_{\ltg} = \calR_{\sylvh} \cup \calR_{\lst}.
	\]
\end{proposition}
The proof of \cite[Lemma~17]{cm_identities} can be easily adapted to show that $\rtg$ is left-cancellative and $\ltg$ is right-cancellative.

\section{Meets and joins of taiga congruences} \label{section:meets_and_joins_of_taiga_congruences}

We now consider, in the lattice of congruences on  $\bbN^*$, the meet and join of the taiga congruences given in the previous subsection. We respectively call them the \emph{meet-taiga} and the \emph{join-taiga} congruences, and denote them by $\equiv_{\mtg}$ and $\equiv_{\jtg}$. Thus, we define the \emph{meet-taiga} monoid $\mtg$ and \emph{join-taiga} monoid $\jtg$ as quotients of $\bbN^*$ by the corresponding congruences. 

We start by giving generating relations for these congruences. Clearly, the join-taiga congruence is generated by the relations $\calR_{\jtg} := \calR_{\rtg} \cup \calR_{\ltg}$. On the other hand, we have that:

\begin{proposition} \label{prop:MeetTaigaPresentation}
	The meet-taiga congruence is generated by the relations
	\begin{align*}
		\calR_{\mtg} := \setd{(b \uord ad \vord c,b \uord da \vord c)}{a \leq d, \; b,c \in \sqt{a,d}, \; \uord,\vord \in \bbN^*}.
	\end{align*}
\end{proposition}

We can characterise the join-taiga class of a word by looking at the hypoplactic classes of specific subsequences of it:

\begin{proposition}
	\label{prop:jtg_characterisation}
	Let $\uord,\vord \in \bbN^*$. Let $A_1,\dots, A_k$ be all the intervals of $\supp{\uord}$ such that $A_i$ only contains simple letters and $A_i \cup \set{a}$ is not an interval, for any simple letter $a \notin A_i$. Then, $\uord \mathop{\equiv_{\jtg}} \vord$ if and only if $\cont{\uord} = \cont{\vord}$ and $\uord\sqt{A_i} \mathop{\equiv_{\hypo}} \vord\sqt{A_i}$ for all $1 \leq i \leq k$. 
\end{proposition}

\section{Robinson--Schensted-like correspondence} \label{section:Robinson_Schensted_like_correspondence}

In this section, we first introduce an analogue of the Robinson--Schensted correspondence for the meet-taiga monoid. We then show how to extract representatives of classes from their $\psymb$-symbols, and give an iterative version of the insertion algorithm, allowing us to compute a combinatorial object while reading a word in one direction only.

\subsection{Definition and correctness of the correspondence} \label{subsection:Definition_and_correctness_of_the_correspondence}

We define the \emph{meet-taiga $\psymb$-symbol} of a word $\word$ as the pair $(\pltg{\word}, \prtg{\word})$ of BSTMs, denoted by $\pmtg{\word}$, and the \emph{meet-taiga $\qsymb$-symbol} of $\word$ as the pair $(\qltg{\word}, \qrtg{\word})$ of (respectively) increasing and decreasing binary trees, denoted by $\qmtg{\word}$.

\begin{example} \label{example:meet_taiga_p_and_q_symbols}
	The meet-taiga $\psymb$ and $\qsymb$-symbols of $451423412$ are, respectively, the following:
	\begin{equation*}
		\left(\begin{tikzpicture}[tinybst,baseline=-8mm]
			\node{$4^3$}
			child { node{$1^2$} 
				child[missing]
				child { node{$2^2$}
					child[missing]
					child { node{$3^1$} }
				}
			}
			child[missing]
			child { node{$5^1$} };
		\end{tikzpicture}\;,\;
		\begin{tikzpicture}[tinybst, baseline=-6mm]
			\node{$2^2$}
			child { node{$1^2$} }
			child { node{$4^3$}
				child { node{$3^1$} }
				child { node{$5^1$} }
			};
		\end{tikzpicture}\right)
		\quad\text{and}\quad
		\left(\begin{tikzpicture}[microbst,baseline=-8mm]
			\node{$1,4,7$}
			child { node{$3,8$} 
				child[missing]
				child { node{$5,9$}
					child[missing]
					child { node{$6$} }
				}
			}
			child[missing]
			child { node{$2$} };
		\end{tikzpicture}\;,\;
		\begin{tikzpicture}[microbst, baseline=-6mm]
			\node{$5,9$}
			child { node{$3,8$} }
			child { node{$1,4,7$}
				child { node{$6$} }
				child { node{$2$} }
			};
		\end{tikzpicture}\right)
	\end{equation*}
\end{example}

\begin{proposition} \label{MtgClassesPsymbolCorr}
	Let $\uord,\vord \in \bbN^*$. Then $\uord \equiv_{\mtg} \vord$ if and only if $\pmtg{\uord} = \pmtg{\vord}$.
\end{proposition}

Let $T_L,T_R$ be BTMs, with the same number of nodes. We say $(T_L,T_R)$ is a \emph{pair of twin binary trees with multiplicities} (pair of twin BTMs), if for all $i$,
\begin{enumerate}[label={(\roman*)}]
	\item the $i$-th node of $T_L$ and the $i$-th node of $T_R$ have the same multiplicities;
	\item if the $i$-th node of $T_L$ has multiplicity 1 and has a left (resp. right) child then the $i$-th node of $T_R$ does not have a left (resp. right) child.
\end{enumerate}
Notice that condition (ii) is equivalent to saying that if $r_i$ has multiplicity 1 then if $r_i$ has a left (resp. right) child then $l_i$ does not have a left (resp. right) child.

Let $T_L,T_R$ be BSTMs. We say $(T_L,T_R)$ is a \emph{pair of twin binary search trees with multiplicities} (pair of twin BSTMs) if $\cont{T_R} = \cont{T_L}$ and the shape of $(T_L,T_R)$ is a pair of twin BTMs. The $\psymb$-symbol given in \Cref{example:meet_taiga_p_and_q_symbols} is a pair of twin BSTMs. In fact, we have the following:

\begin{proposition} \label{prop:pmtg_pair_twin}
	The $\psymb_{\mtg}$-symbol $(\pltg{\word},\prtg{\word})$ of $\word$ is a pair of twin BSTMs, for any $\word \in \bbN^*$.
\end{proposition}

Let $(S_L,S_R)$ be a pair of (respectively) increasing and decreasing binary trees over sets, with the same number of nodes. We say $(S_L,S_R)$ are a \emph{pair of twin binary trees over sets} (pair of twin BTSs) if, for all $i$,
\begin{enumerate}[label={(\roman*)}]
	\item the $i$-th node of $S_L$ has the same label as the $i$-th node of $S_R$;
	\item if the $i$-th node of $S_L$ is labelled by a set of cardinality 1 and has a left (resp. right) child, then the $i$-th node of $S_R$ does not have a left (resp. right) child.
\end{enumerate}

The $\qsymb$-symbol given in \Cref{example:meet_taiga_p_and_q_symbols} is a pair of twin BTSs. In fact, we have the following:

\begin{proposition} \label{prop:qmtg_pair_twin}
	The meet-taiga $\qsymb$-symbol $(\qltg{\word},\qrtg{\word})$ of $\word$ is a pair of twin BTSs, for any $\word \in \bbN^*$.
\end{proposition}

Now, we are able to state our analogue of the Robinson--Schensted correspondence for the meet-taiga case:

\begin{theorem}
	The map $\word \mapsto (\pmtg{\word}, \qmtg{\word})$ is a bijection between the elements of $\bbN^*$ and the set formed by the pairs $((T_L,T_R),(S_L,S_R))$ where
	\begin{enumerate}[label={(\roman*)}]
		\item $(T_L,T_R)$ is a pair of twin BSTMs;
		\item $(S_L,S_R)$ is a pair of twin BTSs such that the union of the sets labelling $S_L$, and therefore $S_R$, is the interval $\sqt{m}$, where $m$ is the sum of the multiplicities of $T_L$ (or $T_R$);
		\item $(T_L,T_R)$ and $(S_L,S_R)$ have the same underlying pair of binary trees shape;
		\item the multiplicity of the $i$-th node of $T_L$ (resp. $T_R$) is the cardinality of the set labelling the $i$-th node of $S_L$ (resp. $S_R$).
	\end{enumerate}
\end{theorem}

\subsection{Extraction algorithm} \label{subsection:Extraction_algorithm}

In the previous subsection, we have shown how to obtain a word from its meet-taiga $\psymb$ and $\qsymb$-symbols. We now show how to obtain (possibly several) words from $\psymb$-symbols alone, without requiring a $\qsymb$-symbol.

Algorithm \hyperref[ExtractMeetTaiga]{\textsf{EmTg}} takes a pair of twin BSTMs $(T_L,T_R)$ and outputs a word in the $\equiv_{\mtg}$-class corresponding to $(T_L,T_R)$. Notice that it is a non-deterministic algorithm, since there may be several choices for $a$ in steps 5 and 14.

\begin{algorithm}[ht] \label{ExtractMeetTaiga}
	\DontPrintSemicolon
	\KwIn{A pair of twin BSTMs $(T_L,T_R)$.}
	\KwOut{A word in the $\equiv_{\mtg}$-class corresponding to $(T_L,T_R)$.}
	\BlankLine
	let $\word := \varepsilon$ and $(U_L,U_R) := (T_L,T_R)$; \\
	\While{$(U_L,U_R) \neq (\perp,\perp)$}{
		\If{all leaves in $U_R$ share letters in their labels with nodes in $U_L$}
			{choose a letter $a$ that labels the root node of a tree in $U_L$, such that $a$ has multiplicity greater than $1$ or $a$ labels a leaf in $U_R$, and let $m_a$ be the multiplicity of $a$; \\
			\lIf{$m_a > 1$}{let $\word := \word a^{m_a-1}$;}
			\lElse{let $\word := \word a$ and remove the node labelled $a$ from $U_R$;}
			remove the node labelled $a$ from $U_L$;}
		\lElse{let $a$ be the letter that labels a leaf in $U_R$ such that $a$ does not label any node in $U_L$, let $\word := \word a$ and remove the node labelled $a$ from $U_R$;}
	}
	\Return the word $\word$.
	\caption{\textit{Extract Meet-Taiga} (\textsf{EmTg}).}
\end{algorithm}

\begin{proposition} \label{ExtractTwinToMtg}
	For any pair of twin BSTMs $(T_L, T_R)$ as input, Algorithm \hyperref[ExtractMeetTaiga]{\textup{\textsf{EmTg}}} computes a word belonging to the $\equiv_{\mtg}$-equivalence class encoded by $(T_L, T_R )$.
\end{proposition}

\begin{example}
	Applying \hyperref[ExtractMeetTaiga]{\textsf{EmTg}} to the meet-taiga $\psymb$-symbol of $451423412$ yields the word $445112342$:
	\begin{gather*}
		\phantom{\quad\rightarrow}
		\left(\begin{tikzpicture}[tinybst,baseline=-8mm]
			\node{$4^3$}
			child { node{$1^2$} 
				child[missing]
				child { node{$2^2$}
					child[missing]
					child { node{$3^1$} }
				}
			}
			child[missing]
			child { node{$5^1$} };
		\end{tikzpicture}\;,\;
		\begin{tikzpicture}[tinybst, baseline=-6mm]
			\node{$2^2$}
			child { node{$1^2$} }
			child { node{$4^3$}
				child { node{$3^1$} }
				child { node{$5^1$} }
			};
		\end{tikzpicture}\right)
		\quad\rightarrow\quad
		\left(\begin{tikzpicture}[tinybst,baseline=-8mm]
			\node[crossed]{$4^3$}
			child { node{$1^2$} 
				child[missing]
				child { node{$2^2$}
					child[missing]
					child { node{$3^1$} }
				}
			}
			child[missing]
			child { node{$5^1$} };
		\end{tikzpicture}\;,\;
		\begin{tikzpicture}[tinybst, baseline=-6mm]
			\node{$2^2$}
			child { node{$1^2$} }
			child { node{$4^3$}
				child { node{$3^1$} }
				child { node{$5^1$} }
			};
		\end{tikzpicture}\right)
		\quad\rightarrow\quad
		\left(\begin{tikzpicture}[tinybst,baseline=-8mm]
			\node[crossed]{$4^3$}
			child { node{$1^2$} 
				child[missing]
				child { node{$2^2$}
					child[missing]
					child { node{$3^1$} }
				}
			}
			child[missing]
			child { node[crossed]{$5^1$} };
		\end{tikzpicture}\;,\;
		\begin{tikzpicture}[tinybst, baseline=-6mm]
			\node{$2^2$}
			child { node{$1^2$} }
			child { node{$4^3$}
				child { node{$3^1$} }
				child { node[crossed]{$5^1$} }
			};
		\end{tikzpicture}\right)
		\quad\rightarrow\\
		\rightarrow\quad
		\left(\begin{tikzpicture}[tinybst,baseline=-8mm]
			\node[crossed]{$4^3$}
			child { node[crossed]{$1^2$} 
				child[missing]
				child { node{$2^2$}
					child[missing]
					child { node{$3^1$} }
				}
			}
			child[missing]
			child { node[crossed]{$5^1$} };
		\end{tikzpicture}\;,\;
		\begin{tikzpicture}[tinybst, baseline=-6mm]
			\node{$2^2$}
			child { node{$1^2$} }
			child { node{$4^3$}
				child { node{$3^1$} }
				child { node[crossed]{$5^1$} }
			};
		\end{tikzpicture}\right)
		\quad\rightarrow\quad
		\left(\begin{tikzpicture}[tinybst,baseline=-8mm]
			\node[crossed]{$4^3$}
			child { node[crossed]{$1^2$} 
				child[missing]
				child { node{$2^2$}
					child[missing]
					child { node{$3^1$} }
				}
			}
			child[missing]
			child { node[crossed]{$5^1$} };
		\end{tikzpicture}\;,\;
		\begin{tikzpicture}[tinybst, baseline=-6mm]
			\node{$2^2$}
			child { node[crossed]{$1^2$} }
			child { node{$4^3$}
				child { node{$3^1$} }
				child { node[crossed]{$5^1$} }
			};
		\end{tikzpicture}\right)
		\quad\rightarrow\quad
		\left(\begin{tikzpicture}[tinybst,baseline=-8mm]
			\node[crossed]{$4^3$}
			child { node[crossed]{$1^2$} 
				child[missing]
				child { node[crossed]{$2^2$}
					child[missing]
					child { node{$3^1$} }
				}
			}
			child[missing]
			child { node[crossed]{$5^1$} };
		\end{tikzpicture}\;,\;
		\begin{tikzpicture}[tinybst, baseline=-6mm]
			\node{$2^2$}
			child { node[crossed]{$1^2$} }
			child { node{$4^3$}
				child { node{$3^1$} }
				child { node[crossed]{$5^1$} }
			};
		\end{tikzpicture}\right)
		\quad\rightarrow\\
		\rightarrow\quad
		\left(\begin{tikzpicture}[tinybst,baseline=-8mm]
			\node[crossed]{$4^3$}
			child { node[crossed]{$1^2$} 
				child[missing]
				child { node[crossed]{$2^2$}
					child[missing]
					child { node[crossed]{$3^1$} }
				}
			}
			child[missing]
			child { node[crossed]{$5^1$} };
		\end{tikzpicture}\;,\;
		\begin{tikzpicture}[tinybst, baseline=-6mm]
			\node{$2^2$}
			child { node[crossed]{$1^2$} }
			child { node{$4^3$}
				child { node[crossed]{$3^1$} }
				child { node[crossed]{$5^1$} }
			};
		\end{tikzpicture}\right)
		\quad\rightarrow\quad
		\left(\begin{tikzpicture}[tinybst,baseline=-8mm]
			\node[crossed]{$4^3$}
			child { node[crossed]{$1^2$} 
				child[missing]
				child { node[crossed]{$2^2$}
					child[missing]
					child { node[crossed]{$3^1$} }
				}
			}
			child[missing]
			child { node[crossed]{$5^1$} };
		\end{tikzpicture}\;,\;
		\begin{tikzpicture}[tinybst, baseline=-6mm]
			\node{$2^2$}
			child { node[crossed]{$1^2$} }
			child { node[crossed]{$4^3$}
				child { node[crossed]{$3^1$} }
				child { node[crossed]{$5^1$} }
			};
		\end{tikzpicture}\right)
		\quad\rightarrow\quad
		\left(\begin{tikzpicture}[tinybst,baseline=-8mm]
			\node[crossed]{$4^3$}
			child { node[crossed]{$1^2$} 
				child[missing]
				child { node[crossed]{$2^2$}
					child[missing]
					child { node[crossed]{$3^1$} }
				}
			}
			child[missing]
			child { node[crossed]{$5^1$} };
		\end{tikzpicture}\;,\;
		\begin{tikzpicture}[tinybst, baseline=-6mm]
			\node[crossed]{$2^2$}
			child { node[crossed]{$1^2$} }
			child { node[crossed]{$4^3$}
				child { node[crossed]{$3^1$} }
				child { node[crossed]{$5^1$} }
			};
		\end{tikzpicture}\right)
		\phantom{\quad\rightarrow}
	\end{gather*}
	The sequence of words obtained in each step of the algorithm is $44$, $445$, $4451$, $44511$, $445112$, $4451123$, $44511234$ and lastly $445112342$. In this example, we chose to remove the node labelled $5$ before the node labelled $1$.
\end{example}

As a consequence of Propositions~\ref{MtgClassesPsymbolCorr}, \ref{prop:pmtg_pair_twin} and \ref{ExtractTwinToMtg}, we have the following:
\begin{corollary}
	For any $n,m \geq 0$, there is a bijection between the set of $\mtg$-equivalence classes of words of length $m$ over $\sqt{n}^*$ and pairs of twin BSTMs, labelled by letters from $\sqt{n}$ and whose sums of multiplicities is $m$.    
\end{corollary}

\subsection{Iterative insertion algorithm} \label{subsection:Iterative_insertion_algorithm}

We now introduce an iterative version of our insertion algorithm which allow us to compute a pair of twin BSTMs from a word, while reading it in only one direction. Thus, we can compute the product of two pairs of twin BSTMs by applying \hyperref[ExtractMeetTaiga]{\textsf{EmTg}} to the second pair and inserting the letters of the resulting word, from left to right, into the first pair.

Algorithm \hyperref[alg:TaigaRootInsertion]{\textsf{TgRI}} allows one to obtain a new BSTM from another one, with the root node labelled by the letter of our choice.

\begin{algorithm}[ht] \label{alg:TaigaRootInsertion}
	\DontPrintSemicolon
	\KwIn{A BSTM $T$, a letter $a \in \bbN$.}
	\KwOut{A BSTM $a \downarrow T$.}
	\BlankLine
	let $T_{<a}$ (resp. $T_{>a}$) be the tree of all nodes of $T$ labelled by letters $<a$ (resp. $>a$), such that a node $x$ is a descendant of a node $y$ in $T_{<a}$ (resp. $T_{>a}$) only if $x$ is a descendant of $y$ in $T$; \\
	let $a \downarrow T$ be the tree with root node labelled $a$ with multiplicity $\len{T}_a + 1$, with left subtree $T_{<a}$ and right subtree $T_{>a}$; \\
	\Return the resulting tree $a \downarrow T$.
	\caption{\textit{Taiga Root Insertion} (\textsf{TgRI}).}
\end{algorithm}

As before in Subsection~\ref{subsection:binary_trees_with_multiplicities_and_binary_search_trees_with_multiplicities}, using Algorithm \hyperref[alg:TaigaRootInsertion]{\textsf{TgRI}}, one can compute a unique BSTM from a word $\word$: starting from the empty tree, read $\word$ from left to right (resp. right to left) and insert its letters one-by-one into the tree. The resulting BSTM is denoted by $\plr_{\rtg}(\word)$ (resp. $\prl_{\ltg}(\word)$). The proof of \cite[Lemma~4.18]{giraudo_baxter} can be easily adapted to show the following:

\begin{lemma} \label{lemma:alternate_insertion_algorithm_taiga}
	Let $\word \in \bbN^*$. Then $\plr_{\rtg}(\word) = \prtg{\word}$ and $\prl_{\ltg}(\word) = \pltg{\word}$.
\end{lemma}

As such, we can compute the $\psymb$-symbol of a meet-taiga class by reading a word in only one direction and applying Algorithms \hyperref[alg:TaigaLeafInsertion]{\textsf{TgLI}} and \hyperref[alg:TaigaRootInsertion]{\textsf{TgRI}} at the same time:

\begin{corollary} \label{corollary:mtg_root_insertion}
	For any $\word \in \bbN^*$, we have that 
	\[
	\pmtg{\word} = \prts{\prl_{\ltg}(\word), \prtg{\word}} = \prts{\pltg{\word}, \plr_{\rtg}(\word)}.
	\]
\end{corollary}

We can now define the \emph{left-to-right iterative meet-taiga $\psymb$-symbol} of a word $\word$ as the pair $(\pltg{\word}, \plr_{\rtg}(\word))$, obtained by reading $\word$ from left to right and iteratively inserting its letters into $(\perp,\perp)$, using Algorithms \hyperref[alg:TaigaLeafInsertion]{\textsf{TgLI}} and \hyperref[alg:TaigaRootInsertion]{\textsf{TgRI}} for $\pltg{\word}$ and $\plr_{\rtg}(\word)$, respectively. Similarly, we define the \emph{left-to-right iterative meet-taiga $\qsymb$-symbol} of $\word$ as the pair $(\qltg{\word}, \qlr_{\rtg}(\word))$, of the same shape as $\pmtg{\word}$, where each node is labelled by the positions in $\word$ of the letter in its corresponding node in $\pmtg{\word}$. In other words, each node in $\qmtg{\word}$ is labelled by the steps in which its corresponding node in $\pmtg{\word}$ was created or had its multiplicity incremented, when applying the left-to-right iterative insertion algorithm.

The correctness of the iterative insertion algorithm follows from \Cref{corollary:mtg_root_insertion}. Thus, we obtain an insertion algorithm in line with the usual Robinson--Schensted correspondence algorithms. We can also define a right-to-left version of the iterative insertion algorithm. 

\section{Counting in the taiga monoids} \label{section:Counting_in_the_taiga_monoids}

We now obtain `hook-length'-like formulas for the sizes of classes of words under the various taiga congruences. We first give the result for the left-taiga case:

\begin{proposition}[{\cite[Proposition 5]{priez_binary_trees}}]
	Let $\word \in \bbN^*$. Let $\supp{\word} = \set{x_1 < \dots < x_k}$ and let $m_i$ be the sum of the multiplicities of the node labelled $x_i$ and its descendants in $\pltg{\word}$, for all $1 \leq i \leq k$. Then, there are
	\[ \frac{\len{\word}!}{\prod_{i=1}^k(\len{\word}_{x_i}-1)! \cdot m_i}\]
	words over $\bbN$ in the same $\equiv_{\ltg}$-class of $\word$.
\end{proposition}

By \Cref{prop:jtg_characterisation}, we can obtain the size of a $\equiv_{\jtg}$-class, by computing the size of specific $\equiv_{\hypo}$-classes, which are known to be efficiently computable \cite[Theorem~3]{cm_hypo_crystal}.

\begin{proposition}
	Let $\word \in \bbN^*$. Let $\supp{\word} = \set{x_1 < \dots < x_k}$ and $A_1,\dots, A_l$ be all the intervals of $\supp{\word}$ such that $A_j$ only contains simple letters and $A_j \cup \set{a}$ is not an interval, for any simple letter $a \notin A_j$. Let $h(\word\sqt{A_j})$ be the size of the hypoplactic class of $\word\sqt{A_j}$.
	Then, there are
	\[ \frac{\len{\word}!}{\prod_{i=1}^{k}\len{\word}_{x_i}!} \prod_{j=1}^{l} \frac{h(\word\sqt{A_j})}{\len{A_j}!}\]
	words over $\bbN$ in the same $\equiv_{\jtg}$-class of $\word$.
\end{proposition}

The formula for the meet-taiga case is recursive, given by an algorithm that counts linear extensions of specific posets. Due to the extensive notation required to write it, we omit it here. With it, we can compute the size of $\equiv_{\mtg}$-classes in $\mathcal{O}(n^{2k-2}(k!)^3)$ operations, where $n$ is the length of the words and $k$ is the size of their support.

For our last result, given a BSTM, we obtain bounds for how many distinct BSTMs form a pair of twin BSTMs with it. 

\begin{proposition}
	Let $T_L$ be a BSTM with $n$ nodes. Suppose there are $k$ simple nodes in $T_L$ that are not leaves. Let $R(T_L)$ denote the number of distinct BSTMs $T_R$ such that $(T_L,T_R)$ is a pair of twin BSTMs. Then, 
	\[ C_{n-k} \leq R(T_L) \leq C_n \]
	where $C_m = \frac{(2m)!}{(m+1)!m!}$ is the $m$-th Catalan number.
\end{proposition}

\acknowledgements{The authors would like to thank Alan Cain and António Malheiro for their suggestions and helpful comments.}

%% 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}
