\documentclass[12pt]{amsart}
\usepackage{latexsym, mathrsfs, color, tikz, multirow, bbm, mathtools}
\usepackage[vcentermath,enableskew]{youngtab}
\usepackage{young}
%\hypersetup{hidelinks}
\usepackage{graphics}
\usepackage{subcaption}
%\usepackage{showlabels}
\input{xy}
\xyoption{all}
%\usepackage{refcheck}

\usepackage[colorlinks=true, pdfstartview=FitV,
 linkcolor=black,citecolor=black,urlcolor=black]{hyperref}
 
\usepackage{tikz}



\renewcommand{\baselinestretch}{1.2}
\setlength{\textwidth}{460pt} \setlength{\hoffset}{-45pt}

\numberwithin{equation}{section}
\theoremstyle{plain}
\newtheorem{Thm}[equation]{Theorem}
\newtheorem{Prop}[equation]{Proposition}
\newtheorem{Cor}[equation]{Corollary}
\newtheorem{Lem}[equation]{Lemma}
\newtheorem{Conj}[equation]{Conjecture}
\newtheorem{Open}{Open Problem}

\theoremstyle{definition}
\newtheorem{Def}[equation]{Definition}
\newtheorem{Exa}[equation]{Example}

\theoremstyle{remark}
\newtheorem{Rmk}[equation]{Remark}

\newcommand{\la}{\langle}
\newcommand{\ra}{\rangle}
\newcommand{\wb}{\overline{w}}
% \newcommand{\red}{\textcolor{red}}
% \newcommand{\blue}{\textcolor{blue}}
\newcommand{\ten}{10}

\newenvironment{red}{\relax\color{red}}{\relax}
\newenvironment{blue}{\relax\color{blue}}{\hspace*{.5ex}\relax}

\newcommand{\ber}{\begin{red}}
\newcommand{\er}{\end{red}}
\newcommand{\beb}{\begin{blue}}
\newcommand{\eb}{\end{blue}}

%\renewcommand{\qedsymbol}{$\blacksquare$}

\DeclareMathOperator{\sgn}{sgn}
\DeclareMathOperator{\rs}{RS}
\DeclareMathOperator{\std}{std}

\begin{document}

\title[Reverse Permutations in the RS Correspondence]{Permutations whose Reverse Shares the Same Recording Tableau in the RS correspondence}

\author[T. J. Ervin]{Tucker J. Ervin}
\address{Department of Mathematics, University of Alabama, Tuscaloosa, AL 35487, U.S.A.}
\email{tjervin@crimson.ua.edu}

\author[B. Jackson]{Blake Jackson}
\address{Department of Mathematics, University of Alabama, Tuscaloosa, AL 35487, U.S.A.}
\email{bajackson9@crimson.ua.edu}

\author[J. Lane]{Jay Lane}
\address{Department of Mathematics, University of Alabama, Tuscaloosa, AL 35487, U.S.A.}
\email{Jay.D.Lane-1@ou.edu}

\author[K. Lee]{Kyungyong Lee}
\address{Department of Mathematics, University of Alabama,
Tuscaloosa, AL 35487, U.S.A. 
and Korea Institute for Advanced Study, Seoul 02455, Republic of Korea}
\email{klee94@ua.edu; klee1@kias.re.kr}

\author[S. D. Nguyen]{Son Dang Nguyen}
\address{Department of Mathematics, University of Alabama, Tuscaloosa, AL 35487, U.S.A.}
\email{sdnguyen1@crimson.ua.edu}

\author[J. O'Donohue]{Jack O'Donohue}
\address{Department of Mathematics, University of Alabama, Tuscaloosa, AL 35487, U.S.A.}
\email{jro5347@psu.edu}

\author[M. Vaughan]{Michael Vaughan}
\address{Department of Mathematics, University of Alabama, Tuscaloosa, AL 35487, U.S.A.}
\email{mvaughan1@crimson.ua.edu}
\thanks{All authors were supported by the University of Alabama. KL was supported by the NSF
grant DMS-2042786 and Korea Institute for Advanced Study. }


\begin{abstract}
The RS correspondence is a bijection between permutations and pairs of standard Young tableaux with identical shape, where the tableaux are commonly denoted $P$ (insertion) and $Q$ (recording). 
It has been an open problem to demonstrate
\begin{center}
\begin{equation*}
|\{w \in \mathfrak{S}_n \mid Q(w) = Q(w^r)\}|
=
\begin{dcases}
	2^{\frac{n-1}{2}}\binom {n-1} { \frac{n-1}{2}} ,& n \text{ odd,} \\
	0 ,& n \text{ even,} \\
\end{dcases}
\end{equation*}
\end{center}
where $w^r$ is the reverse permutation of $w$.
First we show that for each $w$ where $Q(w) = Q(w^r)$ the recording tableau $Q(w)$ has a symmetric hook shape and satisfies a certain simple property.
From these two results, we succeed in proving the desired identity.

\end{abstract}

\maketitle

\thispagestyle{myheadings}
\font\rms=cmr8 
\font\its=cmti8 
\font\bfs=cmbx8

\markright{\its S\'eminaire Lotharingien de
Combinatoire \bfs 86 \rms (2022), Article~B86a\hfill}
\def\thepage{}

\section{Introduction}

The bijection known as the Robinson--Schensted (RS) correspondence was first described in 1938 by Robinson \cite{Ro} as a method for proving the Littlewood--Richardson rule. 
In 1961, Schensted \cite{Sc} gave a much simpler description of the algorithm, and it is the one we will use throughout our paper. 
Even though the two descriptions are very different, the correspondence usually credits both authors. 
Knuth \cite{K} extended the RS correspondence in 1970 to one between non-negative integer matrices and semi-standard Young tableaux. 
The generalized bijection is referred to as the Robinson--Schensted--Knuth (RSK) correspondence. 
While Knuth's formulation and results are important to the theory and have been widely used, we keep our focus solely on permutations, which we write using one line notation. 

Given a permutation $w$, there are three operations we can perform: the reverse $w^r$, the complement $w^c$, and the inverse $w^{-1}$.
\begin{Def} \label{def-permutations}
Let $w = w_1\dots w_n \in \mathfrak{S}_n$. Then we define the {\it reverse permutation} $w^r = w_n\dots w_1$, the {\it complement permutation} $w^c = (n+1-w_1)\dots (n+1-w_n)$, and the {\it reverse-complement permutation} $w^{rc} = w^{cr} = (n+1-w_n)\dots (n+1-w_1)$.
\end{Def}
There exist several relations between the recording and insertion tableaux of $w$ and its image under the three operations.
The insertion tableaux of $w$ and $w^r$ are transposes of each other, written as $P(w) = P(w^r)^T$ \cite[Theorem~3.2.3]{Sa}.
Similarly, the recording tableaux are related by $Q(w) = \epsilon(Q(w^r))^T$ \cite[Theorem~3.9.4]{Sa}, where $\epsilon$ is the evacuation map.
Other relations exist with regards to the inverse and complement operations, such as $P(w) = Q(w^{-1})$, $Q(w) = P(w^{-1})$, $P(w) = \epsilon(P(w^c))^T$, and $Q(w) = Q(w^c)^T$ \cite[Theorem~4.1.1]{L}.
To summarize, the RS correspondence takes $w$ and its images under the operations to the following:
\begin{align*}
\rs(w) &= (P(w), Q(w)),\\
\rs(w^c) &= (\epsilon(P(w))^T, Q(w)^T),\\
\rs(w^r) &= (P(w)^T, \epsilon(Q(w))^T),\\
\rs(w^{rc}) &= (\epsilon(P(w)), \epsilon(Q(w))),\\
\rs(w^{-1}) &= (Q(w),P(w)),\\
\rs(w^{-1c}) &= (\epsilon(Q(w))^T, P(w)^T),\\
\rs(w^{-1r}) &= (Q(w)^T, \epsilon(P(w))^T),\\
\rs(w^{-1rc}) &= (\epsilon(Q(w)), \epsilon(P(w))).
\end{align*}
Every combination of the three operations reduces to one of the eight options above.
This then brings up two interesting questions: what kind of and how many permutations have their recording tableaux fixed by these operations?

For the complement, there are no non-trivial permutations such that $Q(w) = Q(w^c)$, as $Q(w^c) = Q(w)^T$.
The only possible such permutation is $1 \in \mathfrak{S}_1$.
%The complement permutation appears often in the literature as the longest element of the Coxeter/Weyl group (under the Bruhat order) is $w_0 = n(n-1)(n-2)\dots 321$ and the complement permutation can be written as $w^c = w_0w$.
%Similarly, the reverse permutation is $w^r = ww_0$ and the reverse-complement is $w^{rc} = w_0ww_0$.
The set of permutations such that $Q(w) = Q(w^{-1})$ is the set of involutions of $\mathfrak{S}_n$.
Its cardinality is given by $\sum_{\lambda \, \vdash n} f^\lambda$, where $f^\lambda$ is the number of standard Young tableaux of shape $\lambda$.
As $Q(w) = Q(w^{-1 c})$ only when $Q(w) = P(w)^T$, its cardinality is the sum of all $f^{\lambda'}$, where $\lambda'$ is a shape of size $n$ preserved by transposition.
Additionally, it is straightforward to show that the sets of permutations where $Q(w) = Q(w^{-1 rc})$ or $Q(w) = Q(w^{-1 r})$ are respectively equal to the previous two sets under the reverse operation.
This leaves only permutations which have fixed recording tableaux under the reverse and the reverse complement maps to count.

%First page headline in AmS-LaTeX for S\'eminaire Lotharingien de Combinatoire
%--restoring the headers and pagenumbering
\pagenumbering{arabic}
\addtocounter{page}{1}
\markboth{\SMALL T. J. ERVIN, B. JACKSON, J. LANE, K. LEE, S. D. NGUYEN, J. O'DONOHUE, AND M. VAUGHAN}
{\SMALL REVERSE PERMUTATIONS IN THE RS CORRESPONDENCE}


The question of what permutations have fixed recording tableaux under the reverse map may have been posed previously, but we first encountered the problem when using Jeremy L. Martin's ``Lecture Notes on Algebraic Combinatorics'' \cite[Exercise 9.8(b)]{M}.
In this paper we describe and count the permutations, $w$, such that $Q(w) = Q(w^r)$.
Our main theorem is as follows.

\begin{Thm} \label{main-theorem}
Let $w \in \mathfrak{S}_n$.
Then $Q(w) = Q(w^r)$ if and only if $Q(w)$ satisfies both of the following properties:
\begin{itemize}

\item $Q(w)$ has a symmetric hook shape,

\item The element $i$ in the first row of $Q(w)$ implies that $n-i+2$ belongs to the first column of $Q(w)$ for all $i \in [n]$ with $i > 1$.

\end{itemize}
In particular, we have the formula
$$|\{w \in \mathfrak{S}_n \mid Q(w) = Q(w^r)\}| =
\begin{dcases}
	2^{\frac{n-1}{2}}\binom {n-1 } {\frac{n-1}{2}} ,& n \text{ odd,} \\
	0 ,& n \text{ even.} \\
\end{dcases}$$
\end{Thm}
A forthcoming paper will attempt to answer Martin's additional question of what permutations satisfy $Q(w) = Q(w^{rc})$.

As for the structure of this paper, Section~\ref{background} covers background, notation, and definitions needed throughout the paper.
Section~\ref{theta} introduces a family of maps $\Phi_n$ and a function $\theta_n$ which map symmetric groups to ``neighboring'' symmetric groups.
These maps further allow us to prove Theorem~\ref{main-theorem} in Section~\ref{proof-conjectures}.

\noindent \textit{Acknowledgements.} We thank Nick Loehr, Jeremy Martin, Bruce Sagan, and Richard Stanley for their correspondence and insight on earlier drafts.
We also thank the anonymous referee for their detailed reports, which greatly improved the paper.

\section{Background, Notation, and Definitions} \label{background}
%
%\begin{Def} \label{def-RSK}
%The {\bf Robinson-Schensted-Knuth (RSK) correspondence} defines a bijective correspondence between permutations of $n$ letters and pairs of standard tableaux of shape $\lambda \vdash n$:
%$$\mathfrak{S}_n \longrightarrow \bigcup_{\lambda \vdash n} SYT(\lambda) \times SYY(\lambda)$$
%\end{Def}

As the RS correspondence is a bijection from permutations to standard Young tableaux, we begin by fixing our notation.
Let $[n]$ denote the set of letters $1,2, \dots, n$.
We write permutations of $[n]$ in one-line notation so that 
$$\mathfrak{S}_n=\{w = w_1 \dots w_n \mid \{w_1,\dots,w_n\}=[n] \}.$$ 
In other words, $w$ represents the permutation 
$$\sigma = \begin{pmatrix}
1 & 2 & \cdots & n \\
w_1 & w_2 & \cdots & w_n
\end{pmatrix}.$$

A shape $\lambda$ of size $n$, denoted $\lambda \vdash n$, is a tuple $\lambda = (\lambda_1, \lambda_2, \dots, \lambda_k)$ for some $1 \leq k \leq n$ such that $\sum_{i=1}^k\lambda_i = n$ and $\lambda_1 \geq \lambda_2 \geq \dots \geq \lambda_k$.
A Young diagram of shape $\lambda$ is formed from left justified boxes, where the $i$th row from the top has $\lambda_i$ empty boxes.
We often refer to boxes or cells by their coordinates $(i,j)$, where $i$ and $j$ respectively count the number of rows from the top and the number of columns from the left.
For example, the shape $\lambda = (3,1,1)$ gives us the Young diagram of shape $\lambda$:
$$\young(\hfil\hfil\hfil,\hfil,\hfil).$$
We call any cell of a Young diagram whose removal would produce a smaller Young diagram an inner corner.
The last cell in the top row and the first cell in the third row --- located at coordinates $(1,3)$ and $(3,1)$ respectively --- of the Young diagram above are inner corners.

A tableau $T$ of shape $\lambda$ is a filling of a Young diagram of shape $\lambda$ with positive integers that is increasing left-to-right and top-to-bottom.
The entry at cell $(i,j)$ is denoted by $T_{i,j}$.
If $\lambda$ is of size $n$, then we say that a tableau of shape $\lambda$ is of size $n$ as well.
When $\lambda = (3,1,1)$, the following are all tableaux of shape $\lambda$:
$$\young(123,4,5) \qquad  \young(126,4,7) \qquad \young(134,2,5).$$
In the case where a tableau is of size $n$ and the filling uses each of the integers in $[n]$ exactly once, we say that the tableau is a standard Young tableau.
The previous example consists of two standard Young tableaux--the first and third.
Finally, we denote the set of all standard Young tableaux of shape $\lambda$ by $\text{SYT}(\lambda)$.
We can now describe the method by which we turn a permutation into a pair of standard Young tableaux.

\begin{Def} \label{row-insertion}
Let $T$ be a tableau and let $x$ be a positive integer that is not already an entry of $T$.
Then the {\it Schensted insertion} or {\it row-insertion  algorithm} $T \leftarrow x$ is defined as follows:
\begin{itemize}
	\item If $T = \emptyset$, then $T \leftarrow x = \young(x)$.
	\item If $x > u$ for all entries $u$ in the top row of $T$, then append $x$ to the end of the top row of $T$.
	\item Otherwise, find the leftmost entry $u$ such that $x < u$. Replace $u$ with $x$, and then perform the row-insertion with $u$ in the subtableau consisting of the second and succeeding rows. In this case, we say $x$ {\it bumps} $u$.
	\item Repeat until the bumping stops. 
\end{itemize}

To obtain the promised pair of standard Young tableaux, we let $P(w)$ be the {\it insertion tableau} given by $((\emptyset \leftarrow w_1) \leftarrow w_2) \leftarrow \cdots \leftarrow w_n$ and let the {\it recording tableau} $Q(w)$ be the standard tableau of the same shape as $P(w)$ that records where the new box appears in the underlying Young diagram at each step. 
The RS correspondence is the map $w \mapsto (P(w),Q(w))$.
\end{Def}

\begin{Exa} \label{exa-RSK}
Consider $52314 \in \mathfrak{S}_5$.\\
{\sc Step 1:} The initial tableau is empty.
$$ P = \young(5) \qquad Q = \young(1)$$
{\sc Step 2:} 2 bumps 5.
$$ P = \young(2,5) \qquad Q = \young(1,2)$$
{\sc Step 3:} 3 appends to the first row.
$$ P = \young(23,5) \qquad Q = \young(13,2)$$
{\sc Step 4:} 1 bumps 2, 2 bumps 5.
$$ P = \young(13,2,5) \qquad Q = \young(13,2,4)$$
{\sc Step 5:} 4 appends to the first row.
$$ P = \young(134,2,5) \qquad Q = \young(135,2,4)$$
\end{Exa}

One can easily check that $w = 52314$ satisfies $Q(w) = Q(w^r)$.
We next define the evacuation process, beginning with the concept of a skew shape and skew tableau.
A skew shape $\lambda/\mu$ is defined for any shapes $\lambda$ and $\mu$ such that the Young diagram of shape $\mu$ is contained in the Young diagram of shape $\lambda$, i.e., we have $\mu_i \leq \lambda_i$ for all $i$.
If $\lambda = \mu$, then $\lambda/\mu = \emptyset$ is the diagram with no cells.
Skew diagrams are given by the removal of the cells belonging to the diagram of shape $\mu$ from the diagram of shape $\lambda$.
For example, if $\lambda = (3,1,1)$ and $\mu = (2)$, the skew diagram of shape $\lambda / \mu$ is
$$\young(::~,~,~).$$
A skew tableau is any tableau of skew shape $\lambda/\mu$.

\begin{Def}[{\cite[Definition 3.7.2]{Sa}}] \label{def-jeu-de-taquin}
A forward \textbf{jeu de taquin slide} of a skew tableau $T$ of shape $\lambda / \mu$ is given by:

\begin{itemize}

\item Pick $\alpha$ to be an inner corner of $\mu$.
Note that if $\alpha$ does not share at least one cell of $\lambda$ as a neighbor in $\lambda / \mu$, then it must also be an inner corner of $\lambda$.

\item While $\alpha$ is not an inner corner of $\lambda$ do:

\begin{itemize}

\item Suppose that $\alpha = (i,j)$.
As $\alpha$ is not an inner corner of $\lambda$, at least one of the cells $(i+1,j)$ and $(i, j+1)$ must exist in $\lambda$.

\item If only the cell $(i+1,j)$ exists in $\lambda$, let $\alpha'$ be the cell $(i+1,j)$.
Similarly, if only the cell $(i, j+1)$ exists in $\lambda$, let $\alpha'$ be the cell $(i, j+1)$.

\item If both $(i+1,j)$ and $(i, j+1)$ exist in $\lambda$, let $\alpha'$ be the cell of min$\{T_{i+l,j}, T_{i,j+1}\}$, where $T_{i+1,j}$ and $T_{i,j+1}$ are the fillings at cells $(i+1,j)$ and $(i, j+1)$ respectively.

\item Slide $T_{\alpha'}$ into cell $\alpha$ and let $\alpha := \alpha'$.

\end{itemize}

\end{itemize}

The resulting tableau is denoted $j^\alpha(T)$.
\end{Def}

\begin{Def}[{\cite[Definition 3.9.1]{Sa}}] \label{def-delta}
For any tableau $Q$ with distinct entries, let $m$ be the minimal element of $Q$.
Then the \textbf{delta operator} applied to $Q$ yields a new tableau, $\Delta Q$, given by performing the following steps:
\begin{itemize}

\item Erase $m$ from its cell, $\alpha$, in $Q$.

\item Perform the slide $j^\alpha$ on the resultant tableau.

\end{itemize}
\end{Def}

\begin{Def}[{\cite[Definition 3.9.1]{Sa}}] \label{def-evacuation}
For any standard Young tableau $Q$ on $n$ elements, we define the \textbf{evacuation tableau}, $\epsilon(Q)$, as the vacating tableau for the sequence 
$$Q, \Delta Q, \Delta^2 Q, \dots, \Delta^n Q.$$
That is, the cell $\alpha$ of $\epsilon(Q)$ contains $n - i$ if cell $\alpha$ was vacated when passing from $\Delta^i Q$ to $\Delta^{i+1}Q$.
\end{Def}

Again, we return to our previous example to demonstrate evacuation.

\begin{Exa} \label{exa-eva}
Consider $Q(52314)$, which was calculated in Example \ref{exa-RSK}.\\
{\sc Step 1:} Cell (3,1) is vacated.
$$ \Delta Q = \young(235,4) \qquad \epsilon(Q) = \young(\hfil\hfil\hfil,\hfil,5)$$
{\sc Step 2:} Cell (1,3) is vacated.
$$ \Delta^2 Q = \young(35,4) \qquad \epsilon(Q) = \young(\hfil\hfil4,\hfil,5)$$
{\sc Step 3:} Cell (2,1) is vacated.
$$ \Delta^3 Q = \young(45) \qquad \epsilon(Q) = \young(\hfil \hfil 4,3,5)$$
{\sc Step 4:} Cell (1,2) is vacated.
$$ \Delta^4 Q = \young(5) \qquad \epsilon(Q) = \young(\hfil 24,3,5)$$
{\sc Step 5:} The final cell (1,1) is vacated.
$$ \Delta^5 Q = \emptyset \qquad \epsilon(Q) = \young(124,3,5)$$
\end{Exa}

Immediately, we see that $\epsilon(Q(w))^T = Q(w)$ for $w = 52314$, as expected from $Q(w) = Q(w^r)$.
To prove Theorem~\ref{main-theorem}, we first construct three sets that will be used to great effect in Section~4.

\begin{Def} \label{def-R-H-M}
Define two sets of permutations:
$$R_n=\{ w\in \mathfrak{S}_n \mid Q(w)=Q(w^r)  \}$$
and 
$$H_n=\{ w\in \mathfrak{S}_n \mid Q(w)\text{ is of symmetric hook shape}  \},$$
where a symmetric shape is one that shares the same shape with its transpose as Young diagrams and a hook shape tableau has an underlying Young diagram of shape $\mu = (k,1^{n-k}), \ k < n$.
Note that $H_n$ is empty for all even $n$, as there are no symmetric hook shape tableaux for even $n$.

Concerning to sets of standard Young tableaux, for all shapes $\lambda \vdash n$ define the sets
$$M_n^\lambda= \{Q \in \text{SYT}(\lambda) \mid  \epsilon(Q)^T = Q\}.$$
\end{Def}

We now split Theorem~\ref{main-theorem} into two parts.
Theorem~\ref{hooks}, combined with the fact that $H_n$ is empty for all even $n$, sheds light on some of the subtleties of the main result, specifically the dependence on the parity of $n$.

\begin{Thm} \label{hooks}
For all $n \geq 1$, the set $R_n$ is a subset of $H_n$, forcing $Q(w)$ to have a symmetric hook shape for all $w \in R_n$.
\end{Thm}

Finally, Theorem~\ref{count-stuff} --- previously a conjecture --- is what began our research direction.

\begin{Thm} \label{count-stuff}
The cardinality of the set $R_n$ is given by
$$|R_n| =
\begin{dcases}
	2^{\frac{n-1}{2}}\binom {n-1 } { \frac{n-1}{2}} ,& n \text{ odd,} \\
	0, & n \text{ even.} \\
\end{dcases}$$
\end{Thm}

\section{The Maps $\phi_{a,b}$ and Their Left Inverse} \label{theta}

To begin proving Theorem~\ref{hooks}, we define a family of maps that take permutations of $[n]$ to permutations of $[n+2]$ arising from the standardization of a sequence of distinct integers.

\begin{Def} \label{def-standardization}
Let $v = v_1v_2\dots v_n$ be any sequence of distinct positive integers and $v_{i_1} < v_{i_2}< \dots < v_{i_n}$ be the ordering of the integers $v_i$.
The standardization of $v$, denoted $\std(v)$, is obtained by replacing each integer $v_{i_j}$ in $v$ by the integer $j$.
\end{Def}

Since both the reverse and complement operators will change increasing sequences to decreasing and vice-versa, it is apparent that $\std(v^r) = \std(v)^r$ and $\std(v^c) = \std(v)^c$ for all sequences of distinct positive integers $v$.
We may then define our maps $\phi_{a,b}$.

\begin{Def} \label{def-phi-a-b}
For any $w \in \mathfrak{S}_n$ and any two distinct integers $a,b \in [n+2]$, let $v = v_1v_2\dots v_n$ be the unique sequence of integers from $[n+2] \setminus \{a,b\}$ such that $\std(v) = w$.
Define the map $\phi_{a,b} : \mathfrak{S}_n \mapsto\mathfrak{S}_{n+2}$ by $\phi_{a,b}(w) = avb$, where adjacency denotes concatenation.
These maps are then well-defined for all distinct $a,b \in [n+2]$.
Let $\Phi_n$ denote the family of maps $\phi_{a,b}$ from $\mathfrak{S}_n$ to $\mathfrak{S}_{n+2}$.
\end{Def}

\begin{Exa} \label{exa-phi}
Application of $\phi_{1,7}$ to $52314 \in \mathfrak{S}_5$ produces
$$\phi_{1,7}(52314) = 1634257.$$

As we saw previously, the permutation $52314$ belongs to $R_5$, but $\phi_{1,7}(52314)$ does not belong to $R_7$.
When $w \in R_n$ implies $\phi_{a,b}(w) \in R_{n+2}$ is explored in Lemma~\ref{phi-preserves-R}.

\end{Exa}

\begin{Rmk} \label{rmk-phi}
Now that we have seen the maps in action, we can speak more of their properties.

\begin{itemize}
	\item Each map $\phi_{a,b}$ is injective.
	
	\item In general, the maps $\phi_{a,b}$ are not group homomorphisms, as $\phi_{a,b}$ only sends the identity element to the identity element when $a = 1$ and $b = n+2$. However, the map $\phi_{1, n+2}$ is a group monomorphism. 
	
	\item If $\phi_{a,b}(w) = \phi_{x,y}(w)$ for any $w \in \mathfrak{S}_n$, then $a = x$ and $b = y$.
	
	\item The set $\mathfrak{S}_{n+2}$ is partitioned by the images of the functions $\phi_{a,b}$.
	
\end{itemize}

\end{Rmk}

The $\Phi_n$ maps go ``up'' the symmetric groups, but we need a function to go ``down'' from $\mathfrak{S}_{n+2}$ to $\mathfrak{S}_n$.
We then construct a left inverse function shared by every $\phi_{a,b} \in \Phi_n$.

\begin{Def} \label{def-theta}
We define the map $\theta_n : \mathfrak{S}_{n+2} \mapsto\mathfrak{S}_n$ as follows.
If $w = w_1w_2\dots w_{n+1}w_{n+2}\in \mathfrak{S}_{n+2}$, form the subword $w' = w_2w_3\dots w_{n}w_{n+1}$.
Then $\theta_n(w) = \std(w')$.
These maps are well defined for all positive integers $n$.
\end{Def}

\begin{Exa} \label{exa-theta}
If we apply $\theta_3$ to our permutation $52314$, then we arrive at
$$\theta_3(52314) = 231.$$

Note that $\theta_n$ seems to send $R_{n+2}$ to $R_n$, as every permutation, $w$, above has $Q(w) = Q(w^r)$.
This relation is further explored in Lemma~\ref{theta-preserves-R}.
\end{Exa}

\begin{Rmk} \label{rmk-theta-properties}
As before, we will now list some of the important properties of $\theta_n$.
\begin{itemize}
	\item Each map $\theta_n$ is surjective.
	
	\item For all $\phi_{a,b} \in \Phi_n$ and $w \in \mathfrak{S}_n$, $\theta_n$ acts as a left inverse, i.e.,
	$$\theta_n(\phi_{a,b}(w)) = w.$$
	
	\item If $i,j \in [n]$, then $w_{i+1} < w_{j+1}$ implies that $\theta_n(w)_i < \theta_n(w)_j$, following directly from our definition of standardization.
	
\end{itemize}
\end{Rmk}

Because $\theta_n$ is a left inverse and the images of the $\Phi_n$ maps partition $\mathfrak{S}_{n+2}$, we immediately see that
$$\theta_n^{-1}(w) = \biguplus_{\phi_{a,b} \in \Phi_n} \phi_{a,b}(w).$$  
Combined with the next two lemmas, this fact is instrumental in proving Theorem~\ref{hooks}.

\begin{Lem} \label{theta-r-c}
For any $w \in \mathfrak{S}_{n+2}$,
$$\theta_n(w^r) = \theta_n(w)^r$$
and
$$\theta_n(w^c) = \theta_n(w)^c.$$
\end{Lem}

\begin{proof}

From the definition of $\theta_n$, we know that $\theta_n(w^r)$ equals the standardization of the sequence $w_{n+1}w_{n}\dots w_3w_2$.
Additionally, the permutation $\theta_n(w)^r = \std(w_2w_3 \dots w_n w_{n+1})^r$.
As $\std(w_{n+1}w_n \dots w_3 w_2) = \std(w_2w_3 \dots w_n w_{n+1})^r$, we must have  
$$\theta_n(w^r) = \theta_n(w)^r.$$

By a similar argument, we know that $\std((n+3-w_{2}) (n+3-w_3) \dots (n+3-w_n)(n+3-w_{n+1})) = \std(w_2w_3 \dots w_n w_{n+1})^c$.
Hence
$$\theta_n(w^c) = \theta_n(w)^c,$$
proving our desired result.
\end{proof}

\begin{Lem} \label{phi-preserves-symmetry}
Choose $\phi_{a,b} \in \Phi_n$ and $w \in H_n$ for odd $n$.
Then either $\phi_{a,b}(w) \in H_{n+2}$ or $Q(\phi_{a,b}(w))$ is not of symmetric shape.
\end{Lem}

\begin{proof}
Let $w \in H_n$.
Suppose that $\phi_{a,b}(w) \notin H_{n+2}$ for some $\phi_{a,b} \in \Phi_n$.
As $\phi_{a,b}$ preserves all the relative orderings of $w$ by its construction, longest increasing and longest decreasing subsequences of $\phi_{a,b}(w)$ are the same length or longer than respective longest increasing and longest decreasing subsequences of $w$.
It is well-known that the lengths of the first row and the first column of $Q(w)$ equal the lengths of longest increasing and longest decreasing subsequences respectively of $w$ \cite[Theorem~3.3.2]{Sa}.
The first row and the first column of $Q(w)$ both have length $\frac{n+1}{2}$ as $Q(w)$ is of symmetric hook shape.
Hence, longest increasing and longest decreasing subsequences of $\phi_{a,b}(w)$ must have length at least $\frac{n+1}{2}$.
If $Q(\phi_{a,b}(w))$ is of symmetric shape, then the length of longest increasing and longest decreasing subsequences of $\phi_{a,b}(w)$ must equal each other. 
Since $\phi_{a,b}(w) \notin H_{n+2}$, longest increasing and decreasing subsequences necessarily have length $\frac{n+1}{2}$.
Thus two cells were added to the second row or column of $Q(\phi_{a,b}(w))$, contradicting the symmetry of $Q(\phi_{a,b}(w))$.
Therefore, either $\phi_{a,b}(w) \in H_{n+2}$ or $Q(\phi_{a,b}(w))$ is not of symmetric shape.
\end{proof}

As an example of the possibilities discussed in Lemma~\ref{phi-preserves-symmetry}, we give the following.

\begin{Exa}
Consider the Young diagram of symmetric hook shape 
$$\yng(3,1,1).$$
After an application of a $\phi_{a,b} \in \Phi_n$, two new cells will be added to the diagram. 
There are four possibilities --- up to transposition --- for the resulting shape:
$$\yng(4,1,1,1) \qquad \yng(4,2,1) \qquad \yng(5,1,1) \qquad \yng(3,3,1).$$
Clearly, only the tableau in $H_7$ has symmetric shape. 
\end{Exa}

\section{Proof of Theorems \ref{hooks} and \ref{count-stuff}} \label{proof-conjectures}

To begin our proof of Theorem~\ref{hooks}, we first prove the two lemmas we mentioned previously when exploring the actions of the $\Phi_n$ and $\theta_n$ maps.

\begin{Lem} \label{theta-preserves-R}
If $w \in R_{n+2}$, then $\theta_n(w) \in R_n$.
\end{Lem}

\begin{proof}

Suppose that $w \in R_{n+2}$.
Let $x = w_2 w_3 \dots w_{n+2}$ and $y = w_{n+1}w_{n}\dots w_1$.
Then $Q(x) = \Delta Q(w)$ and $Q(y) = \Delta Q(w^r)$  \cite[Proposition~3.9.3]{Sa}.
As $w \in R_{n+2}$, we have $Q(w) = Q(w^r)$, showing that $Q(x) = Q(y)$.
Since $n+1$ occupies the same cell in $Q(x)$ and $Q(y)$, not inserting $w_{n+2}$ or $w_1$ in the respective $x$ and $y$ cases produces the same recording tableau.
Hence,
$$Q(w_2 w_3 \dots w_{n+1}) = Q(w_{n+1} w_{n} \dots w_2).$$

As $\theta_n$ preserves all the relative orderings among middle entries of permutations by our definition of standardization, it follows that
$$Q(\theta_n(w)) = Q(w_2 w_3 \dots w_{n+1})$$
and
$$ Q(\theta_n(w^r)) = Q(w_{n+1} w_{n} \dots w_2).$$
As Lemma~\ref{theta-r-c} proves $Q(\theta_n(w)^r) = Q(\theta_n(w^r)),$ the equality 
$$Q(\theta_n(w)) = Q(\theta_n(w)^r)$$
holds.
Therefore, the permutation $\theta_n(w)$ belongs to $R_n$ for all $w \in R_{n+2}$.
\end{proof}

\begin{Lem} \label{phi-preserves-R}
For all $n$, we have 
$$R_{n+2} \subseteq \bigcup_{\phi_{a,b} \in \Phi_n} \phi_{a,b}(R_{n}).$$
\end{Lem}

\begin{proof}

If $w \in R_{n+2}$, Lemma~\ref{theta-preserves-R} gives us that $\theta_n(w) \in R_n$.
Thus $w \in \phi_{w_1,w_{n+2}}(R_n)$.
Hence,
$$R_{n+2} \subseteq \bigcup_{\phi_{a,b} \in \Phi_n} \phi_{a,b}(R_{n})$$
for all $n$.
\end{proof}

\begin{Thm}[Theorem \ref{hooks}] \label{proof-conj-hooks}
For all $n \geq 1$, the set $R_n$ is a subset of $H_n$, forcing $Q(w)$ to have a symmetric hook shape for all $w \in R_n$.
\end{Thm}

\begin{proof}

We split into two separate induction arguments, one odd and one even.
In the odd scenario, the base case of $n = 1$ is clear, as $R_1 = H_1 = \mathfrak{S}_1$.
As such, we assume that $R_{n-2} \subseteq H_{n-2}$ for $n = 2\ell + 1$.
If $v \in \mathfrak{S}_n$, then $P(v) = P(v^r)^T$ \cite[Theorem~3.2.3]{Sa}.
Hence the shape of $Q(v)$ must be symmetric for all $v\in R_n$.
If $\phi_{a,b}(w)$ is not in $H_n$ for a $\phi_{a,b} \in \Phi_{n-2}$ and some $w \in R_{n-2}$, then the shape of $Q(\phi_{a,b}(w))$ is non-symmetric by Lemma~\ref{phi-preserves-symmetry}.
This further implies that $\phi_{a,b}(w)$ is not in $R_n$.
The contrapositive gives that $\phi_{a,b}(w) \in R_n$ implies $\phi_{a,b}(w) \in H_n$.

From Lemma~\ref{phi-preserves-R}, we have $R_{n} \subseteq \bigcup_{\phi_{a,b} \in \Phi_{n-2}} \phi_{a,b}(R_{n-2}).$
Thus every element of $R_n$ is of the form $\phi_{a,b}(w)$ for $\phi_{a,b} \in \Phi_{n-2}$ and $w \in R_{n-2}$.
Therefore $R_n \subseteq H_n$, completing the inductive step.

In the even case, the base case of $n = 2$ is clear, as $R_2 = H_2 = \emptyset$.
The set $H_n$ is empty for all even $n$.
As such, we assume that $R_{n-2}$ is empty for $ n = 2\ell$.
If $R_n$ is non-empty, Lemma~\ref{theta-preserves-R} gives us that $\theta_{n-2}(R_n) \subseteq R_{n-2}$, creating a contradiction of our inductive assumption.
Hence $R_n$ must be empty and a subset of $H_n$ as well, completing the inductive step.
Therefore $R_n \subseteq H_n$ for all $n$.
\end{proof}

Furthermore, if $\lambda \vdash n$ is a symmetric hook shape for $n > 1$, then the tableau $T$ of shape $\lambda$ with entries $1, 2, 3, \dots, \frac{n+1}{2}$ in the first row and entries $1, \frac{n+3}{2}, \frac{n+5}{2}, \dots, n$ in the first column can be readily seen to satisfy $T = \epsilon(T)^T$.
Thus $T \in M_n^{\lambda}$.
For $n = 5$, we have the example
$$T = \young(123,4,5).$$

\begin{Cor} \label{M-empty}

For all $\lambda \vdash n$, the set $M_n^{\lambda}$ is non-empty if and only if $\lambda$ is a symmetric hook shape.

\end{Cor} 

\begin{Rmk} \label{rmk-hook}
It should be stressed that $R_n$ really is a \textit{proper subset} of $H_n$ for odd $n \geq 5$. 
In other words, there are $w \in \mathfrak{S}_n$ that are of symmetric hook shape but do not have fixed recording tableaux under the reverse operation. 
The permutation $34521$ is such an example.
\end{Rmk}

Since we have shown that $M_n^{\lambda}$ is only non-empty when $n$ is odd and $\lambda$ is a symmetric hook shape, we may restrict ourselves to those conditions and begin to examine the properties of $Q \in M_n^{\lambda}$.

\begin{Lem} \label{first-row-M}
For odd $n$, let $\lambda = (\frac{{n + 1}}{2},1^{\frac{{n - 1}}{2}})$.
The standard Young tableau $Q$ belongs to $M_n^{\lambda}$ if and only if $i$ in the first row of $Q$ implies that $n-i+2$ belongs to the first column of $Q$ for all $i \in [n]$ with $i > 1$.
\end{Lem}
\begin{proof}

Suppose that $Q \in M_n^{\lambda}$. 
Additionally assume that $i$ is in the first row of a symmetric hook shape tableau, $Q$, where $i \in [n]$ and $i > 1$.
The cell vacated when passing from $\Delta^{i-2} Q$ to $\Delta^{i-1} Q$ is filled with $n-i+2$ in $\epsilon(Q)$.
As $i-1$ is minimal in $\Delta^{i-2} Q$, it appears in the first cell of $\Delta^{i-2} Q$ and $i$ is in the cell to its right.
Hence the cell vacated when passing from $\Delta^{i-2} Q$ to $\Delta^{i-1} Q$ will be in the first row.
Thus $n-i+2$ appears in the first row of $\epsilon(Q)$ if $i$ appears in the first row of $Q$.
As $Q = \epsilon(Q)^T$, the location of $i$ in the first row of $Q$ implies that $n-i+2$ belongs to the first column of $Q$ for all $i \in [n]$ with $i > 1$ whenever $Q \in M_n^{\lambda}$.

Conversely, suppose that $i$ in the first row of $Q$ implies that $n-i+2$ belongs to the first column of $Q$ for all $i \in [n]$ with $i > 1$.
Let $1,i_2, i_3, \dots, i_{\frac{n+1}{2}}$ be the increasing sequence that forms the first row of $Q$.
Thus $1, n-i_{\frac{n+1}{2}}+2, \dots, n-i_3+2, n-i_2+2$ must be the increasing sequence that forms the first column of $Q$.
The cell erased when passing from $\Delta^{i-2}Q$ to $\Delta^{i-1}Q$ always contains $i-1$ and is located in the uppermost left corner of the tableau.
This implies that the cell vacated from $\Delta^{i-2}Q$ to $\Delta^{i-1}Q$ will belong to the same row or column in $Q$ as $i$.
Hence $\epsilon(Q)$ will have $n-i+2$ in its first row whenever $i$ is in the first row of $Q$.
This further implies that $1, n-i_{\frac{n+1}{2}}+2, \dots, n-i_3+2, n-i_2+2$ must be the increasing sequence that forms the first row of $\epsilon(Q)$.
Similarly, the first row of $Q$ and the first column of $\epsilon(Q)$ must coincide.
Hence $Q = \epsilon(Q)^T$ whenever $i$ in the first row of $Q$ implies that $n-i+2$ belongs to the first column of $Q$ for all $i \in [n]$ with $i > 1$.
Therefore, for odd $n$, the standard Young tableau $Q$ belongs to $M_n^{\lambda}$ if and only if $i$ in the first row of $Q$ implies that $n-i+2$ belongs to the first column of $Q$ for all $i \in [n]$ with $i > 1$.
\end{proof}

Returning to the previous Example \ref{exa-RSK}, we can verify that the tableau $Q(52314) \in M_5^{\lambda}$ by Lemma~\ref{first-row-M}.
Lemma~\ref{size-M} follows immediately from Lemma~\ref{first-row-M}, and it allows us to correctly count the number of tableaux in $M_n^{\lambda}$.

\begin{Lem} \label{size-M}
Let $\lambda = (\frac{{n + 1}}{2},1^{\frac{{n - 1}}{2}})$.
If $n$ is odd, then
$$|M_n^{\lambda}| = 2^{\frac{n-1}{2}}.$$
\end{Lem}

We may then prove Theorem~\ref{count-stuff}.

\begin{Thm}[Theorem \ref{count-stuff}] \label{proof-conj-count}
The cardinality of the set $R_n$ is given by
$$|R_n| =
\begin{dcases}
	2^{\frac{n-1}{2}}\binom {n-1} { \frac{n-1}{2}} ,& n \text{ odd,} \\
	0 ,& n \text{ even.} \\
\end{dcases}$$
\end{Thm}

\begin{proof}

For even $n$, the result follows directly from Theorem~\ref{proof-conj-hooks} as $R_n$ is empty.
We then focus on odd $n$.
Let $\lambda = (\frac{{n + 1}}{2},1^{\frac{{n - 1}}{2}})$.
If $w \in R_n$, then $Q(w) = Q(w^r) = \epsilon(Q(w))^T$ \cite[Theorem~3.9.4]{Sa}.
Thus $Q(w) \in M_n^{\lambda}$ for all $w \in R_n$.

Let $T \in  M_n^{\lambda}$.
The number of pairs of standard Young tableaux with $T$ as the recording tableau is equal to the number of standard Young tableaux of shape $\lambda$.
As the RSK correspondence is a bijection of permutations and pairs of standard Young tableaux, there are $f^{\lambda} = \binom {n-1 } { \frac{n-1}{2}}$ many $w \in \mathfrak{S}_n$ such that $Q(w) = T$.
If $Q(w) \in M_n^{\lambda}$, then $Q(w) = \epsilon(Q(w))^T =  Q(w^r)$.
Thus $w \in R_n$.
The cardinality of $R_n$ must then be $|M_n^{\lambda}|f^{\lambda}$ for all odd $n$.

Therefore,
$$|R_n| =
\begin{dcases}
	2^{\frac{n-1}{2}}\binom {n-1 } { \frac{n-1}{2}} ,& n \text{ odd,} \\
	0 ,& n \text{ even.} \\
\end{dcases}$$
proving the desired result.
\end{proof}
Theorems~\ref{proof-conj-hooks} and \ref{proof-conj-count}, along with Lemma~\ref{first-row-M}, combine to prove Theorem~\ref{main-theorem}.

\begin{thebibliography}{6}

\bibitem{K} D. E. Knuth, {\em Permutations, matrices, and generalized Young tableaux}, Pacific Journal of Mathematics, {\bf 34}: 709--727, 1970.

\bibitem{Ro} G. de B. Robinson, {\em On the representations of the symmetric group}, American Journal of Mathematics, {\bf60} (3): 745--760,  1938.

\bibitem{Sa} B. E. Sagan, {\em The Symmetric Group}, 2nd edition,
  Graduate Texts in Mathematics, {\bf 203}, New York: Springer-Verlag, 2001.

\bibitem{Sc} C. Schensted, {\em Longest increasing and decreasing subsequences}, Canadian Journal of Mathematics, {\bf 13}: 179--191, 1961. 

\bibitem{M} J. L. Martin, {\em Lecture Notes on Algebraic Combinatorics}, Available online at\newline
  {\tt https://jlmartin.ku.edu/CombinatoricsNotes.pdf} (updated March 12, 2021), 2021.

\bibitem{L} M. V. Leeuwen, {\em The Robinson--Schensted and Sch\"utzenberger algorithms, an elementary approach}, The Electronic Journal of Combinatorics, {\bf 3} (2): Article~R15, 32~pp., 1996.
\end{thebibliography}

\end{document}
