\documentclass[12pt]{article} % %%\documentclass[11pt,reqno,a4paper,twoside]{amsart} %%\usepackage{fullpage} \usepackage{e-jc} % %%\usepackage{fullpage} \usepackage{tikz} \usetikzlibrary{fit} \usepackage{bbm} \usepackage{amsmath,amsthm} \usepackage{color} \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} % %-\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}} % %-\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}} % \theoremstyle{plain} % \numberwithin{equation}{section} \newtheorem{theorem}{Theorem}[section] % \newtheorem{lemma}[theorem]{Lemma} % \newtheorem{corollary}[theorem]{Corollary} % \newtheorem{proposition}[theorem]{Proposition} % \newtheorem{fact}[theorem]{Fact} % \newtheorem{observation}[theorem]{Observation} % \newtheorem{claim}[theorem]{Claim} % % \theoremstyle{definition} % \newtheorem{definition}[theorem]{Definition} % \newtheorem{example}[theorem]{Example} % \newtheorem{conjecture}[theorem]{Conjecture} % \newtheorem{open}[theorem]{Open Problem} % \newtheorem{problem}[theorem]{Problem} % \newtheorem{question}[theorem]{Question} % % \theoremstyle{remark} % \newtheorem{remark}[theorem]{Remark} % \newtheorem{note}[theorem]{Note} % %%\numberwithin{equation}{section} %%\newtheorem{proposition}{Proposition}[section] %%\newtheorem{corollary}[proposition]{Corollary} %%\newtheorem{theorem}[proposition]{Theorem} %%\newtheorem{otheorem}{Theorem} %%\newtheorem{conjecture}[proposition]{Conjecture} %%\newtheorem{problem}[proposition]{Problem} %%\newtheorem{definition}[proposition]{Definition} %%\newtheorem{example}[proposition]{Example} %%\newtheorem{lemma}[proposition]{Lemma} %%\newtheorem{comment}[proposition]{Comment} \newcommand\floor[2]{\left\lfloor \tfrac{#1}{#2} \right\rfloor} \newcommand\ceil[2]{\left\lceil\tfrac{#1}{#2} \right\rceil} \newcommand{\Perm}[1]{\mathsf{Perm}\left( #1 \right)} \renewcommand{\S}{\mathcal{S}} \newcommand{\T}{\mathcal{T}} \newcommand\mps[1]{\marginpar[\raggedleft\tiny\sf\textcolor{blue}{#1}]{\raggedright\tiny\sf\textcolor{blue}{#1}}} \newcommand{\odd}{\mathrm{odd}} \newcommand{\even}{\mathrm{even}} \newcommand\mycom[2]{\genfrac{}{}{0pt}{}{#1}{#2}} \newcommand{\ds}{\displaystyle} \newcommand{\des}{\mathrm{des}} \newcommand{\sn}{\mathfrak{S}_n} \newcommand{\s}{\mathfrak{S}} \newcommand{\sym}{\mathfrak{S}} \newcommand{\GETOUT}[1]{} \newcommand{\al}{\mbox{--}} \newcommand{\imp}{\Rightarrow} \newcommand{\goroman}{\renewcommand{\theenumi}{\roman{enumi}}} \newcommand{\leaveroman}{\renewcommand{\theenumi}{\arabic{enumi}}} \newcommand{\Left}{\mathsf{Left}} \newcommand{\aleft}[2]{\mathsf{left}_{#1}(#2)} \newcommand{\Right}{\mathsf{Right}} \newcommand{\aright}[2]{\mathsf{right}_{#1}(#2)} \newcommand{\Tack}[2]{\mathsf{Revstack}_{#1 , #2}} \newcommand{\Stack}[2]{\mathsf{Stack}_{#1 , #2}} \newcommand{\rev}{\mathsf{rev}} \newcommand{\id}{\mbox{id}} \def\revstack{revstack} \def\Revstack{\text{Revstack}} %\newcommand{\LittlePerm}[1]{\mbox{\footnotesize\scshape{PERM}}{\left\{#1\right\}}} \DeclareMathOperator{\LittlePerm}{{\mathsf{Perms}}} \def\diagramOne{ \begin{tikzpicture}[level distance=10mm] \tikzstyle{every node}=[fill=white!60,inner sep=1pt] \tikzstyle{level 1}=[sibling distance=30mm] \tikzstyle{level 2}=[sibling distance=20mm] \tikzstyle{level 3}=[sibling distance=10mm] \tikzstyle{level 4}=[sibling distance=5mm] \node at (-5,-2) {$\Tree(\pi)~=$}; \node at (0,0) {11} child {node {10} child {node {9} child {node {8} child {edge from parent[draw=none]} child{ node {7}} } child{ node {6} child{ node {4}} child{ node {1}} } } child {node {5} child{ node {3} child{ node {2}} child {edge from parent[draw=none]} } child {edge from parent[draw=none]} } } child {edge from parent[draw=none]}; \end{tikzpicture} } \def\diagramTwo{ \begin{tikzpicture}[level distance=10mm] \tikzstyle{every node}=[fill=white!60,inner sep=1pt] \tikzstyle{level 1}=[sibling distance=30mm] \tikzstyle{level 2}=[sibling distance=20mm] \tikzstyle{level 3}=[sibling distance=10mm] \tikzstyle{level 4}=[sibling distance=5mm] \node {$v_{11}$} child {node {$v_{10}$} child {node {$v_8$} child {node {$v_5$} child {edge from parent[draw=none]} child{ node {$v_1$}} } child{ node {$v_6$} child{ node {$v_2$}} child{ node {$v_3$}} } } child {node {$v_9$} child{ node {$v_7$} child{ node {$v_4$}} child {edge from parent[draw=none]} } child {edge from parent[draw=none]} } } child {edge from parent[draw=none]}; \end{tikzpicture} } \def\diagramThree{ \begin{tikzpicture}[level distance=10mm] \tikzstyle{every node}=[fill=white!60,inner sep=1pt] \tikzstyle{level 1}=[sibling distance=10mm] \tikzstyle{level 2}=[sibling distance=20mm] \tikzstyle{level 3}=[sibling distance=10mm] \tikzstyle{level 4}=[sibling distance=5mm] \node at (-1,-0.5) {$T_7 ~ =$}; \node at (0,0) {8} child {edge from parent[draw=none]} child{ node {7}}; \node at (2,0) {6} child{ node {4}} child{ node {1}}; \node at (4,0) {3} child{ node {2}} child {edge from parent[draw=none]}; \end{tikzpicture} } \def\diagramFour{ \begin{tikzpicture}[level distance=10mm] \tikzstyle{every node}=[fill=white!60,inner sep=1pt] \tikzstyle{level 1}=[sibling distance=30mm] \tikzstyle{level 2}=[sibling distance=20mm] \tikzstyle{level 3}=[sibling distance=10mm] \tikzstyle{level 4}=[sibling distance=5mm] \node at (-5,-2) {$h'(\Tree(\pi))~=$}; \node at (0,0) {11} child {node {10} child {node {9} child {node {8} child{ node {7}} child {edge from parent[draw=none]} } child{ node {6} child{ node {4}} child{ node {1}} } } child {node {5} child {edge from parent[draw=none]} child{ node {3} child {edge from parent[draw=none]} child{ node {2}} } } } child {edge from parent[draw=none]}; \end{tikzpicture} } %%\title{Revstack sort, zigzag patterns, descent polynomials of $t$-revstack sortable permutations, and Steingr\'imsson's sorting conjecture} %%\author{Mark Dukes} %%\address{Department of Computer and Information Sciences, University of Strathclyde, UK} %%\email{mark.dukes@ccc.oxon.org/mark.dukes@strath.ac.uk} \title{\bf Revstack sort, zigzag patterns, descent polynomials of $t$-revstack sortable permutations, and Steingr\'imsson's sorting conjecture} % \author{Mark Dukes\\ % \small Department of Computer and Information Sciences\\[-0.8ex] % \small University of Strathclyde\\[-0.8ex] % \small Glasgow G1 1XH\\[-0.8ex] % \small United Kingdom\\ % \small\tt mark.dukes@strath.ac.uk % } % % \date{\dateline{submission date}{acceptance date}\\ % \small Mathematics Subject Classifications: comma separated list of % MSC codes available from http://www.ams.org/mathscinet/freeTools.html} \date{\dateline{July 15, 2013}{2014}\\ % \small Mathematics Subject Classifications: 05A05, 68P10} % \begin{document} \begin{abstract} In this paper we examine the sorting operator $\T(LnR)=\T(R)\T(L)n$. Applying this operator to a permutation is equivalent to passing the permutation reversed through a stack. We prove theorems that characterise $t$-revstack sortability in terms of patterns in a permutation that we call {\it{zigzag}} patterns. Using these theorems we characterise those permutations of length $n$ which are sorted by $t$ applications of $\T$ for $t=0,1,2,n-3,n-2,n-1$. We derive expressions for the descent polynomials of these six classes of permutations and use this information to prove Steingr\'imsson's sorting conjecture for those six values of $t$. Symmetry and unimodality of the descent polynomials for general $t$-revstack sortable permutations is also proven and three conjectures are given. \end{abstract} \maketitle \section{Introduction} Let $\sn$ be the group of all permutations of $\{1,\ldots ,n\}$. The classical stack sort operator $\S$ on permutations~\cite{knuthvol1} may be defined in two equivalent ways. One way is to define it as an operator on words representing permutations: $\S(\epsilon)=\epsilon$ where $\epsilon$ is the empty permutation, $\S(x)=x$ where $x$ is a word of length 1, and $$\S(LnR) ~=~ \S(L)\S(R)n$$ where $n$ is the unique largest entry in the word $LnR$. For example, $$\S(42513) = \S(42)\S(13)5 = \S(2)4 \S(1)35 = 24135.$$ Another way to define $\S$ is as the output of pushing $\pi=\pi_1\cdots \pi_n\in\sn$ (from left to right) through a stack. The stack has the rule that an element may be above another element in the stack only if it is less than it. If the element at the top of the stack is not less than the next (leftmost) element of $\pi$ which is to next enter the stack, then elements of the stack must be popped from the stack (to the left) until this is the case. This is illustrated in Figure~\ref{fig1} for the permutation $\pi=42513$. \def\mlen{2} \def\mwidth{0.65} \def\sscale{1} \def\mxskip{5.4} \newcommand{\stackdiagram}[6]{ \draw (#5 + 0,#6 + 0)--(#5+ \mlen,#6+ 0) -- (#5+\mlen,#6-\sscale*\mlen) -- (#5+\mlen+\mwidth,#6-\sscale*\mlen) -- (#5+\mlen+\mwidth,#6+0); \draw (#5+\mlen+\mwidth,#6+0) -- (#5+2*\mlen+\mwidth,#6+0); \node at (#5+\mlen+\mwidth,#6+0) (A) {}; \node at (#5+\mlen,#6+0) (B) {}; \node at (#5+\mlen+0.5*\mwidth,#6-0.8*\sscale*\mlen) (C) {#3}; \node at (#5+\mlen+0.5*\mwidth,#6-0.4*\sscale*\mlen) (D) {#2}; \node[anchor=south west,inner sep=8pt] at (A.south west) {#4}; \node[anchor=south east ,inner sep=8pt] at (B.south east) {#1}; } \def\epsi{0.2} \def\aheigh{-0.8} \begin{figure}[!h] \begin{tikzpicture}[scale=0.5] \footnotesize \stackdiagram{}{}{}{42513}{0}{0} \stackdiagram{}{2}{4}{513}{1*\mxskip}{0} \stackdiagram{24}{}{}{513}{2*\mxskip}{0} \stackdiagram{24}{1}{5}{3}{3*\mxskip}{0} \stackdiagram{241}{3}{5}{}{4*\mxskip}{0} \stackdiagram{24135}{}{}{}{5*\mxskip}{0} \foreach \p in {1,2,3,4,5} \draw [gray,->,line width=2pt] (\p*\mxskip - 4*\epsi,\aheigh) -- (\p*\mxskip ,\aheigh); \end{tikzpicture} \caption{Moving the permutation $\pi = 42513$ through the stack once to get $\S(\pi)=24135$. First, 4 is pushed onto the stack, followed by 2. Since 5 is larger than both 2 and 4, both are popped from the stack before 5 can be pushed onto it. 1 is then pushed onto the stack. As 3 is not less than 1, but is less than 5, 1 is popped from the stack, 3 is pushed onto the stack, and then all stack elements are popped from the stack. \label{fig1}} \end{figure} It is clear that repeatedly applying $\S$ to a permutation will yield the identity permutation, and the operator $\S$ is therefore a sorting operator. The set of permutations which are sorted by at most one application of $\S$ is known to be the set of 231-avoiding permutations, and this result is often described as the first result in the combinatorics of permutation patterns. We will assume the reader is familiar with the basic terminology of permutation patterns~\cite{bona.book}. Variants of this operation and their analysis have also thrown up interesting connections to other areas of discrete mathematics. Recently, the author in collaboration with others showed how the sorting operation $B(LnR)=B(L)Rn$ describes one pass of the bubble-sort operator. Further to this, it was shown that permutations in $\sn$ which require at most $t$ passes of $B$ are in bijection with the set of ground state juggling sequences of period $n$ with $t$ balls~\cite{chung}. In this paper, we will consider another variant of the stack sort operator. We will call this variant {\it{\revstack\ sort}} and denote it by $\T = \S \circ \rev$, where $\rev$ is the operation that reverses the list that it acts upon. We may write a recursion for $\T$ as we did for $\S$ above: Given $\pi = L n R \in \sn$, $\T$ satisfies $$\T(LnR) ~=~ \T(R)\T(L)n,$$ $\T(\epsilon)=\epsilon$, and $\T(x)=x$ where $x$ is a word of length 1. For example, $\T(42513)=\T(13)\T(42)5 = \T(1)3 \T(2) 4 5 = 13245$. An equivalent way to describe this operation is that it is what results when a permutation is fed backwards into a stack. For $\pi = 42513$, this is illustrated in Figure~\ref{fig2}. This new sorting operation is interesting because it appears to be faster than stack sort in the following sense: \begin{conjecture}[Steingr\'imsson's sorting conjecture~\cite{einar}] \label{econj} For all $0 \leq t \leq n$, $$|\{ \pi \in \sn ~:~ \S^t(\pi) = \mathrm{id} \}| ~\leq ~ \{ \pi \in \sn ~:~ \T^t(\pi) = \mathrm{id} \}|,$$ where $\mathrm{id}$ is the identity permutation. Furthermore, this inequality is strict for all pairs $(n,t)$ that satisfy $2,line width=2pt] (\p*\mxskip - 4*\epsi,\aheigh) -- (\p*\mxskip ,\aheigh); \end{tikzpicture} \caption{Reversing the permutation $\pi= 42513$ and then moving it through a stack is equivalent to passing the rightmost elements of the permutation to the stack. From this we get $\T(42513)=13245$. \label{fig2}} \end{figure} Let $\Tack{n}{t} = \{ \pi \in \sn ~:~ \T^t(\pi)=\mbox{\id}\}$, the set of $t$-\revstack\ sortable permutations. Given $\pi \in \sn$, let $\deg_{\T}(\pi) = \inf\{ i ~:~ \T^i(\pi)=\id \mbox{ and } \T^{i-1}(\pi) \neq \id\}$, the number of applications of $\T$ that are required to sort $\pi$. \section{Classification theorems and zigzag patterns} In this section we will present classification theorems which assist us in deciding whether or not a permutation is $t$-revstack sortable. These classifications are in terms of {\it{zigzags}} which are subsequences of values in the permutation. These will be used to classify particular classes of $t$-\revstack\ sortable permutations. \begin{lemma}\label{LEMMA:1} %% Lemma 2.1 If $\pi \in \sn$, $1\leq a < b \leq n$, and $b$ precedes $a$ in $\pi$, then $a$ precedes $b$ in $\T(\pi)$ \end{lemma} \begin{proof} Since $b$ precedes $a$ in $\pi$, $a$ enters the stack before $b$. Since $ab$ such that $a$ precedes $c$ and $c$ precedes $b$ in $\pi$. If no such $c$ exists then $a$ precedes $b$ in $\T(\pi)$. \end{lemma} \begin{proof} If there is an element $c>b$ such that $a$ precedes $c$ and $c$ precedes $b$ in $\pi$, then $b$ will be the first of the three elements to enter the stack. Since $c>b$, element $b$ must be popped from the stack before $c$ enters the stack. It is only after $c$ enters the stack that $a$ may enter the stack and be popped. Thus $b$ precedes $a$ in $\T(\pi)$. If no such $c$ exists then all elements that appear between $a$ and $b$ in $\pi$ are less than $b$. Element $b$ will enter the stack and remain in the stack while $a$ enters. Element $a$ must be popped before element $b$, therefore $a$ precedes $b$ in $\T(\pi)$. \end{proof} \begin{lemma}\label{LEMMA:3} %% Lemma 2.3 $(b,a)$ is an inversion in $\T(\pi)$ iff there exists $c$ such that $(a,c,b)$ is a $132$ pattern in $\pi$. \end{lemma} \begin{proof} Lemma~\ref{LEMMA:1} tells us that an inversion $(b,a)$ in $\pi$ becomes a non-inversion $(a,b)$ in $\T(\pi)$. Lemma~\ref{LEMMA:2} tells us that a non-inversion $(a,b)$ in $\pi$ becomes an inversion $(b,a)$ in $\T(\pi)$ iff an element $c$ larger than both exists between the two in $\pi$. Thus if $(b,a)$ is an inversion in $\T(\pi)$ then there exists $c$ such that $(a,c,b)$ is an occurrence of the pattern $132$ in $\pi$. If $(a,c,b)$ is a 132 pattern in $\pi$, then applying $\T$ one finds that $b$ precedes $a$ in $\T(\pi)$, thereby forming an inversion $(b,a)$ in $\T(\pi)$. \end{proof} \begin{theorem}\label{THEOREM:1} $\Tack{n}{1} = \sn(132)$. \end{theorem} \begin{proof} A permutation $\pi \in \sn$ is in $\Tack{n}{1}$ iff $\T(\pi)=\id$, which occurs iff $\T(\pi)$ has no inversions. Lemma~\ref{LEMMA:3} tells us this happens precisely when $\pi$ is 132 avoiding. \end{proof} \begin{theorem}\label{mrbluesky} (i) If $\T(\sigma)$ contains $(a,c,b)$ as a $132$ pattern, then either $(b,d,c,a)$ is a $2431$ pattern in $\sigma$, or $(b,d,a,c)$ is a $2413$ pattern in $\sigma$ and there is no $e>c$ such that $(b,d,a,e,c)$ in $\sigma$.\\ (ii) If $\T(\sigma)$ contains a $132$ pattern, then $\sigma$ either contains a $2431$ pattern, or a $241\overline{5}3$ pattern. \end{theorem} \begin{proof} Lemmas~\ref{LEMMA:1}--\ref{LEMMA:3} provide us with the following information about patterns in $\sigma$ and $\T(\sigma)$. We will say `$(x,y)$ in $\sigma$' to mean $x$ precedes $y$ in the the word representing the permutation $\sigma$, and `$(x,y,z)$ in $\sigma$' to mean $x$ precedes $y$ and $y$ precedes $z$ in the word representing the permutation $\sigma$, etc \begin{itemize} \item If $(b,a)$ in $\sigma$, then $(a,b)$ in $\T(\sigma)$. \item If $(a,b)$ in $\sigma$, then \begin{itemize} \item if $\exists$ $c>b$ such that $(a,c,b)$ in $\sigma$ then $(b,a)$ in $\T(\sigma)$, \item if $\not\!\exists$ $c>b$ such that $(a,c,b)$ in $\sigma$ then $(a,b)$ in $\T(\sigma)$. \end{itemize} \end{itemize} Rewriting these observations in terms of how entries appear in $\T(\sigma)$ first: \begin{itemize} \item If $(a,b)$ in $\T(\sigma)$ then either, \begin{itemize} \item $(b,a)$ in $\sigma$, or \item $(a,b)$ in $\sigma$ and $\not\!\exists$ $c>b$ such that $(a,c,b)$ in $\sigma$. \end{itemize} \item If $(b,a)$ in $\T(\sigma)$ then $\exists$ $c>b$ such that $(a,c,b)$ in $\sigma$. \end{itemize} Using these observations, if $\T(\sigma)$ contains $(a,c,b)$ as a 132 pattern then the following hold: \begin{enumerate} \item[1.] Since $(c,b)$ in $\T(\sigma)$, there exists $d>c$ such that $(b,d,c)$ in $\sigma$. \item[2.] Since $(a,c)$ in $\T(\sigma)$, either 2(i) $(c,a)$ in $\sigma$, or 2(ii) $(a,c)$ in $\sigma$ and $\not\!\exists$ $e>c$ such that $(a,e,c)$ in $\sigma$. \item[3.] Since $(a,b)$ in $\T(\sigma)$, either 3(i) $(b,a)$ in $\sigma$, or 3(ii) $(a,b)$ in $\sigma$ and $\not\!\exists$ $f>b$ such that $(a,f,b)$ in $\sigma$. \end{enumerate} Let us now check all possible combinations of 2(i), 2(ii), 3(i), and 3(ii). \begin{description} \item[1, 2(i) and 3(i)] We have $(b,d,c)$ in $\sigma$, $(c,a)$ in $\sigma$, and $(b,a)$ in $\sigma$. These imply that $(b,d,c,a)$ in $\sigma$ where $d>c$. \item[1, 2(i) and 3(ii)] We have $(b,d,c)$ in $\sigma$, $(c,a)$ in $\sigma$, and $(a,b)$ in $\sigma$ with no $f>b$ such that $(a,f,b)$ in $\sigma$. These are inconsistent as the first two imply that $(b,a)$ in $\sigma$ whereas the third says that $(a,b)$ in $\sigma$. This is impossible, \item[1, 2(ii) and 3(i)] We have $(b,d,c)$ in $\sigma$, $(b,a)$ in $\sigma$, and $(a,c)$ where $\not\!\exists e>c$ such that $(a,e,c)$ in $\sigma$. This implies that $(b,d,a,c)$ in $\sigma$ and $\not\!\exists e>c$ such that $(b,d,a,e,c)$. \item[1, 2(ii) and 3(ii)] We have $(b,d,c)$ in $\sigma$, $(a,c)$ in $\sigma$ where $\not\!\exists$ $e>c$ such that $(a,e,c)$ in $\sigma$, and $(a,b)$ in $\sigma$ where $\not\!\exists$ $f>b$ such that $(a,f,b)$ in $\sigma$. These three are inconsistent and this case is therefore not possible. \end{description} We conclude that if $\T(\sigma)$ contains $(a,c,b)$ as a 132 pattern, then either \begin{itemize} \item $(b,d,c,a)$ is a 2431 pattern in $\sigma$, or \item $(b,d,a,c)$ is a 2413 pattern in $\sigma$ and $\not\!\exists$ $e>c$ such that $(b,d,a,e,c)$ in $\sigma$. \end{itemize} Notice that in the second condition, if $e$ is such that $cc$ such that $(b,d,a,e,c)$ in $\sigma$. Since $d$ is greater than $c$ and less than $e$, this statement implies that there does not exist $e>d$ such that $(b,d,a,e,c)$ in $\sigma$. This implies part (ii) of the theorem. \end{proof} \begin{definition}\label{zigzag:defn} A $k$-zigzag pattern in a permutation $\pi$ is a sequence $z=(z_0,\ldots,z_{k+1})$ such that \begin{enumerate} \item[(a)] $z_0 > z_1>z_2>\cdots > z_{k+1}$, and \item[(b)] $\pi^{-1}(z_{2i}) < \pi^{-1}(z_0) < \pi^{-1}(z_{2i-1})$ for all $i\geq 1$. \end{enumerate} \end{definition} A 0-zigzag pattern is an occurrence of the permutation pattern 21, and so the only permutation that contains no 0-zigzag pattern is the identity. A 1-zigzag pattern is an occurrence of the permutation pattern 132. A 2-zigzag pattern is either an occurrence of the permutation pattern 2413 or an occurrence of the permutation pattern 2431. \begin{figure} \begin{center} \includegraphics[scale=0.6]{rl_forb_examp.pdf} $\hspace*{2em}$ \includegraphics[scale=0.6]{rl_forb_examp2.pdf} \end{center} \caption{The permutation 15327846 contains a 3-zigzag pattern $x=(7,6,5,4,2)$. We have drawn lines between the points in the permutation diagram which correspond to adjacent elements in the 3-zigzag.\label{fig:three} } \end{figure} \begin{theorem}\label{thm:nozigzag} If $\pi \in \sn$ contains no $k$-zigzag pattern, then $\T^{k}(\pi)=\id$. \end{theorem} \begin{proof} If $\pi$ contains no $1$-zigzag pattern, then $\pi$ avoids the pattern $132$, which by Theorem~\ref{THEOREM:1} means $\T(\pi)=\T^1(\pi)=\id$. Therefore the result of the theorem is true for $k=1$. The proof will follow by induction. It will be sufficient to show that given $\pi \in \sn$,\\[1em] \centerline{$\pi$ contains no $k$-zigzag pattern $\Longrightarrow$ $\T(\pi)$ contains no $(k-1)$-zigzag pattern.} \ \\ We will prove the contrapositive to the above statement:\\[1em] \centerline{$\T(\pi)$ contains a $(k-1)$-zigzag pattern $\Longrightarrow$ $\pi$ contains a $k$-zigzag pattern.} \ \\ Suppose that $z=(z_0,\ldots,z_k)$ is a $(k-1)$-zigzag pattern in $\T(\pi)$. Since $\{(z_0,z_{2i-1})\}_{i\geq 1}$ are inversions in $\T(\pi)$, by Lemma~\ref{LEMMA:3} we know there must exist values $c_i$ such that $(z_{2i-1},c_i,z_0)$ are occurrences of 132 patterns in $\pi$. Let $c^{*}$ be the rightmost such $c_i$ in $\pi$. Then $(z_{2i-1}, c^{*},z_0)$ are also all occurrences of 132 patterns in $\pi$ which means $\pi^{-1}(z_{2i-1}) < \pi^{-1}(c^{*})$ for all $i$. Next suppose that there is some $z_{2j}$ (where $j\ \geq 1$) such that $(z_{2j},c^{*})$ is a 12 pattern in $\pi$. Then $(z_{2j},c^{*},z_0)$ is a 132 pattern in $\pi$ by Definition~\ref{zigzag:defn} which, according to Lemma~\ref{LEMMA:3}, means $(z_0,z_{2j})$ is a 21 pattern in $\T(\pi)$. This is a contradiction since $z_{2j}$ precedes $z_0$ in $\T(\pi)$. We conclude that all even indexed $z_i$'s are to the right of $c^{*}$ in $\pi$, hence $\pi^{-1}(c^{*}) < \pi^{-1}(z_{2j})$ for all $j\geq 1$. The two pairs of inequalities above, together with $c^{*} > z_0 > z_1 > \cdots > z_{k}$, show that $z'=(c^{*},z_0,\ldots ,z_{k})$ is a $k$-zigzag pattern in $\pi$. \end{proof} \begin{definition} Let $z=(z_0,\ldots,z_{k+1})$ be a $k$-zigzag pattern in $\pi \in \sn$. We will call $z$ {\it{interrupted}} if there exists $c>z_0$ such that either \begin{enumerate} \item[(i)] $z_{2a}$ precedes $c$ and $c$ precedes $z_{2b}$ in $\pi$ for some $a,b \geq 1$, or \item[(ii)] $z_{2a-1}$ precedes $c$ and $c$ precedes $z_{2b-1}$ in $\pi$ for some $a,b \geq 1$. \end{enumerate} Otherwise we will call $z$ {\it{uninterrupted}}. \end{definition} \begin{example} The $3$-zigzag $z=(7,6,5,4,2)$ in the permutation $\pi=(1,5,3,2,7,8,4,6)$ shown in Figure~\ref{fig:three} is uninterrupted. The $3$-zigzag $z'=(7,6,5,4,2)$ in the permutation $\pi'=(1,5,3,2,7,4,8,6)$ shown is interrupted because there is an $8$ between $4$ and $6$. The $4$-zigzag $z''=(10,9,8,7,6,5)$ in the permutation $\pi'' = (4,6,11,8,3,2,10,12,7,1,9,5)$ is interrupted because there is an $11$ between $8$ and $6$ in $\pi''$. See also Figure~\ref{unint_example}. \begin{figure}[h] \centerline{\includegraphics[scale=0.75]{rl_unint_example.pdf}} \caption{An illustration of where points are forbidden (the grey areas) in order for a $5$-zigzag $z=(z_0,z_1,\ldots,z_6)$ to be an uninterrupted 5-zigzag. \label{unint_example} } \end{figure} \end{example} \begin{definition} Given $\pi \in \sn$ and a set of elements $A \subseteq \{1,\ldots,n\}$, let $\aleft{\pi}{A}$ (resp. $\aright{\pi}{A}$) be the element of $A$ that is leftmost (resp. rightmost) in $\pi$. We will say that an element $x$ is {\it{among}} $A$ in $\pi$ if $x$ does not precede $\aleft{\pi}{A}$ in $\pi$ and $\aright{\pi}{A}$ does not precede $x$ in $\pi$. \end{definition} For example if $\pi=285491376$ and $A=\{1,3,5,9\}$ then $\aleft{\pi}{A}=5$ and $\aright{\pi}{A}=3$. The elements 4 and 5 are among $A$ in $\pi$ whereas the elements 2 and 7 is not. \begin{theorem}\label{thm:zigzag} If $\pi \in \sn$ contains an uninterrupted $k$-zigzag then $\T^k(\pi) \neq \id$. \end{theorem} \begin{proof} An uninterrupted 1-zigzag in a permutation $\pi \in \sn$ is an occurrence of the pattern 132. If $\pi \in \sn$ contains an occurrence of the pattern 132 then $\T(\pi) \neq \id$ by Theorem~\ref{THEOREM:1}. The theorem is true for $k=1$. Now we claim that if $\pi$ contains an uninterrupted $k$-zigzag, then $\T(\pi)$ contains an uninterrupted $(k-1)$-zigzag. To see the validity of this claim consider the following. Let $z=(z_0,z_1,\ldots,z_{k+1})$ be the lexicographically largest $k$-zigzag in $\pi$ that begins with $z_0$ that is uninterrupted. Let $z_{\odd}=\{z_{2j-1}:j\geq 1\}$ and $z_{\even} = \{z_{2j}: j\geq 1\}$. All elements of $z_{\odd}$ enter and leave the stack before $z_0$ does. There are no elements larger than $z_0$ among $z_{\odd}$ in $\T(\pi)$ as $z$ is uninterrupted (the elements among $z_{\odd}$ in $\T(\pi)$ start by some element among $z_{\odd}$ in $\pi$ and end by the maximal element among $z_{\odd}$). Similarly there are no elements larger than $z_0$ among $z_{\even}$ in $\T(\pi)$. Since $z$ is the lexicographically largest $k$-zigzag with the desired properties, we know that there are no elements larger than $z_1$ among $z_{\even}$. Also $z_1$ is, by definition, the largest element of $z_{\odd}$ that is less than $z_0$ (otherwise there would exist a lexicographically larger $k$-zigzag $z'$ which starts with $z_0$ in $\pi$). From this we know that $z_1$ is the rightmost element among $z_{\odd}$ in $\T(\pi)$. The sequence $(z_1,\ldots,z_{k+1})$ is therefore an uninterrupted $(k-1)$-zigzag in $\T(\pi)$. Iterating the above claim, we have that if $\pi$ contains an uninterrupted $k$-zigzag, then $\T(\pi)$ contains an uninterrupted $(k-1)$-zigzag, $\T^2(\pi)$ contains an uninterrupted $(k-2)$-zigzag, and $\T^{k}(\pi)$ contains an uninterrupted $0$-zigzag. An uninterrupted $0$-zigzag is simply an inversion, so $\T^k(\pi)$ contains an inversion and is therefore not the identity permutation. \end{proof} The following result is the companion to West's result~\cite{west.phd} which tells us that the set of 2-stack sortable permutations is $\sn(2341,3\overline{5}241)$. \begin{theorem} $\Tack{n}{2} = \sn(2431,241\overline{5}3)$. \end{theorem} \begin{proof} Suppose that $\pi \in \sn$ with $\T^2(\pi)=\id$. According to Theorem~\ref{thm:zigzag}, $\pi$ does not contain an uninterrupted 2-zigzag. There are two 2-zigzags: 2431 and 2413. The statement `$\pi$ does not contain an uninterrupted 2-zigzag' is equivalent to `$\pi$ does not contain a 2-zigzag, or if it does then it is interrupted', and this happens iff $\pi \in \sn(243\overline{5}1) \cap \sn (241\overline{5} 3)$. Notice, however, that if $\pi$ contains $(b,d,c,e,a)$, where $a3$, \begin{align*} W(\Tack{n}{n-3};x) &= A_n(x) - A_{\lfloor \frac{n-1}{2} \rfloor}(x) A_{{\lceil \frac{n-1}{2} \rceil}}\\ & \phantom{=} - \left\lfloor\dfrac{n+2}{2}\right\rfloor A_{\lfloor \frac{n-1}{2}\rfloor}(x) A_{\lfloor \frac{n}{2} \rfloor }(x) - \left\lfloor\dfrac{n-1}{2}\right\rfloor A_{\lfloor \frac{n-2}{2}\rfloor}(x) A_{\lfloor \frac{n+1}{2} \rfloor }(x)\\ & \phantom{=}+A_{\lfloor \frac{n-1}{2} \rfloor}(x) D_{\lfloor \frac{n}{2} \rfloor}(x) - A_{\lfloor \frac{n-2}{2} \rfloor}(x) D_{\lfloor \frac{n+1}{2} \rfloor}(x) \end{align*} where \begin{align*} D_n(x) &= \dfrac{1}{2} \sum_i \binom{n-1}{i} A_i(x) A_{n-1-i}(x). \end{align*} \end{theorem} \begin{proof} We wish to obtain an expression for \begin{align*} W(\Tack{n}{n-3};x) &= W(\Tack{n}{n-2};x) - \sum_{\mycom{\pi \in \sn}{\deg_{\T}(\pi)=n-2}} x^{1+\des(\pi)}. \end{align*} Theorem~\ref{rl:nm1} gives an expression for $W(\Tack{n}{n-2})$. We will now classify those permutations $\pi \in \sn$ for which $\deg_{\T}(\pi)=n-2$. Suppose that $\pi \in \sn$ with $\deg_{\T}(\pi)= n-2$. Then $\T^{n-2}(\pi)=\id$ and $\T^{n-3}(\pi) \neq \id$. The contrapositive of Theorem~\ref{thm:nozigzag} tells us that $\pi$ must contain an $(n-3)$-zigzag. (Theorem~\ref{thm:zigzag} does not assist us in this situation as it translates into a statement concerning a zigzag too large to fit into the permutation.) Therefore will check all types of permutations $\pi$ in $\sn$ which contain an $(n-3)$-zigzag and classify those for which $\deg_{\T}(\pi)=n-2$. In order to do this, we will condition on the lexicographically largest zigzag in each case so as to avoid overlapping cases. An $(n-3)$-zigzag in a permutation $\pi$ is a strictly decreasing sequence $z=(z_0,\ldots, z_{n-2})$. Let us suppose that $z$ is maximal in the sense that it is the lexicographically largest $(n-3)$-zigzag in $\pi$. Because $z$ contains $n-1$ elements out of a possible $n$ elements, and because it is strictly decreasing, it must be the sequence $(n,n-1,\ldots,1)$ with one element removed. We indicate this using a hat above the element that is removed: $$z=(n,n-1,\ldots,\hat{i},\ldots,1).$$ To perform this classification, we must split the analysis into four distinct cases: (a) $i=n$ (b) $i=n-1$ (c) $i=n-2$ and (d) $1\leq i \leq n-3$. \noindent {\bf{Case (a) $i=n$:}}\\ In this case the $(n-3)$-zigzag is $(n-1,n-2,\ldots,1)$. Let $\pi'$ be $\pi$ with $n$ removed. Then $\pi'$ must be of the form $L(n-1)R$ where $L \in \Perm{\dtwo{n-3}}$ and $R \in \Perm{\dtwo{n-2}}$. All that remains is to carefully check how the position of $n$ in $\pi$ changes the degree of $\pi$ with respect to $\T$. We must be careful that by inserting $n$ in different places, the resulting permutation does not contain an $(n-2)$-zigzag (as these were taken care of previously in Theorem~\ref{rl:nm1}). Let $L_1L_2\in \Perm{\dtwo{n-3}}$ and $R_1R_2 \in \Perm{\dtwo{n-2}}$. From Theorem~\ref{rl:nm1}, the permutation $\pi\in\sn$ must have one of two forms; \begin{itemize} \item $\pi=L_1nL_2(n-1)R_1R_2$: First observe that if $L_2= \emptyset$, then $z'=(n,n-2,n-3,\ldots,1)$ will be an $(n-3)$-zigzag that is lexicographically greater than $z=(n-1,\ldots,1)$. This is forbidden so we must have $L_2\neq \emptyset$. Bearing this in mind, \begin{align*} \T(\pi) &= \T(L_1nL_2 (n-1)R_1R_2) \\ &= \T(R_1R_2)\T(L_2)(n-1)\T(L_1)n,\end{align*} where $\T(R_1R_2)$ ends in $(n-2)$. Suppose $\T(R_1R_2)=R_3(n-2)$ where $R_3\in\Perm{\dtwo{n-4}}$. Then \begin{align*} \T^2(\pi) &= \T(R_3(n-2)\T(L_2)(n-1)\T(L_1)n) \\ &= \T^2(L_1)\T^2(L_2)\T(R_3)(n-2)(n-1)n. \end{align*} Notice that $\T^2(L_1)\T^2(L_2)\T(R_3) \in \sym_{n-3}$. Since $L_2 \neq \emptyset$, we have $\deg_{\T}(\pi)=n-2$ iff $\deg_{\T}(\T^2(\pi)) = n-4$, and this is true iff $n-3 \in \T^2(L_2)$. The set of all permutations satisfying $\deg_{\T}(\pi)=n-2$ in this case is \begin{align} \pi &= L(n-1)R\;\in\; \sn \nonumber\\ L &\in \Perm{\{n,n-3,n-5,\ldots\} } \mbox{ and $n$ precedes $(n-3)$ in $L$} \label{saturday}\\ R &\in \Perm{\{n-2,n-4,\ldots\}}. \nonumber \end{align} \item $\pi=L_1L_2(n-1)R_1nR_2$: If $R_1 = \emptyset$ then $\pi$ will contain a $(n-2)$-zigzag that is lexicographically larger than $(n-1,\ldots,1)$. This is forbidden and so we have $R_1\neq \emptyset$. With this in mind, $$\T(\pi) = \T(R_2) \T(R_1)\T(L_1L_2)(n-1)n.$$ The permutation $\T(R_2) \T(R_1)\T(L_1L_2) \in \sym_{n-2}$ has degree $n-3$ iff $\T(R_2)\T(R_1)$ ends in $n-2$. This happens iff $(n-2) \in R_1$ (since we already showed that $R_1$ cannot be empty). The set of all permutations for which this is true is \begin{align} \pi &= L(n-1)R\;\in\;\sn \nonumber\\ L &\in \Perm{\{n-3,n-5,\ldots \}} \label{sunday}\\ R &\in \Perm{\{n,n-2,n-4,\ldots\} } \mbox{ and $n-2$ precedes $n$ in $R$.} \nonumber \end{align} \end{itemize} \noindent {\bf{Case (b) $i=n-1$:}}\\ In this case the maximal $(n-3)$-zigzag is $(n,n-2,n-3,\ldots ,1)$. We will consider how the position of $(n-1)$ in $\pi$ affects the degree of the resulting permutation. The permutation $\pi$ must have the form $L_1(n-1)L_2nR_1R_2$ or $L_1L_2nR_1(n-1)R_2$ where $L_1L_2\in\Perm{\dtwo{n-3}}$ and $R_1R_2 \in \Perm{\dtwo{n-2}}$ (otherwise there will be a lexicographically larger $(n-3)$-zigzag starting with $(n,n-1,\ldots)$ which is forbidden). \begin{itemize} \item $\pi=L_1(n-1)L_2nR_1R_2$: In this case $\T(\pi) = \T(R_1R_2) \T(L_2)\T(L_1) (n-1)n$. Since $\T(R_1R_2)$ ends in $(n-2)$ we have that $\deg_{\T}(\T(R_1R_2) \T(L_2)\T(L_1)) = n-3$ and so $\deg_{\T}(\pi) = n-2$. All permutations of this form have $\deg_{\T}(\pi) = n-2$. This collection is \begin{align} \pi&= LnR \; \in\; \sn \nonumber\\ L&\in\Perm{\{n-1,n-3,\ldots\} }\label{monday}\\ R&\in\Perm{\{n-2,n-4,\ldots\}}. \nonumber \end{align} \item $L_1L_2nR_1(n-1)R_2$: This permutation contains another $(n-3)$-zigzag starting with $(n,n-1,n-3,n-4,\ldots)$. This case is therefore not relevant since it violates the assumption that $(n,n-2,n-3,\ldots ,1)$ is maximal. \end{itemize} \noindent {\bf{Case (c) $i=n-2$:}}\\ The maximal $(n-3)$-zigzag in this case is $(n,n-1,n-3,\ldots ,1)$ so we will consider how the position of $(n-2)$ affects the degree of the resulting permutation. The permutation $\pi$ is either of the form $L_1(n-2)L_2nR_1R_2$ or $L_1L_2nR_1(n-2)R_2$ where $L_1L_2\in\Perm{\{n-3,n-5,\ldots\} }$ and $R_1R_2 \in \Perm{\{n-1,n-4,n-6,\ldots\}}$. \begin{itemize} \item $\pi=L_1(n-2)L_2nR_1R_2$: This contains an $(n-3)$-zigzag that begins with $(n,n-1,n-2,n-4,\ldots)$ and therefore contradicts the assumption that $(n,n-1,n-3,\ldots ,1)$ is maximal amongst $(n-3)$-zigzags. \item $\pi=L_1L_2nR_1(n-2)R_2$: We have $$\T(\pi) = \T(L_1L_2nR_1(n-2)R_2) = \T(R_1(n-2)R_2) \T(L_1L_2) n.$$ Consider the two sub-cases: $n-1 \in R_1$ and $n-1 \in R_2$. {\it{Sub-case $n-1 \in R_1$}}: If $n-1 \in R_1$ then $R_1=R_3(n-1)R_4$ and $R_2R_3R_4$ is a permutation of $\dtwo{n-4}$. Consequently \begin{align*} \T(\pi)&=\T(R_3(n-1)R_4(n-2)R_2) \T(L_1L_2) n \\ &= \T(R_2)\T(R_4)(n-2)\T(R_3) (n-1) \T(L_1L_2) n \end{align*} and $\T^2(\pi) = \T^2(L_1L_2) \T^2(R_3) \T(\T(R_2)\T(R_4)) (n-2)(n-1)n$. This is a permutation of the form $A(n-3)B(n-2)(n-1)n$ with $\T^2(L_1L_2)=A(n-3)$ where $A$ is permutation of $\dtwo{n-5}$ and $B$ is a permutation of $\dtwo{n-4}$. We therefore have $\deg_{\T}(\T^2(\pi))=n-4$ which means $\deg_{\T}(\pi) = n-2$. All permutations of this form have degree $n-2$. {\it{Sub-case $n-1 \in R_2$}}: If $n-1\in R_2$ then $R_2=R_3(n-1)R_4$ and $R_1R_3R_4$ is a permutation in $\Perm{\dtwo{n-4}}$. Consequently \begin{align*} \T(\pi) &=\T(R_1(n-2)R_3(n-1) R_4) \T(L_1L_2) n \\ &= \T(R_4)\T(R_3)\T(R_1)(n-2)(n-1) \T(L_1L_2) n \end{align*} and \begin{align*} \T^2(\pi) &= \T(\T(R_4)\T(R_3)\T(R_1)(n-2)(n-1) \T(L_1L_2) n) \\ &= \T^2(L_1L_2) \T(\T(R_4)\T(R_3)\T(R_1)) (n-2)(n-1) n . \end{align*} Since $\T^2(L_1L_2)$ ends in $n-3$ (we know this because $n-3 \in L_1L_2$ and so $n-3 \not\in R_1R_3R_4$) and $$\T^2(L_1L_2) \T(\T(R_4)\T(R_3)\T(R_1))$$ is a permutation of the form $A(n-3)B \in \sym_{n-3}$ with $\T^2(L_1L_2)=A(n-3)$ where $A \in \Perm{\dtwo{n-5}}$ and $B\in\Perm{\dtwo{n-4}}$, we have $\deg_{\T}(\T^2(\pi)) = n-4$ which gives $\deg_{\T}(\pi)=n-2$. All permutations of this form have degree $n-2$. Combining both sub-cases yields the following classification of permutations for this case: \begin{align} \pi&=LnR\;\in\;\sn \nonumber \\ L &\in \Perm{\{n-3,n-5,\ldots\}} \label{thursday}\\ R&\in\Perm{\{n-1,n-2,n-4,\ldots\}}. \nonumber \end{align} \end{itemize} \noindent {\bf{Case (d) $1\leq i \leq n-3$:}}\\ This case is in many ways similar to Case (c) so we only will highlight the main difference. It turns out that in order to obtain $z$ maximal among $(n-3)$-zigzags, the restriction in this case is that two consecutive elements of $\{1,\ldots,n-2\}$, let us call the pair $\overline{i}=\{i,i+1\}$, must both be either to the left or to the right of $n$ in the permutation $\pi$. Then the sequence of elements $n-1,n-2,\ldots ,i+2,\overline{i},i-1,\ldots 1$ alternate from right to left to right etc. of $n$ (for any value $1\leq i\leq n-3$). The result depends, of course, on the parity of $i$ (i.e. whether we have $i$ and $i+1$ both to the left, or to the right, of $n$ in $\pi$). \begin{itemize} \item If $n-i$ is odd then $i$ and $i+1$ are both to the left of $n$ in $\pi$. The number of possible values of $i$ is $\lfloor (n-2)/2\rfloor$. The sizes of $L$ and $R$ in this case are then $\lfloor n/2 \rfloor$ and $\lfloor (n-1)/2\rfloor$, respectively. \item If $n-i$ is even then $i$ and $i+1$ are both to the right of $n$ in $\pi$. The number of possible values of $i$ is $\lfloor (n-3)/2 \rfloor$. The sizes of $L$ and $R$ are $\lfloor (n-2)/2\rfloor$ and $\lfloor (n+1)/2\rfloor$, respectively. \end{itemize} The class of these permutations given by this classification and for which $\deg_{\T}(\pi)= n-2$ is \begin{align} \pi&= LnR \; \in\; \sn \nonumber \\ L &\in \Perm{\{n-2,n-4,\ldots ,i+1,i,i-2,i-4,\ldots\}} \label{friday}\\ R &\in \Perm{\{n-1,n-3,\ldots ,i+2,i-1,i-3,\ldots\} }, \nonumber \\ \noalign{for all appropriate $i \in [1,n/2]$ when $n-i$ is odd, and} \nonumber \pi&= LnR \; \in\; \sn \nonumber \\ L &\in \Perm{\{n-2,n-4,\ldots,i+2,i-1,i-3,\ldots\}} \label{noday}\\ R &\in \Perm{\{n-1,n-3,\ldots ,i+3,i+1,i,i-2,\ldots\} }, \nonumber\\ \noalign{for all appropriate $i \in [1,n/2]$ when $n-i$ is even.} \nonumber \end{align} The permutations in Equations ~\ref{saturday}--\ref{noday} are all of the permutations $\pi\in \sn$ for which $\deg_{\T}(\pi) = n-2$. We will use these to calculate the descent polynomial \begin{align}\label{despol} \sum_{\mycom{\pi\in\sn}{\deg_{\T}(\pi)=n-2}} x^{1+\des(\pi)}. \end{align} In some of the classifications of permutations, we see that the sum is over all permutations in a set except that the largest value must always be to the left or right of the second largest value. (See for example Equations~\ref{saturday} and \ref{sunday}.) To accommodate descent polynomials over these restricted sets we define: \begin{align*} D_n(x) &= \sum_{\mycom{\pi \in \sn}{{\pi^{-1}(n) > \pi^{-1}(n-1)}}} x^{1+\des(\pi)} \quad \mbox{ and } \quad L_n(x) = \sum_{\mycom{\pi \in \sn}{{\pi^{-1}(n) < \pi^{-1}(n-1)}}} x^{1+\des(\pi)}. \end{align*} Clearly $D_n(x)+L_n(x)=A_n(x)$. In order to give an expression for $D_n(x)$ in terms of polynomials that we know, we do as follows. The polynomial $D_n(x)$ is the Eulerian distribution on length $n$ permutations for which $n$ is to the right of $n-1$ in the permutation. Split the sum over those permutations $\pi\in\sn$ for which (i) $\pi_n=n$ and (ii) $\pi_j=n$ for some $1\leq j \leq n-1$. In the second case, there are $\binom{n-2}{j-2}$ ways of choosing the elements which precede $n$ in $\pi$, because $n-1$ must be one of them. Let us write $\pi = \pi ' n \pi''$. So we have \begin{eqnarray*} D_n(x) &=& \sum_{\mycom{\pi \in \sn}{\pi_n=n}} x^{1+\des(\pi)} + \sum_{j=2}^{n-1} \sum_{\mycom{A\subseteq \{1,\ldots,n-2\}}{|A|=j-2}} \sum_{\mycom{\pi' \in \LittlePerm(A\cup \{n-1\})}{\pi '' \in \LittlePerm(\{1,\ldots,n-2\}-A)}} x^{1+\des(\pi=\pi' n \pi'')} \end{eqnarray*} where $\pi = \pi ' n \pi''$ and $\LittlePerm(X)$ is the set of all permutations of the elements in $X$. Clearly the first sum is $A_{n-1}(x)$. Since $\des(\pi)=\des(\pi ' ) + 1 +d(\pi'')$ for all $2\leq j \leq n-1$, we have $x^{1+\des(\pi)} = x^{1+\des(\pi ' )} x^{1+\des(\pi '')}$. Replacing this in the second summation, we find \begin{eqnarray*} D_n(x) &=& A_{n-1}(x) + \sum_{j=2}^{n-1} \binom{n-2}{j-2} A_{j-1}(x) A_{n-j}(x) \end{eqnarray*} Now \begin{eqnarray*} \lefteqn{\sum_{j=2}^{n-1} \binom{n-2}{j-2} A_{j-1}(x) A_{n-j}(x)} \\ &=& \sum_{j=1}^{n-2} \binom{n-2}{j-1} A_{j}(x) A_{n-1-j}(x) \\ &=& \dfrac{1}{2} \left( \sum_{j=1}^{n-2} \binom{n-2}{j-1} A_j(x) A_{n-1-j}(x) + \sum_{i=1}^{n-2} \binom{n-2}{n-2-i} A_{n-1-i}(x) A_i(x) \right) \\ &=& \dfrac{1}{2} \left( \sum_{j=1}^{n-2} \binom{n-2}{j-1} A_j(x) A_{n-1-j}(x) + \sum_{j=1}^{n-2} \binom{n-2}{j} A_{n-1-j}(x) A_j(x) \right) \\ &=& \dfrac{1}{2} \sum_{j=1}^{n-2} \binom{n-1}{j} A_j(x) A_{n-1-j}(x). \end{eqnarray*} Since $A_{n-1}(x) = \frac{1}{2} \left( A_0(x)A_{n-1}(x) + A_{n-1}(x) A_{0}(x) \right)$, we have \begin{align} \label{didentity} D_n(x) &= \dfrac{1}{2} \sum_i \binom{n-1}{i} A_i(x) A_{n-1-i}(x). \end{align} The sums over all permutations in each of Equations ~\ref{saturday}--\ref{noday} are given in the table in Figure~\ref{fig:one}, and their total noted in the final row. \begin{figure} $$\begin{array}{|c|c|} \hline \mbox{A} & \ds\sum_{\pi\in \mathrm{Equation\; A} } x^{1+\des(\pi)} \\ \hline \hline \mbox{(\ref{saturday})} & L_{\lfloor \frac{n}{2}\rfloor}(x) A_{\lfloor \frac{n-1}{2}\rfloor }(x) \\[0.5em] \mbox{(\ref{sunday})} & A_{\lfloor \frac{n-2}{2}\rfloor}(x) D_{\lfloor \frac{n+1}{2}\rfloor }(x) \\[0.5em] \mbox{(\ref{monday})} & A_{\lfloor \frac{n}{2}\rfloor}(x) A_{\lfloor \frac{n-1}{2} \rfloor }(x) \\[0.5em] \mbox{(\ref{thursday})} & A_{\lfloor \frac{n-2}{2}\rfloor}(x) A_{\lfloor \frac{n+1}{2} \rfloor }(x) \\[0.5em] \mbox{(\ref{friday})} & \left\lfloor\frac{n-2}{2}\right\rfloor A_{\lfloor \frac{n}{2}\rfloor}(x) A_{\lfloor \frac{n-1}{2} \rfloor }(x) \\[0.5em] \mbox{(\ref{noday})} & \left\lfloor\frac{n-3}{2}\right\rfloor A_{\lfloor \frac{n-2}{2}\rfloor}(x) A_{\lfloor \frac{n+1}{2} \rfloor }(x) \\[0.5em] \hline\hline \mbox{Total} & \left\lfloor\frac{n}{2}\right\rfloor A_{\lfloor \frac{n}{2}\rfloor}(x) A_{\lfloor \frac{n-1}{2} \rfloor }(x) +\left\lfloor\frac{n-1}{2}\right\rfloor A_{\lfloor \frac{n-2}{2}\rfloor}(x) A_{\lfloor \frac{n+1}{2} \rfloor }(x) \\[0.5em] \star \star \star & + L_{\lfloor \frac{n}{2}\rfloor}(x) A_{\lfloor \frac{n-1}{2}\rfloor }(x) + A_{\lfloor \frac{n-2}{2}\rfloor}(x) D_{\lfloor \frac{n+1}{2}\rfloor }(x) \\ \hline \end{array}$$ \caption{Contributions to the descent polynomial from different cases.\label{fig:one}} \end{figure} We thus have \begin{align*} \lefteqn{W(\Tack{n}{n-3};x)}\\ &= W(\Tack{n}{n-2};x) - (\star\star\star) \\ &= A_n(x) - A_{\lfloor \frac{n-1}{2} \rfloor}(x) A_{{\lceil \frac{n-1}{2}\rceil}} - \left\lfloor\frac{n}{2}\right\rfloor A_{\lfloor \frac{n}{2}\rfloor}(x) A_{\lfloor \frac{n-1}{2} \rfloor }(x) -\left\lfloor\frac{n-1}{2}\right\rfloor A_{\lfloor \frac{n-2}{2}\rfloor}(x) A_{\lfloor \frac{n+1}{2} \rfloor }(x)\\ &\phantom{= } - L_{\lfloor \frac{n}{2}\rfloor}(x) A_{\lfloor \frac{n-1}{2}\rfloor }(x) - A_{\lfloor \frac{n-2}{2}\rfloor}(x) D_{\lfloor \frac{n+1}{2}\rfloor }(x). \end{align*} The statement of the theorem follows by substituting $L_{\lfloor \frac{n}{2}\rfloor}(x)=A_{\lfloor \frac{n}{2}\rfloor}(x) - D_{\lfloor \frac{n}{2}\rfloor}(x).$ \end{proof} \section{Steingr\'imsson's conjecture} In this section we will use the results of Section 3 to prove Steingr\'imsson's conjecture (Conjecture~\ref{econj}) in some special cases. \begin{theorem} Let $n\geq 3$ be fixed. Then $|\Stack{n}{k}|\leq |\Tack{n}{k}|$ for $k=0,1,2,n-3,n-2$, and $n-1$. This inequality is strict for all of these pairs $(n,k)$ that satisfy $2 5$.\qedhere \end{proof} Equation \ref{rara} admits a reduction to the more compact form: \begin{align} |\Tack{n}{n-3}| &= n! - \floor{n-1}{2}! \ceil{n-1}{2}! - \tfrac{n^2}{2} \floor{n-1}{2}! \floor{n-2}{2}! \end{align} \section{The descent polynomial of $t$-revstack sortable permutations} Let $V_t(n,i)$ and $W_t(n,i)$ be the sets of permutations in $\sn$ having $i$ descents which are $t$-\revstack\ sortable and $t$-stack sortable, respectively. Let us write $v_t(n,i)=|V_t(n,i)|$ and $w_t(n,i)=|W_t(n,i)|$ so that \begin{align*} W(\Tack{n}{t};x) &= \sum_{i} v_t(n,i) x^{i+1} \\ W(\Stack{n}{t};x) &= \sum_{i} w_t(n,i) x^{i+1}. \end{align*} B\'ona\cite{bona.1,bona.2} proved symmetry and unimodality of the numbers $w_t(n,i)$ with respect to the descent parameter, i.e. \begin{align*} w_t(n,i) &= w_t(n,n-1-i) \mbox{ for all }0\leq i \leq n-1 \mbox{, and}\\ w_t(n,0) &\leq w_t(n,1) \leq \ldots \leq w_t(n,\lfloor (n-1)/2\rfloor) \geq \ldots \geq w_t(n,n-1). \end{align*} In this section we will do the same for the numbers $v_t(n,i)$. Symmetry is proven by showing that the reflection operation on permutations commutes with B\'ona's~\cite{bona.1} {\it{duality map}}. Unimodality is proven by using the same argument of B\'ona~\cite{bona.1,bona.2} and showing that his function $z:W_t(n,i) \to W_t(n,i+1)$ is injective for all $0\leq i \leq \floor{n-3}{2}$ and preserves $t$-\revstack\ sortability. \begin{theorem} $v_t(n,i) = v_{t}(n,n-1-i)$. \end{theorem} \begin{proof} B\'ona's duality map~\cite[Section 2]{bona.1} $f:\sn \to \sn$ is defined in the following recursive way. Note that permutations are written as words, and the definition is necessarily a definition on words. The value $n$ stands for the unique largest value in a word. \begin{itemize} \item $f(\epsilon) = \epsilon$ \item $f(x)=x$ where $x$ is a word of length 1 \item $f(LnR)=f(L)nf(R)$ if neither $L$ nor $R$ is empty \item $f(Ln)=nf(L)$ \item $f(nR)=f(R)n$. \end{itemize} Let us recall B\'ona's method of proof of symmetry. He showed~\cite[Lemma 2.6]{bona.1} that $f$ preserves the $t$-stack sortable property: \begin{align}\label{bonapreserve} \S(\pi)&=\S(f(\pi)) \end{align} from which he concludes that $\pi$ is $t$-stack sortable iff $f(\pi)$ is $t$-stack sortable. He also showed~\cite[Proposition 2.5]{bona.1} that \begin{align}\label{bonades} \des(\pi) + \des(f(\pi)) &= n-1 \end{align} for all $\pi \in \sn$. Combining these two observations: applying $f$ to permutations in $\sn$ that are $t$-stack sortable gives another permutation that is $t$-stack sortable, but which has $n-1-\des(\pi)$ descents, i.e. there is symmetry in the descent statistic. The reverse operation $\rev:\sn \to \sn$ is defined recursively via \begin{itemize} \item $\rev(\epsilon) = \epsilon$ \item $\rev(LnR) = \rev(R)n \rev(L)$ where $n$ is the largest value in the word $LnR$. \end{itemize} It is easy (by induction on the length of the word) to see that $f \circ \rev = \rev \circ f = g$ where $g$ is defined as follows: \begin{itemize} \item $g(\epsilon)=\epsilon$ \item $g(x)=x$ where $x$ is a word of length 1 \item $g(LnR)=g(R)ng(L)$ if neither $L$ nor $R$ is empty \item $g(Ln)=g(L)n$ \item $g(nR)=ng(R)$. \end{itemize} The operator $f$ preserves the $t$-\revstack\ sortable property since \begin{align*} \T(\pi) &= \S(\rev(\pi))\\ &= \S(f(\rev(\pi)))\\ \noalign{by applying B\'ona's equation \ref{bonapreserve} above,} &= \S(\rev(f(\pi)))\\ \noalign{since $f$ commutes with $\rev$,} &= \T(f(\pi)). \end{align*} This fact, in conjunction with equation~\ref{bonades}, gives the stated result. \end{proof} \begin{theorem} The sequence of numbers $(v_t(n,0),v_t(n,1),\ldots,v_t(n,n-1))$ is unimodal. \end{theorem} \newcommand\Tree{\mathsf{Tree}} \begin{proof} This proof is a slight modification of B\'ona's unimodality proof of the number sequence $(w_t(n,i))_{i=0}^{n-1}$ (see \cite[Section 3]{bona.1} and \cite{bona.2}). Let $\sn^{\des=i}$ be the set of permutations in $\sn$ that have $i$ descents. Let $T(n,i)$ be the set of decreasing binary trees on $n$ vertices whose label set is $\{1,\ldots,n\}$ and which have $i$ right edges. The sets $\sn^{\des=i}$ and $T(n,i)$ are in one-to-one correspondence, and we write $\Tree(\pi)$ for the tree in $T(n,i)$ that corresponds to $\pi \in \sn^{\des=i}$ using the following rule: {{$x$ is a left (resp. right) child of $y$ in $\Tree(\pi)$ iff $x$ is the largest value to the left (resp. right) of $y$ in $\pi$ and which is less than it.}} (One easily recovers the permutation $\pi$ from $\Tree(\pi)$ by reading its labels using in-order traversal, and $\des(\pi)$ equals the number of right edges in $\Tree(\pi)$.) B\'ona proved unimodality by exhibiting an function $h':T(n,i) \to T(n,i+1)$ that is injective for all $i\leq \floor{n-3}{2}$ and preserves the $t$-stack sortable property. Due to the bijective correspondence between $\sn^{\des=i}$ and $T(n,i)$ (outlined in the previous paragraph), the injective function $h'$ is equivalent to a function $h: W_t(n,i) \to W_t(n,i+1)$ that is injective for all $0\leq i \leq \floor{n-3}{2}$ and for all $t$. Let us describe the function $h$ by way of an example, and explain why it also preserves the property of $t$-revstack-sortability. The function $h$ operates on a permutation $\pi$ by looking at its tree $\Tree(\pi)$. Suppose $\pi = (8,7,9,4,6,1,10,2,3,5,11)$. Then $\Tree(\pi)$ is given in Figure~\ref{d:One}. \begin{figure}[h!] \begin{center} {\diagramOne} \end{center} \caption{The decreasing binary tree corresponding to $\pi=(8,7,9,4,6,1,10,2,3,5,11).$\label{d:One}} \end{figure} Index the vertices of the tree from bottom to top, and within every level from left to right. This starts by labeling the bottom-most vertex on the left hand side $v_1$. If there is a vertex on the same level and to its right then label it vertex $v_2$, but otherwise go up one level and label the leftmost vertex $v_2$, and so forth. The labeling of $\Tree(\pi)$ in Figure~\ref{d:One} is given in Figure~\ref{d:Two}. \begin{figure}[h!] \begin{center} {\diagramTwo} \end{center} \caption{The labeling of the tree from Figure~\ref{d:One}.\label{d:Two}} \end{figure} Let $T_i$ be the subgraph of $\Tree(\pi)$ when restricted to the vertices $\{v_1,\ldots,v_i\}$. $T_7$ is shown in Figure~\ref{d:Three}. \begin{figure}[h!] \begin{center} {\diagramThree} \end{center} \caption{$T_7$, the restriction of $\Tree(\pi)$ to the vertices $\{v_1,\ldots,v_7\}$.\label{d:Three}} \end{figure} Determine the minimum value of $i$ such that the number of left edges in $T_i$ is precisely one more than the number of right edges in $T_i$. (B\'{o}na proved the existence of such an $i$ using a continuity argument~\cite{bona.2}.) In our example this minimum value is $i=9$. Next we look at the vertices in $\Tree(\pi)$ that are both part of $T_i$ and have only either a left or a right child (but not both). If such a vertex has a left child, then move it to be a right child instead. If such a vertex has a right child, then move it to be a left child instead. Let the resulting tree be $h'(\Tree(\pi))$. For example, the nodes in $\Tree(\pi)$ that are part of $T_9$ and which have only left or right children (but not both) are $v_5$, $v_7$ and $v_9$. Consequently $h'(\Tree(\pi))$ is illustrated in Figure~\ref{d:Four}. \begin{figure}[h!] \begin{center} {\diagramFour} \end{center} \caption{The outcome of applying $h'$ to $\Tree(\pi)$.\label{d:Four}} \end{figure} The tree $h'(\Tree(\pi))$ has exactly one more right edge than $\Tree(\pi)$. This map $h':T(n,i) \to T(n,i+1)$ was proven to be injective for $i \leq \floor{n-3}{2}$ (see B\'ona\cite{bona.2}). The permutation $h(\pi)$ is the unique permutation corresponding to $h'(\Tree(\pi))$. For our example we have $$h(\pi) = (7,8,9,4,6,1,10,5,3,2,11).$$ To summarise: the function $h:\sn^{\des=i} \to \sn^{\des=i+1}$ is injective for all $0\leq i \leq \floor{n-3}{2}$. B\'ona then showed that $h$ preserves the $t$-stack sortable property: $\S(\pi) = \S(h(\pi))$. This was done by noting that $\S(\pi)$ is given by reading the tree $\Tree(\pi)$ using post-order traversal. The post-order reading of the tree is the same even after the application of the operator $h'$ on $\Tree(\pi)$ because $h'$ only changes the direction of subtrees that are the only-children of nodes, and therefore preserves the post-order reading. The same argument holds in our case, and all we need to show in order to prove the theorem is that $h$ preserves the $t$-\revstack\ sortable property: $\T(\pi)=\T(h(\pi))$. To do this, let us define the {\it{rpostorder}} traversal of a tree as the list one obtains by first listing the rpostorder of its right subtree, then the rpostorder of the left subtree, and then finally listing the label of the root node. The rpostorder of the tree $\Tree(\pi)$ is then $\T(\pi)$. Since $h'$ only changes the orientation of subtrees that are only-children of nodes, the rpostorder reading of $h'(\Tree(\pi))$ is the same as the rpostorder reading of $\Tree(\pi)$. \end{proof} The coefficients of the two smallest and two largest powers of $x$ in $W(\Tack{n}{t};x)$ and $W(\Stack{n}{t};x)$ are always the same. This follows from symmetry and using the following results. Note that the coefficient of $x$ in both is always unity because $\Tack{n}{0}=\Stack{n}{0} = \{\id\}$ which means $v_t(n,0)=w_t(n,0)=1$. \begin{proposition} $v_t(n,1) = w_t(n,1)$. \end{proposition} \begin{proof} The set $\{\pi \in \sn: \T(\pi)=\id \mbox{ and } \des(\pi)=1\} = \{\pi\in \sn: \S(\rev(\pi))=\id \mbox{ and } \des(\pi)=1\}$. Since $\des(\rev(\pi))+\des(\pi)=n-1$ we have $|\{\pi\in \sn: \S(\rev(\pi))=\id \mbox{ and } \des(\pi)=1\}|=|\{\pi\in \sn: \S(\pi)=\id \mbox{ and } \des(\rev(\pi))=n-2\}|$. This last set is the same as $\{\pi\in \sn: S(\pi)=\id \mbox{ and } \des(\pi)=1\}$ since $\des(\pi)=n-1-\des(\rev(\pi))$, hence the result. \end{proof} Proving real-rootedness and log-concavity of the coefficient sequences of the descent polynomials for $t$-stack sortable permutations remains an unsolved problem. We present companion conjectures for revstack sort that have been verified for all $0\leq t