\documentclass[12pt,reqno]{article}
\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}
\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}
\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}
\usepackage{color}
\usepackage{fullpage}
\usepackage{float}
\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{subfigure}
\usepackage{multirow}
\usepackage[Large]{caption}
\usepackage[table]{xcolor}
\catcode`~=11 \def\UrlSpecials{\do\~{\kern -.15em\lower .7ex\hbox{~}\kern .04em}} \catcode`~=13
\newcommand{\Blocks}{\mathrm{Blocks}}
\newcommand{\Classes}{\mathrm{Classes}}
\newcommand{\Num}{\#\Classes}
\newcommand{\Eq}{\mathrm{Eq}}
\newcommand{\fourdots}{{\begin{smallmatrix}
\cdot\kern -1.8pt & \cdot \\[-2.7pt]
\cdot\kern -1.8pt& \cdot \end{smallmatrix}}}
\newcommand{\twolines}{{\bf \kern 0.6pt\vrule height6pt depth0pt width0.5pt
\kern 4pt \vrule height6pt depth0pt width0.5pt}}
\newcommand{\oursquare}{\square}
\newcommand{\ourstar}{*}
\newcommand{\inv}{\mathrm{inv}}
\newcommand{\Inv}{\mathrm{Inv}}
\newcommand{\floor}[1]{\lfloor #1 \rfloor}
\newcommand{\ceiling}[1]{\lceil #1 \rceil}
\newcommand{\cred}[1]{{\color{red}#1}}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}
\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}
\begin{document}
\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\begin{center}
\vskip 1cm{\LARGE\bf Equivalence Classes of
Permutations under \\
\vskip .03in
Various Relations Generated by Constrained \\
\vskip .11in
Transpositions
}
\vskip 1cm
\large
Steven Linton \\
Centre for Interdisciplinary Research in Computational Algebra \\
University of St Andrews\\
St Andrews, Fife KY16 9AJ \\
Scotland \\
United Kingdom \\
\href{mailto:steve.linton@st-andrews.ac.uk}{\tt steve.linton@st-andrews.ac.uk}\\
\ \\
James Propp \\
University of Massachusetts\\
Lowell, MA 01854 \\
USA\\
\ \\
Tom Roby\\
University of Connecticut\\
Storrs, CT 06269 \\
USA\\
\href{mailto:tom.roby@uconn.edu}{\tt tom.roby@uconn.edu}\\
\ \\
Julian West \\
University of Bristol\\
Bristol BS8 1TW \\
England \\
\href{mailto:aeijlnstuw@gmail.com}{\tt aeijlnstuw@gmail.com}
\end{center}
\newpage
\begin{abstract}
We consider a large family of equivalence relations on the symmetric
group of permutations of $n$ that generalize those discovered by Knuth
in his study of the Robinson-Schensted correspondence. In our most
general setting, two permutations are equivalent if one can be obtained
from the other by a sequence of pattern-replacing moves of prescribed
form; however, we limit our focus to patterns where two elements are
transposed, subject to the constraint that a third element of a suitable
type be in a suitable position. For various instances of the problem,
we compute the number of equivalence classes, determine how many
$n$-permutations are equivalent to the identity permutation, or
characterize this equivalence class. Although our results feature
familiar integer sequences (e.g., Catalan, Fibonacci, and Tribonacci
numbers) and special classes of permutations (layered, connected, and
123-avoiding), some of the sequences that arise appear to be new.
\end{abstract}
\section{Introduction and motivation}\label{sec:int}
We consider a family of equivalence relations on permutations in
$S_{n}$ in which two permutations are considered to be equivalent if
one can be converted into the other by replacing a short subsequence of
(not necessarily adjacent) elements by the same elements permuted
in a specific fashion, or (extending by transitivity) by a sequence
of such moves. These generalize the relations discovered by Knuth
in his study of the Robinson-Schensted correspondence, though the
original motivations for this project were unrelated. We begin the
systematic study of such equivalence relations, connecting them with
integer sequences both familiar and (apparently) new.
Consider the following three examples of turning one 7-permutation into another
in which selected 3-subsequences (marked in \textbf{bold}) are re-ordered:
\begin{eqnarray}\label{eqn:eg1}
12\mathbf{34}56\mathbf{7} &\rightarrow & 12\mathbf{74}56\mathbf{3}\\
\mathbf{127}4563 &\rightarrow & \mathbf{721}4563\\
721\mathbf{456}3 &\rightarrow &721\mathbf{654}3
\end{eqnarray}
In each of these examples, a subsequence of \textit{pattern} 123 (i.e.,
a triple of not necessarily adjacent entries whose elements are in the
same relative order as 123) is replaced by the same set of elements arranged
in the pattern 321. Allowing replacements of a designated kind to be
performed ad libitum, in reverse as well as forward, induces an equivalence
relation on the symmetric group $S_{7}$. Accordingly we can say that the
permutations 1234567, 1274563, 7214563, and 7216543 are all equivalent
under the replacement $123 \leftrightarrow 321$.
Interesting enumerative questions arise when the elements being replaced
are allowed to be in general position (Section~\ref{sec:gen}), when the
replacements are constrained to involve only adjacent elements
(Section~\ref{sec:adj}), and when replacements are constrained to affect
only subsequences of consecutive elements representing a run of
consecutive values (Section~\ref{sec:dbl}). Each of these respective
\emph{types} of replacements is illustrated in one of the three examples
above. It will be convenient to group subsequences that are allowed to
replace one another into sets, e.g., describing the three permutations
above as being ``$\{123,321 \}$-equivalent''. We may also wish to allow
more than one type of (bi-directional) replacement, such as both $123
\leftrightarrow 321$ and $123 \leftrightarrow 132$. If the intersection
of these sets is nonempty, the new relation can be described simply by
the union of the two sets: $\{123,132,321\} = \{123,321\} \cup
\{123,132\}$. To formalize this more generally we consider collections
of disjoint replacement sets that form a set partition of $S_{3}$; any
two patterns within the same set may replace one another within the
larger permutation to give an equivalent permutation.
Let $\pi \in S_{n}$, and let $P=\{B_{1},B_{2},\dots,
B_{t}\}$ be a (set) partition of $S_{k}$, where $k\leq n$. Each block
$B_{l}$ of $P$ represents a list of $k$-length patterns which can
replace one another. We call two permutations $P^{\fourdots}$-equivalent if one
can be obtained from the other by a sequence of replacements, each
replacing a subsequence of pattern $\sigma_{i}$
with the same elements in the pattern $\sigma_{j}$,
where $\sigma_{i}$ and $\sigma_{j}$ lie in the same block
$B_{l}$ of $P$. Let $\Eq^{\fourdots}(\pi,P)$ denote the set of permutations
equivalent to $\pi$ under $P^{\fourdots}$-equivalence; e.g.,
1234567, 7214563, and $7216543\in
\Eq^\fourdots\left(1274563,\big\{\{123,321\}\big\}\right)$.
Similarly we denote by $P^{\twolines}$ the equivalence
relation, and by $\Eq^{\twolines}(\pi,P)$ the equivalence
class of $\pi$, under replacement within $P$ only of adjacent elements; e.g.,
7214563 and $7216543 \in \Eq^\twolines\left(1274563,\big\{\{123,321\}\big\}\right)$.
We use $P^{\oursquare}$ and $\Eq^\oursquare(\pi,P)$ when both positions
and values are constrained, e.g.,
$7214563 \in \Eq^\oursquare\left(7216543,\big\{\{123,321\}\big\}\right)$.
To refer to such classes generically we use the notation
$\Eq^\ourstar(\pi,P)$. The automorphism $\pi\mapsto \pi^{-1} $ replaces
adjacency of positions with adjacency of values; hence, for the enumerative
questions we treat, there is no need to separately consider a fourth
case where we only constrain values to be adjacent.
The set of distinct equivalence classes into which $S_n$ splits under
an equivalence $P^{\ourstar}$ is denoted by $\Classes^\ourstar(n,P)$.
The present paper begins the study of these equivalence relations by
considering three types of questions:
(A) Compute the number of equivalence classes,
$\#\Classes^{\ourstar}(n,P)$, into which $S_{n}$ is partitioned.
(B) Compute the size, $\#\Eq^\ourstar(\iota_n,P)$, of the equivalence
class containing the identity $\iota _{n}=123\cdots n$.
(C) Characterize the set $\Eq^\ourstar(\iota_n,P)$ of
permutations equivalent to the identity.
Although the framework above allows for much greater generality, in this
paper we will mainly restrict our attention to replacements by patterns of
length $k=3$, and usually to replacement patterns built up from pairs in
which one permutation is the identity, and the other is a transposition
(i.e., fixes one of the elements). This is both to keep the paper within
reasonable bounds and so that the equivalence class of the identity
$12\dotsb n$ emerges as a large component of specific interest.
Omitting some cases by symmetry,
we have the following possible partitions of $S_{3}$, where (as usual)
we omit singleton blocks:
\begin{eqnarray*}
P_1 = \big\{ \{123, 132\} \big\}, \\
P_2 = \big\{ \{123, 213\} \big\}, \\
P_4 = \big\{ \{123, 321\} \big\}.
\end{eqnarray*}
We will also consider applying two of these replacement operations
simultaneously, and we will number the appropriate partitions as
\begin{eqnarray*}
P_3 = \big\{ \{123, 132, 213\} \big\}, \\
P_5 = \big\{ \{123, 132, 321\} \big\}, \\
P_6 = \big\{ \{123, 213, 321\} \big\},
\end{eqnarray*}
following the convention $P_{i+j} := P_i \vee P_j$, the \emph{join} of
these two partitions~\cite[ch.3]{StanleyEC1}. Indeed we
can allow all three replacements: $P_7 = \big\{ \{123, 132, 213, 321\} \big\}$.
(In fact, the cases $P_1$ and $P_2$ are equivalent by symmetry, as
are $P_5$ and $P_6$. We list $P_1$ and $P_2$ separately only
in order to consider their join.)
Our motivation for focussing attention on pairs of this form is that
we can then think of an operation, not in terms of replacing one
pattern by another, but simply in terms of \emph{swapping} two
elements within the pattern, with the third serving as a catalyst
enabling the swap. In a followup~\cite{PRW11} to the current paper, the
authors treat the remaining (non-swapping) cases for all partitions of
$S_{3}$ consisting of exactly one non-singleton block which contains the
identity $123$.
By far the best-known example of constrained swapping in permutations is
the \emph{Knuth Relations}~\cite{Knuth}, which allow the swap of
adjacent entries provided an intermediate value lies immediately to the
right or left. In the notation of this paper, they correspond to
$P^{\twolines}_{K}=\big\{ \{ 213,231\}, \{132,312\}\big\}$. Permutations
equivalent under this relation map to the same first coordinate
($P$-tableau) under the Robinson-Schensted correspondence.
Mark Haiman introduced the notion of \emph{dual equivalence} of
permutations: $\pi$ and $\tau$ are dual equivalent if one can be
obtained from the other by swaps of adjacent \emph{values} from the above
$P_{K}$, i.e., if their inverses are Knuth-equivalent, or
(equivalently) if they map to
the same second coordinate ($Q$-tableau) under the Robinson-Schensted
correspondence~\cite{HaimanDEq}. For the enumerative problems in this
paper, we get the same answers for Knuth and dual equivalence.
In her dissertation~\cite{AssafDEG} Sami Assaf constructed graphs (with
some extra structure) whose vertices are tableaux of a fixed shape
(which may be viewed as permutations via their ``reading words''), and
whose edges represent (elementary) dual equivalences between
vertices. For this particular relation (equivalently for the Knuth
relations), she was able to characterize the local structure of these
graphs, which she later used to give a combinatorial formula for the Schur
expansion of LLT polynomials and Macdonald polynomials. She also used
these, along with crystal graphs, to give a combinatorial realization of
Schur-Weyl duality~\cite{AssafSWD}.
Sergey Fomin has a very clear elementary exposition of how Knuth and dual
equivalence are related to the Robinson-Schensted correspondence,
Sch\"utzenberger's \textit{jeu de taquin}, and the Littlewood-Richardson
rule in~\cite[Ch.~7, App.~1]{StanleyEC2}. For the problems considered
above, the answers for $P_{K}^{\twolines}$ are well known to be: (A) the
number of involutions in $S_{n}$; (B) 1; and (C) $\{\iota_{n}\}$. In fact one
can compute $\#\Eq^{\twolines}(\pi ,P_{K})$ for any permutation $\pi$ by
using the Frame-Robinson-Thrall hook-length formula to compute the
number of standard Young tableaux of the \emph{shape} output by the
Robinson-Schensted correspondence applied to $\pi$.
Any of the relations we consider can be naturally generalized to operate
on $\mathcal{W}([n])$, the set of \textbf{words} (with repeated entries
allowed) on the alphabet $[n]$: for example, the relation $123
\leftrightarrow 321$ would imply also moves of the form
$112\leftrightarrow 211$ and $122\leftrightarrow 221$, treating letters
with the same label within a word as increasing from left to right. In
the case of the Knuth relations, the equivalence classes are simply the
\emph{elements} of the well-known \textit{plactic monoid} of Lascoux and
Sch\"utzenberger: $\mathcal{W}([n])/P_{K}$ \cite{LSPlactic, LLTPlactic}.
In \cite{Chinese}
the authors study the analogous
\textit{Chinese monoid}, which is $\mathcal{W}([n])/P_{3}$ (up to
the involution that reverses all words), for which they develop an
analogue of the Robinson-Schensted correspondence and count some of the
equivalence classes. It would be interesting to find variants of RSK
connected with the other moves we study, but we have not managed to do
this.
In recent work that was independently motivated~\cite{StanleyEquiv}, Richard
Stanley studies the equivalence given by allowing the transposition of
\emph{any} adjacent pair of elements whose values are also adjacent.
The corresponding partition of $S_{n}$ is a refinement
of all the classes we consider in Section~\ref{sec:dbl}. He counts the
number of equivalence classes and all their sizes, and also connects
$\Eq (\iota )$ to the set of linear extensions of a certain poset, whose
corresponding distributive lattice has a multiplicity-free flag
$h$-vector.
Given that the Knuth relations act on adjacent elements, and lead to
some deep combinatorial results, it is perhaps not surprising that the
most interesting problems and proofs in this paper are to be found in
Section~\ref{sec:adj}. A summary of our numbers and results is given
in Figure~\ref{fig:sum}.
An extended abstract of this paper appeared in the proceedings of
FPSAC10~\cite{LPRW}.
\begin{figure}[h]
\begin{center}
\caption{Summary of Results}
\label{fig:sum}
\medskip
\begin{minipage}[t]{\textwidth}
These tables give numerical values and names (when available) of the
sequences associated with enumerative questions (A) and (B). All
sequences begin with the value for $n=3$. Results proven in this paper
have a gray background; for other cases we lack even conjectural
formulae. Six-digit codes preceded by ``A'' cite specific sequences in
Sloane~\cite{OEIS}; those set in italic type were added to OEIS in
conjunction with this paper.
\end{minipage}
\medskip
\begin{tiny}
\begin{large}Number of classes\end{large}
\bigskip
\begin{tabular}{|c|l|l|l|l|}
\hline
\multicolumn{2}{|l|}{\multirow{2}{*}{\normalsize Transpositions}} & \small \S~2 & \small \S~3& \small\S~4 indices and\\
\multicolumn{2}{|l|}{} &{\small general} & {\small only indices adjacent} & {\small values adjacent} \\
\hline
(1) & $123 \leftrightarrow 132$ & \cellcolor{lightgray}[5, 14, 42, 132, 429] &{[5, 16, 62, 284, 1507, 9104]} & {[5, 20, 102, 626, 4458, 36144]} \\
\cline{1-2}
(2) & $123 \leftrightarrow 213$ & \cellcolor{lightgray}Catalan \seqnum{A000108} & \textit{\seqnum{A210667}} & \textit{\seqnum{A212580}}\\
\hline
\multirow{2}{*}{(4)} & \multirow{2}{*}{$123 \leftrightarrow 321$} & \cellcolor{lightgray}[5, 10, 3, 1, 1, 1] & {[5, 16, 60, 260, 1260, 6744] } & {[5, 20, 102, 626, 4458, 36144]} \\
& & \cellcolor{lightgray}trivial &\textit{\seqnum{A210668}} & \textit{\seqnum{A212580}}\\
\hline
\multirow{2}{*}{(3)} & \multirow{2}{*}{$123 \leftrightarrow 132 \leftrightarrow 213$} & \cellcolor{lightgray}[4, 8, 16, 32, 64, 128] & \cellcolor{lightgray}[4, 10, 26, 76, 232, 764] & {[4, 17, 89, 556, 4011, 32843]} \\
& & \cellcolor{lightgray}powers of 2 \seqnum{A000079} &\cellcolor{lightgray}involutions \seqnum{A000085} &\textit{\seqnum{A212581}}\\
\hline
(5) & $123 \leftrightarrow 132 \leftrightarrow 321$ & \cellcolor{lightgray}[4, 2, 1, 1, 1, 1] & {[4, 8, 14, 27, 68, 159, 496]} & {[4, 16, 84, 536, 3912, 32256]} \\
\cline{1-2}
(6) & $123 \leftrightarrow 213 \leftrightarrow 321$ & \cellcolor{lightgray}trivial &\textit{\seqnum{A210669}} &\textit{\seqnum{A212432}} \\
\hline
\multirow{2}{*}{(7)} & $123 \leftrightarrow 132$ & \cellcolor{lightgray}[3, 2, 1, 1, 1, 1] & {[3, 4, 5, 8, 11, 20, 29, 57]} & {[3, 13, 71, 470, 3497]} \\
& $\leftrightarrow 213 \leftrightarrow 321$ & \cellcolor{lightgray}trivial &\textit{\seqnum{A210671}} &\textit{\seqnum{A212433}}\\
\hline
\end{tabular}
\vspace{3mm}
\begin{large}Size of class containing identity\end{large}
\bigskip
\begin{tabular}{|c|l|l|l|l|}
\hline
\multicolumn{2}{|l|}{\multirow{2}{*}{\normalsize Transpositions}} & \small \S~2 & \small \S~3& \small\S~4 indices and\\
\multicolumn{2}{|l|}{} &{\small general} & {\small only indices adjacent} & {\small values adjacent} \\
\hline
(1) & $123 \leftrightarrow 132$ &\cellcolor{lightgray}[2, 6, 24, 120, 720] &\cellcolor{lightgray}[2, 4, 12, 36, 144, 576, 2880] & \cellcolor{lightgray}[2, 3, 5, 8, 13, 21, 34, 55] \\
\cline{1-2}
(2) & $123 \leftrightarrow 213$ & \cellcolor{lightgray}$(n-1)!$ \seqnum{A000142} &\cellcolor{lightgray}prod. of adj. fact. \seqnum{A010551} & \cellcolor{lightgray}Fibonacci \seqnum{A000045} \\
\hline
\multirow{2}{*}{(4)} & \multirow{2}{*}{$123 \leftrightarrow 321$} &\cellcolor{lightgray}[2, 4, 24, 720] &\cellcolor{lightgray}[2, 3, 6, 10, 20, 35, 70, 126] & \cellcolor{lightgray}[2, 3, 4, 6, 9, 13, 19, 28] \\
& &\cellcolor{lightgray}trivial & \cellcolor{lightgray}central bin. coeff.
\seqnum{A001405} & \cellcolor{lightgray}Comp. into \{1,3\} \seqnum{A000930} \\
\hline
\multirow{2}{*}{(3)} & \multirow{2}{*}{$123 \leftrightarrow 132 \leftrightarrow 213$} &\cellcolor{lightgray}[3, 13, 71, 461] & [3, 7, 35, 135, 945, 5193] &\cellcolor{lightgray}[3, 4, 8, 12, 21, 33, 55, 88] \\
& &\cellcolor{lightgray}connected \seqnum{A003319} & Chinese Monoid \textit{\seqnum{A212417}} &\cellcolor{lightgray}Fib. or Fib.$-1$ \seqnum{A052952} \\
\hline
(5) & $123 \leftrightarrow 132 \leftrightarrow 321$ &\cellcolor{lightgray}[3, 23, 120, 720]
&\cellcolor{lightgray}[3, 9, 54, 285, 2160, 15825] &\cellcolor{lightgray}[3, 5, 9, 17, 31, 57, 105, 193] \\
\cline{1-2}
(6) & $123 \leftrightarrow 213 \leftrightarrow 321$ &\cellcolor{lightgray}trivial &\cellcolor{lightgray}\textit{\seqnum{A212419}} &\cellcolor{lightgray}tribonacci numbers \seqnum{A000213} \\
\hline
\multirow{2}{*}{(7)} & $123 \leftrightarrow 132$ & \cellcolor{lightgray}[3, 23, 120, 720] &[4, 21, 116, 713, 5030] &\cellcolor{lightgray}[4, 6, 13, 23, 44, 80, 149, 273] \\
& $\leftrightarrow 213 \leftrightarrow 321$ &
\cellcolor{lightgray}trivial & \textit{\seqnum{A212419}}
&\cellcolor{lightgray}tribonacci \seqnum{A000073} $-[n\ \mathrm{ even}]$
\\
\hline
\end{tabular}
\end{tiny}
\end{center}
\end{figure}
If $\tau \in \Eq^\ourstar(\pi,P)$ we will say that $\tau$ is \emph{reachable}
from $\pi$ (under $P$). If $\Eq^\ourstar(\iota_n,P) = S_n$, then every
permutation in $S_n$ is reachable from every other, and we will say that
$S_n$ is \emph{connected} by $P$. If $\Eq^\ourstar(\pi,P) =\{\pi\}$
we will say that $\pi$ is \emph{isolated} (under $P$).
It is obvious that if $P_i$ refines $P_j$ as partitions of $S_{k}$
(i.e., $P_{i}\leq P_{j}$ in the lattice of partitions of $S_{k}$),
then the partition of $S_n$ induced by $P_i$ refines the one induced by
$P_j$, because a permutation reachable from $\pi$ under $P_i$ is also
reachable under $P_j$. This enables the following simple observations:
\begin{proposition}\label{propo:Refine}
If $P_i$ refines $P_j$ (as partitions of $S_{k}$), then for all $\pi \in
S_{n}$ with $n\geq k$
\begin{eqnarray*}
\Eq^\ourstar(\pi,P_i) \subseteq \Eq^\ourstar(\pi,P_j) \\
\#\Eq^\ourstar(\pi,P_i) \leq \#\Eq^\ourstar(\pi,P_j) \\
\Num^\ourstar(n,P_i) \geq \Num(n,P_j)
\end{eqnarray*}
\end{proposition}
\section{General pattern equivalence}\label{sec:gen}
In this section, we allow moves within an equivalence relation with no
adjacency restrictions. This case is closely related to the theory of
\textit{pattern avoidance\/} in permutations: replacing one
pattern with another repeatedly leads eventually to a permutation which
avoids the first pattern.
Some of the equivalence relations in this section are trivial, following
immediately from the following observation. The others lead to familiar
combinatorial numbers and objects.
\begin{proposition}\label{propo:OneClass}
Fix $k$ with $2\leq k\leq n-1$, and let $P$ be any partition of
$S_{k}$.
If $\Num^{\fourdots}(n-1,P) = 1$, then $\Num^{\fourdots}(n,P) = 1$.
\end{proposition}
\begin{proof}
We will show that any $\pi \in S_n$ can be reached from the identity, $\iota_{n}$,
under the supposition that any two permutations in $S_{n-1}$ are
equivalent, in two stages. If $\pi(1) \neq n$, simply apply the
supposition to the elements/positions $1 \dots n-1$ in $\iota_{n}$ to
obtain any permutation beginning with $\pi(1)$; if $\pi(1)=n $, we use
instead the elements/positions $1,3,4,5,\dotsc n$ (omitting 2, which is
$\leq n-1$ by hypothesis) to move $\pi (1)=n$ to the front of a
permutation equivalent to $\iota_{n}$. Then in stage 2 we apply the
supposition to the elements now occupying \textit{positions\/} $2,
\dots, n$ to complete the construction of $\pi$.
\end{proof}
The following results follow.
\begin{proposition}\label{propo:P457OneClass}
$\Num^\fourdots\left(n,\big\{ \{123,321\} \big\}\right) = 1$ for $n \geq
6$. While for $n \geq 5$, we have $\Num^\fourdots\left(n,\big\{ \{123,132,321\} \big\}\right) = 1$
and $\Num^\fourdots\left(n,\big\{ \{123,132,213,321\} \big\}\right) = 1$
\end{proposition}
\begin{proof}
It is easy to verify by hand, or by computer, that all permutations
in $S_5$ are reachable from $12345$ by moves in $P_5 = \big\{ \{123,132,321\} \big\}$.
(Indeed, all permutations in $S_4$ are reachable from $1234$ except for
$3412$, which is isolated.) As $S_5$ is connected, it follows
(by induction) from the preceding proposition that $S_n$ is connected
for all $n\geq 5$.
Proposition~\ref{propo:Refine} tells us that $S_n$ is connected under
$P_7 = \big\{ \{123,132,213,321\} \big\}$ whenever it is connected under
$P_5$ since $P_7 \geq P_5$. (In $S_4$, the permutation $3412$ remains
isolated.)
Finally, we can check by computer that under $P_4 = \big\{ \{123,321\} \big\}$
$S_6$ is connected; whence, $S_n$ is connected for $n \geq 6$.
\end{proof}
We remark that under $P_4$, $S_4$ splits into 10 equivalence classes,
and $S_5$ into three classes. The class containing $12345$ contains 24
elements. This suggests a possible bar bet. Hand your mark six cards
numbered $1$ through $6$ and invite him or her to lay them out in any
sequence. By applying moves of the form $123 \leftrightarrow 321$
(``Interchange two cards if and only if an intermediate (value) card
lies (in any position) between them.'') you will always be able to put
the cards in order. (It may take some practice, however, to become
proficient at doing this quickly.) Now ``go easy'' on your mark by
reducing the number of cards to 5. Even from a random sequence, the mark
has only one chance in five of being able to reach the identity.
Of course from Proposition~\ref{propo:P457OneClass} it immediately follows that:
\begin{corollary}\label{cor:P457Id}
$\#\Eq^\fourdots\left(\iota_n,\big\{ \{123,132,321\} \big\}\right) =
n!$,
$\#\Eq^\fourdots\left(\iota_n,\big\{ \{123,132,213,321\} \big\}\right) = n!$ for $n \geq 5$; and
$\#\Eq^\fourdots\left(\iota_n,\big\{ \{123,321\} \big\}\right) = n!$ for $n \geq 6$.
\end{corollary}
\begin{proposition}\label{propo:P2Id}
$\#\Eq^\fourdots\left(\iota_n,\big\{ \{123,213\} \big\}\right) = (n-1)!$ for $n \geq 2$.
\end{proposition}
\begin{proof}
Obviously the largest element $n$ cannot be moved away from the end
of the permutation. Equally obviously the $n$, remaining at the far right,
enables the other elements to be freely pairwise transposed, thereby
generating any permutation in $S_{n-1}$.
\end{proof}
\begin{proposition}\label{propo:P2ClassCat}
For $n \geq 1$, $\Num^\fourdots\left(n,\big\{ \{123,213\} \big\}\right) = c_n =
\frac{2n!}{n!(n+1)!}$, the $n$th Catalan number.
\end{proposition}
\begin{proof}
Let $\pi \in S_{n}$. If $i < j < k$, and $\pi(i) < \pi(j) < \pi(k)$,
then $\pi(k)$ enables the swapping
of $\pi(i)$ and $\pi(j)$ to arrive at a permutation $\pi^{(1)}$ with a strictly larger
number of inversions. We can continue in this way to obtain a sequence
$\pi =\pi^{(0)}\rightarrow \pi^{(1)}\rightarrow \dots \rightarrow \pi^{(n)}$,
where $\pi^{(n)}$ has no such triples, i.e., $\pi^{(n)}$ is $123$-avoiding.
It remains to show that no matter which sequence of moves we make, the
final permutation $\pi^{(n)}$ is unique.
Call an element in a permutation $\sigma \in S_{n}$, a
\textit{right-to-left maximum} if it is greater than every element that
occurs to its right. (More formerly, $\sigma_{k}$ is a right-to-left
maximum if $\sigma_{k}>\sigma_{l}$ for all $k1$ to move two positions rightward while maintaining
that the segment to its left is increasing. So if the target position
for $b$ is an even number of positions away, an appropriate number of
such moves will suffice. If $b$ is an odd number of positions away,
first apply the move $\mathbf{abx}y\rightarrow axby$, then proceed as
before. This shows that we can reach any permutation that starts with a
1 from $\iota_{n}$.
\textit{Stage~2:\/} To show that we can get to the identity from an
arbitrary admissible permutation, it remains to show that the element 1
can always be moved to the front of such a permutation. In fact we
only need show that the element 1 can always be moved \emph{toward} the
front (necessarily by two positions), and then we can just move it
repeatedly until it is \emph{at} the front.
If the 1 is at the very end of the permutation, the 2 must be to its
left and in a position of opposite parity. Move the 2 rightward using
moves $123\rightarrow 321$ or $132\rightarrow 321$ (the 2 functioning as
a ``1'') until it is adjacent to the 1; the 1 can then be moved
leftward.
We use the term \textit{$k$-factor} here and in later proofs as
shorthand for ``length $k$ subsequence of adjacent elements'' of a
permutation. If the 1 is not at the very end of the permutation, then
consider the 5-factor centred on the 1. (At this point, we
are relying on the assumption that $n$ is odd, because the largest
element occupies a position of odd index, and therefore if it is
not at the end of an odd permutation, it must be at least two
positions away from the end, guaranteeing the 5-factor
which we need. We will return to this point when we consider the
even case below.) There are 24 cases.
For 18 of these cases, we know that we can convert this segment
to an increasing one (or to any other permutation beginning
with a 1) using the analysis for $n=5$, which is easy to check by hand.
The cases which cannot be handled are those of the form 2*1**.
We will add a preprocessing step to make sure that we are not in
such a case. Namely, we will locate the element 2 (the actual 2)
and move into one of the spaces indicated by a $*$.
If the 2 is somewhere to the left of the 1 then the same argument used
above in the case of permutations ending in 1 again shows that the 1 can
be moved leftward.
If the 2 is somewhere to the right of the 1, we will go and fetch it as
follows. Move the 1 to the \emph{right} until it is either one or two
positions left of the 2. We do this by moving it two positions at a
time, using either $123 \rightarrow 321$ or $132 \rightarrow 321$, as
required. This leaves behind a consecutive trail of elements in which
each odd-position element is larger than the even-position element which
follows it. We will call these ``odd/even descents''.
If the 2 was in an odd position, we will arrive at $1x2$, which we
correct to $12x$. If the 2 was in an even position, we will arrive
at $12x$ directly.
Now we pull both the 1 and the 2 back through the odd/even descents by a
sequence of consecutive moves of the form $\mathbf{yx1}2\rightarrow
\mathbf{1xy}2\rightarrow 1\mathbf{yx2}\rightarrow 12yx$, where $y>x>2$.
(We may also apply $12\mathbf{yx}\rightarrow 12xy$ if we wish, but this
isn't necessary.) This brings us to a permutation in the same
equivalence class, where the 5-factor has been modified to **12*. But
we know that just working within this 5-factor, we can use the $n=5$
case to modify it to the form $12345$ (where the 1 and 2 are actual
values, the others relative values). In particular, we have moved the
actual 1 two spaces to the left. Doing this repeatedly gets us to a
permutation beginning with 1, which we have seen in Stage~1 is
equivalent to $\iota_{n}$.
\medskip
\textit{Case~2: $n=2k$ is even. \/}
In the even case, we need to describe an additional class of
permutations that not reachable from $\iota_{n}$. Let $\mathcal{X}_{n}$
consist of all permutations obtainable as follows: Fill the positions in
order $n-1,n,n-3,n-2,n-5,n-4 \ldots 3,4,1,2$, according to the following
rule. When filling positions of odd index, the smallest available element
must be chosen; the subsequent selection of an element to place to its
right is then unconstrained. Thus 1 must be placed in position $n-1$,
and the element placed in position $n$ could be any other number; however, if it
is not 2, then the 2 is immediately placed in position $n-3$; otherwise
$3$ is placed in this position.
For example, $\mathcal{X}_{4}=\{3412, 2413, 2314\}$ and
\[
\mathcal{X}_{6}=\left\{
\begin{matrix}
563412 & 562413 & 562314 & 462315 & 452316 \\
463512 & 462513 & 362514 & 362415 & 352416 \\
453612 & 452613 & 352614 & 342615 & 432516 \\
\end{matrix}
\right\}\,.
\]
The number of permutations in the class $\mathcal{X}_n$ just described is $(n-1)!!$.
As we will see next, none of them is reachable. However, it is also true
that most of them are not in $\mathcal{A}_n$, and therefore have not been
included in the enumeration; this is because most of
the permutations in $\mathcal{X}_n$ have the $2$ in position $n-3$, which is a
position of odd index to the left of the $1$. The only permutations in
$\mathcal{X}_n$ which we have counted, and which therefore must be subtracted off,
are the ones where the $2$ is in position $n$, of which there are $(n-3)!!$.
To see that none of the permutations in $\mathcal{X}_n$ is reachable, consider
their $3$-factors. Every $3$-factor centred on a position of odd index
is either a $213$ or a $312$, because the middle element was placed before
either of its neighbors, and was the minimal available element at the
time it was placed. And every $3$-factor centred on a position of even
index is a $231$, because the elements in positions of odd index, which
are the minimal elements, descend from left to right. Therefore permutations
belonging to $\mathcal{X}_n$ contain \emph{no} factors of form $123$, $132$, or
$321$, and are therefore isolated by the relation, each one being a singleton
equivalence class. In particular they are not in the equivalence
class of the identity.
Now we have to consider which permutations in $\mathcal{A}_n$ are not in fact
reachable. The proof for odd $n$ almost carries through completely; indeed,
as remarked, it only fails when the element 1 lies in the penultimate
position $n-1$. We have already seen that the permutations belonging
to $\mathcal{X}_n \cap \mathcal{A}_n$ are not reachable; we will show that all
others are. Take any permutation $\pi \not\in \mathcal{X}_n$, but with the
minimal element $1$ placed in position $n-1$. Checking the conditions
from right to left, suppose the element $\pi_{j}=y$ represents
the last time that we were in compliance with the conditions, and suppose
$\pi_{i}=x$ is the first minimal element which has not
gone where it should go. That is, all odd positions from $j$ to $n-1$ are
occupied by elements which are left-to-right minima, but the smallest
element situated in positions $1$ through $j-1$ is not in position
$j-2$, as expected, but in position $i$ with value $x$.
As before, all we need to do is show that we can move the element $1$
to the left. This exploits two facts: that $x$ is the minimal element in
a lefthand region, and the righthand region is alternating.
Because the righthand portion of $\pi$, from position $j$ onward, is
alternating, with every step from an odd to an even position being an
ascent, and every step from even to odd being a descent, we will have
a particular interest in a certain type of $3$-factor beginning in
a position of odd index. Namely, we will refer to a $3$-factor
$\pi_{h},\pi_{h+1},\pi_{h+2}$ as an \emph{odd 321} if
$\pi_{h}>\pi_{h+1}>\pi_{h+2}$ and if $h$ is odd. Note that an odd $321$
beginning in position $n-3$ is exactly what we need, because either option
for replacing it shifts the element $1$ from position $n-1$.
First, take the element $x$ and use moves $\rightarrow 321$ to shift
it rightward, two positions at
a time, until it arrives in position $j-2$ or $j-1$. This is possible
because $x$ is moving through a region in which it is itself the minimal
element.
Now $j-2$ is an odd position, so if $x$ has reached position $j-2$
then positions $j-4,j-3,j-2$ now form an odd $321$. Alternatively, if $x$
has reached position $j-1$ then positions $j-2,j-1,j$ now form an odd $321$,
because the second and third of these positions are occupied by $x$ and $y$
and $y\pi'_{i+1}>\pi'_{i+2}$.
Finally, $\pi'_{i}$ is the largest element of the block, so could only
play the role of ``3'' in a 321 pattern, but there is only one odd
element to its right in the block. So any 321 pattern of odd elements
in $B'$ that did not already exist in $B$ must use $\pi'_{i+2}$ as ``1''
and odd elements to the left of $\pi'_{i}$ for ``3'' and ``2''. But
then these elements (which haven't moved) together with $\pi_{i}$ would
have formed a 321 in $B$, which wasn't allowed.
\medskip
\textit{Case~(c)} Just one element is in a singleton block.
This can't be the third (or, symmetrically, the first) element, because
if $\pi_i$ and $\pi_{i+1}$ are the final two elements of a large
block, then $\pi_i > \pi_{i+1}$, so our 3-factor is not a 123. So it must be
$\pi_{i+1}$ which is the singleton, while the other two elements belong
to two large blocks. The replacement merges these three blocks into one;
the even elements, including $\pi_{i+1}$, remain on the diagonal, and as
in the previous case any point at which the new block split would also
imply a decomposition of one of the old blocks at the same
position. The odd elements of $\pi '$ are $321$-avoiding because if a $321$
contained just one of $\pi'_i$ or $\pi'_{i+2}$ then it would be
pre-existing (with $\pi_{i+2}$ or $\pi_{i}$ respectively). If it
contained both, then the third element in the pattern would be either on
the left and too large for the old lefthand block, or on the right and
too small for the old righthand block.
\medskip
\textit{Case (d)} The three elements are all within a single large block
$\mathcal{B}$.
First we claim that the middle element, $\pi_{i+1}$ must be in an even
position (within $\mathcal{B}$). Otherwise, $\pi_{i}$ and $\pi_{i+2}$
would be in even positions, hence on the diagonal, and the 123 form of
the 3-factor would mean $\pi_{i+1}$ was also on the diagonal; thus,
$\mathcal{B}$ would have to be of size at least 5. Now if all elements to
the left of $\pi_{i}$ were smaller than it, $\mathcal{B}$ would split into
summands before position $i$. But if some $\pi_{j}$ is greater than
$\pi_{i}$ (for some odd $j*i+2$. But then $\pi_{j}$, $\pi_{i+1}$, $\pi_{k}$ formed a
321-pattern of odd positions within the block, contrary to hypothesis.
The claim follows.
Now the replacement $\pi_{i}\pi_{i+1}\pi_{i+2}\rightarrow
\pi_{i+2}\pi_{i+1}\pi_{i}$ cannot create a new direct sum decomposition
since it is increasing the left element and decreasing the right one.
Suppose that somehow this move created a $321$ among the odd elements
(within $\mathcal{B}$). If it only used one of $\pi_{i}, \pi_{i+2}$,
then it must have been pre-existing with the other one, contrary to
hypothesis. If it used both, then without loss of generality assume
$\mathcal{B}$ contains an element $x$ to the left of the replaced
3-factor, but larger than $\pi_{i+2}$. Because $x$ is also greater than
$\pi_{i+1}$, it uses up one of the odd values greater than the diagonal
element $\pi_{i+1}$, meaning that there must be a $y$ to the right of
$\pi_{i+1}$ but smaller than it, and then $x,\pi_{i+2},y$ is a
pre-existing $321$. The case where $\mathcal{B}$ contains an element
$y$ to the right of the replaced 3-factor, but smaller than $\pi_{i}$
follows by symmetry.
\medskip
\textit{Non-Case (e)} The last possibility to consider is that the
3-factor is split across two adjacent large blocks, necessarily with two
elements at the start or end of one of the large blocks. But this is
ruled out because large blocks begin and end with descents.
Note that in each of these cases the replacement $123
\rightarrow 321$ winds up gluing together all the blocks of $\pi$ which
it straddles, leaving the same number or fewer blocks in $\pi'$. In
particular, the replacement may glue together blocks, but never splits
any apart.
Now consider applications of $321 \rightarrow 123$ within a permutation
$\rho \in \mathcal{A}_n$ to obtain a new permutation $\hat{\rho}$. Clearly,
any adjacent $321$ must lie within a single
block, as in any two blocks, all the elements in the block to the right
are larger than all the elements in the block to the left. Because the
even elements within a block increase monotonically, the $321$ is
composed of odd, even, odd elements. An analysis similar to that given
above shows that any such
transformation is simply the reverse of one of the cases (a--d)
described above, so $\hat{\rho}$ is always in $\mathcal{A}_{n}$.
Now we need to show that we can use these transformations to return to the identity from any
permutation $\sigma$ in $\mathcal{A}_n$. We first claim that every large block of
$\sigma$ contains a $321$ as a factor. For the first
element of the block must lie below the diagonal and the last element
must lie above it; therefore, there are two consecutive odd elements in
the block with the first below and the second above the
diagonal. Together with the even element which separates them, and which
lies \emph{on} the diagonal, this forms a $321$.
Unless $\rho $ is itself the identity, it contains a large block, and
therefore a $321$. Replacing this $321$ with a $123$ yields a
permutation $\hat{\rho}$ having strictly fewer inversions than $\rho$. But
as $\mathcal{A}_n$ is closed under such replacements, we know that $\hat{\rho}$
also belongs to $\mathcal{A}_n$, and therefore is either the identity or
else contains a $321$. By iterating this process, we must eventually
arrive at a permutation having no inversions, namely the identity.
This establishes that $\Eq^\twolines\left(\iota_n,\big\{ \{123,321\}
\big\}\right)=\mathcal{A}_{n}$, so all that is left is the enumeration
of these classes. It is an easy exercise
\cite[(n$^{6}$)]{StanleyCatAdd} or \cite[p.~15]{ClaKit} that the number of \emph{indecomposable}
$321$-avoiding permutations on $m+1$ elements is the Catalan number
$c_{m}={\frac{1}{m+1}}{{2m}\choose{m}}$. This is also the number of possible
blocks of size $2m+1$.
We define the following three generating functions, which enumerate
central binomial coefficients of even order (E), of odd order (O),
and the Catalan numbers (C).
\begin{eqnarray*}
E(x) & = \frac{1}{\sqrt{1-4x}} & = 1 + 2x + 6x^2 + 20x^3 + 70x^4 + \dots \\
O(x) & = \frac{\frac{1}{\sqrt{1-4x}}-1}{2x} & = 1 + 3x + 10x^2 + 35x^3 + 126x^4 + \dots \\
C(x) & = \frac{1-\sqrt{1-4x}}{2x} & = 1 + x + 2x^2 + 5x^3 + 14x^4 + \dots
\end{eqnarray*}
The statement of the theorem is equivalent
to showing that $E(x)=\sum_{n\geq 0} A_{2n+1}x^{n}$ and $O(x)=\sum_{n\geq
0} A_{2n+2}x^{n}$, where we set $A_{n}:=\#\mathcal{A}_{n}$.
Now a reachable permutation of even size $2n+2$ is the direct sum of
an indecomposable block of size $2i+1$ ($i\geq 0$) and a reachable
permutation of odd size $2(n-i)+1$. This translates into the
recursion/convolution
\[
A_{2n+2}=\sum_{i=0}^{n}c_{k}A_{2(n-i)+1}
\]
which is equivalent to $O(x)=E(x)C(x)$, and which is also easily verified from
the closed-form expressions for these generating functions. Similarly,
a reachable permutation of odd-size $2n+1 $ is
the direct sum of an indecomposable block of size $2i+1$ and a
reachable permutation of even size $2(k-i)$, corresponding to the
easily-verified equality of generating functions $E(x)=(1+xO(x))C(x)$.
This completes the proof.
\end{proof}
Although the above proof seems natural enough from the structure of the
equivalence class $\mathcal{A}_{n}$, the simple form of the enumeration
as a single binomial coefficient begs the question of whether there is a
more direct (perhaps bijective) argument.
The next theorem provides independent proofs of two results which
appeared 10 years ago in [CEHKN].
\begin{theorem}\label{propo:P3bClassInv}
(a) $\Num^\twolines\left(n,\big\{ \{123,132,213\} \big\}\right) = \inv_{n}$, the
number of involutions of order $n$.
(b) $\#\Eq^\twolines\left(\pi,\big\{ \{123,132,213\} \big\}\right)$ is odd for all $n$ and for each $\pi \in S_n$.
\end{theorem}
\begin{proof}
Write each involution in $\tau \in \Inv_{n}\subseteq S_{n}$ canonically
as a product of 1-cycles and 2-cycles, with the elements increasing within each 2-cycle,
and with the cycles in decreasing order of largest element. Omitting
the parentheses, we view the resulting word $D(\tau)$ as a
permutation. Let $\mathcal{D}_{n}:=D(\Inv_{n})$ be the image of this map
(which is easily reversible by placing parentheses around the ascents of
$\sigma \in \mathcal{D}_{n}$). We claim that this is a canonical set of
representatives for the equivalence classes of $S_{n}$ under $P_{3}= \{
\{123,132,213\} \}$ transformations.
Each permutation $\pi\in S_{n}$ can be transformed to an element of
$\mathcal{D}_{n}$ as follows:
if $n$ is at the front of $\pi$, it must stay there. (This corresponds
to having $n$ as a fixed point of the involution.) Otherwise, use $123
\rightarrow 132$ and $213 \rightarrow 132$ (at least one of which is
possible at each step) to push $n$ leftward into
position 2, which is as far as it will go. The element which is thus
pushed into position 1 is the minimal element $m$ which was to the left of
$n$ to begin with. This is because $m$ can never trade
places with $n$ under the given operations, as 1 is left of 3 in all of
123, 132 and 213. Leaving the leftmost 1-factor $n$ or 2-factor $mn$
fixed, proceed inductively among the remaining elements, at each step
moving the maximal remaining element as far left as possible. The end
result of this deterministic procedure is a permutation $L(\pi)\in
\mathcal{D}_{n}$. This shows that the number of $P_{3}$-equivalence
classes is at most $\inv_{n}=\#\mathcal{D}_{n}$.
To show that they are the same, it remains to show that each $\pi$ can
be transformed to a \emph{unique} member of $\mathcal{D}_{n}$, or
equivalently that it is not possible to move from one member of
$\mathcal{D}_{n}$ to another using $P_{3}$-moves.
We will prove this by induction on $n$. At the same time we will prove
statement (b) of the theorem. Assume as an induction hypothesis that
both statements have been demonstrated for $n-1$ and $n-2$. It is
straightforward to check the base cases by hand. For $n=3$ the four
equivalence classes are $P_{3}$ and three singleton classes. For $n=4$
the classes are $\{1234,1243,1324,2134,\mathbf{1423},1342,2143,3142,2314
\}$, $\{1342, 3124, \mathbf{1432}, 3142, 3214 \}$, $\{4123,
\mathbf{4132}, 4213 \}$, $\{2341, \mathbf{2431}, 3241\}$, and six
singletons: $\mathbf{\{ 2413\}, \{3412\},}$ $\mathbf{\{4312\},}$
$\mathbf{4231}$, $\mathbf{3421}$, $\mathbf{4321}$. (The
elements in \textbf{bold} are the class representatives within
$\mathcal{D}_{n}$.)
First note that if the largest element, $n$, is at the front of a
permutation, then it is immobile under $P_{3}$-moves. Thus the
equivalence classes split into two kinds: \emph{special} equivalence
classes, in which $n$ is at the front of each permutation in the class,
and \emph{ordinary} equivalence classes, in which $n$ is never at the
front. Moreover it is obvious that the special equivalence classes for
$S_n$ correspond exactly to \emph{all} the equivalence classes for
$S_{n-1}$ upon deletion of the first elements; therefore,
the truth of both (a) and (b) as they apply to the
\emph{special} equivalence classes follows by induction.
Next we will look at the \emph{ordinary} equivalence classes. For
convenience of exposition, consider a (directed) graph in which the
vertices correspond to the permutations in $S_n$, and there is a blue
(directed) edge from $\pi$ to $\pi'$ if $\pi'$ can be obtained from
$\pi$ by applying $123 \rightarrow 132$, and similarly a red edge for
each $213 \rightarrow 132$, and a green edge for each $123 \rightarrow
213$. A blue edge just corresponds to a green edge followed by a red
one, and indeed the edges always appear in matched sets: the appearance
of a $213$ in a permutation implies an incident green edge pointing in
and a red edge pointing out, and also a blue edge making the chord of
this triangle (and similarly for appearances of $123$ and $132$). The
equivalence classes in which we are interested are the (undirected)
connected components of this graph.
Now consider the forest of rooted trees which one obtains by taking only
those red and blue edges in which the element $n$ plays the role of the
``3''. The roots (i.e., sinks) of these trees are exactly the
permutations in which the $n$ has moved to position $2$, which is as
far left as it will go within an ordinary equivalence class. More generally,
if $\pi_{k}=n$, then $\pi$ lies on level
$k-2$ of the tree. (We can say that it has \emph{energy}
$E(\pi)=k-2=\pi^{-1}(n)-2$.) Note that blue and red edges reduce the
energy by one, while green edges leave it unchanged.
Each vertex in this forest has either zero or two children, because if it
has a blue child (obtained by travelling backwards along a blue edge)
then it also has a red child, and vice versa.
Each permutation $\pi$ lies on a unique directed path to the
root of its tree, which we will call the \emph{ground state} of $\pi$,
$g(\pi)$. Note that $g(\pi)_{2}=n$, while $g(\pi)_{1}$ is the smallest
element $m$ to the left of $n$ in $\pi$.
Because each node has either zero or two children, each rooted tree has
an odd number of nodes; indeed all of its level-sums are even except the
zeroth level sum, which corresponds to the root vertex (i.e., ground
state).
Now we will create larger classes as follows: declare two ground states
$\tau$ and $\sigma$ \emph{similar} if $\tau_{1}=\sigma_{1}$ and
$\tau_{3}\dotsb \tau_{n}$ is $P_{3}$-equivalent to $\sigma_{3}\dotsb
\sigma_{n}$ regarded (in the obvious way) as members of $S_{n-2}$. For
$m\in [n-1]$ and $\nu \in \mathcal{D}_{n-2}$, let
$\mathcal{K}(m,\nu)$ be the (disjoint!) union of all trees with similar ground
states $\tau $, where $\tau_{1}=m$ and $\tau_{3}\dotsb \tau_{n}$ is
$P_{3}$-equivalent to $\nu$. Note that this gives us a total of
$(n-1)\inv_{n-2}$ equivalence classes, in agreement with the well-known
recursion: $\inv_{n}=\inv_{n-1}+(n-1)\inv_{n-2}$. (The special
equivalence classes account for the first summand.)
We claim that these larger classes $\mathcal{K}(m,\nu)$ are exactly (the
vertex sets of) the connected components of our directed graph; that is,
there are no directed edges in the graph which escape from one class to
another. Once this is shown, then by induction there is a unique member
of the class $\mathcal{D}_{n-2}$ of canonical permutations among the
ground states in a large component, to which we prepend $mn$ to obtain
the unique representative of $\mathcal{K}(m,\nu)$ within
$\mathcal{D}_{n}$.
Furthermore, each $\mathcal{K}(m,\nu)$ will then be of odd size, because
each rooted tree has odd size, having all level-sums even except the one
corresponding to the ground states, and because the number of rooted
trees in the union is odd by the induction hypothesis for $n-2$.
So suppose there is an edge (of any colour) from a $\pi \in
\mathcal{K}(m,\nu)$ to $\pi'\in \mathcal{K}(m',\nu')$.
Since this move does not involve moving the largest element $n$,
$\pi$ and $\pi'$ have the same energy. Our goal is to show that
$m=m'$ and $\nu $ is $P_{3}$-equivalent to $\nu'$. The former follows
from our earlier description of $m$ as the minimum element lying to the
left of $n$ in $\pi$, because $\pi$ and $\pi'$ have the same set of
elements to the left of $n$. The latter requires an analysis of the
cases that can arise as $\pi$ and $\pi'$ move towards their ground
states in their respective trees.
As the $n$ moves leftward through each of the two permutations
(following red and/or blue edges toward their respective ground states)
then it sometimes encounters identical elements and therefore has the
same effect; eventually it encounters the positions where the
difference lies, having swept before it the
minimal intervening element, $b$. What happens from this point forward
depends on how $\pi$ and $\pi'$ differ, and the relative value of $b$.
To clarify the cases, let the three values where the difference was
applied be $d < f < h$, and designate $b$ by one of $C,E,G$ or $I$
(where $C3$:
$P_1$: $a_n = a_{n-1} + a_{n-2}$, by appending respectively a $\rho_1$ or a $\rho_2$.
$P_4$: $a_n = a_{n-1} + a_{n-3}$, by appending respectively a $\rho_1$ or a $\rho_3$.
$P_5$: $a_n = a_{n-1} + a_{n-2} + a_{n-3}$, by appending $\rho_1$, $\rho_2$ or $\rho_3$.
$P_3$: Count all direct sums of $\rho_1$ and $\rho_2$
(obviously Fibonacci) and then subtract 1 from the even terms to remove
the special case $2*$ (all blocks of size 2).
$P_7$: Count all direct sums of $\rho_1$, $\rho_2$, $\rho_3$ to get
tribonacci numbers [\seqnum{A000073}],
and subtract 1 from the even terms because block structure $2*$ is
disallowed. Alternatively,
verify the recurrence $a_n = a_{n-2} + U_n$, where $U_n$ is the
$P_{5}$-recurrence [\seqnum{A000213}], by
noting that a permutation in $\Eq^\oursquare(\iota_n,P_7)$ is either a $\rho_2$
prepended to a permutation in $\Eq^\oursquare(\iota_{n-2},P_7)$, or else
belongs to $\Eq^\oursquare(\iota_{n},P_5)$.
\end{proof}
\section{Final remarks and open questions}\label{sec:open}
Our results in this paper are just a tractable subset of questions that
could be explored within these families of equivalence relations. We
created the framework to easily allow for a number of extensions. The
connections with familiar integer sequences, pattern-avoidance in
permutations, and important combinatorial bijections indicate the value
of further work. Possible directions for further study include the
following:
\begin{enumerate}
\item Study the sizes (and characterize if possible) all equivalence
classes $\Eq^\ourstar(\pi,P)$, not just for the case $\pi
=\iota_{n}$. Corresponding to each equivalence relation is the multiset
of sizes of the equivalences classes, perhaps best considered as an
integer partition of $n!$. Is the study of these of interest?
\item Allow for more generality among the (set) partition $P$ of $S_{3}$
which defines our relations. The authors in~\cite{PRW11} allow
substitution of patterns in $S_{3}$ where no element is fixed, but still
restrict to partitions $P$ consisting of exactly one non-singleton block
containing the identity $123$. Although it seems unwieldy to work with
all $B(6)=203$ possible partitions of $S_{4}$, perhaps a different
restriction that forces greater symmetry among the relations would be
useful. For example, the Knuth relations $P^{\twolines}_{K}=\big\{ \{
213,231\}, \{132,312\}\big\}$ are closed under reversal and
complementation.
\item Consider relations generated by partitions $P$ of $S_{k}$ for
$k>3$. Here one definitely needs some conditions to restrict focus to
relations of particular interest, since the Bell number $B(4!)$ is
already far too large to handle all cases.
\item Study in greater detail the structure of the graphs defined by
these relations. What can one say about their degree sequences or
diameters? How many moves are necessary in order to transform a given
$\pi $ to the identity?
\end{enumerate}
\section{Acknowledgments}\label{sec:ack}
The first author gratefully acknowledges the support of EPSRC grant
EP/C523229/01. The third author is grateful to Sami Assaf, Karen
Edwards, and Stephen Pon for helpful conversations. The fourth author
gratefully acknowledges support of NSERC operating grant OGP0105492.
\begin{thebibliography}{19}
\bibitem{AAKSimple} M. H.~Albert, M. D.~Atkinson, and
M.~Klazar, {\rm The enumeration of simple permutations}, \textit{J. Integer
Sequences} {\bf 6} (2003),
\href{https://cs.uwaterloo.ca/journals/JIS/VOL6/Albert/albert.html}{Article 03.4.4}.
\bibitem{AssafSWD} S.~Assaf, {\rm A combinatorial
realization of Schur-Weyl duality via crystal graphs and dual
equivalence graphs}, in \textit{FPSAC 2008,
Discrete Math. Theor. Comput. Sci. Proc.}, %% Nancy, France,
2008, pp.\ 141--152.
\bibitem{AssafDEG} S.~Assaf, \textit{Dual equivalence
graphs, ribbon tableaux and Macdonald polynomials}, Ph.\ D. Thesis, UC
Berkeley, 2007.
\bibitem{BonaPerm}
M.~Bona, {\it Combinatorics of Permutations}, Chapman \& Hall/CRC, 2004.
\bibitem{BonaWalk}
M.~Bona, {\it A Walk Through Combinatorics}, 2nd ed.,
World Scientific Publishing Co., 2006.
\bibitem{Chinese}
J.~Cassaigne, M.~Espie, D.~Krob, J.-C.~Novelli, and F.~Hivert,
The Chinese monoid, \textit{Int'l. J. Algebra and Comp.} \textbf{11} (2001),
301--334.
\bibitem{ClaKit}
A.~Claesson and S.~Kitaev, {\rm Classification of bijections
between 321- and 132-avoiding permutations}, \textit{S\'eminaire Lotharingien de
Combinatoire} \textbf{60} (2008), Article B60d.
\bibitem{Com72} L.~Comtet, Sur les coefficients de l'inverse de
la series formelle $\sum n! t^{n}$, \textit{Comptes Rend. Acad. Sci. Paris}
\textbf{A 275} (1972), 569--572.
\bibitem{ComAdv} L.~Comtet, \textit{Advanced
Combinatorics}, Reidel, 1974.
%%pp.~84 (\#25), 262 (\#14), and 295 (\#16)
\bibitem{HaimanDEq}
M.~Haiman, {\rm Dual equivalence with applications, including a
conjecture of Proctor}, \textit{Discrete Math.} {\bf 99} (1992), 79--113.
\bibitem{Knuth}
D.~Knuth, {\rm Permutations, matrices and generalized Young
tableaux}, \textit{Pacific J. Math.} {\bf 34} (1970), 709--727.
\bibitem{LLTPlactic} A.~Lascoux, B.~Leclerc, and
J.-Y.~Thibon, \textrm{The plactic monoid}, Ch.~5 in M.~Lothaire, ed.,
\textit{Combinatorics on Words}, Encyclopedia of Math and its Applications,
Cambridge University Press, 2002, pp.\ 164--196. Available at
\url{http://www-igm.univ-mlv.fr/~jyt/articles.html}.
\bibitem{LSPlactic} A.~Lascoux and
M.~P.~Sch\"utzenberger, ``Le mono\"ide plaxique'', in \textit{Non commutative
structures in Algebra and Combinatorics}, Quaderni della Ricerca
Scientifica del CNR, Roma, 1981.
\bibitem{LPRW} S.~Linton, J.~Propp, T.~Roby, and
J.~West, Equivalence relations of permutations generated by constrained
transpositions, \textit{FPSAC 2010, Discrete
Math. Theor. Comput. Sci. Proc.}, July 2010,
\url{http://tinyurl.com/8ly7fpw}.
\bibitem{OEIS} N. J. A.~Sloane, \textrm{The On-line Encyclopedia of Integer Sequences},
\url{http://oeis.org}.
\bibitem{PRW11} \textrm{A.~Pierrot, D.~Rossin, and J.~West}, \textrm{Adjacent
transformations in permutations}, \textit{FPSAC 2011, Discrete
Math. Theor. Comput. Sci. Proc.}, 2011.
\url{http://tinyurl.com/8c6lw6o}.
\bibitem{PriceLayered} \textrm{A. L.~Price}, \textit{Packing
densities of layered patterns}, Ph.\ D. Thesis, University of
Pennsylvania, 1997.
\bibitem{StanleyEC1}
R.~Stanley, {\it Enumerative Combinatorics, Volume 1}, no.~49 in Cambridge
Studies in Advanced Mathematics, Cambridge University Press, 1999.
\bibitem{StanleyEC2}
R.~Stanley, {\it Enumerative Combinatorics, Volume 2}, no.~62 in Cambridge
Studies in Advanced Mathematics, Cambridge University Press, 1999.
\newblock With Appendix 1 by Sergey Fomin.
\bibitem{StanleyEquiv}
R. Stanley, An equivalence relation on the symmetric group
and multiplicity-free flag $h$-vectors, preprint, 2012.
\bibitem{StanleyCatAdd}
R.~Stanley, {\rm Catalan addendum},
\url{http://www-math.mit.edu/~rstan/ec/catadd.pdf}.
\bibitem{StromLayered}
W.~Stromquist, \textrm{Packing
layered posets into posets}, preprint, 1993,
\url{http://walterstromquist.com/}.
\end{thebibliography}
\bigskip
\hrule
\bigskip
\noindent 2010 {\it Mathematics Subject Classification}:
Primary 05A05; Secondary 05A15.
\noindent \emph{Keywords:} permutation pattern, equivalence class,
Knuth relation, plactic monoid, Chinese monoid, integer sequence,
Fibonacci number, tribonacci number, Catalan number, layered
permutation, connected permutation, involution, pattern-avoiding
permutation, transposition.
\bigskip
\hrule
\bigskip
\noindent (Concerned with sequences
\seqnum{A000045},
\seqnum{A000073},
\seqnum{A000079},
\seqnum{A000085},
\seqnum{A000108},
\seqnum{A000142},
\seqnum{A000213},
\seqnum{A000930},
\seqnum{A001405},
\seqnum{A003319},
\seqnum{A010551},
\seqnum{A052952},
\seqnum{A210667},
\seqnum{A210669},
\seqnum{A210671},
\seqnum{A212417},
\seqnum{A212419},
\seqnum{A212419},
\seqnum{A212432},
\seqnum{A212433},
\seqnum{A212580}, and
\seqnum{A212581}.)
\bigskip
\hrule
\bigskip
\vspace*{+.1in}
\noindent
Received June 21 2012;
revised version received November 1 2012.
Published in {\it Journal of Integer Sequences}, November 2 2012.
\bigskip
\hrule
\bigskip
\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in
\end{document}
*