\documentclass[finalversion]{FPSAC2025}
\articlenumber{42}
% \usepackage[utf8]{inputenc}
\usepackage{mathtools,amsfonts,amsthm,mathrsfs,amssymb,stmaryrd}
\usepackage[dvipsnames]{xcolor}
\usepackage{tikz}
\usepackage{standalone}
%\usepackage[justification=centering,belowskip=-15pt,aboveskip=0pt]{caption}
\usepackage{comment}

\newtheorem{thm}{Theorem}[section]
\newtheorem{lemma}[thm]{Lemma}
\newtheorem{corol}[thm]{Corollary}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{conj}[thm]{Conjecture}
\newtheorem{quest}[thm]{Question}
\newtheorem{defin}[thm]{Definition}
\newtheorem{rem}[thm]{Remark}
\newtheorem{example}[thm]{Example}

\renewcommand{\S}{\mathfrak{S}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\B}{\mathcal{B}}

\newcommand{\x}{r_{\sigma}}
\newcommand{\y}{l_{\tau}}
\newcommand{\move}{\rightarrow}
\newcommand{\orb}{\mathcal{O}}
\newcommand{\id}{{\text{id}}}
\newcommand{\desc}{\overline{\text{id}}}
\newcommand{\intval}[1]{\llbracket #1 \rrbracket}
\newcommand{\vsum}{\obar}
\newcommand{\hsum}{\ominus}
\newcommand{\dsum}{\obslash}
\newcommand{\usum}{\odot}
\newcommand{\filling}{\varphi}

\definecolor{colorx}{RGB}{136, 189, 30}
\definecolor{colory}{RGB}{212, 43, 11}
\definecolor{colorz}{RGB}{20, 65, 204}
\newcommand{\blue}[1]{\textcolor{colorz}{#1}}
\newcommand{\red}[1]{\textcolor{colory}{#1}}
\newcommand{\green}[1]{\textcolor{colorx}{#1}}

\newcommand{\ddincr}{(\blue{12}, \red{12})}
\newcommand{\pat}{(\blue{312}, \red{231})}
\newcommand{\sigtau}{(\blue{\sigma}, \red{\tau})}
\newcommand{\colpair}[2]{(\blue{#1}, \red{#2})}
\newcommand{\Hn}{(\blue{\desc_n}, \red{\id_n})}
\newcommand{\Vn}{(\blue{\id_n}, \red{\desc_n})}
\newcommand{\Dn}{(\blue{\desc_n}, \red{\desc_n})}
\newcommand{\A}{Av_n(\ddincr, \pat)}
\newcommand{\basis}{triangle basis}

%\newcommand{\todo}[1]{\textcolor{red}{#1}}
\newcommand{\note}[1]{\textcolor{blue}{#1}}

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

\newcommand{\orange}[1]{\textcolor{orange}{#1}}
\newcommand{\shorten}[1]{\orange{#1}}
% pour les phrases que tu peux éventuellement supprimer pour gagner de la place, en couleur orange. Remplacer \orange par \comment pour voir ce que ça te fait gagner comme place
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\everymath{\displaystyle}
%\geometry{top=3cm, bottom = 4cm, left = 3cm, right = 3cm}


\title{3D permutations and triangle solitaire}
\author{\texorpdfstring{Juliette Schabanel\thanks{\href{mailto:juliette.schabanel@u-bordeaux.fr}{juliette.schabanel@u-bordeaux.fr}}\addressmark{1}}{Juliette Schabanel}}
\address{\addressmark{1}LaBRI, Université de Bordeaux}

\received{November 15th 2024}


\abstract{We provide a bijection between a class of $3$-dimensional pattern avoiding permutations
%a generalization of permutations which can be identified to diagrams in $\llbracket1,n\rrbracket^3$ with exactly one point per plane $x_i = j$ for $i \in \{1,2,3\}$ and $j\in \llbracket1,n\rrbracket$. 
and triangle bases, special sets of integer points arising from the theory of TEP subshifts. This answers a conjecture of Bonichon and Morel.
%\todoJ{ref à conjecture ?}
%\todoblin{faire un peu plus percutant: ne pas parler des diagramme, juste "a class of 3-dimensional permutations avoiding certain patterns", glisser le mot subshifts, et oui dire que ça répond à une conjecture}
}

%\resume{\todo{Resume}}

\keywords{$d$-permutations, tilings, bijection, patterns in permutation, subshifts}

\usepackage[backend=bibtex, giveninits]{biblatex}
\addbibresource{PermutBasis}

\begin{document}

\maketitle

%\tableofcontents

\section{Introduction}

%A permutation $\sigma = \sigma(1)\sigma(2) \ldots \sigma(n) \in \S_n$ is a bijection from $\intval{1, n} = \{1, 2, \ldots n\}$ to itself. The ($2$-dimensional) diagram of $\sigma$ is simply the set of points $P_\sigma := \{(1, \sigma(1)), (2, \sigma(2)), \ldots, (n,\sigma(n))\}$. The diagrams of permutations of size n are exactly the point sets such that each row and column of $\intval{1,n}^2$ contains exactly one point.

%In this paper, we are interested in $d$-dimensional diagrams : sets of points $P_{\pmb{\sigma}}$ such that every hyperplane $x_i = j$ with $i\in \intval{1,d}$ and $j \in\intval{1,n}$ contains exactly one point. Such diagrams are equivalently describes by tuples of $d-1$ permutations $\pmb{\sigma} = (\sigma_1, \ldots, \sigma_{d-1})$ such that $P_{\pmb{\sigma}} = \{(i, \sigma_1(i), \sigma_2(i), \ldots, \sigma_{d-1}(i)) \mid \i \in \intval{1,n}\}$. 

In this paper, we build a bijection between objects that are seemingly unrelated: a class of pattern avoiding $3$-dimensional permutations and objects arising from the theory of subshifts called triangle bases, that was conjectured by Bonichon and Morel in \cite{BoMo22}.

Permutations are a central object in combinatorics and their study has received a lot of attention. One topic of particular interest is pattern avoidance in permutations, which led to numerous enumerative and bijective results with various objects (see \cite{Kit11, Bona} and references therein).


One can see a permutation $\sigma$ as a ($2$-dimensional) diagram with points $(i, \sigma(i))$, which satisfies the property that in each row and column lies a unique point. With this definition comes a natural generalization to higher dimensions by defining a $d$-dimensional diagram, and the notion of pattern avoidance extends naturally~\cite{AsMa10, BoMo22, PermutMach}.

%Bonichon and Morel initiated the study of small patterns for $3$-permutations in \cite{BoMo22} and conjectured several bijections for different classes. In this paper, we prove their conjecture for the set of patterns $\{\ddincr, \pat\}$. 

The second object arises from the theory of \emph{tilings and symbolic dynamics}. A tiling is a coloring of the grid $\Z^2$ with allowed subpatterns determined by a rule set $\mathcal{R}$. %It is valid with respect to a set of rules $\mathcal{R}$ of shape $S \subset \Z^2$ if all its $S$-shaped subpattens are in $\mathcal{R}$. 
The set of tilings respecting a certain rule set is called a \emph{subshift} \cite{Ho16}. Tilings have been widely studied during the last decades and many questions, such as the \emph{tiling problem}, %\shorten{which asks whether $\Z^2$ can be colored in a way that avoid a finite collection of local forbidden patterns,} 
were proved undecidable \cite{Ber66}. However, for some classes with strong structure or combinatorial properties, such as cellular automata, some problems become decidable and a deeper study can be carried \cite{Kari05}. The class we consider in this paper, named TEP for \emph{totally extremally permutive}, was introduced by Salo in \cite{Sa22} and generalizes bipermutive cellular automata. %\shorten{by asking that if all but one cell of a subpattern of a given shape are filled, there is a unique valid way to complete it}.
The language of any TEP subshift is decidable, and they possess bases, i.e. sets of cells whose content can be chosen freely and determine the values of a larger set. Our object of interest are the bases of triangles for the \emph{Ledrappier subshift}.%\shorten{, which uses the shape $S = \{(0,0), (1,0), (0,1)\}$}. %Indeed, those basis are in finite number, easily recognizable and their number coincide with the number of $3$-permutations avoiding $\ddincr$ and $\pat$. %In this paper, we provide a bijective explanation to this.


In \cite{BoMo22}, Bonichon and Morel considered $3$-permutations avoiding small patterns and enumerated the first terms of these classes. It turned out that several of those sequences matched existing sequences in the OEIS\footnote{such as $Av(\ddincr)$ matching the number of intervals of the weak Bruhat order, for which they were able to provide a bijection}. In particular,  the sets of triangle bases of size $n$ and $\A$ have the same cardinalities up to $n=8$, and they conjectured that these two sets are in bijection.
Our main result is to prove their conjecture:

\begin{thm}
    There is an explicit bijection between $3$-permutations of size $n$ avoiding patterns $\ddincr$ and $\pat$ and triangle bases of size $n$.
\end{thm}

This bijection makes a link between objects from two previously independent classes which are hard to enumerate, and it allows to transport structure properties and methods from one class to the other, such as a random sampling method relying on a Markov chain. In addition to that, the construction is quite simple and could be applied to other classes of pattern avoiding $d$-permutations (even for $d>3$).%, maybe leading to new bijections.

Precise definitions are given \Cref{sec:defs} and the construction is explained \Cref{sec:bijection}. This bijection is quite simple in its construction and brings keys to understand better those two objects. In the process of the proof, we also provide a description of $Av_n(\ddincr, \pat)$ through sums analogous to the one of separable permutations but with a shift. In \Cref{sec:solitaire}, we describe a dynamical system on bases, the \emph{solitaire}, which translates to permutations though the bijection and allows uniform sampling. 


\section{Definitions and Setting}
\label{sec:defs}

\subsection{3-Permutations avoiding a pattern}
\label{sec:permut}

%\subsubsection{Permutations avoiding a pattern}

A permutation $\sigma = \sigma(1)\sigma(2) \ldots \sigma(n) \in \S_n$ is a bijection from $\intval{1, n} = \{1, 2, \ldots n\}$ to itself. %We denote by $\S_n$ their set. 
The (2 dimensional) \emph{diagram} of a permutation $\sigma \in \S_n$ is the set of points $P_\sigma := \{(1, \sigma(1)), \ldots, (n,\sigma(n))\}$. The diagrams of permutations of size $n$ are exactly the point sets such that each row and column of $\intval{1,n}^2$ contains exactly one point.

A permutation $\sigma$ \emph{contains} a \emph{pattern} $\pi \in \S_k$ if there is a set of indices $i_1 < i_2 < \ldots < i_k$ such that $\sigma(i_1)\sigma(i_2)\ldots\sigma(i_k) = \pi$ (once standardized). Otherwise, we say that $\sigma$ \emph{avoids} $\pi$. Given a set of patterns $\pi_1, \ldots, \pi_k$, we denote by $Av_n(\pi_1, \ldots, \pi_k)$ the set of permutations of size $n$ avoiding all the $\pi_i$s. 


\begin{figure}[ht]
    \centering
    \includegraphics[page=1, height=2cm]{Figures/Fig_permut.pdf}
    \caption{The permutation $\sigma = 324615$ with an occurrence of the pattern $231$ in red.}
    \label{fig:permut ex}
\end{figure}

%\subsubsection{Higher dimension permutations}

\begin{defin}
    A \emph{$d$-permutation} (or \emph{$d$-dimensional permutation}) of size $n$, is a tuple $\pmb{\sigma} = (\sigma_1, \ldots, \sigma_{d-1})$ of $d-1$ permutations of size $n$ . We denote by $\S_n^{d-1}$ their set. %$d$ is called the dimension of the permutation. 
    The \emph{diagram} of a $d$-permutation is the set of points $P_{\pmb{\sigma}} \coloneqq \{(i, \sigma_1(i), \ldots, \sigma_{d-1}(i)) \mid 1 \leqslant i \leqslant n\}\in\Z^d$. %Notice that $d$ is the dimension of the diagram.
    %$d$ is the dimension of the diagram and by extension of the permutation
\end{defin}

The diagrams of $d$-permutations of size $n$ are exactly the point sets such that every hyperplane $x_i = j$ with $i \in \intval{1, d}$ and $j \in \intval{1, n}$ contains exactly one point. Examples are given in \Cref{fig:forb pattern}.

%One can observe that $2$-permutation correspond to ``classical'' permutations. 

%Let $P \coloneqq \{p_1,\ldots,p_n\}$ be a set of points in $\Z^d$ such that every hyperplane $x_i = k$ with $k \in \Z$ contains at most one point of $P$. The \emph{standardization} of $P$ is the set $P' = \{p_1', \ldots, p_n'\}$ in $\intval{1,n}^{d-1}$ such that the relative order with respect to each axis is the same. Hence the standardization of a subset of points of a diagram is the diagram of a (smaller) $d$-permutation (with the same dimension).



%In what follows, we assimilate a $d$-permutation and its diagram. A transformation on one can be directly translated into one the other. For instance, removing a point of a permutation, means removing one point of its diagram and considering the permutation of the standardization of the sub-diagram.

%\subsubsection{Pattern avoidance in $d$-permutations}

The definition of pattern avoidance extends naturally to $d$-permutations as follows. Let $\pmb{\pi} \in \S_k^{d-1}$ be a pattern, a $d$-permutation $\pmb{\sigma} \in \S_n^{d-1}$ \emph{contains} $\pmb{\pi}$ if there is a set of indices $I \subset \intval{1, n}$ such that $\pmb{\sigma}_{|I} = \pmb{\pi}$ (once standardized), otherwise it \emph{avoids} it. 
%\shorten{$I$ is then called an \emph{occurrence} of $\pmb{\pi}$}. 
%A $d$-permutation \emph{avoids} a pattern if it does not contain it and
Given a set of $d$-patterns $\pmb{\pi}_1, \ldots, \pmb{\pi_k}$ we denote by $Av_n(\pmb{\pi}_1, \ldots, \pmb{\pi}_k)$ the set of $d$-permutations of size $n$ that avoid all the $\pmb{\pi}_i$. 

In what follows, we focus on $3$-permutations avoiding two particular patterns : \\ $(\blue{12}, \red{12})$ and $(\blue{312}, \red{231})$ which are depicted \Cref{fig:forb pattern}.

\begin{figure}[ht]
    \centering
    \includegraphics[page=2, height=3cm]{Figures/Fig_permut.pdf}
    \quad
    \includegraphics[page=3, height=3cm]{Figures/Fig_permut.pdf}
    \quad \quad
    \includegraphics[page=4, height=3.5cm]{Figures/Fig_permut.pdf}
    \caption{Left : The two forbidden patterns : $\ddincr$ (left) and $\pat$ (right). \\ Right : a $3$-permutation, $\colpair{54231}{32514}$, with an occurrence of $\pat$ in orange} 
    \label{fig:forb pattern}
\end{figure}

\begin{rem}
    Note that a $3$-permutation avoiding a $3$-pattern is not the same as a couple of permutations each avoiding a pattern as we require the occurrence to be on the same indices. For example $\colpair{312}{231}$ avoids $\ddincr$ although both $312$ and $231$ contain $12$.
\end{rem}


\subsection{Tilings, configurations and bases}
\label{sec:basis}

Our other class of objects, \emph{triangle bases}, arises from the study of tilings which we will now introduce.

\subsubsection{Tilings}

Let $A$ be a set of symbols and $S$ be a finite subset of $\Z^2$. Let $\mathcal{R}$ be a subset of $A^S$. A \emph{tiling} with \emph{tile set} $A$ and \emph{allowed patterns} $\mathcal{R}$ is a coloring $c : \Z^2 \to A$ of the grid $\Z^2$ with symbols of $A$ such that for each translation $S'$ of $S$, $c_{|S'} \in \mathcal{R}$. In other words, we require that wherever one looks at the coloring through an $S$-shaped window, what one sees is in $\mathcal{R}$. The elements of $S^A \setminus \mathcal{R}$ are called the \emph{forbidden patterns} and the set of valid tilings for $\mathcal{R}$ the \emph{subshift} (of finite type) with rule set $\mathcal{R}$.

\begin{figure}[ht]
    \centering
    \includegraphics[page=1, height=2cm]{Figures/Fig_basis.pdf}
    \caption{An example of a tiling. Left: the rule set $\mathcal{R}$. Middle: a valid tiling. \\Right: an invalid tiling with a forbidden pattern highlighted.}
    \label{fig:tiling ex}
\end{figure}

%\begin{prop}
%    Any translation of a tiling is also a tiling.
%\end{prop}

In what follows, we consider a special kind of subshifts, called \emph{TEP subshifts} (where TEP stands for Totally Extremally Permutive), which were introduced in \cite{Sa22}. A subshift is TEP if for all $x \in S$, for each partial coloring $c : S\setminus \{x\} \to A$, there is a unique $a \in A$ such that the extension of $c$ with $c(x) = a$ is in $\mathcal{R}$. In other words, if one fills all cells of $S$ but one with arbitrary symbols of $A$, there is a unique way to complete it so that this does not create a forbidden pattern. An example ,the XOR automaton tiling, is given \Cref{fig:XOR rule}. In what follows, we only consider TEP subshifts with $S = \{(0,0), (1,0), (0,1)\}$.

%\begin{example}
%    Take $A = \{0,1\}$, $S = \{(0,0), (1,0), (0,1)\}$ and $\mathcal{R} = \{(0,0,0), (0, 1, 1), (1,0,1),$ $ (1,1,0)\}$ the XOR rule (written as $(c((0,0)),c((1,0)),c((1,0)))$). One can check that this tiling rule is TEP and the valid tilings are exactly the space-time diagrams of the XOR automaton. Adding or removing a pattern from $\mathcal{R}$ breaks the TEP property.%\shorten{ : by adding one we loose the uniqueness of the completion and by deleting one we lose the property that all partial coloring can be completed}.
\begin{figure}[ht]
    \centering
    \includegraphics[page=2, height = 2cm]{Figures/Fig_basis.pdf}
    \caption{Left: The tiling rules of the XOR automaton. Right: An example of a valid tiling. Adding or removing a pattern from $\mathcal{R}$ breaks the TEP property.}
    \label{fig:XOR rule}
\end{figure}
%\end{example}

\begin{comment}
\begin{example}
    \Cref{fig:not TEP} gives an example of a rule set that is not TEP. Indeed, there are two valid ways to complete a triangle with two orange tile at the bottom and none to complete one with pink and blue at the bottom.
\begin{figure}[ht]
    \centering
    \includegraphics[page=3, height = 2cm]{Figures/Fig_basis.pdf}
    \caption{A tiling rule that is not TEP.}
    \label{fig:not TEP}
\end{figure}
\end{example}
\end{comment}


\subsubsection{Filling}

When confronted to a TEP subshift, one natural question to ask is ``given a set of cells $P$ whose content are known, what other values can be deduced ?''. The following definition aims at formalizing this notion. 

%We call a \emph{sample} of size $n$ a set of $n$ points in $\Z^2$.

\begin{defin}
   Let $P\subset \Z^2$ be a set of cells. Performing a \emph{filling step} of $P$ consists in choosing a position $(x,y)$ such that $|P \cap \{(x,y), (x+1,y), (x,y+1)\}| = 2$ and adding the missing point to $P$. This process is confluent and converges to a limit set denoted $\filling(P)$ called the \emph{filling} of $P$.
\end{defin}

Intuitively, if we know the values of a tiling on $P$, then a filling step consists in using the tiling rules to deduce the value of a new cell and adding it to the known set. The filling of $P$ is then the set of values which can always be deduced from $P$.

\begin{figure}[ht]
    \centering
    \includegraphics[page=4, width=0.85\textwidth]{Figures/Fig_basis.pdf}
    \caption{An example of application of the filing process. Dark cells are the original set, colored ones are added by the current step and light cells were filled earlier.}
    \label{fig:filling}
\end{figure}

\begin{comment}
A \emph{triangle} with size $k \in \N$ is a set $T = \{(x, y) \mid a \leqslant x \wedge b \leqslant y \wedge x+y \leqslant k\}$ for some $a, b \in \Z$. 

The neighborhood of a point $(x,y)\in \Z^2$ is the set $\{(x, y+1), (x, y-1), (x+1, y), (x-1, y), (x-1, y+1), (x+1, y-1)\}$. It corresponds to the set of points with which a filling step involving $(x,y)$ can be performed. The neighborhood of a set $X \subset \Z^2$ is then the union of the neighborhood of its points. Two subsets $X$ and $Y$ of $\Z^2$ touch if one intersects the neighborhood of the other.


\begin{thm}[\cite{SaSc23}]
    For all sample $P$, $\varphi(P)$ is a union of disjoint triangle which size sum to at most $|P|$.
\end{thm}
\end{comment}


\subsubsection{Independence and Bases}

The other natural question is ``given a set of cells $P$, can any choice of symbols for $P$ be extended into a valid tiling of $\Z^2$ ?''. When it is the case, we say that $P$ is \emph{independent}. 

Denote $T_n = \{(x,y) \mid x,y \in \N, x+y < n\}$ the triangle of size $n$. A set of cells $P$ is a \emph{basis} (of $T_n$) if for any partial coloring $c : P \to A$, by iteratively deducing value using the TEP rules of $\mathcal{R}$ we always end up with a valid coloring of $T_n$ (i.e. all of $T_n$ is determined by $P$ and there is no conflict). We denote by $\mathcal{B}_n$ the set of bases of $T_n$. We call \emph{configuration} of size $n$ a set of $n$ points $C \subset T_n$, those are the candidates for bases.

\begin{thm}[\cite{SaSc23}]
    A configuration of size $n$ is a triangle basis if and only if its filling is $T_n$.
\end{thm}

\begin{figure}[ht]
    \centering
    \includegraphics[page=6, height = 1.8cm]{Figures/Fig_basis.pdf}
    \caption{Configurations of size $5$ (dark cells) with their filling (light cells). \\Left : A basis of $T_5$. Middle : A non independent pattern. Right : A non filling pattern.}
    \label{fig:basis}
\end{figure}

The idea is that $n$ is the minimal amount of information needed to fill $T_n$, and if there is a conflict then one point is redundant and there is not enough left to fill all of $T_n$. 

The number of triangle bases for $n$ up to $8$ were computed in \cite{Sa22} and are the following: $1$, $3$, $16$, $122$, $1188$, $13844$, $185448$, $2781348$, $\ldots$ %which is the same as the numbers of $3$-permutations avoiding $\ddincr$ and $\pat$ computed by Bonichon and Morel. They conjecture the existence of a bijection between those two sets which we will prove in the next section.

%In the rest of the paper, we give a bijective explanation of this.


\section{The bijection}
\label{sec:bijection}

In this section, we define a function that send $3$-permutations to configurations and prove that it is a bijection between $\A$ and the set of triangle bases of size $n$. This function relies on the inversion sequence of the permutations, which we will now define.

\subsection{Inversions}

Let $\sigma \in \S_n$ be a permutation. For $i \in \intval{1,n}$,  we denote by $r_\sigma(i)$ (resp. $l_\sigma(i)$) the number of $i < j \leqslant n$ (resp. $1 \leqslant j <i$) such that $\sigma(i)>\sigma(j)$ (resp. $\sigma(i)<\sigma(j)$). These are called the number of right (resp. left) \emph{inversions} of $\sigma$ at $i$ and the sequence $(r_\sigma(i))_{1 \leqslant i \leqslant n}$ (resp. $(l_\sigma(i))_{1 \leqslant i \leqslant n}$) the right (resp. left) \emph{inversion sequence} of sigma.

Looking at the diagram of $\sigma$, for each $i$ $r_\sigma(i)$ is the number of points to the bottom right of $(i, \sigma(i))$ and $l_\sigma(i)$ the number of points to the top left of it (see \Cref{fig:inv num}). We denote respectively by $R_\sigma(i)$ and $L_\sigma(i)$ those sets of points. 

\begin{figure}[ht]
    \centering
    \includegraphics[page=1, height = 2.5cm]{Figures/Fig_Gamma.pdf}
    \caption{The set $R_\sigma(i)$ (resp. $L_\tau(i)$) is the points in the blue (resp. orange) area.}
    \label{fig:inv num}
\end{figure}

\begin{prop}
    The mapings $\sigma \mapsto (r_\sigma(i))_{1 \leqslant i \leqslant n}$ and $\sigma \mapsto (l_\sigma(i))_{1 \leqslant i \leqslant n}$ are bijective.
    %The knowledge of $\sigma$ is equivalent to the knowledge of one of its inversion sequence.
\end{prop}
\begin{comment}
\begin{proof}
    Observe that $\sigma(1) = r_\sigma(1) + 1$ and is $\sigma'$ is the permutation obtained after deleting $1$, then $r_{\sigma'} (i) = r_\sigma(i+1)$ for all $1 \leqslant i < n$. This allows to recover all of $\sigma$ by inserting point in decreasing order.
\end{proof}
\end{comment}

\subsection{The function \texorpdfstring{$\Gamma$}{Gamma}}

Let $\Gamma$ be the function that maps a $3$-permutation $\sigtau \in \S_n^2$ to the configuration composed of the points $(r_\sigma(i), l_\tau(i))$ for $1 \leqslant i \leqslant n$. When there is no ambiguity, we write $x_i = \x(i)$, $y_i = \y(i)$ and denote $p_i$ the point $(x_i, y_i) \in \Gamma\sigtau$. 

\begin{example}
    Let us consider the $3$-permutation (\blue{254361}, \red{624315}). Its inversion sequences are (\blue{132110}, \red{011241}) and its image through $\Gamma$ is depicted \Cref{fig:Gamma ex}.
\end{example}

\begin{figure}[ht]
    \centering
    \includegraphics[page=2, height = 2.2cm]{Figures/Fig_Gamma.pdf}
    \caption{The diagram of the $3$-permutation (\blue{254361}, \red{624315}) and its image through $\Gamma$.}
    \label{fig:Gamma ex}
\end{figure}

\begin{prop}
    For all $\sigtau \in Av_n(\ddincr)$, $\Gamma\sigtau$ is a configuration of size $n$.
\end{prop}
\begin{proof}
    If $\sigtau \in \S_n^2$ avoids $\ddincr$ then for all $i<j$, either $\sigma(i) > \sigma(j)$ and $\x(i) > \x(j)$ or $\tau(i) > \tau(j)$ and $\y(i) < \y(j)$, hence all $p_i$'s are distinct.
\end{proof}

\begin{rem}
    $\Gamma$ in fact sends $3$-permutations to \emph{labeled} configuration (by labeling point with the integer used to compute its coordinates). Observe that if points are labeled, we can recover the inversion sequences and so the permutations. However, our triangle bases are not labeled so we have to forget this labeling and find a way to recover it. Still, the label variant might be useful for some generalizations (see \Cref{sec:discu}).
\end{rem}

% \shorten{\begin{rem}
%     Observe that $\Gamma$ carries some symmetries of both objects : rotating the diagram of $\sigtau$ around the axis $x+y+z$ (i.e. $\sigtau \mapsto (\red{\tau^{-1}}, \green{\sigma \circ \tau^{-1}})$) rotates the image by 120° and if $\desc = n(n-1) \ldots 21$ then applying $\sigtau \mapsto (\red{\desc \circ \tau \circ \desc}, \blue{\desc \circ \sigma \circ \desc})$ exchanges the axis abscissa and ordinates.
% \end{rem}}

In the rest of this section, we will prove that when $\sigtau \in \A$, $\Gamma\sigtau$ is a triangle basis. Intuitively, avoiding $\ddincr$ ensures that the points are ``not too close'' and avoiding $\pat$ that they are ``not too far''. In the two following subsections we formalize these notions and prove that this is true.

\begin{figure}[ht]
    \centering
    \includegraphics[page=3, height = 1.7cm]{Figures/Fig_Gamma.pdf}
    \caption{The positions forbidden by the patterns $\ddincr$ (left) and $\pat$ (right).}
    \label{fig:pat inv}
\end{figure}


\begin{comment}
\begin{conj}
    Let $(\sigma, \tau)$ and $(\sigma', \tau')$ be two pairs of permutation leading to the same configuration, then one of them has $(12,12)$ as a pattern.
\end{conj}
$\implies$ False : $(4132, 2431)$ and $(4213, 3241)$ have the same image (both have a $(312, 231)$). 
\end{comment}


\subsection{Sparsity}

For integers $a, b$ and $k$, we denote by $(a,b) + T_k$ the triangle $\{(x, y) \mid a \leqslant x, b \leqslant y \text{ and } x + y < a+b+k\}$.  A configuration $C$ is \emph{sparse} if for all $1 \leqslant k < n$, there is no triangle $T = (a,b) + T_k$ such that $|C \cap T| > k$.

\begin{prop}[\cite{SaSc23}]
    All independent sets (and so all bases) are sparse.
    %All configurations in $\B_n$ are sparse.
\end{prop}

Intuitively, if a configuration is not sparse then we have too much information in one area and it creates a default of independence.% and therefore not enough to cover all of $T_n$.

\begin{thm}
    If $\sigtau \in \S_n^2$ avoids $\ddincr$ then $\Gamma\sigtau$ is sparse.
\end{thm}

We omit the proof of this theorem as it is not needed to prove that $\Gamma$ is a bijection. Nonetheless, this theorem helps to understand the consequences of avoiding $\ddincr$ on the image through $\Gamma$ and can be useful for potential generalizations of this function to some other classes (see \Cref{sec:discu}).
%\todoblin{Une phrase pour dire que on omet la preuve, ça n'intervient pas dans la preuve du main thm, mais ça permet de comprendre les objets et peut-être de généraliser cf section 5}
\begin{comment}
\begin{proof}
    Let $\sigtau \in Av_n(\ddincr)$. Assume that there is a triangle $T = (a,b)+T_k \subset T_n$ of size $k$ such that $|\Gamma\sigtau \cap T|>k$. Denote $I \subset \intval{1, n}$ the set of indices such that $p_i \in T$. Notice that for all $i \in I$, since $p_i \in T$, $a \leqslant x_i < a+k$, $b \leqslant x_i < b+k$ and $x_i + y_i <k+a+b$.
    
    Let $m \in I$ be the point where $\sigma_{|I}$ reaches its maximum. Then for all $i \in I$, either $i > m$ and $i \in R_\sigma(m)$ or $i<m$ and $i \in L_\tau(m)$, so $(R_\sigma(m) \cup L_\tau(m)) \cap I = I\setminus\{m\}$. If $m \neq \max I$ and $m \neq \min I$, then there are points $i, j \in I$ with $i < m < j$, so $x_m + y_m = |R_\sigma(m)| + |L_\tau(m)| \geqslant |R_\sigma(m) \cup L_\tau(m)| \geqslant |I|-1 + |R_\sigma(j)| + |L_\tau(i)| \geqslant k+a+b$, thus $p_m \notin T$. Now if $m = \max I$, then $R_\sigma(m) \cap I = \varnothing$ and $L_\tau(m)$ contains $I \setminus\{m\}$ as well as all $L_\tau(i)$ for $i \in I$, so $y_m \geqslant b+k$ and $m \notin T$. Symmetrically, if $m = \min I$ then $x_m \geqslant a+k$.
\end{proof}
\end{comment}

\subsection{Cuts and shifted sums}

%We now define the notion of ``the points are too far from each others''.
To prove that $\Gamma$ is a bijection, we will give a recursive definition of triangle bases, define an analogous decomposition for $3$-permutations avoiding $\ddincr$ and $\pat$ and prove that $\Gamma$ transports these decompositions.

\begin{defin}
Let $C_1$ and $C_2$ be two configurations and $h \in \intval{0, |C_1|}$. The $h$-vertically \emph{shifted sum} of $C_1$ and $C_2$ is $C_1 \vsum_h C_2 = ((|C_2|, 0) + C_1) \cup ((0, h)+C_2)$. It is a configuration of size $|C_1| + |C_2|$. Similarly, we define the $h$-horizontally \emph{shifted sum} by $C_1 \hsum_h C_2 = ((0,|C_2|)+ C_1) \cup ((h, 0)+C_2)$ and the $h$-diagonally \emph{shifted sum} by $C_1 \dsum_h C_2 =C_1 \cup ((|C_1|-h,h)+ C_2)$.

If $C$ is a configuration, a couple of subconfigurations of $C$, $(C_1, C_2)$, is a vertical (resp. horizontal, resp. diagonal) \emph{cut} of $C$ if $C$ is a vertical (resp. horizontal, resp. diagonal) shifted-sum of $C_1$ and $C_2$. Its position is the coordinate of the line separating $C_1$ and $C_2$.
\end{defin}

%A \emph{cut} of a configuration is a couple $(T\cap C, T'\cap C)$ with $T$ and $T'$ two disjoints triangles such that $C$ intersects both and is contained in their union. The cut is \emph{vertical} (resp. \emph{horizontal}, resp \emph{diagonal}) if the two subconfigurations are separated by a vertical (resp. \emph{horizontal}, resp \emph{diagonal}) line.   

\begin{figure}[ht!]
    \centering
    \includegraphics[page=4, width=0.8\textwidth]{Figures/Fig_Gamma.pdf}
    \caption{Shifted sums of configurations and $3$-permutations. Left : Vertical sum. Middle : Horizontal. Right : Diagonal. Parameters $k$ and $h$ are preserved through $\Gamma$.}
    \label{fig:shifted sums}
\end{figure}


\begin{prop}
    A configuration is a triangle basis if and only if it is either a single point or a shifted sum of two triangle bases. %sparse and can be recursively cut into triangles consisting of single points.
\end{prop}
\begin{proof}
    If $C = B_1 \usum B_2$, then each $B_i$ fills a triangle of its size and those triangles touch, so $C$ fills the smallest triangle containing them, which has size $|C|$. So $C$ is also a basis.
\end{proof}

\noindent
We now define the shifted sums on $3$-permutations and show that $\Gamma$ transports the cuts. 

\begin{defin}
Let $\colpair{\sigma_1}{\tau_1} \in \S_{k_1}^2$ and $\colpair{\sigma_2}{\tau_2} \in \S_{k_2}^2$ be two $3$-permutations and $h \in \intval{0,k_1}$. Their $h$-shifted sums are defined as the $3$-permutations $\sigtau$ of size $k_1+k_2$ obtained by inserting the diagram $\colpair{\sigma_2}{\tau_2}$ into the one of $\colpair{\sigma_1}{\tau_1}$ as described in \Cref{fig:shifted sums}. 
%\begin{itemize}
    %\item Vertical sum : put $\colpair{\sigma_2}{\tau_2}$ at indices $I = \intval{k_1+1, k_2}$ with $\sigma(I) = \intval{1,k_2}$ and $\tau(I) = {k_1+1-h, k_1+k_2-h}$.% for $\sigma$ put $\sigma_1$ in the top left sector and $\sigma_2$ in the bottom right, for $\tau$ put $\tau_2$ at height $k_1-h$, possible separating $\tau_1$ in two.
    %\item Horizontal sum : put $\colpair{\sigma_2}{\tau_2}$ so that is occupies the block $\intval{1,k_2}\times\intval{h+1, h+k_2}\times\intval{k_1+1,k_1+k_2}$.  %put $\colpair{\sigma_2}{\tau_2}$ at indices $I = \intval{1, k_2}$ with $\sigma(I) = \intval{1,k_2}$ and $\tau_2(I) = {k_1+1-h, k_1+k_2-h}$. %for $\tau$ put $\tau_1$ in the bottom right sector and $\tau_2$ in the top left, for $\sigma$ put $\sigma_2$ at height $h$.
    %\item Diagonal sum : put $\colpair{\sigma_2}{\tau_2}$ at the indices $\intval{h+1, h+k_2}$, with $\sigma_2$ above $\sigma_1$ and $\tau_2$ under $\tau_1$.
%\end{itemize}
%Theses sums are illustrated \Cref{fig:shifted sums}. 
As for configuration, we say that a $3$-permutation admits a cut if it is a shifted sum of two $3$-permutations. We denote by $\usum$ a shifted sum of unknown direction and shift.
\end{defin}

\begin{lemma}
    Let $\sigtau \in Av_n(\ddincr)$. It  admits a cut $\sigtau=\colpair{\sigma_1}{\tau_1} \usum \colpair{\sigma_2}{\tau_2}$ in a given direction, at a position $k$ with shift $h$ if and only $\Gamma\sigtau$ does. In that case, $\Gamma(\colpair{\sigma_1}{\tau_1} \usum \colpair{\sigma_2}{\tau_2}) = \Gamma\colpair{\sigma_1}{\tau_1} \usum \Gamma\colpair{\sigma_2}{\tau_2}$.
\end{lemma} 
\begin{proof}
    Let $\sigtau \in Av_n(\ddincr)$. We only consider the vertical cut case $\sigtau = \colpair{\sigma_1}{\tau_1}$ $\vsum_h \colpair{\sigma_2}{\tau_2}$, the others can be obtained with similar arguments. Denote $k$ the size of $\colpair{\sigma_1}{\tau_1}$, for all $i \in \intval{1,k}$ $R_\sigma(i) = R_{\sigma_1}(i) \cup \intval{k+1, n}$ and $L_\tau(i) = L_{\tau_1}(i)$ so the first $k$ points of $\Gamma\sigtau$ are $\Gamma\colpair{\sigma_1}{\tau_1}+(n-k, 0)$. And for all $i \in \intval{k+1, n}$, $R_\sigma(i) = R_{\sigma_2}(i)$ and $L_\tau(i) = L_{\tau_1}(i) + h$ so the last $n-k$ points of $\Gamma\sigtau$ are $\Gamma\colpair{\sigma_2}{\tau_2}+(0, h)$. This is exactly $\Gamma(\colpair{\sigma_1}{\tau_1} \vsum_h \colpair{\sigma_2}{\tau_2}) = \Gamma\colpair{\sigma_1}{\tau_1} \usum \Gamma\colpair{\sigma_2}{\tau_2}$.

    Reciprocally, assume that $\Gamma\sigtau = C_1 \vsum_h C_2$. All points in $C_1$ have abscissa at least $n-k$, so they must be $\intval{1, k}$ since for all $i$, $x_i < n-i$. We first need to prove that for all $i\in \intval{1,k}$, $\intval{k+1, n}\subset R_\sigma(i)$. Equality holds for $i=k$, and then for the others by induction: for $i \leqslant k$, either there is a $j >i$ such that $j \in R_\sigma(i)$ and so $\intval{k+1, n} \subset R_\sigma(j) \subset R_\sigma(i)$ or there is none and $R_\sigma(i) = \intval{k+1, n}$. Now consider the points $M$ and $m$ where $\tau$ reaches respectively it maximum and minimum on $\intval{k+1, n}$, $\y(M) = h$ so there must be exactly $h$ points in $\intval{1,k}$ above $(M, \tau(M))$. Now for $m$, all integers greater than $k$ contribute to either $x_m$ or $y_m$ since $\sigtau$ avoids $\ddincr$ and $L_\tau(M) \subset L_\tau(m)$ since $L_\tau \subset \intval{1,k}$ and $\tau(m) \leqslant \tau(M)$. So $x_m + y_m = n-k-1 + |L_\tau(m) \cap \intval{1,k}| \geqslant n-k-1+h$ but $x_m+y_m <n-k+h$ so equality must hold, which means $L_\tau(m) \cap \intval{1,k} = L_\tau(M)$. So $\sigtau$ admits a vertical cut at index $k$ with shift $h$.
\end{proof}

    %The horizontal case is obtained symmetrically so lets assume the cut is diagonal. Such a cut separates $\intval{1,n}$ in $3$ parts, $\intval{1, h}$, $\intval{h+1, h+k}$ and $\intval{h+k+1, n}$, $\sigma_2$ applying in the middle and $\sigma_1$ on the sides. If $i \notin \intval{h+1, h+k}$, then $R_\sigma(i) = R_{\sigma_1}(i)$ and $L_\tau(i) = L_{\tau_1}(i)$ so the image of these points is exactly $\Gamma\colpair{\sigma_1}{\tau_1}$. If $i \in \intval{h+1, h+k}$ then $R_\sigma(i) = R_{\sigma_2}(i) \cup \intval{h+k+1, n}$ and $L_\tau(i) = L_{\tau_2}(i) \cup \intval{1, h}$ so the image of these points through $\Gamma$ is $\Gamma\colpair{\sigma_2}{\tau_2} + (n-k-h, h)$.

    %Reciprocally, assume $\Gamma \sigtau = C_1 \dsum_h C_2$. Denote $I$ the set of labels of points in $C_1$ and $k = |C_1|$. Let $i \in \intval{1,n}$, if $\tau(i) \leqslant k$, then for all $j$ such that $\tau(j) > k$, either $j < i$ and $j \in L_\tau(i)$ or $j > i$ and so $\sigma(j) < \sigma(i)$ and $j \in R_\sigma(i)$, so $x_i + y_i \geqslant n-k$ so $i \in I$. Symmetrically, if $\sigma(i) > n-k$ then $i \in I$. This forces $I = \tau^{-1}(\intval{1,k}) = \sigma^{-1}(\intval{n-k+1,n})$. Let $m = \min I$, $\y(m) > h$ and $L_\tau(m) \cap I = \varnothing$ so $m > h$. Now consider $M = \max I$, $R_\sigma(M) \cap I = \varnothing$ and $\x(M) \geqslant n-k-h$ so $M \leqslant k+h$. This forces $I = \intval{h+1, h+k}$.
    

\begin{comment}
\begin{lemma}
    Let $\sigtau$ in $\A$. If $\Gamma\sigtau$ admits a cut $(C_1, C_2)$, then denoting $I = \{i\mid p_i \in C_1\}$ and $J = \{i\mid p_i \in C_2\}$, $\Gamma\colpair{\sigma_{|I}}{\tau_{|I}}$ is a translate of $C_1$ and $\Gamma\colpair{\sigma_{|J}}{\tau_{|J}}$ is one of $C_2$. 
\end{lemma}
\begin{proof}
    To prove this, we need to prove that if $C_1$ is contained in a triangle translated by $(a,b)$ then for all $i \in I$, $|R_\sigma(i) \cap J| = a$ and $|L_\tau(i) \cap J|=b$, and the symmetric condition on $C_2$.

    Lets first assume that $\Gamma\sigtau$ admits a vertical cut $(C_r, C_l)$ with $C_r$ the right part and $C_l$ the left and denote $k = |C_r|$. Notice that $C_r$ is then the set of points with abscissa at least $n-k$.  Since for all $i \in \intval{1, n}$ $x_i < n-i$, we must have $C_r = \{p_i \mid i \leqslant k\}$. Then, by induction, $\intval{k+1, n} \subset R_\sigma(i)$ for all $i \leqslant k$: equality holds for $i=k$ as otherwise $x_k < n-k$, and then either $j \in R_\sigma(i)$ for some $j < i$ and $\intval{k+1, n} \subset R_\sigma(j) \subset R_\sigma(i)$ or $R_\sigma(i)$ contains no point between $i+1$ and $k$ and it must contains contain $\intval{k+1, n}$.

    Now lets look at $\tau$. Let $h$ be the minimum ordinate in $C_l$, it is reached by the integer $M$ that maximizes $\tau_{|>k}$. Let $m$ be the index where $\tau_{|>k}$ is minimal. All other integers greater than $k$ contribute to either $y_m$ or $x_m$ since $\sigtau$ avoids $(12,12)$, and $L_\tau(M) \subset L_\tau(m)$ since $L_\tau(M) \subset I$ and $\tau(m) < \tau(M)$ if $m \neq M$. Therefore, $x_m + y_m \geqslant h + n-k-1$ with equality if and only if $L_\tau(m) \cap I = L_\tau(M)$. $C_l$ is contained in a triangle of size $n-k$ touching the vertical axe, which implies that for all points in it $x + y < h + n-k$, so equality must hold. 

    The horizontal cut case is obtained symmetrically, so lets assume that the cut is diagonal. Let $k = |C_1|$, without loss of generality, $C_1 \subset T_k$ and there are $(a, b)$ with $a+b = k$ such that $C_2 \subset T_{n-k}+(a,b) = \{(x,y) \mid a \leqslant x, b\leqslant y \text{ and } x+y < n\}$. Let $i \in \intval{1,n}$, all $j \in \intval{1,n}$ with $\sigma(j) < \sigma(i)$ are either in $R_\sigma(i)$ (when $j >i)$ or $L_\tau(i)$ (when $j <i$), and symmetrically all $j$ with $\tau(j) > \tau(i)$ are either in $L_\tau(i)$ (when $j <i)$ or $R_\sigma(i)$ (when $j <i$). This implies that if $\sigma(i) > n-k$ or $\tau(i) \leqslant k$ then $\x(i) + \y(i) \geqslant n-k$, so $\sigma^{-1}(\intval{n-k+1, n}) \cup \tau^{-1}(\intval{1,k}) \subset J$ and since $|J| = n-k$, $\sigma^{-1}(\intval{n-k+1, n}) = \tau^{-1}(\intval{1,k}) = J$. Let $M = \max J$ and $m = \min J$, by construction $R_\sigma(M) = \{i > M \mid i \in I\} = \{i > M\}$ so $x_M = n-M \geqslant a$ and $L_\tau(m) = \{i < m\}$ so $y_m = m-1 \leqslant b$. Since $|I| = a+b$, this means that $I = \intval{1, b} \cup \intval{n-a-1, n}$ and $J = \intval{b+1, n-a}$, which gives the required property. 
\end{proof}

This lemma allows to decompose permutations to prove recursively that their image through $\Gamma$ is a basis. All that remains to prove is that all couples of permutations of $\A$ admit a cut, with the following definition of cuts :
\begin{itemize}
    \item $\sigtau$ admits a vertical cut at position $k$ with shift $h$ if $\sigma(\intval{1, k}) = \intval{n-k+1, k}$ and $\tau(\intval{k+1, n}) = \intval{h+1, h+n-k})$.
    \item $\sigtau$ admits a horizontal cut at position $k$ with shift $h$ if $\tau(\intval{1, k}) = \intval{n-k+1, k}$ and $\sigma(\intval{1, k}) = \intval{h+1, h+k})$.
    \item $\sigtau$ admits a diagonal cut at height $k$ with shift $h$ if $\tau^{-1}(\intval{1,k}) = \sigma^{-1}(\intval{n-k+1, n}) = \intval{h+1, h+k}$.
\end{itemize}
\end{comment}

All that remains to prove now is that when $\sigtau$ avoids $\ddincr$ and $\pat$, it admits a cut. An induction will then give that $\Gamma(\A) = \B_n$. %\shorten{Intuitively, forbidding $\pat$ ensures a cut by avoiding triplets of points that form large triangles (which can block cuts because then no shifted triangle can contain all points).}

%Intuitively, forbidding $\pat$ ensures a cut by forbidding triplets of points to form larges triangles (i.e. triplets $i<j<k$ with $x_i >> x_j \equiv x_k$ and $y_i \equiv y_j << y_k$) which can block cuts because then no shifted triangle can contain all points.
%\todoblin{pas au bon endroit et pas très clair}

\begin{lemma}
    For all $n \geqslant 2$, if $\sigtau \in \A$ then $\sigtau$ admits a cut.
\end{lemma}
\begin{proof}
    We proceed by induction. One can easily check that all permutations of $\S_n^2$ avoiding $\ddincr$ admit a cut (even two).

    Let $n>2$ and $\sigtau \in \A$. Observe that if $n$ is an extrema for either $\sigma$ or $\tau$, then isolating $n$ is a valid cut : if $\sigma(n) = 1$ (resp $\tau(n)=1$), there is a vertical (resp. horizontal) cut and if $\sigma(n) = n$ (resp $\tau(n)=n$) then $\tau(n) = 1$ (resp $\sigma(n) =1$). 

    Now assume $n$ is not an extrema. For $1 \leqslant i \leqslant n$, denote by $\colpair{\sigma_i}{\tau_i}$ the $3$-permutation obtained by deleting $n$. By induction hypothesis, it admits a shifted cut. We denote by $k_i$ its position and $h_i$ its shift. To simplify, we do not standardize $\colpair{\sigma_i}{\tau_i}$. Consider the cut of $\colpair{\sigma_n}{\tau_n}$ and assume that $n$ is not compatible with the cut, otherwise we are done, and that the cut is vertical (the other directions can be treated similarly). 

    %\begin{enumerate}
        %\item \textbf{$\colpair{\sigma_n}{\tau_n}$ admits a vertical cut.} 
        If $n$ is in the bottom right sector of $\sigma$, then it must be under the right block of $\tau$ (or there would be a $\ddincr$), but then one can take $i \leqslant k_n$ such that $\tau(n) < \tau(i) < h_n$ and $j$ such that $\sigma(j) < \sigma(n)$ which is an occurrence of $\pat$. Now assume $n$ is in the top right sector of $\sigma$, $n$ must still be under the right block of $\tau$. Let $m = \sigma^{-1}(1) \neq n$ and consider the cut of $\colpair{\sigma_m}{\tau_m}$.
        \begin{enumerate}
            \item \textbf{$\colpair{\sigma_m}{\tau_m}$ admits a vertical cut.} Then $n$ must be in the bottom right sector of $\sigma$ so $k_m < k_n$ and so the right block of $\tau$ in this cut must contain the one of the first cut, thus $m$ is compatible with the cut.

            \item \textbf{$\colpair{\sigma_m}{\tau_m}$ admits a horizontal cut.} Then since $h_n = 0$ (or we would have $\tau(n) = 1$) $k_m<k_n$ or there would be empty planes, so all the right block of $\tau_n$ must be in the bottom right sector of $\tau_m$ and therefore $m$ is compatible with the cut.

            \item \textbf{$\colpair{\sigma_m}{\tau_m}$ admits a diagonal cut.} Denote $I$ its middle interval. It is impossible to have $n \in I$ because that would require an empty column in $\sigma$. This means that $I \subset \intval{1, k_n}$ and so $m$ is compatible with this cut.\qedhere
        \end{enumerate} 
\end{proof}
\begin{comment}
        \item \textbf{$\colpair{\sigma_n}{\tau_n}$ admits a horizontal cut.} If $n$ is not in the bottom right sector of $\tau$, then the bottom block of $\sigma$ must be empty (or there would be a $\ddincr$ since $\sigma(n) \neq 1$) and $n$ cannot be in the top block of $\sigma$, so $\sigtau$ admits a diagonal cut with $\{n\}$ as the right block. Now assume $n$ is in the sector and consider the cut of $\colpair{\sigma_m}{\tau_m}$ where $m = \tau^{-1}(1) \neq n$. 
        \begin{enumerate}
            \item \textbf{$\colpair{\sigma_m}{\tau_m}$ admits a vertical cut.} Then either $h_n = n-k_n$ or $k_m > k_n$ or there would be empty lines. $h_n = n-k_n$ is a vertical cut so we can assume $k_m > k_n$ and in fact $k_m > n-h_n$, but then $n$ should be in an empty area of $\sigma$.  

            \item \textbf{$\colpair{\sigma_m}{\tau_m}$ admits a horizontal cut.} Then $k_m < k_n$ or $n$ would still be between the blocks, so $m$ is compatible with this cut.

            \item \textbf{$\colpair{\sigma_m}{\tau_m}$ admits a diagonal cut.} Denote $I$ its middle interval and assume that $m \neq \sigma^{-1}(n) = M$ or we would have a diagonal cut for $\sigtau$. If $I$ is not included in $\intval{k_n+1, n-1}$ then the other inclusion holds and the cut is compatible with $m$. Otherwise, consider the cut of $\colpair{\sigma_M}{\tau_M}$. Observe that the argument for the vertical and horizontal cases still hold for $M$ and if both have diagonal cut then the cut with the largest middle interval is compatible with its missing point.
        \end{enumerate}

        \item \textbf{$\colpair{\sigma_n}{\tau_n}$ admits a diagonal cut.} Denote by $I$ its middle interval. If the right block of the cut is empty, then this is also a horizontal cut so we go back to the previous case. If $n$ is in the right block in $\tau$, then it must also be inside in $\sigma$ so $n$ is compatible with the cut. %If $n$ is not in the right block of $\sigma$, then if $i \in I$ and $\sigma(i) > \sigma(n)$, then $\tau(i) < \tau(n)$ or they would be a $\pat$ with any point in the right block. So $\{i \mid \sigma(i) > \sigma(n)\} = \{i \mid \tau(i) < \tau(n)\} \subset I$. 

        \begin{enumerate}
            \item \textbf{$\colpair{\sigma_m}{\tau_m}$ admits a vertical cut.} Then $I$ must be contained in the top left sector of $\sigma$ or there would be an empty line, so $m$ is compatible with the cut.
        
            \item \textbf{$\colpair{\sigma_i}{\tau_i}$ admits a horizontal cut.} Then $I$ must be contained in the bottom right sector or $\tau$ and so $m$ is compatible with the cut.

            \item \textbf{$\colpair{\sigma_i}{\tau_i}$ admits a diagonal cut.} Denote $J$ its interval. If $n \in J$ then $I \subset J$ and the cut is compatible with $m$. Otherwise, consider the cut for $M = \sigma^{-1}(n)$. For the vertical and horizontal cases, the same arguments as for $m$ hold and if the cut is diagonal, the one of the two with the largest interval is compatible with its missing point.
        \end{enumerate}
\end{comment}
    %\end{enumerate}

\begin{comment}
\begin{proof}
    We proceed by induction. One can easily check that all permutations of $\S_n^2$ avoiding $\ddincr$ admit a cut (even two).

    Let $n >2$ and $\sigtau \in \A$. First, observe that is either $1$ or $n$ is an extrema for either $\sigma$ or $\tau$, then $\sigtau$ admit a cut where one side is this single point. Indeed, if $\sigma(1) = n$ (resp. $\tau(1) = n$, then there is a vertical (resp. horizontal) cut at $1$, and if $\sigma(1) = 1$ (resp. $\tau(1) = 1$) then since $\sigtau$ avoids $\ddincr$, $\tau(1) = n$ (resp. $\sigma(1) = n$). A similar statement hold for $n$ by symmetry. 

    Now assume neither $1$ nor $n$ is an extrema, and consider $\colpair{\sigma_+}{\tau_+}$ and $\colpair{\sigma_-}{\tau_-}$ the $3$-permutations obtained by deleting respectively $1$ and $n$. Both still avoid $\ddincr$ and $\pat$ and have size $n-1$, so by induction hypothesis each admits a cut. The addition of a point is compatible with a cut if it does not fall in an empty area. If $(1, \sigma(1), \tau(1))$ (resp.$(n, \sigma(n), \tau(n))$) is compatible with the cut of $\colpair{\sigma_+}{\tau_+}$ (resp. $\colpair{\sigma_-}{\tau_-}$) we are done. We now assume this is not the case and distiguinsh several cases depending of the direction of the two cuts. 

    Figure~?? explains which insertions are allowed for $1$ and $n$ depending on the nature of the other cut. We detail here the case  where $\colpair{\sigma_-}{\tau_-}$ admits a horizontal cut at $k$ with shift $h$. Green squares are when inserting $n$ is compatible with the cut. If $\tau(n) > n-k$ (orange cross or blue square), then for all $i>k$, $\sigma(i) > \sigma(n)$ or they would be an occurrence of $\ddincr$ (orange crosses). This imposes $h = n-k$ and $\sigma(n) >n-k$. Else, we have $\tau(n) \leqslant n-k$ and must have $\sigma(n) > \sigma(1)$, because otherwise there is a point $i \leqslant k$ such that $\sigma(i) < \sigma(n)$ (or $n$ would be compatible with the cut), and this points creates an occurrence of $\pat$. 

    Lets now see what happens depending on the direction of cuts.
    \begin{enumerate}
        \item \textbf{$\colpair{\sigma_+}{\tau_+}$ admits a diagonal cut.} Denote $J$ the corresponding middle interval.
        \begin{enumerate}
            \item \textbf{$\colpair{\sigma_-}{\tau_-}$ admits a horizontal cut.} Denote $k$ its position and $h$ its shift. We must have $h < n-k$ or the cuts are incompatible, then $J \subset \sigma^{-1}(\intval{h+k, n})$ so $1$ is compatible with the diagonal cut.
            
            \item \textbf{$\colpair{\sigma_-}{\tau_-}$ also admits a diagonal cut.} Denote $I$ the middle interval of the cut. For none of the extremal point to be compatible with the other's cut, exactly one must be in the middle interval (if none is, one interval is included in the other and defines a cut for $\sigtau$ ; if both are then $1$ or $n$ must be an extrema or they would be no possible values for $(\sigma(2), \tau(2))$ or $(\sigma(n-1), \tau(n-1))$). Assume $1 \in I$, then $J \subset I$. Let $j \in J$, if $\tau(j) < \tau(1)$ then $\sigma(j) > \sigma(1)$ or there would be a $\pat$ with any point in $I \setminus J$ so $\{j \in J \mid \sigma(j) > \sigma(1)\} = \{j \in J \mid \tau(j) < \tau(1)\}$ and this gives a diagonal cut for $\sigtau$ \todo{bah non}. The case $n \in J$ can be handled symmetrically.
            
            \item \textbf{$\colpair{\sigma_-}{\tau_-}$ admits a vertical cut.} Denote $k$ the position of the vertical cut and $J$ the middle interval of the diagonal cut. $J \subset \intval{2,k}$ otherwise no choice of $\sigma(k+1)$ is possible and $n \notin J$ or no point can have $1$ as an image for $\sigma$. Then for the same reason as above $\{j \in J \mid \sigma(j) > \sigma(1)\} = \{j \in J \mid \tau(j) < \tau(1)\}$ and $\sigtau$ admits a diagonal cut at height $\tau(1)-1$.
        \end{enumerate}

        
        \item \textbf{$\colpair{\sigma_+}{\tau_+}$ admits a horizontal cut.} Denote $k_+$ its position and $h_+$ its shift.
        \begin{enumerate}
            \item {$\colpair{\sigma_-}{\tau_-}$ admits a diagonal cut.} Denote $I$ its interval. We must have $I \subset \sigma(\intval{1,n-h-k})$. If $i\in I$, $\tau(i) < \tau(k) \implies \sigma(i) > \sigma(k)$ (no $\ddincr$) and  $\sigma(i) > \sigma(n) \implies \tau(i) < \tau(k)$ (no $\pat$), this gives a diagonal cut of $\sigtau$.
            
            \item {$\colpair{\sigma_-}{\tau_-}$ admits a vertical cut.} Denote $k_-$ its position and $h_-$ its shift. If $k_+ > k_-$, then $h_-=0$ or $1$ cannot have a preimage through $\tau$ and $h_+ = n-k_+$ or $n$ cannot have a preimage through $\sigma$, then both cut work for $\sigtau$. 
            If $k_->k_+$, then $h_+ > n-k_-$ and $h_- < n-k_+$. Let $I = \{i \in \intval{2,n-1} \mid \tau(i) < \tau(n)\}$, $I$ is none empty and contained in $\intval{k_+, k_-}$. Since $\sigtau$ avoids $\ddincr$, for all $i \in I$, $\sigma(i) > \sigma(n)$, and for all $j$ such that $\sigma(j) > \sigma(n)$, $\tau(j) < \tau(n)$ or they would form $\pat$ with all points in $\intval{k_-+1, n-1}$ (which is non empty). Similarly, $J = \{i \in \intval{2,n-1} \mid \sigma(i) > \sigma(1)\} = \{i \in \intval{2,n-1} \mid \tau(i) < \tau(1)\}$ and one included in the other. Consider the points $M$ and $m$ where respectively $\sigma$ reaches its maximum and $\tau$ its minimum. If $M=m$ then this gives a diagonal cut and if $m < M$, they form a $\ddincr$, so $M<m$. If $\intval{M, m}$ is empty then it is a diagonal cut, if it contains a point $i \notin I\cap J$ then this forms a $\pat$. Let $i \in I\cap J$, \todo{Not done}
            
            \item {$\colpair{\sigma_-}{\tau_-}$ admits a horizontal cut.} Denote $k_-$ its position and $h_-$ its shift. If $k_- < k_+$, any of the cut works for $\sigtau$. Otherwise, $h_- \leqslant h_+ \leqslant h_- + k_+-k_-$ or they would be an empty line.
            If $\tau(n) > n-k_-$ then $h_- = 0$ and there is a diagonal cut at height $k_-$ (with right part = $\{n\}$. Now assume $\tau(n)\leqlant n-k_-$, 
            
            
            As observed earlier, for all $i \lesqlant k_+$, $\sigma(1) > \sigma(i)$ and if $\tau(n) \leqlant n-k_-$, then $\sigma(n) > \sigma(1)$ or they would be a $\pat$. Assume $\tau(n)\leqlant n-k_-$ and let $k_+ < i <k_-$ be such that $\sigma(i) > \sigma(n)$, such $i$ exits or $n$ would be compatible with the cut. Assume there is a $j>i$ such that $\sigma(1) > \sigma(j)$, 

            \todo{not done}
            
            %Let $i, j \in \intval{k_++1, k_-}$ such that $\sigma(i) > \sigma(n)$ and $\tau(j) > \tau(1)$, they exist or one cut would work for $\sigtau$. Then $\sigma(j) < \sigma(1) < \sigma(n)$ and $\sigma(i) > \sigma(n)$ so $\tau(i) <  \tau(n)$, which means $i>j$ or they would form a $\pat$ with $n$. 
            
            %Let $2 \leqslant i \leqslant k_+$ and $k_+< j \leqslant k_-$ such that $\sigma(j) < \sigma(1)$, such $j$ exist otherwise $1$ would be compatible with the cut. 
        \end{enumerate}

        
        \item  \textbf{$\colpair{\sigma_+}{\tau_+}$ admits a vertical cut.} Denote $k_+$ its position and $h_+$ its shift.
        \begin{enumerate}
            \item {$\colpair{\sigma_-}{\tau_-}$ admits a diagonal cut.} Denote $I$ its interval. If $I\setminus\{1\} \subset \tau^{-1}(\intval{2,k})$ then $n$ is compatible with this cut. Otherwise, the other inclusion should holds but that creates a contradiction. 
            
            \item {$\colpair{\sigma_-}{\tau_-}$ admits a vertical cut.} Denote $k_-$ its position and $h_-$ its shift. If $k_- < k_+$ then the both cuts work for $\sigtau$. Else, if $\sigma(1) <n-k_+$ then $h_+ = 0$ and there is a diagonal cut (with left part = $\{1\}$). Now assume $k_+<k_-$ and $\sigma(1) > n-k_+$. If  $\sigma(1) < h_-$,  
            
            % observe that for all $i>k_-$, $\tau(i) > \tau(n)$

            \todo{not done}
            
            \item {$\colpair{\sigma_-}{\tau_-}$ admits a horizontal cut.} Denote $k_-$ its position and $h_-$ its shift. By symmetry of the case 2.b), $k_+ < k_+$. If $\sigma(1) < n-k_+$ or $\tau(n) > n-k_-$, then there is a diagonal cut. Otherwise both points are compatible with the other's cut.
        \end{enumerate}
    \end{enumerate}


    If both cuts are diagonal, denote respectively $I$ and $J$ their middle interval. If $1 \notin I$ and $n \notin J$, one is included in the other and gives a diagonal cut of $\sigtau$. If $1 \in I$ and $n \in J$, then either $I = \{1\}$ or $J = \{n\}$ so $1$ or $n$ is an extrema. If $1 \in I$ and $n \notin J$ then $I = \intval{1,k}$ and we can assume $J \subset I$. Then, if $\sigma(n) < n-k$ and $\tau(n) > k$, the cut with $I$ extends to $\sigtau$ and if $\sigma(1) \notin \sigma_+(J)$ and $\tau(1) \notin \tau_+(J)$ the cut with $J$ extends to $\sigtau$. If $\sigma(1) \in \sigma_+(J)$, then we also have $\tau(1) \in \tau_+(J)$ or there would be a $\ddincr$, and $\{j \in J \mid \sigma(j) > \sigma(1)\} = \{j \in J \mid \tau(j) < \tau(1)\}$ as a $j$ in one but not the other creates a occurrence of $\pat$. So $\sigtau$ has a diagonal cut above $\sigma(1)$. The last case, $1 \notin I$ and $n \in J$ can be handled symmetrically.
\end{proof}
\end{comment}

Combining the two previous lemmas, we get the following :

\begin{thm}
    A $3$-permutation avoiding $\ddincr$ and $\pat$ is either $(\blue{1},\red{1})$ or a shifted sum of two permutations in $Av(\ddincr, \pat)$.
\end{thm}

\begin{corol}
    For all $\sigtau \in \A$, $\Gamma\sigtau$ is a triangle basis.
\end{corol}
\begin{proof}
    This is true for $n = 1$. If $n \geqslant 2$, then $\sigtau$ admits a cut. By induction, the image of each side of the cut is a basis and so $\Gamma\sigtau$ is a shifted sum of two bases, so a basis.
\end{proof}

\begin{thm}
    For $n \geqslant 1$, $\Gamma$ is a bijection between $Av_n(\ddincr, \pat)$ and bases of size $n$.
\end{thm}
\begin{proof}
    The decomposition with shifted sums allows to inverse $\Gamma$ as when a basis $B$ is the sum of two others, we know exactly which labels should appear in which subconfiguration, so we can recover all labels this way. A pre-image of $B$ by $\Gamma$ can then be reconstruct from the inversion sequences. 

    As for injectivity, although the decomposition is not unique, we can choose a canonical cut, for instance prioritize vertical over horizontal over diagonal and minimize the size of $C_1$. Since a $3$-permutation and its image throught $\Gamma$ admit exactly the same cuts, this ensures that no two $3$-permutations give the same basis which different labels. 
\end{proof}

\section{Solitaire}
\label{sec:solitaire}
%\todoblin{Here we introduce the solitaire blabla. It has good properties that can be helpful for random generation purposes, or to extend our bijection to other pattern avoiding classes, see XXX. Quelque chose comme ça, en fusionnant avec la phrase du dessous. }

In this section, we introduce a dynamical system on configurations called the \emph{triangle solitaire} (defined in~\cite{Sa22}) and we extend it to $3$-permutations. This dynamical system presents nice properties that makes it useful for random generation purposes, or to extend our bijection to other pattern avoiding classes.

%The solitaire is a dynmical system on subsets of $\Z^2$ introduced by Salo in \cite{Sa22} for which the basis are exactly the orbit of the line $\llbracket0,n-1\rrbracket \times \{0\}$ \cite{SaSc23}. 

%\subsection{Solitaire on the grid}

%Let $P$ be a set of points, i.e. a subset of $\Z^2$, and $(x,y) \in \Z^2$. A solitaire move at $(x,y)$ allows, if $|P \cap \{(x,y), (x+1, y), (x, y+1)\}|=2$, to replace one of those two points by the missing one. Intuitively, seeing $\Z^2$ as a playing grid and $P$ as marbles of this grid, a solitaire move allows to move a marble inside a triangle if another marble (a "pivot") is in this triangle.

\begin{defin}
    Let $P$ and $Q$ be sets of points. There is a \emph{solitaire move} from $P$ to $Q$, denoted $P \move Q$, if there is a position $(x,y) \in \Z^2$ such that their symmetric difference $P \Delta Q$ is a subset of size $2$ of $\{(x,y), (x+1, y), (x, y+1)\}$.
    %$$|P \cap \{(x,y), (x+1, y), (x, y+1)\}|=|Q \cap \{(x,y), (x+1, y), (x, y+1)\}|=2.$$ 
    If $P$ is a configuration, its \emph{orbit}, denoted $\orb(P)$ is the set of configurations reachable from it using solitaire moves.
\end{defin}
%\todoblin{Rajouter la condition que $P$ et $Q$ ne diffèrent qu'à un seul endroit.}

Intuitively, seeing $\Z^2$ as a playing grid and $P$ and $Q$ as marbles on this grid, when two marbles are adjacent a solitaire move allows to move one using the other as a ``pivot''. %a solitaire move allows to move a marble inside a triangle if another marble, a "pivot", is in this triangle.

\begin{thm}[\cite{SaSc23}]
    For $n \geqslant 1$, the orbit of the line $\intval{0,n-1} \times \{0\}$ 
    is exactly the bases $\B_n$. %the triangle bases of size $n$.
\end{thm}


%A configuration $C$ is \emph{labeled} if its points have distinct labels ranging from $1$ to $n = |C|$. In this case, we denote $p_i = (x_i, y_i)$ the point with label $i$. $C$ is \emph{well labeled} if for all $i \in \intval{1, n}$ $x_i \leqslant n-i$, $y_i < i$ and for all $j > i$ either $x_i > x_j$ or $y_i < y_j$. Observe that with this definition, $\Gamma$ sends $Av_n(\ddincr)$ to the set of well labeled configuration of size $n$ when labeling the points with the index used to compute their coordinates and that restricting solitaire moves to those who preserve a good labeling does not change the orbits. 


%\subsection{Solitaire on $3$-permutations}

%Lets now look at how solitaire moves on configurations translate on permutations. 

The solitaire extends naturally to labeled configurations, it can then be pulled back through $\Gamma$ to obtain a dynamical system on $Av(\ddincr)$. See \Cref{fig:solit moves}.

%By restricting its moves to those who preserve a correct order on the points of a configuration, on can obtain a solitaire on $\Gamma(Av(\ddincr))$ with the same orbits. This solitaire can then be pulled on $3$-permutations as depicted in \Cref{fig:solit moves}. 



%Let $i<j$ be indices such that the points $p_i$ and $p_j$ are in position for a solitaire move in $\Gamma(\sigma, \tau)$. Then the equalities on $x_i, y_i, x_j$ and $y_j$ forces the points to be positioned as depicted in \Cref{fig:solit moves}. Then, applying a solitaire moves consists in exchanging the coordinate of the points $i$ and $j$ along one of the three axes in the diagram of $\sigtau$. 
%We detail only the case $p_i = (x, y)$ and $p_j = (x, y+1)$, the two others are obtained similarly. Since $x_i = x_j$, we must have $\sigma(i) < \sigma(j)$, then as $(\sigma, \tau)$ avoids $(12,12)$, we have $\tau(i) > \tau(j)$. Now $y_j = x_i +1$ forces $L_\tau(j) = L_\tau(i) \cup \{i\}$, so the orange area must be empty. This also forces the blue area to be empty, otherwise a $(12,12)$ pattern would appear (remember that there are as many point in $R_\sigma(j)\setminus R_\sigma(i)$ as in $R_\sigma(i)\setminus R_\sigma(j)$).


\begin{figure}[ht]
    \centering
    \includegraphics[page=2, width=0.8\textwidth]{Figures/Fig_solit.pdf}
    \caption{The solitaire on the grid and the corresponding situation on $3$-permutations avoiding $\ddincr$ with $i<j$. Hashed areas must be empty for the move to be allowed. One moves from one position to the other by exchanging the coordinates of points $i$ and $j$ along the indicated axis in the diagram.}
    \label{fig:solit moves}
\end{figure}

\begin{comment}
This observation translates as follows: 

\begin{lemma}
    Let $(\sigma, \tau) \in \A$, $1 \leqslant i < j \leqslant n$. A solitaire move involving $p_i$ and $p_j$ can be performed if and only if $R_\sigma(i)$ is either $R_\sigma(j)$ or $R_\sigma(j) \cup \{j\}$ and $L_\tau(j)$ is either $L_\tau(i)$ or $L_\tau(i) \cup \{i\}$. 
    
    Such a move consists in exchanging the coordinates of $i$ and $j$ along one of the three axes in the diagram of $(\sigma, \tau)$, i.e. exchanging the values of $\sigma(i)$ and $\sigma(j)$ or $\tau(i)$ and $\tau(j)$ or both (which is the same as exchanging $i$ and $j$).
\end{lemma}

\begin{lemma}
    Solitaire moves stabilize $\A$.
\end{lemma}
\begin{proof}
    First, observe that doing a solitaire move does not create a $(12, 12)$ pattern. Indeed, such pattern should involve either $i$ or $j$. Let $k$ be the other index. If $i < k < j$, then $\sigma(k) > \max(\sigma(i), \sigma(j))$ and $\tau(k) < \min(\tau(i), \tau(j))$ so a solitaire move does not create a $(12,12)$ with $k$. If $k <i$, then for a $(12,12)$ to appear $\sigma(k)$ must be between $\sigma(i)$ and $\sigma(j)$, but that forces $\tau(k) > \max(\tau(i), \tau(j))$. Symmetrically, if $k >j$, then for a $(12,12)$ to appear $\tau(k)$ must be between $\tau(i)$ and $\tau(j)$ but that forces $\sigma(k) < \min(\sigma(i), \sigma(j))$.

    Now assume a $(312, 231)$ appears, it still has to involve $i$ or $j$. First observe that if a $312$ was created in $\sigma$, then $i$ is the $1$ and $j$ the $2$. Similarly, if a $213$ is created in $\tau$ then $i$ is the $2$ and $j$ the $3$. In both cases, the other side of the pattern would require a point in an empty area.
\end{proof}
\end{comment}

Denote $\desc$ the permutation $n(n-1)(n-2)\ldots21$.%and $L_n = \llbracket0, n-1\rrbracket \times \{0\}$.

\begin{thm}
    For all $n\geqslant 1$, $\orb((\desc, \id)) = Av_n(\ddincr, \pat)$.
\end{thm}


%\begin{proof}
 %   The first inclusion is given by the fact that solitaire stabilizes $\A$. The other can be obtained by induction using the cuts : solitaire moves can be applied of each side of the cut without affecting the other, and then one can use the line forme by one side to slide the other to the right position.
%\end{proof}

%\subsection{Applications}

%Using solitaire, we can make another proof of the surjectivity and injectivity of $\Gamma$. For surjectivity, on can simply find a sequence of moves from the line to the goal basis (which is doable in time $O(n^3)$ and apply the same sequence on $\colpair{\desc}{\id}$. The following lemma gives an injectivity result.
\begin{comment}
\begin{thm}
    For all $n$, $\Gamma(\orb((\desc, \id))) = \orb(L_n) = \B_n$.
\end{thm}
\begin{proof}
    First note that $\Gamma(\desc, \id) = L_n$ with $p_i = (n-i,0)$. Now applying solitaire moves in parallel starting respectively from $L_n$ and from $(\desc, \id)$, one creates an antecedent in $\orb((\desc,\id))$ for each element of $\orb(L_n)$ and symmetrically, we obtain that the image through $\Gamma$ of each element of $\orb((\desc, \id))$ is in $\orb(L_n)$.
\end{proof}


\begin{lemma}
    Let $C$ and $C'$ be two well labeled sparse configuration with the same support. Then $C$ and $C'$ are not in the same orbit.
\end{lemma}

\begin{proof}
    Assume the difference between $C$ and $C'$ is that they exchange the labels $i$ and $j$ with $i<j$. Then since they are well labeled, without loss of generality $x_i < x_j$ and $y_i < y_j$. Consider a sequence of solitaire moves that would exchange $p_i$ and $p_j$. It requires $a = x_j - x_i$ points with label greater than $j$ to move $p_j$ left (no less since to use the same point twice it need to be moved left too) and $b = y_j - y_i$ with label smaller than $i$ to move $p_i$ up. That makes $a+b+2$ points in the smallest triangle that contains $p_i$ and $p_j$, but this triangle only has size $a+b+1$, so its impossible since configurations are sparse.

    This argument can then be generalized to a biggest permutation of labels. 
    
    %A solitaire move cannot exchange two points, so the points have to ``go around each other''. Since all the intermediate configurations are well labeled, $p_i$ has to stay to the bottom or right of $p_j$. Now the moves to move $p_j$ to the left in $C$ can also be used on $C'$ since for $p_j$, they require a point $p_k$ with $k >j$ and $j>i$. By applying them, we can get $p_j$ and $p_i$ in the same column but with $p_i$ above, which is impossible in a well labeled configuration. 
\end{proof}
\end{comment}

\section{Discussion}
\label{sec:discu}

\textbf{Enumerative bounds:}
We now know that $\A$ and the set of triangle bases of size $n$ have the same cardinality, but the question of its value remains open. The difficulty comes the lack of nice recursive decomposition of the objects. 

In \cite{SaSc23}, we gave the following bounds on triangle bases, which transfer to the class $Av_n(\ddincr, \pat)$ through our bijection. To our knowledge, those are the first bounds on this class: $3n! \leqslant |\B_n| \leqslant c\left(e/2\right)^nn^{n -\frac52} \text{ with } c >0.$
%and we do not know any `nice'' bounds on the size of $\A$. 

\textbf{Random sampling:}
The solitaire defines a Markov chain on triangle bases. The diameter of the reconfiguration graph is $O(n^3)$ \cite{SaSc23}, and we conjecture that its mixing time is also \emph{polynomial} since the graph has strong connectivity properties. This would allow to sample uniformly triangle bases, and hence $3$-permutations of $\A$ by our bijection.

%The solitaire was invented to sample basis uniformly and could be used to do so with $3$-permutations in $\A$ as well. Though we do not know its mixing time, we believe it to be polynomial as the underlying reconfiguration graph seems to have strong connectivity properties. 




%The construction of the bijection is quite simple, and there do not seem to be any particular reason for it to work particularly on $Av_n(\ddincr, \pat)$ though avoiding $\ddincr$ ensures that no points collide. It would be interesting to see if it leads to a bijection between $3$-permutations avoiding other patterns and some set of points to determine, or to generalize it to higher dimension.

%Note that contrary to an early conjecture we had, avoiding $\ddincr$ is not enough for the function $\Gamma$ to be injective when forgetting the labels. For example $(4132, 2431)$ and $(4213, 3241)$ both avoid $\ddincr$ but have the same image up to relabeling (both have a $\pat$). 
\textbf{Other pattern avoiding classes:}
Our function $\Gamma$ is well defined and invertible on all of $Av(\ddincr)$ if we consider labeled configurations, so it might be use to study bijectively other sub classes of $Av(\ddincr)$. For this, studying the orbits of the solitaire might be relevant. 
$\Gamma$ can also be generalized to $d$-permutations by using each permutation to compute a coordinate, the image set would then be configurations of dimension $d-1$.

%Since the solitaire is well define not only on $\A$ but on all $Av_n(\ddincr)$, it might be interesting to consider it on other classes and see if we have a classification of orbit analogous to the one for configuration.


\textbf{Large random permutations:} 
The combinatorial (and especially bijective) understanding of pattern avoiding permutations gives detailed information about their structure, which can be applied to study the properties of large random objects. For instance, the theory of \emph{permutons} describes the scaling limit of many classes of pattern avoiding permutations (see e.g.~\cite{permuton}).
One can ask the same questions about large random $3$-permutations \cite{BoLi25}, and perhaps our bijection can help study the properties of large random permutations of $Av_n(\ddincr,$ $\pat)$.


\printbibliography

\end{document}
