\documentclass[12pt]{article} \usepackage{e-jc} \specs{P4.11}{21(4)}{2014} % August 2014: final revision for Electronic Journal of Combinatorics \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} \usepackage{amsmath, amsthm, amssymb} \usepackage{tikz} \usepackage{xspace} \usetikzlibrary{patterns} \usetikzlibrary{snakes} \usetikzlibrary{shapes.geometric} \renewcommand{\theenumi}{(\Alph{enumi})} \renewcommand{\labelenumi}{\theenumi} \newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}} \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{fact}[theorem]{Fact} \newtheorem{observation}[theorem]{Observation} \newtheorem{claim}[theorem]{Claim} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{open}[theorem]{Open Problem} \newtheorem{problem}[theorem]{Problem} \newtheorem{question}[theorem]{Question} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \newtheorem{note}[theorem]{Note} \newcommand{\bigclass}{{\mathcal M}} \renewcommand{\S}{\mathbf{S}} \newcommand{\R}{\mathbf{R}} \newcommand{\A}{\mathbf{A}} \newcommand{\B}{\mathbf{B}} \newcommand{\Z}{\mathbf{Z}} \renewcommand{\P}{P} \newcommand{\Av}{\mathop{\mathrm{Av}}} \newcommand{\post}{\mathop{\mathrm{\bf Post}}} \newcommand{\inreading}{\mathop{\mathrm{\bf In}}} \newcommand{\InTree}{\mathop{\mathrm{T_{in}}}} \newcommand{\canT}{\mathop{\mathcal{T}}} \newcommand{\Push}{\ensuremath{\mathbf{Push}}\xspace} \newcommand{\Pop}{\ensuremath{\mathbf{Pop}}\xspace} \DeclareMathOperator{\zeil}{\mathrm{zeil}} \DeclareMathOperator{\Rzeil}{\mathrm{Rzeil}} \newcounter{indice} \newcommand{\permutation}[1]{ \setcounter{indice}{0}; \foreach \i in {#1} \addtocounter{indice}{1}; \addtocounter{indice}{1} \draw [help lines] (1,1) grid (\theindice,\theindice); \setcounter{indice}{1}; \foreach \i in { #1 } { \draw (\theindice+.5,\i+.5) [fill] circle (.2); \addtocounter{indice}{1}; } \addtocounter{indice}{-1}; } \title{\bf Operators of equivalent sorting power \\ and related Wilf-equivalences} \author{Michael Albert\\ \small Department of Computer Science\\[-0.8ex] \small University of Otago\\[-0.8ex] \small Dunedin, New Zealand\\ \small\tt malbert@cs.otago.ac.nz\\ \and Mathilde Bouvel\\ \small Institut f\"ur Mathematik\\[-0.8ex] \small Universit\"at Z\"urich\\[-0.8ex] \small Z\"urich, Switzerland\\ \small\tt mathilde.bouvel@math.uzh.ch} \date{\dateline{Feb 18, 2014}{Sep 26, 2014}{Oct 9, 2014}\\ \small Mathematics Subject Classifications: 05A05, 05A19, 68R05} \begin{document} \maketitle \begin{abstract} We study sorting operators $\mathbf{A}$ on permutations that are obtained composing Knuth's stack sorting operator $\mathbf{S}$ and the reversal operator $\mathbf{R}$, as many times as desired. For any such operator $\mathbf{A}$, we provide a size-preserving bijection between the set of permutations sorted by $\mathbf{S} \circ \mathbf{A}$ and the set of those sorted by $\mathbf{S} \circ \mathbf{R} \circ \mathbf{A}$, proving that these sets are enumerated by the same sequence, but also that many classical permutation statistics are equidistributed across these two sets. The description of this family of bijections is based on a bijection between the set of permutations avoiding the pattern $231$ and the set of those avoiding $132$ which preserves many permutation statistics. We also present other properties of this bijection, in particular for finding pairs of Wilf-equivalent permutation classes. \bigskip\noindent \textbf{Keywords:} permutation, stack, sorting, enumeration, bijection, Wilf-equivalence \end{abstract} \section{Introduction} Partial sorting algorithms were one of the early motivations for the study of permutation patterns. In the late 1960s, Knuth~\cite{Knuth:Art} considered the problem of sorting a permutation of $[n] = \{1,2,\dots,n\}$ using only a stack. This problem takes a permutation $\pi$ in one line notation as input, starts with an empty stack, and its goal is to sort $\pi$ using only the \Push and \Pop operations. Knuth showed that a permutation $\pi = \pi(1) \pi(2) \ldots \pi(n)$ may be sorted by a stack if and only if the following procedure sorts $\pi$: \newpage \begin{quote} For $i$ from $1$ to $n$\\ \hspace*{0.7cm} While the stack is nonempty and $\pi(i)$ is larger than the top of the stack, \\ \hspace*{1.4cm} \Pop to the output\\ \hspace*{0.7cm} \Push $\pi(i)$ on the stack\\ While the stack is nonempty, \\ \hspace*{0.7cm} \Pop to the output \end{quote} Not all permutations are stack sortable, and Figure~\ref{FIG:Stack} shows an example of a permutation that fails to be sorted by a stack. \begin{figure}[ht] \begin{center} \begin{tikzpicture}\begin{scope}[scale=0.35] \draw (14,4) -- (14,0) -- (16,0)-- (16,4); \draw[->] (17,4.5) .. controls (16,4.5) .. (15.3,3.5); \draw[->] (14.7,3.5) .. controls (14,4.5) .. (13,4.5); \draw (19.5,4.5) node {$6\, 1\, 3\, 2\, 7\, 5\, 4$}; \draw (15,-0.2) node {$~$}; \end{scope} \end{tikzpicture} \quad \begin{tikzpicture} \begin{scope}[scale=0.35] \draw (14,4) -- (14,0) -- (16,0)-- (16,4); \draw[->] (17,4.5) .. controls (16,4.5) .. (15.3,3.5); \draw[->] (14.7,3.5) .. controls (14,4.5) .. (13,4.5); \draw (15,0.5) node {$6$}; \draw (12.5,4.5) node {$1$}; \draw (15,1.5) node {$3$}; \draw (15,2.5) node {$2$}; \draw (18,4.5) node {$7\, 5\, 4$}; \draw (15,-0.2) node {$~$}; \end{scope} \end{tikzpicture} \quad \begin{tikzpicture} \begin{scope}[scale=0.35] \draw (14,4) -- (14,0) -- (16,0)-- (16,4); \draw[->] (17,4.5) .. controls (16,4.5) .. (15.3,3.5); \draw[->] (14.7,3.5) .. controls (14,4.5) .. (13,4.5); \draw (15,0.5) node {$7$}; \draw (11.5,4.5) node {$1\, 2\, 3\, 6$}; \draw (17.7,4.5) node {$5\, 4$}; \draw (15,-0.2) node {$~$}; \end{scope} \end{tikzpicture} \quad \begin{tikzpicture} \begin{scope}[scale=0.35] \draw (14,4) -- (14,0) -- (16,0)-- (16,4); \draw[->] (17,4.5) .. controls (16,4.5) .. (15.3,3.5); \draw[->] (14.7,3.5) .. controls (14,4.5) .. (13,4.5); \draw (10.5,4.5) node {$1\, 2\, 3\, 6\, 4\, 5 \, 7$}; \draw (15,-0.2) node {$~$}; \end{scope} \end{tikzpicture} \end{center} \vspace*{-1ex} \caption{Some steps of the stack sorting procedure applied to $\pi = 6\, 1\, 3\, 2\, 7\, 5\, 4$. \label{FIG:Stack}} \end{figure} Knuth~\cite{Knuth:Art} also characterized the permutations that may be sorted by a stack. A first way to present this characterization is as follows: if a permutation $\pi$ of $[n]$ is written in one line notation as $\alpha n \beta$, then $\pi$ is sortable if and only if: each of $\alpha$ and $\beta$ is sortable (thought of as permutations of the values they contain); and each value in $\alpha$ is less than any value in $\beta$ (or simply $\alpha < \beta$). The first condition is clearly necessary -- the second condition is also necessary as, when $n$ is the first element remaining to be added to the stack, the entire stack must be emptied to have any hope of success, otherwise $n$ will precede some other element in the output, and the output will not be sorted. That the conditions are sufficient is also clear -- the requisite operations are: sort and output $\alpha$; add $n$ to the stack; sort and output $\beta$; remove $n$ from the stack. Another classical characterization of stack sortable permutations is simply derived from the description above. Stack sortable permutations are those that may not contain subwords (not necessarily consecutive) of the form $bca$ where $a < b < c$. Such permutations are said to \emph{avoid the pattern} $231$, and the collection of all such is denoted $\Av(231)$. This result opened the way to the study of pattern avoidance in permutations. A permutation $\pi = \pi(1) \pi(2) \ldots \pi(k)$ is a \emph{pattern} of a permutation $\sigma = \sigma(1) \sigma(2) \ldots \sigma(n)$ when there exist $1 \leq i_1 < i_2 < \ldots < i_k \leq n$ such that $\pi$ is order isomorphic to $\sigma(i_1)\ldots \sigma(i_k)$. If $\pi$ is not a pattern of $\sigma$ then we say that $\sigma$ \emph{avoids} $\pi$. We denote by $\Av(B)$ the set of all permutations that avoid simultaneously all the patterns $\pi \in B$. The simple behavior explained by Knuth prompted many other investigations of stack sorting and its variations beginning with works by Pratt and Tarjan \cite{Pratt:Computing, Tarjan:Sorting}. In the 1990s, West \cite{West:Twice} described by the avoidance of generalized patterns the permutations that can be sorted using $\S \circ \S$, and Zeilberger \cite{Zeilberger:West} subsequently confirmed a conjecture of West's on their enumeration. A characterization of permutation sorted by $\S \circ \S \circ \S$ has recently been given by Claesson and \'Ulfarsson~\cite{Ulf12,ClUl12}. It involves even more general patterns, but does not allow the enumeration of permutations sorted by $\S^3$. Going further, the characterization and enumeration of permutations sorted by $\S^k$ for $k\geq 4$ are open questions. \bigskip Instead of a procedure, stack sorting can equivalently be considered as an operator, $\S$, applied to permutations and defined recursively as: $\S(\alpha n \beta) = \S(\alpha) \S(\beta) n$. In this work, we shall take this point of view. We also adopt the viewpoint throughout that any sequence of distinct values can be interpreted as a permutation and ``$n$'' always denotes the maximum element of such a sequence. Bousquet-M\'{e}lou \cite{Bousquet:Sorted} considered the operator $\S$ and characterized, given $\pi$, the set $\S^{-1}(\pi)$. We shall be extending her results, and will discuss them in more detail later. As explained in Section~\ref{SEC:Mireille}, central to her analysis is the observation that the operator $\S$ can be described in the following terms: given a permutation $\pi$ form the unique decreasing binary tree $\InTree(\pi)$ whose in-order reading is $\pi$, then $\S(\pi)$ is the post-order reading of this tree. A second operator on permutations is the reversal operator, that reads permutations from right to left -- it can also be modeled by using a stack where we are obliged to input the entire permutation to the stack before performing any output. The reversal operator, $\R$ is one of eight natural symmetries on the collection of permutations. Bouvel and Guibert \cite{Bouvel:Enumeration} considered the enumeration of permutations sorted by $\S \circ \R \circ \S$ as well as the sets defined similarly with other symmetries in place of $\R$. In experimental investigations aimed at providing extensions to their results they noticed an interesting phenomenon that can be expressed as: \begin{conjecture} Take $\A$ to be any composition of the operators $\S$ and $\R$; then the number of permutations sorted by $\S \circ \A$ and by $\S \circ \R \circ \A$ is the same. Moreover, many permutation statistics are equidistributed across these two sets. \label{CONJ:BouvelGuibert} \end{conjecture} It is the primary purpose of this article to prove that this is indeed the case. A more precise statement of Conjecture~\ref{CONJ:BouvelGuibert} is given by Theorem~\ref{THM:main_result}, whose proof is provided in Section~\ref{SEC:main}. With the characterization of stack sortable permutations as $\Av(231)$, proving Conjecture~\ref{CONJ:BouvelGuibert} is equivalent to showing that there is a size-preserving bijection between the elements of $\Av(231)$ belonging to the image of $\A$, and the elements of $\Av(231)$ belonging to the image of $\R \circ \A$, with the additional condition that the bijection preserves the cardinality of the fiber above an element (i.e.~the number of preimages under $\A$, resp. $\R \circ \A$). Equivalently, we can replace this latter set by the elements of $\Av(132)$ belonging to the image of $\A$, since the self-inverse operator $\R$ immediately provides a bijection between $\Av(231)$ and $\Av(132)$. In establishing this result we make use of a very natural bijection -- denoted $\P$ -- between $\Av(231)$ and $\Av(132)$, which however rarely appears in the literature. As noticed in~\cite{DDJSS12}, this bijection preserves many permutation statistics, and we add more statistics to the list in Section~\ref{SEC:P}. Finally, in Section~\ref{SEC:Wilf}, we show how this bijection $\P$ can be used to derive Wilf-equivalences between some pairs of permutation classes of the form $\Av(231,\tau)$, for $\tau$ avoiding $231$. Namely, for every $n$, we describe $\lceil n/2 \rceil$ pairs of patterns $\tau$ and $\tau'$ such that $\R \circ \P$ is a bijection between $\Av(231,\tau)$ and $\Av(231,\tau')$. \section{Preimages of permutations in the image of $\S$}\label{SEC:Mireille} As noted earlier, the description of the elements of $\S^{-1}(\pi)$ for $\pi$ in the image of $\S$ was carried out in \cite{Bousquet:Sorted}. This description is central to our work, so we review it here. \subsection{Some basics about binary trees and permutations} A binary tree (whose internal vertices are labeled by integers) is \emph{decreasing} when $a < b$ for any child labeled by $a$ of a vertex labeled by $b$. The \emph{post-order reading} $\post$ is recursively defined by associating the empty word $\varepsilon$ to the empty tree $T_{\varepsilon}$, and the word $\post(T_\ell) \cdot \post(T_r) \cdot n$ to any non empty binary tree \raisebox{-1.5ex}{\begin{tikzpicture} \begin{scope} \tikzstyle{every child}=[level distance=3mm] \tikzstyle{every node}=[inner sep=0,minimum size=0mm] \tikzstyle{level 1}=[sibling distance=10mm] \node{\footnotesize $n$} child {node {$T_\ell$}} child { node {$T_r$}}; \end{scope} \end{tikzpicture} }. Similarly, the \emph{in-order reading} $\inreading$ is recursively defined by associating the empty word $\varepsilon$ to the empty tree $T_{\varepsilon}$, and the word $\inreading(T_\ell) \cdot n \cdot \inreading(T_r)$ to any non empty binary tree \raisebox{-1.5ex}{\begin{tikzpicture} \begin{scope} \tikzstyle{every child}=[level distance=3mm] \tikzstyle{every node}=[inner sep=0,minimum size=0mm] \tikzstyle{level 1}=[sibling distance=10mm] \node{\footnotesize $n$} child {node {$T_\ell$}} child { node {$T_r$}}; \end{scope} \end{tikzpicture} }. \begin{observation} \label{OBS:Tin} For any permutation $\pi$, there is a unique decreasing binary tree whose in-order reading is $\pi$. We denote it $\InTree(\pi)$. \end{observation} Namely, $\InTree(\pi)$ is recursively described by $\InTree(\varepsilon) = T_{\varepsilon}$ and \[ \InTree(\alpha n \beta) = \raisebox{-1.5ex}{\begin{tikzpicture} \begin{scope} \tikzstyle{every child}=[level distance=1.5mm] \tikzstyle{every node}=[inner sep=0,minimum size=0mm] \tikzstyle{level 1}=[sibling distance=12mm] \node {\footnotesize $n$} child[child anchor=north] {node[draw,shape=isosceles triangle, shape border rotate=90,anchor=north, inner sep=0.1,isosceles triangle apex angle=60] {\scriptsize $\InTree(\alpha)$}} child[child anchor=north] {node[draw,shape=isosceles triangle, shape border rotate=90,anchor=north, inner sep=0.1,isosceles triangle apex angle=60] {\scriptsize $\InTree(\beta)$}}; \end{scope} \end{tikzpicture} } \text{ where } n = \max (\alpha n \beta)\text{.} \] \subsection{Trees and preimages of permutations in the image of $\S$} As observed in~\cite[Proposition 2.1]{Bousquet:Sorted}, it may be deduced from the recursive definitions of $\InTree$, $\post$ and $\S$ given above (recall that $\S(\alpha n \beta) = \S(\alpha) \S(\beta) n$) that $\S$ converts in-order reading of decreasing binary trees to post-order reading: \begin{observation} For any permutation $\pi$, the post-order reading of the in-order tree of $\pi$ is the result of applying the stack sorting operator to $\pi$, i.e.~$\post(\InTree(\pi))=\S(\pi)$. \label{OBS:stack_sorting_on_trees} \end{observation} Notice furthermore for future use that, because every decreasing binary tree is the in-order tree of some permutation, Observation~\ref{OBS:stack_sorting_on_trees} implies that: \begin{corollary} The post-order reading of any decreasing binary tree is in the image of $\S$. \label{COR:post_in_S} \end{corollary} From Observation~\ref{OBS:stack_sorting_on_trees}, for any permutation $\tau$ in the image of $\S$, describing $\S^{-1}(\tau)$ is equivalent to describing the decreasing binary trees, $T$, with post-order reading $\tau$. As~\cite{Bousquet:Sorted} shows, this set of trees may be characterized by a single tree associated with $\tau$. \begin{definition} A decreasing binary tree is \emph{canonical} if it has the following property: any vertex, $z$, that has a left child, $x$, also has a right child, and the leftmost value $y$ in the subtree of the right child of $z$ is less than $x$. \end{definition} \begin{proposition}[\cite{Bousquet:Sorted}, Proposition 2.6] For any $\tau$ in the image of $\S$, there is a unique canonical tree, denoted $\canT_{\tau}$, with $\post(\canT_\tau) = \tau$. \label{PROP:unique_canonical_tree} \end{proposition} In fact, \cite{Bousquet:Sorted} also shows that the permutation $\pi$ obtained from the in-order reading of $\canT_{\tau}$ is the element of $\S^{-1}(\tau)$ having the greatest number of inversions. Moreover, \cite{Bousquet:Sorted} shows that all permutations in $\S^{-1}(\tau)$ (or equivalently, their in-order trees) may be recovered from $\canT_{\tau}$: \begin{proposition} Any decreasing binary tree whose post-order reading is $\tau$ (and only such trees) can be obtained from $\canT_\tau$ by a sequence of operations of the following type: take a vertex $z$ with no left child, and one of its descendants $y$ on the leftmost branch of its right subtree; remove the subtree rooted at $y$ and make it the left subtree of $z$. \label{PROP:all_preimages_from_canonical_tree} \end{proposition} As shown in \cite[Proposition 2.7]{Bousquet:Sorted}, it follows in particular that $|\S^{-1}(\tau)|$ depends only on the structure of the tree $\canT_{\tau}$ and not on its labeling. \begin{example} The canonical tree associated with $\tau = 5 \, 1 \, 8 \, 2 \, 3 \, 6 \, 4 \, 7 \, 9$ is \begin{center} $T_{\tau} =$ \raisebox{-3.1ex} {\begin{tikzpicture} \begin{scope} \tikzstyle{every child}=[level distance=2.5mm] \tikzstyle{every node}=[inner sep=0,minimum size=0mm] \tikzstyle{level 1}=[sibling distance=15mm] \tikzstyle{level 2}=[sibling distance=8mm] \tikzstyle{level 3}=[sibling distance=8mm] \tikzstyle{level 4}=[sibling distance=8mm] \node {\footnotesize $9$} child {node {\footnotesize $8$} child {node {\footnotesize $5$} } child {node {\footnotesize $1$} } } child { node {\footnotesize $7$} child { node {\footnotesize $6$} child [missing] child { node {\footnotesize $3$} child [missing] child { node {\footnotesize $2$} } } } child { node {\footnotesize $4$} } }; \end{scope} \end{tikzpicture}}. \end{center} Its in-order reading, $\pi = 5 \, 8 \, 1 \, 9 \, 6 \, 3 \, 2 \, 7 \, 4$ gives the permutation with the largest number of inversions subject to $\S(\pi) = \tau$. The four other decreasing binary trees with the same post-order reading are shown in Figure~\ref{FIG:example_canonical_tree}. Thus $|\S^{-1}(\tau)| = 5$. If the labels $8$ and $7$, and $5$ and $4$, were exchanged in the original tree, corresponding to $\tau' = 4 \, 1 \, 7 \, 2 \, 3 \, 6 \, 5 \, 8 \, 9$ then, because the tree is still canonical, the method for constructing permutations in $\S^{-1}(\tau')$ is still the same, and in particular $|\S^{-1}(\tau')| = |\S^{-1}(\tau)|$. \end{example} \begin{figure}[ht] \begin{center} \raisebox{1.8ex}{\begin{tikzpicture} \begin{scope} \tikzstyle{every child}=[level distance=2.5mm] \tikzstyle{every node}=[inner sep=0,minimum size=0mm] \tikzstyle{level 1}=[sibling distance=15mm] \tikzstyle{level 2}=[sibling distance=8mm] \tikzstyle{level 3}=[sibling distance=8mm] \tikzstyle{level 4}=[sibling distance=8mm] \node {\footnotesize $9$} child {node {\footnotesize $8$} child {node {\footnotesize $5$} } child {node {\footnotesize $1$} } } child { node {\footnotesize $7$} child { node {\footnotesize $6$} child { node {\footnotesize $2$} } child { node {\footnotesize $3$} } } child { node {\footnotesize $4$} } }; \end{scope} \end{tikzpicture} } \hspace{20pt} \raisebox{0ex}{\begin{tikzpicture} \begin{scope} \tikzstyle{every child}=[level distance=2.5mm] \tikzstyle{every node}=[inner sep=0,minimum size=0mm] \tikzstyle{level 1}=[sibling distance=15mm] \tikzstyle{level 2}=[sibling distance=8mm] \tikzstyle{level 3}=[sibling distance=8mm] \tikzstyle{level 4}=[sibling distance=8mm] \node {\footnotesize $9$} child {node {\footnotesize $8$} child {node {\footnotesize $5$} } child {node {\footnotesize $1$} } } child { node {\footnotesize $7$} child { node {\footnotesize $6$} child [missing] child { node {\footnotesize $3$} child { node {\footnotesize $2$} } child [missing] } } child { node {\footnotesize $4$} } }; \end{scope} \end{tikzpicture} } \hspace{20pt} \raisebox{0ex}{\begin{tikzpicture} \begin{scope} \tikzstyle{every child}=[level distance=2.5mm] \tikzstyle{every node}=[inner sep=0,minimum size=0mm] \tikzstyle{level 1}=[sibling distance=15mm] \tikzstyle{level 2}=[sibling distance=8mm] \tikzstyle{level 3}=[sibling distance=8mm] \tikzstyle{level 4}=[sibling distance=8mm] \node {\footnotesize $9$} child {node {\footnotesize $8$} child {node {\footnotesize $5$} } child {node {\footnotesize $1$} } } child { node {\footnotesize $7$} child { node {\footnotesize $6$} child { node {\footnotesize $3$} child [missing] child { node {\footnotesize $2$} } } child [missing] } child { node {\footnotesize $4$} } }; \end{scope} \end{tikzpicture} } \hspace{20pt} \raisebox{0ex}{\begin{tikzpicture} \begin{scope} \tikzstyle{every child}=[level distance=2.5mm] \tikzstyle{every node}=[inner sep=0,minimum size=0mm] \tikzstyle{level 1}=[sibling distance=15mm] \tikzstyle{level 2}=[sibling distance=8mm] \tikzstyle{level 3}=[sibling distance=8mm] \tikzstyle{level 4}=[sibling distance=8mm] \node {\footnotesize $9$} child {node {\footnotesize $8$} child {node {\footnotesize $5$} } child {node {\footnotesize $1$} } } child { node {\footnotesize $7$} child { node {\footnotesize $6$} child { node {\footnotesize $3$} child { node {\footnotesize $2$} } child [missing] } child [missing] } child { node {\footnotesize $4$} } }; \end{scope} \end{tikzpicture} } \end{center} \vspace*{-1ex} \caption{The four non canonical decreasing trees whose post-order reading is $\tau = 5 \, 1 \, 8 \, 2 \, 3 \, 6 \, 4 \, 7 \, 9$.} \label{FIG:example_canonical_tree} \end{figure} \section{A recursive bijection between $\Av(231)$ and $\Av(132)$} \label{SEC:P} In this section we introduce a bijection, that we denote $\P$, between permutations in $\Av(231)$ and those in $\Av(132)$. Even though it is very naturally defined, this bijection seems to appear rather rarely in the literature -- only in~\cite{DDJSS12} to our knowledge. It is very easy to describe $\P$ recursively using the \emph{sum}, $\oplus$, and \emph{skew sum}, $\ominus$, operations on permutations. These operations are easily understood on the \emph{diagrams} corresponding to permutations. The diagram of any permutation $\sigma$ of $[n]$ is the set of $n$ points in the plane at coordinates $(i, \sigma(i))$ -- see Figure~\ref{FIG:diagram} for some examples. If $\alpha$ is a permutation of $[a]$ and $\beta$ of $[b]$ we define: \vspace*{-0.3cm} \begin{align*} \alpha \oplus \beta &= \alpha \, (\beta + a) \text{ whose diagram is } \begin{tikzpicture} \begin{scope}[scale=.2] \useasboundingbox (0,1) rectangle (4,5); \draw (0,0) rectangle (2,2); \draw (1,1) node {\small $\alpha$}; \draw (2,2) rectangle (4,4); \draw (3,3) node {\small $\beta$}; \end{scope} \end{tikzpicture} \\ \alpha \ominus \beta &= (\alpha + b) \, \beta \text{ whose diagram is } \begin{tikzpicture} \begin{scope}[scale=.2] \useasboundingbox (0,1) rectangle (4,5); \draw (0,2) rectangle (2,4); \draw (1,3) node {\small $\alpha$}; \draw (2,0) rectangle (4,2); \draw (3,1) node {\small $\beta$}; \end{scope} \end{tikzpicture}\ . \end{align*} Here for example $\beta + a$ is just that sequence obtained by adding $a$ to every element of the sequence $\beta$ and \begin{tikzpicture} \begin{scope}[scale=.2] \useasboundingbox (0,0.5) rectangle (2,2.5); \draw (0,0) rectangle (2,2); \draw (1,1) node {\small $\alpha$}; \end{scope} \end{tikzpicture} represents the diagram of permutation $\alpha$. \begin{example} Let $\alpha = 2\,3\,1$ and $\beta = 3\,1\,4\,2$. Then $\alpha \oplus \beta = 2\,3\,1\,6\,4\,7\,5$, while $\alpha\ominus \beta = 6\,7\,5\,3\,1\,4\,2$, as shown in Figure~\ref{FIG:diagram}. \end{example} \begin{figure}[ht] \begin{center} \begin{tikzpicture} \begin{scope}[scale=0.4] \permutation{2,3,1} \end{scope} \end{tikzpicture} \qquad \begin{tikzpicture} \begin{scope}[scale=0.4] \permutation{3,1,4,2} \end{scope} \end{tikzpicture} \qquad \begin{tikzpicture} \begin{scope}[scale=0.4] \permutation{2,3,1,6,4,7,5} \draw (1,1) rectangle (4,4); \draw (4,4) rectangle (8,8); \end{scope} \end{tikzpicture} \qquad \begin{tikzpicture} \begin{scope}[scale=0.4] \permutation{6,7,5,3,1,4,2} \draw (1,5) rectangle (4,8); \draw (4,1) rectangle (8,5); \end{scope} \end{tikzpicture} \qquad \end{center} \vspace*{-1ex} \caption{From left to right, the diagrams of the permutations $\alpha = 2\,3\,1$, $\beta = 3\,1\,4\,2$, $\alpha \oplus \beta$ and $\alpha\ominus \beta$. \label{FIG:diagram}} \end{figure} Any $\pi \in \Av(231)$ is either the empty permutation $\varepsilon$ or has a unique decomposition in the form $\alpha \oplus (1 \ominus \beta)$ where $\alpha, \beta \in \Av(231)$ (and are possibly empty), and conversely any permutation of this latter form lies in $\Av(231)$. This is simply because the elements preceding the maximum in a $231$-avoiding permutation must all be less than those following the maximum, and the prefix before and suffix after the maximum must also avoid 231. Conversely, if a permutation has this structure it cannot involve 231. This decomposition makes it easy to define the bijection $\P$ recursively: $\P(\varepsilon)=\varepsilon$ and \[ \text{If } \pi = \alpha \oplus (1 \ominus \beta) \text{ then } \P(\pi) = (\P(\alpha) \oplus 1) \ominus \P(\beta). \] Alternatively, with diagrams: \[ \begin{tikzpicture} \begin{scope}[scale=.3] \useasboundingbox (-0.1,1) rectangle (5.6,5); \draw (0,0) rectangle (2.5,2.5); \draw (1.25,1.25) node {\scriptsize $\alpha$}; \draw (3,2.5) rectangle (5.5,5); \draw (4.25,3.75) node {\scriptsize $\beta$}; \draw (2.75,5.25) [fill] circle (0.2); \end{scope} \end{tikzpicture} \quad \mbox{\raisebox{10pt}{$\stackrel{P}{\longrightarrow}$}} \quad \begin{tikzpicture} \begin{scope}[scale=.3] \useasboundingbox (-0.1,1) rectangle (5.6,5); \draw (0,2.5) rectangle (2.5,5); \draw (1.25,3.75) node {\scriptsize $\P(\alpha)$}; \draw (3,0) rectangle (5.5,2.5); \draw (4.25,1.25) node {\scriptsize $\P(\beta)$}; \draw (2.75,5.25) [fill] circle (0.2); \end{scope} \end{tikzpicture} \: \text{\raisebox{12pt}{.}} \] As the $132$-avoiding permutations have a generic decomposition of the form shown on the right above, and since $\P(1) = 1$ maps the unique $231$-avoiding permutation of size $1$ to the unique $132$-avoiding permutation of size $1$, induction immediately implies that $\P: \Av(231) \to \Av(132)$ is a bijection. Let us introduce a notational convention that we shall use throughout. For any $\pi \in \Av(231)$, we can think of the sequence $P(\pi)$ as describing a relabeling of the values that occur in $\pi$ according to a certain permutation, denoted $\lambda_\pi$. Specifically, this means that $\lambda_\pi$ is defined by $P(\pi) = \lambda_\pi \circ \pi$. \begin{example}\label{EX:bijection_P} For $\pi = 1 \, 5\, 3\, 2\, 4\, 9\, 8\, 6\, 7 \in \Av(231)$, we have $\P(\pi) = 7\, 8\, 5\, 4\, 6\, 9\, 3\, 1\, 2$. The corresponding relabeling $\lambda_\pi$ is $\lambda_\pi = 7\, 4\, 5\, 6\, 8\, 1\, 2\, 3\, 9$. \end{example} Recall from Section~\ref{SEC:Mireille} that $\InTree(\pi)$ is the decreasing binary tree whose in-order reading is $\pi$. It follows immediately by induction from the recursive description of $\P$ that: \begin{observation}\label{OBS:P_preserves_Tin} For any $\pi \in \Av(231)$, both $\InTree(\pi)$ and $\InTree(\P(\pi))$ have the same underlying unlabeled tree, or briefly ``$\P$ preserves the shape of in-order trees''. \end{observation} \begin{figure}[ht] \begin{center} $\InTree(\pi)=$\begin{tikzpicture} \begin{scope} \tikzstyle{every child}=[level distance=2.5mm] \tikzstyle{every node}=[inner sep=0,minimum size=0mm] \tikzstyle{level 1}=[sibling distance=15mm] \tikzstyle{level 2}=[sibling distance=11mm] \tikzstyle{level 3}=[sibling distance=8mm] \tikzstyle{level 4}=[sibling distance=6mm] \node {\footnotesize $9$} child {node {\footnotesize $5$} child {node {\footnotesize $1$} } child {node {\footnotesize $4$} child {node {\footnotesize $3$} child [missing] child {node {\footnotesize $2$}} } child [missing] } } child {node {\footnotesize $8$} child [missing] child {node {\footnotesize $7$} child {node {\footnotesize $6$}} child [missing] } }; \end{scope} \end{tikzpicture} \qquad $\InTree(\P(\pi))=$\begin{tikzpicture} \begin{scope} \tikzstyle{every child}=[level distance=2.5mm] \tikzstyle{every node}=[inner sep=0,minimum size=0mm] \tikzstyle{level 1}=[sibling distance=15mm] \tikzstyle{level 2}=[sibling distance=11mm] \tikzstyle{level 3}=[sibling distance=8mm] \tikzstyle{level 4}=[sibling distance=6mm] \node {\footnotesize $9$} child {node {\footnotesize $8$} child {node {\footnotesize $7$} } child {node {\footnotesize $6$} child {node {\footnotesize $5$} child [missing] child {node {\footnotesize $4$}} } child [missing] } } child {node {\footnotesize $3$} child [missing] child {node {\footnotesize $2$} child {node {\footnotesize $1$}} child [missing] } }; \end{scope} \end{tikzpicture} \end{center} \caption{$\InTree(\pi)$ and $\InTree(\P(\pi))$ for the permutation $\pi = 1 \, 5\, 3\, 2\, 4\, 9\, 8\, 6\, 7$ of Example~\ref{EX:bijection_P}. \label{FIG:T_in}} \end{figure} Figure~\ref{FIG:T_in} shows an example. The acute reader will notice that in Figure~\ref{FIG:T_in}, not only $\InTree(\pi)$ and $\InTree(\P(\pi))$ have the same shape, but we also have $\lambda_\pi(\InTree(\pi)) = \InTree(\P(\pi))$. This is actually true in general, but the proof requires a bit more work (see the proof of Observation~\ref{OBS:identity} at the end of Subsection~\ref{SSEC:main}). However, some nice properties of $\P$ in terms of permutation statistics follow from the simple fact that $\P$ preserves the shape of in-order trees. Recall that, for $\pi$ a permutation of $[n]$, a \emph{left-to-right} (resp.~\emph{right-to-left}) \emph{maximum} of $\pi$ is an element $\pi(i)$ such that for all $ji$), $\pi(j) < \pi(i)$, and that the \emph{up-down word} of $\pi$ is $w_{\pi} \in \{u,d\}^{n-1}$ with $w_{\pi}(i) = u$ (resp.~$d$) if $\pi(i) < \pi(i+1)$ (resp.~$\pi(i) > \pi(i+1)$). \begin{observation} For any permutation, the shape of its in-order tree determines the number and positions of its right-to-left maxima, the number and positions of its left-to-right maxima and its up-down word. \label{OBS:stat_on_InTree} \end{observation} \begin{proof} Let $\pi$ by any permutation. That $w_{\pi}$ is determined by the shape of $\InTree(\pi)$ follows immediately by induction, from the recursive definition of the in-order reading $\inreading$. And the right-to-left (resp. left-to-right) maxima of $\pi$ correspond to the vertices lying on the right (resp. left) branch from the root of $\InTree(\pi)$, yielding the conclusion. \end{proof} Observations~\ref{OBS:P_preserves_Tin} and~\ref{OBS:stat_on_InTree} then give that: \begin{corollary} The bijection $\P$ preserves the following statistics: the number and positions of the right-to-left maxima, the number and positions of the left-to-right maxima and the up-down word. \end{corollary} As noted earlier, $\P$ has already been used in the study of permutation statistics. Namely, \cite[proof of Theorem 2.6]{DDJSS12} shows that $\P$ preserves the descent set, and hence the major index. However, many other classical permutation statistics are also preserved by $\P$, namely all those that depend only on the up-down word, for instance the descent set, the major index, the number of peaks. Among all the statistics reported in~\cite[Section 2]{ClKi08}, the only ones that are preserved by $\P$ are the ones that depend only on the shape of in-order trees. \section{Proof of Conjecture~\ref{CONJ:BouvelGuibert}} \label{SEC:main} \subsection{Preparation}\label{SEC:prep} In addition to the results of Section~\ref{SEC:Mireille}, the principal ingredients in the proof to follow are a pair of observations concerning $\P$ and operators $\A$ which are compositions of $\S$ and $\R$. \begin{observation} \label{OBS:SR} Let $\tau$ be any permutation, and $\A$ be any composition of the operators $\S$ and $\R$. Suppose that $x, y \in [n]$ and that in $\tau$ there are no values larger than $\max(x,y)$ occurring between $x$ and $y$. Then the same holds in $\A(\tau)$. \end{observation} \begin{proof} It suffices to prove the result for $\S$ and $\R$ individually. For $\R$ it is trivial since the elements between $x$ and $y$ in $\tau$ and $\R(\tau)$ are the same. But for $\S$ it follows immediately from the recursive description: $\S(\tau) = \S(\alpha n \beta) = \S(\alpha) \S(\beta) n$. If one of $x$ or $y$ is $n$ then there is nothing to prove, while if not then they must both occur in $\alpha$ or in $\beta$ and the result follows by induction. \end{proof} For the second observation, recall that, for any $\pi \in \Av(231)$, we denote $\lambda_\pi$ the permutation such that $P(\pi) = \lambda_\pi \circ \pi$, and that we view it as a relabeling of the elements of $\pi$. \begin{observation} \label{OBS:P} Let $\pi \in \Av(231)$ be given and suppose that $x, y \in [n]$, $x < y$, and in $\pi$ there are no values larger than $y$ occurring between $x$ and $y$. Then $\lambda_{\pi}(x) < \lambda_{\pi}(y)$. \end{observation} In other words, Observation~\ref{OBS:P} simply says that $\lambda_\pi$ preserves the ordering among elements of $\pi$ which do not contain a larger element between them. \begin{proof} The key argument is that, from the construction of $P$, the only way that one element can be moved above another one is to (at some point in the recursion) have a larger element in between. This can be expressed formally by induction, using the recursive definition of~$\P$. Let $\pi = \alpha n \beta = \alpha \oplus (1 \ominus \beta)$ and let $a=|\alpha|$ and $b = |\beta|$ (so $a + b = n-1$). If $y = n$ the result is trivial as $\lambda_{\pi}$ fixes $n$. Otherwise $x, y \in \alpha$ or $x, y \in \beta$, as by assumption they have no larger element between them in $\pi$. In the first case we have $x=\pi(i) = \alpha(i)$ and $y=\pi(j) = \alpha(j)$ for $i, j \in [a]$, and in the second case we have $x=\pi(i+a+1) = \beta(i) + a$ and $y=\pi(j+a+1) = \beta(j) + a$ for $i, j \in [b]$. It follows by induction that (depending on which case applies) $\lambda_{\alpha}(x) < \lambda_{\alpha}(y)$ or $\lambda_{\beta}(x-a) < \lambda_{\beta}(y-a)$. Note that $\lambda_{\pi}$ sends every $\ell \in [a]$ to $b + \lambda_{\alpha}(\ell)$ and every $a+\ell$ for $\ell \in [b]$ to $\lambda_{\beta}(\ell)$. Hence, when $x$ and $y$ are in $\alpha$ (resp.~$\beta$) we deduce from $\lambda_{\alpha}(x) < \lambda_{\alpha}(y)$ (resp.~$\lambda_{\beta}(x-a) < \lambda_{\beta}(y-a)$) that $\lambda_{\pi}(x) < \lambda_{\pi}(y)$, concluding the proof. \end{proof} \subsection{The main argument}\label{SSEC:main} In this section we prove the main result. Recall that $\A$ is an operator formed by some composition of $\S$ and $\R$. For any such operator, we shall write $\pi \in \A$ to denote that $\pi$ is in the image of $\A$. As above, for any $\pi \in \Av(231)$, we consider $\lambda_{\pi}$ as a relabeling of the elements of $[n]$. We extend its effect to permutations, trees etc.~that carry labels from $[n]$: applying $\lambda_{\pi}$ to such an object will simply mean to apply $\lambda_{\pi}$ to each of its labels. \begin{definition} We define a function $\Phi_{\A}$ from the set of permutations sorted by $\S \circ \A$ to the set of all permutations as follows. For $\theta$ a permutation sorted by $\S \circ \A$, since $\A(\theta) \in \Av(231)$, we have $\lambda_{\A(\theta)}$ defined by $\P(\A(\theta)) = \lambda_{\A(\theta)} \circ \A(\theta)$ and we then set $\Phi_{\A}(\theta)= \lambda_{\A(\theta)} \circ \theta$. \end{definition} In other words $\Phi_{\A}$ relabels a permutation $\theta$ sorted by $\S \circ \A$ in the same way that $\A(\theta)$ is relabeled to produce $P(\A(\theta))$. We will prove (see Corollary~\ref{COR:bijection}) that $\Phi_{\A}$ is a bijection from the set of permutations sorted by $\S \circ \A$ to the set of those sorted by $\S \circ \R \circ \A$. The key to this argument of course is to establish that $\A(\Phi_{\A}(\theta)) = P(\A(\theta))$. \begin{definition} An operator $\A$ which is a composition of $\S$ and $\R$ \emph{respects $\P$} if it has the following property (illustrated in Figure~\ref{FIG:A_respects_P}): For each $\pi \in \Av(231) \cap \A$, \begin{itemize} \item For each $\theta$ such that $\A(\theta) = \pi$, we have $ \A(\Phi_{\A}(\theta)) = \P(\pi) = \lambda_{\pi} \circ \pi$ and \\ $\InTree(\Phi_{\A}(\theta)) = \lambda_{\pi}(\InTree(\theta))$, and \item the correspondence $\Phi_{\A}: \theta \mapsto \Phi_{\A}(\theta)$ is a bijection between $\A^{-1}(\pi)$ and $\A^{-1}(\P(\pi))$. \end{itemize} \end{definition} In the above, notice that because $\A(\theta) = \pi$ we actually have $\Phi_{\A}(\theta) = \lambda_{\pi} \circ \theta$. \begin{figure}[ht] \begin{center} \begin{tikzpicture} \begin{scope}[scale=1.2] \node at (-0.3,1) {\small $\{12\dots n\}$}; \node at (1.1,1) {$\xleftarrow{\hspace*{1.2cm}}$}; \node at (1.2,1.3) {$\S$}; \filldraw[fill=gray!15!white, draw=black] (4,1) arc (0:360:1cm and 0.4cm); \node at (3,1.7) {\small {$\Av(231) \cap \A$}}; \node[anchor=east] at (3.9,1) {{\small $\pi$}}; \filldraw[fill=gray!15!white, draw=black] (7.6,1) arc (0:360:1.3cm and 0.45cm); \node at (4.5,1) {$\xleftarrow{\hspace*{1.4cm}}$}; \node at (4.4,1.3) {$\A$}; \node[anchor=west] at (5.1,1) {\small {$\theta$}}; \node at (6.3,1.7) {\small {$\A^{-1}(\pi)$}}; \node at (-0.3,0) {\small $\{12\dots n\}$}; \node at (0.75,0) {$\xleftarrow{\hspace*{0.5cm}}$}; \node at (0.75,0.3) {$\S$}; \node at (1.6,0) {$\xleftarrow{\hspace*{0.5cm}}$}; \node at (1.6,0.3) {$\R$}; \filldraw[fill=gray!15!white, draw=black] (4,0) arc (0:360:1cm and 0.4cm); \node at (3,-0.7) {\small {$\Av(132) \cap \A$}}; \node[anchor=east] at (3.9,0) {{\small $\P(\pi)$ \hspace*{-0.7em} $=$ \hspace*{-0.7em} $\lambda_{\pi}$ \hspace*{-0.7em} $\circ$ \hspace*{-0.7em} $\pi$}}; \filldraw[fill=gray!15!white, draw=black] (7.6,0) arc (0:360:1.3cm and 0.45cm); \node[anchor=west] at (5.1,0) {{\small $\Phi_{\A}(\theta) = \lambda_{\pi} \circ \theta$}}; \node at (4.5,0) {$\xleftarrow{\hspace*{1.4cm}}$}; \node at (4.4,0.3) {$\A$}; \node at (6.3,-0.7) {\small {$\A^{-1}(\P(\pi))$}}; \draw[<->] (7.7,1) .. controls +(right:1cm) and +(right:1cm) .. (7.7,0); \node at (9.1,0.7) {\small {$\Phi_{\A}$ is a }}; \node at (9.1,0.3) {\small {bijection}}; \end{scope} \end{tikzpicture} \end{center} \vspace*{-2ex} \caption{Overview of an operator $\A$ that respects $\P$. \label{FIG:A_respects_P}} \end{figure} \begin{proposition} If $\A$ respects $\P$ then so does $\A \circ \R$. \label{PROP:AoR_respects_P} \end{proposition} \begin{proof} Let $\pi \in \Av(231) \cap (\A \circ \R)$ and $\theta$ be such that $(\A \circ \R)(\theta) = \pi$. Let $\tau = \R(\theta)$. Then $\A(\tau) = \pi$ and since $\A$ respects $\P$, $\A(\Phi_{\A}(\tau)) = \P(\pi)$ and $\InTree(\Phi_{\A}(\tau)) = \lambda_{\pi}(\InTree(\tau))$. Because $\R$ is an involution on permutations that acts only on positions whereas $\lambda_{\pi}$ acts on values only, we prove that $\R\big(\Phi_{\A \circ \R}(\theta)\big) = \Phi_{\A}(\tau)$. Indeed, for any $i \in [n]$, we have: \[ \R\big(\Phi_{\A \circ \R}(\theta)\big) (i) = \Phi_{\A \circ \R}(\theta) (n+1-i) = \lambda_{\A \circ \R(\theta)}\big(\theta(n+1-i)\big) = \lambda_{\A(\tau)}\big(\tau(i)\big) = \Phi_{\A}(\tau)(i). \] It follows that $(\A \circ \R)\left( \Phi_{\A \circ \R}(\theta) \right) = \A(\Phi_{\A}(\tau)) = \P(\pi)$. Moreover, applying $\R$ to a permutation is equivalent to recursively exchanging left and right subtrees in its in-order tree. Because we have $\R \left( \Phi_{\A}(\tau) \right) = \Phi_{\A \circ \R}(\theta)$ and $\R(\tau) = \theta$, we deduce from $\InTree(\Phi_{\A}(\tau)) = \lambda_{\pi}(\InTree(\tau))$ that $\InTree(\Phi_{\A \circ \R}(\theta)) = \lambda_{\pi}(\InTree(\theta))$. Finally, the correspondence $\Phi_{\A \circ \R}: \theta \mapsto \Phi_{\A \circ \R}(\theta)$ is a composition of three bijections: first $\R$ from $(\A \circ \R)^{-1}(\pi)$ to $\A^{-1}(\pi)$, then $\Phi_{\A}$ from $\A^{-1}(\pi)$ to $\A^{-1}(\P(\pi))$ since $\A$ respects $\P$, and last $\R^{-1}=\R$ again from $\A^{-1}(\P(\pi))$ to $( \A \circ \R)^{-1}(\P(\pi))$. This proves that $\Phi_{\A \circ \R}$ is a bijection between $(\A \circ \R)^{-1}(\pi)$ and $( \A \circ \R)^{-1}(\P(\pi))$ and concludes the proof that $\A \circ \R$ respects $\P$. \end{proof} \begin{proposition} If $\A$ respects $\P$ then so does $\A \circ \S$. \label{PROP:AoS_respects_P} \end{proposition} \begin{proof} In this case, the argument is a little more involved. Let $\pi \in \Av(231) \cap (\A \circ \S)$. Throughout the proof, let us denote the relabeling accomplished by $\lambda_\pi$ by a primed symbol, i.e.~$w'$ represents the effect of relabeling $w$ by $\lambda_\pi$ for any object $w$. For instance, $\P(\pi) = \lambda_\pi \circ \pi = \pi'$. Consider $\theta \in (\A \circ \S)^{-1}(\pi)$, and define $\tau =\S(\theta)$. Then, we have $\tau \in \S$ and $\A(\tau) = \pi$. Because $\A$ respects $\P$, we have $\A(\tau') = \pi'$ and $\InTree(\tau') = \InTree(\tau)'$. We prove in the following that $\tau' \in \S$, $\S(\theta') = \tau'$ and $\InTree(\theta') = \InTree(\theta)'$ (see Claims $1$, $4$ and $3$ below). \smallskip Because $\tau \in \S$, we may consider the canonical tree $T= \canT_{\tau}$ associated with $\tau$. Consider also its relabeling by $\lambda_\pi$, denoted $T'$. Of course, because $\post(T) = \tau$, we have $\post(T') = \tau'$. This will prove the first condition of $\A \circ \S$ respecting $\P$. \smallskip\emph{Claim $1$:} $T'$ is decreasing. \smallskip It then follows from $\post(T') = \tau'$ and Corollary~\ref{COR:post_in_S} that $\tau' \in \S$. \smallskip\emph{Proof of Claim $1$:} Consider any edge from a parent $b$ to a child $a$ in $T$, and the corresponding edge from $b'$ to $a'$ in $T'$. Because $T$ is decreasing, $a a'$, proving that $T'$ is decreasing. \smallskip\emph{Claim $2$:} $T'$ is canonical. \smallskip It then follows from $\post(T') = \tau'$ and Proposition~\ref{PROP:unique_canonical_tree} that $T'=\canT_{\tau'}$ (the unique canonical tree associated with $\tau'$). \smallskip\emph{Proof of Claim $2$:} Let $x$ be the left child of some vertex $z$ in $T$ and let $y$ be the leftmost element of the right subtree of $z$. Then $x > y$ since $T$ is canonical. Let $x'$ and $y'$ occupy the corresponding positions in $T'$. Since $x$ occurs immediately before $y$ in $\tau = \post(T)$, $x' > y'$ (by Observations \ref{OBS:SR} and \ref{OBS:P}, as in the proof of Claim $1$). \smallskip\emph{Claim $3$:} $\InTree(\theta') = \InTree(\theta)'$. \smallskip\emph{Proof of Claim $3$:} Recall that $\S(\theta) = \tau$. By Proposition~\ref{PROP:all_preimages_from_canonical_tree}, $\InTree(\theta)$ is obtained from $T$ by applying some sequence of operations of the form: \[ (\star) \left\{ \text{\begin{minipage}{0.9\textwidth} Take a vertex $z$ with no left child, and one of its descendants $y$ on the leftmost branch of its right subtree. Remove the subtree rooted at $y$ and make it the left subtree of $z$. \end{minipage}} \right. \] Applying the same sequence of operations to $T'$ creates a tree with the same underlying structure as $\InTree(\theta)$, but with the labels arising from $T'$: this is the tree $\InTree(\theta)'$ and its in-order reading is $\inreading(\InTree(\theta)') = \theta'$. Because $T'$ is decreasing and since the operations $(\star)$ cannot create an increasing pair, $\InTree(\theta)'$ is a decreasing tree. Observation~\ref{OBS:Tin} then ensures that $\InTree(\theta') = \InTree(\theta)'$. \smallskip\emph{Claim $4$:} $\S(\theta') = \tau'$. \smallskip\emph{Proof of Claim $4$:} From Claim $3$, we know that $\InTree(\theta')$ is obtained from $T'$ by a sequence of operations $(\star)$. Moreover, from Claim $2$, $T'$ is the canonical tree of $\tau'$. Therefore, Proposition~\ref{PROP:all_preimages_from_canonical_tree} ensures that $\post(\InTree(\theta'))=\tau'$. Hence with Observation~\ref{OBS:stack_sorting_on_trees}, we deduce that $\S(\theta')=\post(\InTree(\theta'))=\tau'$. \smallskip To conclude the proof that $\A \circ \S$ respects $\P$, it remains to show that $\Phi_{\A \circ \S}: \theta \mapsto \theta'$ is a bijection between $(\A \circ \S)^{-1}(\pi)$ and $(\A \circ \S)^{-1}(\P(\pi)) = (\A \circ \S)^{-1}(\pi')$. First, we claim that, for every $\tau \in \A^{-1}(\pi)$, the correspondence $\theta \mapsto \theta'$ is a bijective map between $\S^{-1}(\tau)$ and $\S^{-1}(\tau')$. This follows from Proposition~\ref{PROP:all_preimages_from_canonical_tree} (together with Observations~\ref{OBS:Tin} and~\ref{OBS:stack_sorting_on_trees}), as in the proofs of Claims $3$ and $4$ above. Details may also be found in the proof of Proposition~2.7 of~\cite{Bousquet:Sorted}. Second, the set $(\A \circ \S)^{-1}(\pi)$ (resp. $(\A \circ \S)^{-1}(\pi')$) may be partitioned into the disjoint union of the sets $\S^{-1}(\tau)$ for $\tau \in \A^{-1}(\pi)$ (resp. $\S^{-1}(\tau')$ for $\tau' \in \A^{-1}(\pi')$). Because $A$ respects $\P$, the correspondence $\Phi_\A: \tau \mapsto \tau'$ is a bijection between $\A^{-1}(\pi)$ and $\A^{-1}(\pi')$. Hence the complete correspondence $\Phi_{\A \circ \S}: \theta \mapsto \theta'$ from $(\A \circ \S)^{-1}(\pi)$ to $(\A \circ \S)^{-1}(\pi')$ is a bijection, and $P$ respects $\A \circ \S$. \end{proof} Finally, let us observe that: \begin{observation} The identity operator respects $\P$. \label{OBS:identity} \end{observation} \begin{proof} When $\A$ is the identity, we have $\Phi_\A = \P$. So to show that the identity fulfills the definition of respecting $\P$, the only thing to prove is that $\InTree(\P(\pi)) = \lambda_\pi(\InTree(\pi))$ for any $\pi \in \Av(231)$. Because $\InTree(\pi)$ is decreasing, we deduce from Observation~\ref{OBS:P} that $\lambda_\pi(\InTree(\pi))$ is also decreasing. Moreover, the in-order reading of $\lambda_\pi(\InTree(\pi))$ is $\lambda_\pi \circ \pi = \P(\pi)$, since the one of $\InTree(\pi)$ is $\pi$. Observation~\ref{OBS:Tin} then gives $\lambda_\pi(\InTree(\pi)) = \InTree(\P(\pi))$. \end{proof} Propositions~\ref{PROP:AoR_respects_P} and~\ref{PROP:AoS_respects_P} and Observation~\ref{OBS:identity} together imply our main theorem: \begin{theorem}\label{THM:respects} Every operator that is formed by composition from $\{\S, \R\}$ respects $\P$. \end{theorem} \begin{corollary}\label{COR:bijection} For any composition $\A$ of operators from $\{\S,\R\}$, $\Phi_{\A}$ is a size-preserving bijection between the set of permutations sorted by $\S \circ \A$ and those sorted by $\S \circ \R \circ \A$. \end{corollary} \begin{proof} A permutation $\theta$ is sorted by $\S \circ \A$ if and only if there exists $\pi \in \Av(231)$ such that $\theta \in \A^{-1}(\pi)$. From $\pi = \A(\theta)$, we have $\Phi_{\A}(\theta)= \lambda_{\pi} \circ \theta$. Because $\A$ respects $\P$, $\theta \in \A^{-1}(\pi)$ is equivalent to $\Phi_{\A}(\theta) \in \A^{-1}(\P(\pi))$. Finally, because $\P$ is a bijection between $\Av(231)$ and $\Av(132)$, the existence of $\pi \in \Av(231)$ such that $\Phi_{\A}(\theta) \in \A^{-1}(\P(\pi))$ is equivalent to the existence of $\tau \in \Av(132)$ such that $\Phi_{\A}(\theta) \in \A^{-1}(\tau)$, i.e.~to $\Phi_{\A}(\theta)$ being sorted to $\S \circ \R \circ \A$. \end{proof} Corollary~\ref{COR:bijection} proves the first part of Conjecture~\ref{CONJ:BouvelGuibert}, namely that the number of permutations of each size sorted by $\S \circ \A$ and by $\S \circ \R \circ \A$ is the same. We now study the properties of bijections $\Phi_{\A}$ in somewhat greater detail. This will prove the second part of Conjecture~\ref{CONJ:BouvelGuibert}, that deals with permutation statistics equidistributed over the set of permutations sorted by $\S \circ \A$ and the set of those sorted by $\S \circ \R \circ \A$. \subsection{Statistics preserved by the bijections $\Phi_{\A}$}\label{SEC:stat} As before, $\A$ denotes any composition of operators from $\{\S,\R\}$. \begin{theorem} The bijection $\Phi_{\A}$ preserves the shape of the in-order tree. \end{theorem} \begin{proof} From Theorem~\ref{THM:respects}, $\A$ respects $\P$. Hence for all permutations $\theta$ sorted by $\S \circ \A$, and denoting $\pi = \A(\theta)$, we have $\InTree(\Phi_{\A}(\theta)) = \lambda_{\pi}(\InTree(\theta))$, so that $\InTree(\Phi_{\A}(\theta))$ and $\InTree(\theta)$ have the same shape. \end{proof} Because the shape of the in-order tree determines many permutation statistics (see Observation~\ref{OBS:stat_on_InTree} at the end of Section~\ref{SEC:P}), we have: \begin{corollary} The bijection $\Phi_{\A}$ preserves the following statistics: the number and positions of the right-to-left maxima, the number and positions of the left-to-right maxima and the up-down word (and hence also the many classical permutation statistics determined by the up-down word). \end{corollary} \begin{theorem}\label{THM:zeil} If $\A = \A_0 \circ \S$ for some arbitrary composition $\A_0$ of operators from $\{\S,\R\}$, then $\Phi_{\A}$ preserves the Zeilberger statistic, defined as: $\zeil(\pi) = \max \{k \mid n (n-1) \ldots (n-k+1) \text{ is a subword of } \pi\}$. In addition, if there is at least an operator $\S \circ \R$ in the composition that defines $\A_0$, then $\Phi_{\A}$ also preserves the reversal of the above statistics: $\Rzeil(\pi) = \max \{k \mid (n-k+1) \ldots (n-1) n \text{ is a subword of } \pi\}$. \end{theorem} \begin{proof} Consider $\theta$ a permutation sorted by $\S \circ \A$, and set $\pi = \A(\theta)$. Notice that $\pi \in \Av(231)$. Writing $\P(\pi) = \lambda_{\pi} \circ \pi = \pi'$, and using the primed notation throughout as before, we have $\Phi_{\A}(\theta) = \theta'$. Let $c \leq n$ be the smallest value such that for all $d \geq c$, $d' = d$. In what follows, we assume that $c \neq 1$, or the results follow trivially from $\Phi_{\A}(\theta) = \theta$. Set $k = \zeil(\theta)$. This means that the right branch from the root of $\InTree(\theta)$ is labeled by $n, n-1, \ldots, n-k+1$, and that the right child of the vertex labeled by $n-k+1$ (if it exists) is not labeled by $n-k$. Because $\InTree(\theta') = \InTree(\theta)'$, % this is from Theorem~\ref{THM:respects}, ie because \A respects \P to show that $\zeil(\theta')=\zeil(\theta)$, it is enough to prove that the relabeling $z \mapsto z'$ does not affect the elements larger than or equal to $n-k$, i.e.~that $c \leq n-k$. Assume to the contrary $c>n-k$ holds. Then the post-order reading of $\InTree(\theta)$ gives $\S(\theta) = \sigma c (c+1) \ldots (n-1) n$, where $\sigma$ contains all values from $1$ to $(c-1)$. By assumption $\sigma$ contains at least two distinct elements $y=c-1$ and $x$ such that $x'=c-1$. We have $x