\documentclass[12pt]{amsart}
\usepackage[latin1]{inputenc}
\usepackage{eepic,epic, amsmath, mathtools}
%\usepackage{graphicx}
\usepackage{xypic}
% specify the margins (instead of height, width, etc):
\usepackage[left=3.1cm,top=3.3cm,right=3.1cm,bottom=3.3cm]{geometry}
\newcommand{\n}{*=0{{\scriptstyle\bullet}}}
\newcommand{\eru}{\ar@{-}[ru]}
\newcommand{\erd}{\ar@{-}[rd]}
\newcommand{\er}{\ar@{-}[r]} % edge right
\newcommand{\eu}{\ar@{-}[u]} % edge up
\newcommand{\sym}{\mathcal{S}} % the symmetric group
\newcommand\mpg[1]{\marginpar{\raggedright\tiny#1}}
\newcommand{\NN}{{\mathbb N}} % Natural numbers
\newcommand{\ZZ}{{\mathbb Z}} % Integers
\newcommand{\CC}{{\mathbb C}} % Complex numbers
\newcommand{\dyck}{{\mathcal D}} % The set of Dyck paths
\newcommand{\B}{{\mathcal B}} % The set of 'Ballot sequences'
\DeclareMathOperator{\std}{\mathrm{std}}
\DeclareMathOperator{\Knuth}{\mathrm{Knuth}}
\DeclareMathOperator{\Ri}{\mathrm{Richards}}
\DeclareMathOperator{\KRi}{\mathrm{Knuth--Richards}}
\DeclareMathOperator{\KRo}{\mathrm{Knuth--Rotem}}
\DeclareMathOperator{\Astrid}{\mathrm{Billey--Jockusch--Stanley--Reifegerste}}
\DeclareMathOperator{\MDD}{\mathrm{Mansour--Deng--Du}}
\DeclareMathOperator{\SiS}{\mathrm{Simion--Schmidt}}
\DeclareMathOperator{\Krattan}{\mathrm{Krattenthaler}}
\DeclareMathOperator{\ED}{\mathrm{Elizalde--Deutsch}}
\DeclareMathOperator{\West}{\mathrm{West}}
\DeclareMathOperator{\reverse}{\mathrm{reverse}}
\DeclareMathOperator{\complement}{\mathrm{complement}}
\DeclareMathOperator{\inverse}{\mathrm{inverse}}
\DeclareMathOperator{\identity}{\mathrm{identity}}
\DeclareMathOperator{\comp}{\mathrm{comp}}
\DeclareMathOperator{\compR}{\mathrm{comp.\!r}}
\DeclareMathOperator{\compC}{\mathrm{comp.\!c}}
\DeclareMathOperator{\rank}{\mathrm{rank}}
\DeclareMathOperator{\rankR}{\mathrm{rank.\!r}}
\DeclareMathOperator{\rankRC}{\mathrm{rank.\!r.\!c}}
\DeclareMathOperator{\Nrank}{\mathrm{n-rank}}
\DeclareMathOperator{\lmax}{\mathrm{lmax}}
\DeclareMathOperator{\rmax}{\mathrm{rmax}}
\DeclareMathOperator{\lmin}{\mathrm{lmin}}
\DeclareMathOperator{\rmin}{\mathrm{rmin}}
\DeclareMathOperator{\Nrmin}{\mathrm{n-rmin}}
\DeclareMathOperator{\ldr}{\mathrm{ldr}}
\DeclareMathOperator{\ldrR}{\mathrm{ldr.\!r}}
\DeclareMathOperator{\ldrI}{\mathrm{ldr.\!i}}
\DeclareMathOperator{\ldrIR}{\mathrm{ldr.\!i.\!r}}
\DeclareMathOperator{\Mldr}{\mathrm{m-ldr}}
\DeclareMathOperator{\MldrI}{\mathrm{m-ldr.\!i}}
\DeclareMathOperator{\lir}{\mathrm{lir}}
\DeclareMathOperator{\lirR}{\mathrm{lir.\!r}}
\DeclareMathOperator{\lirI}{\mathrm{lir.\!i}}
\DeclareMathOperator{\lirIR}{\mathrm{lir.\!i.\!r}}
\DeclareMathOperator{\rdr}{\mathrm{rdr}}
\DeclareMathOperator{\rdrI}{\mathrm{rdr}.\!i}
\DeclareMathOperator{\rir}{\mathrm{rir}}
\DeclareMathOperator{\rirI}{\mathrm{rir.\!i}}
\DeclareMathOperator{\fp}{\mathrm{fix}}
\DeclareMathOperator{\cyc}{\mathrm{cyc}}
\DeclareMathOperator{\zeil}{\mathrm{zeil}}
\DeclareMathOperator{\zeilC}{\mathrm{zeil.\!c}}
\DeclareMathOperator{\head}{\mathrm{head}}
\DeclareMathOperator{\headI}{\mathrm{head.\!i}}
\DeclareMathOperator{\headIR}{\mathrm{head.\!i.\!r}}
\DeclareMathOperator{\last}{\mathrm{last}}
\DeclareMathOperator{\lastI}{\mathrm{last.\!i}}
\DeclareMathOperator{\lastIR}{\mathrm{last.\!i.\!r}}
\DeclareMathOperator{\lis}{\mathrm{lis}}
\DeclareMathOperator{\lds}{\mathrm{lds}}
\DeclareMathOperator{\inv}{\mathrm{inv}}
\DeclareMathOperator{\exc}{\mathrm{exc}}
\DeclareMathOperator{\excR}{\mathrm{exc.\!r}}
\DeclareMathOperator{\peak}{\mathrm{peak}}
\DeclareMathOperator{\peakI}{\mathrm{peak.\!i}}
\DeclareMathOperator{\peakIR}{\mathrm{peak.\!i.\!r}}
\DeclareMathOperator{\peakR}{\mathrm{peak.\!r}}
\DeclareMathOperator{\valley}{\mathrm{valley}}
\DeclareMathOperator{\valleyC}{\mathrm{valley.\!c}}
\DeclareMathOperator{\valleyI}{\mathrm{valley.\!i}}
\DeclareMathOperator{\valleyIR}{\mathrm{valley.\!i.\!r}}
\DeclareMathOperator{\petter}{\mathrm{petter}}
\DeclareMathOperator{\des}{\mathrm{des}}
\DeclareMathOperator{\Ndes}{\mathrm{n-des}}
\DeclareMathOperator{\asc}{\mathrm{asc}}
\DeclareMathOperator{\ascR}{\mathrm{asc.\!r}}
\DeclareMathOperator{\slmax}{\mathrm{slmax}}
\DeclareMathOperator{\slmaxI}{\mathrm{slmax.\!i}}
\DeclareMathOperator{\slmaxIR}{\mathrm{slmax.\!i.\!r}}
\DeclareMathOperator{\slmaxRI}{\mathrm{slmax.\!r.\!i}}
\DeclareMathOperator{\slmaxR}{\mathrm{slmax.\!r}}
\DeclareMathOperator{\slmaxC}{\mathrm{slmax.\!c}}
\DeclareMathOperator{\slmaxRC}{\mathrm{slmax.\!r.\!c}}
\DeclareMathOperator{\slmaxRCI}{\mathrm{slmax.\!r.\!c.\!i}}
\DeclareMathOperator{\slmaxCR}{\mathrm{slmax.\!c.\!r}}
\DeclareMathOperator{\LMIN}{\mathfrak{lmin}}
\DeclareMathOperator{\RMIN}{\mathfrak{rmin}}
\DeclareMathOperator{\LMAX}{\mathfrak{lmax}}
\DeclareMathOperator{\RMAX}{\mathfrak{rmax}}
\DeclareMathOperator{\PEAK}{\mathfrak{peak}}
\newcommand{\CK}{\ensuremath{\Phi}}
\newcommand{\STAT}{\ensuremath{\mathrm{STAT}}}
\newcommand{\emptyword}{\epsilon}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{conjecture}{Conjecture}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}{Example}
\newtheorem{problem}{Problem}
\newtheorem{remark}{Remark}
\newcommand\p{\circle*{0.25}}
\author{Anders Claesson\and Sergey Kitaev}
\title[Classification of bijections]
{Classification of bijections between \\ 321- and 132-avoiding permutations}
\thanks{The research presented here was supported by grant no. 060005012 from
the Icelandic Research Fund}
\address{The Mathematics Institute, Reykjavik University, Kringlan 1,
103 Reykjavik, Iceland}
\keywords{bijection, permutation statistics, equidistribution,
pattern avoidance, Catalan structures}
\begin{document}
\begin{abstract}
It is well-known, and was first established by Knuth in 1969, that
the number of $321$-avoiding permutations is equal to that of
$132$-avoiding permutations. In the literature one can find many
subsequent bijective proofs of this fact. It turns out that some of
the published bijections can easily be obtained from others. In this
paper we describe all bijections we were able to find in the
literature and show how they are related to each other via
``trivial'' bijections. We classify the bijections according to
statistics preserved (from a fixed, but large, set of statistics),
obtaining substantial extensions of known results. Thus, we give a
comprehensive survey and a systematic analysis of these bijections.
We also give a recursive description of the algorithmic bijection
given by Richards in 1988 (combined with a bijection by Knuth from
1969). This bijection is equivalent to the celebrated bijection of
Simion and Schmidt (1985), as well as to the bijection given by
Krattenthaler in 2001, and it respects 11 statistics --- the largest
number of statistics any of the bijections respects.
\end{abstract}
\maketitle
\setcounter{tocdepth}{1}
\tableofcontents
%First page headline in LaTeX for S\'eminaire Lotharingien de Combinatoire
%--first part
\thispagestyle{myheadings}
\font\rms=cmr8
\font\its=cmti8
\font\bfs=cmbx8
\markright{\its S\'eminaire Lotharingien de
Combinatoire \bfs 60 \rms (2008), Article~B60d\hfill}
\def\thepage{}
\section{Introduction and main results}
\label{sec:in}
Given two different bijections between two sets of combinatorial
objects, what does it mean to say that one bijection is better than
the other? Perhaps, a reasonable answer would be ``The one that is
easier to describe.'' While the ease of description and how easy it is
to prove properties of the bijection using the description is one
aspect to consider, an even more important aspect, in our opinion, is
how well the bijection reflects and translates properties of elements
of the respective sets.
A natural measure for a bijection between two sets of permutations,
then, is how many statistics the bijection preserves. Obviously, we
don't have an exhaustive list of permutation statistics, but we have
used the following list as our ``base'' set:
\begin{gather*}
\asc, \des, \exc, \ldr, \rdr, \lir, \rir, \zeil, \comp, \lmax, \lmin,
\rmax, \rmin,\\
\head, \last, \peak, \valley, \lds, \lis, \rank, \cyc, \fp, \slmax.
\end{gather*}
These are defined in Section~\ref{sec:stat}. To make sure we find all
statistics that a given bijection ``essentially'' preserves, we
include in our list of statistics those that are obtained from our
``basic'' statistics by applying to them the {\em trivial bijections}
on permutations ({\em reverse=r}, {\em complement=c}, {\em
inverse=i\/}) and their compositions. Moreover, for each statistic
stat, in this extended list we consider two other statistics:
$\textrm{n-stat}(\pi) = n-\textrm{stat}(\pi)$ and
$\textrm{m-stat}(\pi) = n+1-\textrm{stat}(\pi)$, where $n$ is the
length of the permutation. The meaning of n-stat or m-stat is
often ``non-stat''; for example, n-fix counts non-fixed-points.
%First page headline in AmS-LaTeX for S\'eminaire Lotharingien de Combinatoire
%--restoring the headers and pagenumbering
\pagenumbering{arabic}
\addtocounter{page}{1}
\markboth{\SMALL ANDERS CLAESSON AND SERGEY KITAEV}{\SMALL CLASSIFICATION OF BIJECTIONS}
%
%
This way each basic statistic gives rise to 24 statistics. The base
set contains 23 statistics, giving a total of 552 statistics. There
are, however, many statistics in that set that are equal as functions;
for instance, $\des = \ascR$, and $\peak = \peakR = \valleyC$, where
we use a dot to denote composition of functions. The classes of equal
statistics are listed in the Appendix (Section~\ref{App}). To prove
the correctness of this partitioning is a trivial but very lengthy
task. Thus we omit giving that proof. Choosing one representative from
each of the classes of equal statistics results in a final set of
$148$ statistics; we call this set \STAT.
In the theorems below, the statistics presented are linearly
independent. An example of linear dependence among the statistics
over permutations avoiding $132$ is $\lmin -\lmax + \Ndes -\head = 0$.
The results below are also maximal in that they cannot be
non-trivially extended using statistics from $\STAT$. That is, adding
one more pair of equidistributed statistics from \STAT\ to any of the
results would create a linear dependency among the statistics.
A permutation $\pi=a_1a_2\dots a_n$ avoids the \emph{pattern} 321 if
there are no indices $ii$;
\item[$\fp\, = $] number of fixed points: positions $i$ such that $a_i=i$;
\item[$\head\, = $] first element: $\head(\pi)=a_1$;
\item[$\last\, = $] last element: $\last(\pi)=a_n$;
\item[$\ldr\, = $] length of the leftmost decreasing run: largest $i$
such that $a_1>a_2>\dots>a_i$;
\item[$\lds\, = $] length of the longest decreasing sequence in a
permutation;
\item[$\lir\, = $] length of the leftmost increasing run: largest $i$
such that $a_1a_{i+1}$;
\item[$\rank\, = $] largest $k$ such that $a_i>k$ for all $i\leq k$ (see
\cite{EP04});
\item[$\rdr\, = $] $\lirR\,=\,$ length of the rightmost decreasing run;
\item[$\rmax\, = $] number of right-to-left maxima;
\item[$\rmin\, = $] number of right-to-left minima;
\item[$\rir\, = $] $\ldrR \,=\,$ length of the rightmost increasing run;
\item[$\slmax\, = $] the number of letters to the left of second
left-to-right maximum in $\pi\infty$: largest $i$ such that $a_1\geq
a_1$, $a_1\geq a_2$, \dots, $a_1\geq a_i$;
\item[$\valley\, = $] number of valleys: positions $i$ in $\pi$ such that
$a_{i-1}>a_i[F]{7} &6 &*=<3.5ex>[F]{9} &8 \\
& & 2 &4 &*=<3.5ex>[F]{10}&1 &3 &5 &*=<3.5ex>[F]{7} &6 &*=<3.5ex>[F]{9} &8 \\
\pi'&=& 2 &4 &*=<3.5ex>[F]{7} &1 &3 &5 &*=<3.5ex>[F]{9} &6 &*=<3.5ex>[F]{10} &8
}}
$$ In the first row we box the left-to-right maxima to the right of
$1$ that are not right-to-left minima. Here, those are $7$ and $9$. In
the second row we insert a new largest letter, $10$, immediately to
the left of $1$ and box it. Finally, in the third row, we cyclically
shift the sequence of boxed letter one step to the left, thus
obtaining $\pi'$. Let us call this map $\beta$.
The induced map $\CK$, between $231$- and $321$-avoiding permutations
is then formally defined by
$$
\CK(\emptyword) = \emptyword;\quad
\CK(\alpha(\sigma)) = \beta(\CK(\sigma));\quad
\CK(\sigma\oplus\tau) = \CK(\tau)\oplus\CK(\sigma).
$$
As an example, consider the permutation $5213476$ in $\sym_6(231)$. Decompose
it using $\oplus$ and $\alpha$:
$$
5213476
= 52134\oplus 21
= \alpha(2134)\oplus\alpha(1)
= \alpha(\alpha(1)\oplus 1\oplus 1)\oplus\alpha(1).
$$
Reverse the order of summands and change each $\alpha$ to $\beta$:
$$
\beta(1) \oplus \beta(1\oplus 1\oplus \beta(1))
= 21\oplus\beta(1243)
= 21\oplus 41253
= 2163475.
$$
In conclusion, $\CK(5213476) = 2163475$.
\section{Proof of Theorem~\ref{relations}}
\label{sec:relations}
In the following five subsections we shall prove the equalities of
Theorem~\ref{relations} --- one subsection for each equality. The last
statement of Theorem~\ref{relations}, that there can be no other
relations than the ones presented, is easily realized as follows: The
set \STAT\ is by definition closed with respect to the trivial
bijections, meaning that if $f$ is a trivial bijection and
$\textrm{stat}\in\STAT$, then $\textrm{stat}.\!f\in \STAT$. Thus, two
bijections related by trivial bijections will preserve the same number
of statistics from \STAT. Consequently, bijections preserving
different number of statistics (from \STAT) cannot be related by
trivial bijections.
\subsection{Simion--Schmidt versus \CK}
We prepare for this proof by characterizing the Simion--Schmidt
bijection in terms of left-to-right minima. (That characterization can
be said to be implicit in \cite{SS85}.) We also characterize the
bijection \CK\ in terms of right-to-left minima.
\begin{definition}
For a permutation $\pi = a_1a_2\dots a_n$ of length $n$, define
$$\LMIN(\pi) = \big\{\,(i,a_i)
\;\big\vert\;\text{$a_i$ is a left-to-right minima in $\pi$} \,\big\}
$$ as the set of positions of left-to-right minima together with
their values. Also, define $\sym_n/\LMIN$ as the set of equivalence
classes with respect to the equivalence induced by $\LMIN$: that is,
$\pi$ is equivalent to $\tau$ if\/ $\LMIN(\pi) =
\LMIN(\tau)$. Similarly, define $\RMIN$, $\LMAX$ and $\RMAX$.
\end{definition}
The cardinality of $\LMIN(\sym_n)=\{\LMIN(\pi) \mid\pi\in\sym_n \}$ is
easily seen to be $C_n$, the $n$-th Catalan number. The following
lemma strengthens that observation:
\begin{lemma}\label{lemma:lmin}
Each equivalence class in $\sym_n/\LMIN$ contains exactly one
permutation that avoids $123$ and one that avoids $132$. In other
words, both $\sym_n(123)$ and $\sym_n(132)$ are complete sets of
representatives for $\sym_n/\LMIN$.
\end{lemma}
\begin{proof}
Given a set $L$ in $\LMIN(\sym_n)$, this is how we construct the
corresponding permutation $\tau=c_1c_2\dots c_n$ in $\sym_n(132)$:
For $i$ from $1$ to $n$, if $(i,a)$ is in $L$ let $c_i = a$;
otherwise, let $c_j$ be the smallest letter not used that is greater
than all the letters used thus far.
Given a set $L$ in $\LMIN(\sym_n)$, this is how we construct the
corresponding permutation $\pi=a_1a_2\dots a_n$ in $\sym_n(123)$:
For $i$ from $1$ to $n$, if $(i,c)$ is in $L$ let $a_i = c$;
otherwise, let $a_j$ be the largest letter not used thus far.
It is easy to see that filling in the letters in any other way than
the two ways described will either change the sequence of
left-to-right minima or result in an occurrence of $132$ or $123$.
\end{proof}
As an illustration of the preceding proof, with
$L=\{(1,6),(3,3),(4,2),(6,1)\}$ we get $67324158$ in $\sym_8(132)$ and
$68327154$ in $\sym_8(123)$.
Using Lemma~\ref{lemma:lmin} we can thus define a bijection between
$\sym_n(123)$ and $\sym_n(132)$ by letting $\pi$ correspond to $\sigma$
if $\LMIN(\pi) = \LMIN(\sigma)$. However, this map is not new --- it
is the Simion--Schmidt bijection:
\begin{lemma}\label{lemma:SiS}
For $\pi$ in $\sym_n(123)$ and $\sigma$ in $\sym_n(132)$, the
following two statements are equivalent:
\begin{enumerate}
\item $\SiS(\pi) = \sigma$;
\item $\LMIN(\pi) = \LMIN(\sigma)$.
\end{enumerate}
\end{lemma}
Indeed, looking at the algorithm defining the Simion--Schmidt
bijection we see that the variable $x$ keeps track of the smallest
letter read thus far; lines~3 and 4 express that left-to-right minima
are left unchanged; and line~6 assigns $c_j$ to be the smallest letter
not used that is greater than all the letters used thus far (as
described above).
Here is a characterization of $\CK$ in terms of $\RMIN$:
\begin{lemma}\label{lemma:CK}
For $\pi$ in $\sym_n(231)$ and $\sigma$ in $\sym_n(321)$, the
following two statements are equivalent:
\begin{enumerate}
\item $\CK(\pi)=\sigma$;
\item $(n+1-i,a)\in \RMIN(\pi) \iff (n+1-a,i)\in \RMIN(\sigma)$.
\end{enumerate}
\end{lemma}
\begin{proof}
That the latter statement characterizes a bijection from
$\sym_n(231)$ to $\sym_n(321)$ follows from Lemma~\ref{lemma:lmin},
so all we need to show is that $\CK$ is that bijection.
We use induction on $n$, the length of the permutation. The case
$n=1$ is obvious: the right-to-left minimum $(1,1)$ goes to the
right-to-left minimum $(1,1)$. For the induction step we distinguish
two cases: $\pi$ is decomposable and $\pi$ is indecomposable (see
Section~\ref{sec:CK} for definitions).
Suppose that $\pi$ is indecomposable, and hence $\pi =
\alpha(\sigma)$ for some $\sigma$. By definition,
$\CK(\pi)=\beta(\CK(\sigma))$. The claim follows from the
following equivalences:
\begin{align*}
(n+1-i,a)\in \RMIN(\pi)
&\iff (n-i,a)\in \RMIN(\sigma) \\
&\iff (n-a,i)\in \RMIN \CK(\sigma) \\
&\iff (n+1-a,i)\in \RMIN \CK(\pi).
\end{align*}
Here, the first equivalence is immediate from the definition of
$\alpha$ --- recall that all $\alpha$ does is to insert a new largest
letter in front of $\sigma$. The second equivalence holds by
induction. The third equivalence follows from the definition of
$\beta$: the cyclic shift involves no right-to-left minima and the
space for the new letter is created to the left of the letter
$1$; therefore, $1$ is added to the indices of right-to-left minima.
Suppose $\pi=\tau\oplus\rho$ is decomposable, and let $k=|\tau|$
and $\ell=|\rho|$. By definition,
$\CK(\pi)=\CK(\rho)\oplus\CK(\tau)$. We have
\begin{align*}
&(n+1-i,a)\in\RMIN(\pi) \\
&\iff (n+1-i,a)\in\RMIN(\tau)\text{ or }(\ell+1-i,a-k)\in\RMIN(\rho)
&&\text{def' of $\oplus$} \\
&\iff (k+1-(i-\ell),a)\in\RMIN(\tau)\text{ or }(\ell+1-i,a-k)\in\RMIN(\rho)
&&\text{$n=k+\ell$} \\
&\iff (k+1-a,i-\ell)\in\RMIN\CK(\tau)\text{ or }
(\ell+1-(a-k),i)\in\RMIN\CK(\rho)
&&\text{induction} \\
&\iff (k+1-a,i-\ell)\in\RMIN\CK(\tau)\text{ or }(n+1-a,i)\in\RMIN\CK(\rho)
&&\text{$n=k+\ell$} \\
&\iff (n+1-a,i)\in\RMIN(\CK(\rho)\oplus\CK(\tau))
&&\text{def' of $\oplus$}
\end{align*}
from which the claim follows.
\end{proof}
We now turn to the proof of the first identity of
Theorem~\ref{relations}. It is equivalent to
$$
\inverse\,\circ \,
\SiS\,\circ\,\reverse\,\circ\
\CK\,\circ\,\reverse\ =\ \identity.
$$
With all the preparation we have done, this is easy to prove:
\begin{align*}
(i,a)\in\LMIN(\pi)
&\iff (n+1-i,a)\in\RMIN.\reverse(\pi) \\
&\iff (n+1-a,i)\in\RMIN.\CK.\reverse(\pi) \\
&\iff (a,i)\in\LMIN.\reverse.\CK.\reverse(\pi) \\
&\iff (a,i)\in\LMIN.\SiS.\reverse.\CK.\reverse(\pi) \\
&\iff (i,a)\in\LMIN.\inverse.\SiS.\reverse.\CK.\reverse(\pi).
\end{align*}
\subsection{Simion--Schmidt versus Krattenthaler}
In Lemma~\ref{lemma:SiS} we characterized the Simion--Schmidt
bijection. We shall do the same for Krattenthaler's bijection. We
start by looking at the standard bijection from 132-avoiding
permutations to Dyck paths (as defined in Section~\ref{subsec:Knuth}).
\newcommand{\U}{\mathfrak{u}}
\newcommand{\D}{\mathfrak{d}}
Let $P$ be a Dyck path of length $2n$; index its up- and down-steps
$1$ through $n$. For instance,
$$P = u_1u_2u_3d_1d_2u_4u_5d_3d_4u_6d_5d_6.
$$
A \emph{peak} in a Dyck path is an up-step directly followed by a
down-step. Define
$$\PEAK(P) = \{\, (i,j) \mid u_id_j \text{ is a peak in }P \,\}.
$$
For instance, with $P$ as before, we have $\PEAK(P)=\{(3,1),(5,3),(6,5)\}$.
\begin{lemma}\label{lemma:standard}
Let $f$ be the standard bijection from $\sym_n(132)$ to $\dyck_n$.
For $\pi$ in $\sym_n(132)$ and $P$ in $\dyck_n$, the following two
statements are equivalent:
\begin{enumerate}
\item $f(\pi) = P$;
\item $(i,n+1-a)\in\LMIN(\pi) \iff (a,i)\in\PEAK(P)$.
\end{enumerate}
\end{lemma}
\begin{proof}
Clearly, knowing $\PEAK(P)$ is equivalent to knowing the path
$P$. Thus the second statement determines a bijection (by
Lemma~\ref{lemma:lmin}). It remains to show that the first statement
implies the second.
We shall use induction on the length of the permutation. Assume that
$\pi^r$ is indecomposable (with respect to $\oplus$). It is easy to
see that $\pi$ ends with its largest letter. Hence, $\pi=\tau n$ for
some $\tau$ in $\sym_{n-1}(132)$. Let $Q=f(\tau)$. Then
$P=f(\pi)=uf(\tau)d=uQd$ and
\begin{align*}
(i,n+1-a)\in\LMIN(\pi)
& \iff (i,n+1-a)=(i,n-(a-1))\in\LMIN(\tau) \\
& \iff (a-1,i)\in\PEAK(Q) \\
& \iff (a,i)\in\PEAK(P).
\end{align*}
Assume that $\pi^r$ is decomposable, so $\pi^r = \rho^r\oplus\tau^r$
for some $\tau$ in $\sym_{k}(132)$ and $\rho$ in $\sym_{\ell}(132)$
with both $k$ and $\ell$ positive and $k+\ell=n$. Let
$Q=f(\tau)$ and $R=f(\rho)$. Then $P=f(\pi)=f(\tau)f(\rho)=QR$ and
\begin{align*}
& (i,n+1-a)\in\LMIN(\pi) \\
& \iff (i,k+1-a)\in\LMIN(\tau)\text{ or } (i-k,n+1-a)\in\LMIN(\rho) \\
& \iff (i,k+1-a)\in\LMIN(\tau)\text{ or } (i-k,\ell+1-(a-k))\in\LMIN(\rho) \\
& \iff (a,i)\in\PEAK(Q)\text{ or } (a-k,i-k)\in\PEAK(R) \\
& \iff (a,i)\in\PEAK(P),
\end{align*}
which completes the proof.
\end{proof}
\begin{lemma}\label{lemma:g}
Let $K$ be Krattenthaler's bijection from $\sym_n(123)$ to $\dyck_n$
as described in Section~\ref{subsec:Krattan}. For $\pi$ in
$\sym_n(123)$ and $P$ in $\dyck_n$, the following two statements are
equivalent:
\begin{enumerate}
\item $K(\pi) = P$;
\item $(i,n+1-a)\in\RMAX(\pi) \iff (a,i)\in\PEAK(P)$.
\end{enumerate}
\end{lemma}
\begin{proof}
This is an easy consequence of $K$'s definition.
\end{proof}
Putting Lemma~\ref{lemma:standard} and Lemma~\ref{lemma:g} together we get
the desired characterization of Krattenthaler's bijection.
\begin{lemma}\label{lemma:Krattan}
For $\pi$ in $\sym_n(123)$ and $\sigma$ in $\sym_n(132)$, the
following two statements are equivalent:
\begin{enumerate}
\item $\Krattan(\pi) = \sigma$;
\item $(n+1-i,a)\in\RMAX(\pi) \iff (n+1-a,i)\in\LMIN(\sigma)$.
\end{enumerate}
\end{lemma}
Having established this characterization, the rest is easy. From the
sequence of equivalences
\begin{align*}
&(i,a)\in\LMIN(\pi) \\
&\iff (n+1-i,a)\in\RMIN.\reverse(\pi) \\
&\iff (a,n+1-i)\in\LMAX.\inverse.\reverse(\pi)\\
&\iff (n+1-a,n+1-i)\in\RMAX.\reverse.\inverse.\reverse(\pi) \\
&\iff (i,a)\in\LMIN.\Krattan.\reverse.\inverse.\reverse(\pi) \\
&\iff (i,a)\in\LMIN.\SiS^{-1}.\Krattan.\reverse.\inverse.\reverse(\pi)
\end{align*}
it follows that
$$
\SiS^{-1}\circ\,\Krattan\,\circ\,\reverse\,\circ\,\inverse\circ\,\reverse
\ =\ \identity
$$
as desired.
\subsection{Knuth--Richards versus \CK}\label{KR-vs-CK}
Consider the Dyck path $P=uudduududuuddd$ of semi-length $n=7$. Let us
index its up- and down-steps 1 through $n$:
$$P = u_1u_2d_1d_2u_3u_4d_3u_5d_4u_6u_7d_5d_6d_7.
$$ From this path we shall construct a permutation $\pi=a_1a_2\dots
a_n$. Scan $P$'s down-steps from left to right: if $d_i$ is preceded
by an up-step $u_j$, then let $a_{n+1-j}=i$; otherwise, let $j$ be the
largest value for which $a_j$ is unset, and let $a_j = i$. In our
example, this leads to:
\begin{enumerate}
\item $d_1$ is preceded by the up-step $u_2$; let $a_{8-2}=a_6=1$.
\item $d_2$ is preceded by a down-step; let $j=7$ and $a_7=2$.
\item $d_3$ is preceded by the up-step $u_4$; let $a_{8-4}=a_4=3$.
\item $d_4$ is preceded by the up-step $u_5$; let $a_{8-5}=a_3=4$.
\item $d_5$ is preceded by the up-step $u_7$; let $a_{8-7}=a_1=5$.
\item $d_6$ is preceded by a down-step; let $j=5$ and $a_5=6$.
\item $d_7$ is preceded by a down-step; let $j=2$ and $a_2=7$.
\end{enumerate}
The resulting permutation is $\pi=5743612$. What we have just
described is the algorithm defining Richard's bijection. Lines 3, 4 and
5 of that algorithm cover the case when $d_i$ is preceded by an
up-step; lines 6, 7 and 8 the case when $d_i$ is preceded by a
down-step.
Plainly, if $d_i$ is preceded by an up-step $u_i$ then $u_id_j$ is a
peak in $P$. Moreover, $a_{n+1-j}=i$ is a left-to-right minimum in the
corresponding permutation. To be precise we have the following lemma.
\begin{lemma}
Let $\Ri$ be Richards' bijection from $\sym_n(123)$ to $\dyck_n$ as
described in Section~\ref{subsec:KRi}. For $\pi$ in $\sym_n(123)$
and $P$ in $\dyck_n$, the following two statements are equivalent:
\begin{enumerate}
\item $\Ri(P) = \pi$;
\item $(n+1-i,a)\in\LMIN(\pi) \iff (i,a)\in\PEAK(P)$.
\end{enumerate}
\end{lemma}
Using Lemma~\ref{lemma:standard} we get a characterization of the
Knuth--Richards bijection:
\begin{lemma}\label{lemma:KRi}
For $\pi$ in $\sym_n(132)$ and $\sigma$ in $\sym_n(123)$, the
following two statements are equivalent:
\begin{enumerate}
\item $\KRi(\pi) = \sigma$;
\item $(i,a)\in\LMIN(\pi) \iff (a,i)\in\LMIN(\sigma)$.
\end{enumerate}
\end{lemma}
The rest is easy. We have
\begin{align*}
(i, a) \in \LMIN(\pi)
& \iff (a,i) \in\LMIN.\KRi^{-1}(\pi) \\
& \iff (n+1-a,i) \in\RMIN.\reverse.\KRi^{-1}(\pi) \\
& \iff (n+1-i,a) \in\RMIN.\CK.\reverse.\KRi^{-1}(\pi) \\
& \iff (i,a) \in\LMIN.\reverse.\CK.\reverse.\KRi^{-1}(\pi)
\end{align*}
and hence
$$\reverse\,\circ\,\CK\,\circ\,\reverse\,\circ\,\KRi^{-1}\, =\ \identity.
$$
\subsection{Simion--Schmidt versus Mansour--Deng--Du}
We will show that
$$
\MDD\,=\,\reverse\,\circ\,\SiS\,\circ\,\reverse.
$$
Due to Lemma~\ref{lemma:SiS} it suffices to prove the following lemma.
\begin{lemma}
For $\pi$ in $\sym_n(132)$ and $\pi'$ in $\sym_n(123)$, the
following two statements are equivalent:
\begin{enumerate}
\item $\MDD(\pi) = \pi'$;
\item $\RMIN(\pi) = \RMIN(\pi')$.
\end{enumerate}
\end{lemma}
\begin{proof}
Assume that $\pi$ and $\pi'$ are as above. According to the proofs of
Corollaries~\cite[Cor.~4]{MDD} and~\cite[Cor.~16]{MDD}, the positions
of right-to-left minima in $\pi$ and $\pi'$ are the same and, in
particular, $\rmin(\pi)=\rmin(\pi')$. Thus we only need to prove that
right-to-left minima are preserved in value under the Mansour--Deng--Du
bijection. Equivalently, we need to prove that
non-right-to-left-minima ($\Nrmin$) are preserved in value.
One can see that a letter $a$ is an $\Nrmin$ in $\pi$ if and only if
the reduced decomposition of $\pi$ contains a run of adjacent
transpositions $(s_{a-1}\dots)$. In particular, $a=1$ is always an
$\Nrmin$. Thus $\pi=\sigma_1\dots\sigma_k$ and
$\pi'=\sigma'_1\dots\sigma'_k$ for $k=n-\rmin(\pi)$. That
is, $\pi$ and $\pi'$ have the same number of runs of adjacent
transpositions in the reduced decompositions and it remains to show
that the first letter of $\sigma_j$ equals the first letter of
$\sigma'_j$ whenever $1\leq j\leq k$.
Let $P$ be the intermediate Dyck path and consider its $(x+y)$- and
$(x-y)$-labellings of $P$. Note that cells touching the $x$-axis
receive the same labels under both labellings. From this, and the way
that the zigzag and trapezoidal decompositions are constructed, it
immediately follows that $\sigma_k$ and $\sigma'_k$ begin with the
same letter, namely, the label $C$ of the rightmost cell.
We now proceed by induction on the number of essential cells. If there
are no essential cells, then the statement is true. Suppose we have
$k>0$ essential cells. Remove the rightmost zigzag strip to get a Dyck
path $P'$. Note that $|P'| = |P|-2$ and that $P'$ has $k-1$ essential
cells. Clearly, the permutation corresponding to the $(x+y)$-labeling
of $P'$ is $\tau=\sigma_1\dots\sigma_{k-1}$. Let the
permutation corresponding to the $(x-y)$-labeling of $P'$ be
$\tau''=\sigma_1''\dots\sigma_{k-1}''$. From the
properties of the $(x-y)$-labeling, a cell labeled $Q\neq C$ is the
rightmost cell of a trapezoidal strip in $P$ if and only if $Q$ is the
rightmost cell of a trapezoidal strip in $P'$. This means that
$\sigma_i'$ and $\sigma_i''$ begin with the same letter for $1\leq
i\leq k-1$. The desired result now follows from the induction
hypothesis applied to $P'$, $\tau$ and $\tau''$.
\end{proof}
\subsection{Billey--Jockusch--Stanley--Reifegerste versus Knuth--Rotem}
We will\break show the following equality:
\begin{equation}\label{eq:Astrid_KRo}
\Astrid\,=\,
\inverse\,\circ\,\KRo\,\circ\,\inverse.
\end{equation}
The Billey--Jockusch--Stanley--Reifegerste bijection is defined by values
and positions of excedances. Suppose that $\pi=a_1a_2\dots a_n$ is a
321-avoiding permutation and that $\pi'$ is the image of $\pi$ under
the Billey--Jockusch--Stanley--Reifegerste bijection. The only
permutation of length $n$ without excedances is $12\dots n$. As is
easy to see, that permutation is fixed by both sides of
identity~\eqref{eq:Astrid_KRo}. So we can assume that $\pi$ has at
least one excedance. Let $\pi$ have an excedance $a$ at position $i$,
denoted $(i,a)$. Also, let $(j,b)$ be the excedance closest to the
left of $(i,a)$. If no such excedance exists we define $j=0$. Note
that $bi$, $b>j$ and $b2$. Let $D$ be the diagram constructed from the
sequence (in $\B_n$) corresponding to $\pi$. Let $P$ be the Dyck path we
read from $D$. Let $(r,s)$ be the coordinate in $D$ corresponding to
the first return to the $x$-axis in $P$. In particular, $r=s$.
Consider the following four cases.
{\sc Case 1:} $s=0$. This case is sketched in
Figure~\ref{proof001}B. Note that $a>i+1$, and we can remove the first
step and the last step of the path, thus shifting the path one step to
the left. This corresponds to adjoining $n$ to the right side of the
permutation obtained inductively from the reduced Dyck path. Moreover,
the number of steps is now $2(n-1)$, $i$ and $j$ are unchanged, while
$a$ becomes $a-1$. From the induction hypothesis it follows that $j+1$
will be in position $(n-1)+2-(a-1)=n+2-a$, as desired.
{\sc Case 2:} $n>s>i$. From the definition of the standard bijection
we see that the permutation $f^{-1}(P)$ is of the form $\pi'=\sigma
n\tau$ where each letter of $\sigma$ is larger than any letter of
$\tau$; the largest letter, $n$, is in position $n-s+1$; part
$\sigma$ is obtained inductively from the portion of the path above
the line $y=s$; and $\tau$ is obtained inductively from the portion of
the path below the line $y=s$. Applying the induction to $\tau$ we see
that the letter $j+1$ is in position $(s-1)+2-a=s+1-a$. Thus, in
$\pi'$, the letter $j+1$ is in position $(s+1-a)+(n-s+1)=n+2-a$.
{\sc Case 3:} $0