\documentclass[ALCO,ThmDefs,Unicode,epreuves]{cedram}
\OneNumberAllTheorems
\usepackage{tikz,ytableau}
\usepackage{shuffle}
\DeclareMathOperator{\std}{std}
\DeclareMathOperator{\SSYT}{SSYT}
\DeclareMathOperator{\RS}{RS}
\DeclareMathOperator{\MaR}{MR}
\DeclareMathOperator{\Pk}{Pk}
\newcommand{\shu}{\shuffle}
\newcommand{\pshu}{\hspace{2pt}\ol{\shu}\hspace{2pt}}
\newcommand{\ofS}{\ol{\fS}}
\newcommand{\lab}{\ol{\la}}
\newcommand{\cHb}{\ol{\cH}}
\newcommand{\comp}{\models}
\newcommand{\ol}{\overline}
\newcommand{\emp}{\emptyset}
\newcommand{\sbs}{\subset}
\newcommand{\sbe}{\subseteq}
\newcommand{\ptn}{\vdash}
\newcommand{\ree}[1]{\eqref{#1}}
\newcommand{\ra}{\rightarrow}
\newcommand{\al}{\alpha}
\newcommand{\be}{\beta}
\newcommand{\de}{\delta}
\newcommand{\io}{\iota}
\newcommand{\ka}{\kappa}
\newcommand{\la}{\lambda}
\newcommand{\si}{\sigma}
\newcommand{\Th}{\Theta}
\newcommand{\bx}{\mathbf{x}}
\newcommand{\bbQ}{{\mathbb Q}}
\newcommand{\cA}{{\mathcal A}}
\newcommand{\cH}{{\mathcal H}}
\newcommand{\cP}{{\mathcal P}}
\newcommand{\cS}{{\mathcal S}}
\newcommand{\cT}{{\mathcal T}}
\newcommand{\cZ}{{\mathcal Z}}
\newcommand{\fS}{{\mathfrak S}}
\newcommand{\Hb}{\ol{H}}
\DeclareMathOperator{\des}{des}
\DeclareMathOperator{\Des}{Des}
\DeclareMathOperator{\sh}{sh}
\DeclareMathOperator{\Sym}{{Sym}}
\DeclareMathOperator{\QSym}{{QSym}}
\DeclareMathOperator{\SYT}{SYT}
\newcommand{\dil}{\displaystyle}
\newcommand\llbracket{[\![}
\newcommand\rrbracket{]\!]}
%%%%%%%%% a placer avant \begin{document}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand*{\mk}{\mkern -1mu}
\newcommand*{\Mk}{\mkern -2mu}
\newcommand*{\mK}{\mkern 1mu}
\newcommand*{\MK}{\mkern 2mu}
\hypersetup{urlcolor=purple, linkcolor=blue, citecolor=red}
\newcommand*{\romanenumi}{\renewcommand*{\theenumi}{\roman{enumi}}}
\newcommand*{\Romanenumi}{\renewcommand*{\theenumi}{\Roman{enumi}}}
\newcommand*{\alphenumi}{\renewcommand*{\theenumi}{\alph{enumi}}}
\newcommand*{\Alphenumi}{\renewcommand*{\theenumi}{\Alph{enumi}}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%% Auteur
%%%1
\author{\firstname{Zachary} \lastname{Hamaker}}
\address{University of Florida\\
Department of Mathematics \\
Gainesville\\
FL 32611-1941, USA}
\email{zhamaker@ufl.edu}
%%%2
\author{\firstname{Brendan} \lastname{Pawlowski}}
\address{University of Southern California\\
Department of Mathematics\\
Los Angeles\\
CA 90089-2532, USA}
\email{bpawlows@usc.edu}
%%%3
\author{\firstname{Bruce} \middlename{E.} \lastname{Sagan}}
\address{Michigan State University\\
Department of Mathematics\\
East Lansing\\
MI 48824-1027, USA}
\email{sagan@math.msu.edu}
%%%%% Sujet
\keywords{Knuth class, pattern avoidance, quasisymmetric function, Schur function, shuffle, symmetric function, Young tableau}
\subjclass{05E05, 05A05}
%%%%% Gestion
\DOI{10.5802/alco.96}
\datereceived{2018-10-26}
\daterevised{2019-06-07}
\dateaccepted{2019-09-18}
%%%%% Titre et résumé
\title[Pattern avoidance and quasisymmetric functions]{Pattern avoidance and quasisymmetric functions}
\begin{abstract}
Given a set of permutations $\Pi$, let $\mathfrak{S}_n(\Pi)$ denote the set of permutations in the symmetric group $\mathfrak{S}_n$ that avoid every element of $\Pi$ in the sense of pattern avoidance. Given a subset $S$ of $\{1,\dots,n-1\}$, let $F_S$ be the fundamental quasisymmetric function indexed by $S$. Our object of study is the generating function $Q_n(\Pi) =\sum F_{\mathop{\text{Des}}\sigma}$ where the sum is over all $\sigma\in\mathfrak{S}_n(\Pi)$ and $\mathop{\text{Des}}\sigma$ is the descent set of $\sigma$. We characterize those $\Pi\subseteq\mathfrak{S}_3$ such that $Q_n(\Pi)$ is symmetric or Schur nonnegative for all $n$. In the process, we show how each of the resulting $\Pi$ can be obtained from a theorem or conjecture involving more general sets of patterns. In particular, we prove results concerning symmetries, shuffles, and Knuth classes, as well as pointing out a relationship with the arc permutations of Elizalde and Roichman. Various conjectures and questions are mentioned throughout.
\end{abstract}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}
\maketitle
\section{Introduction}
Let $\fS_n$ be the symmetric group of all permutations of $[n]=\{1,\dots,n\}$. We view the permutations in $\fS_n$ as sequences $\pi=\pi_1\dots\pi_n$. Given any sequence $\si$ of $k$ distinct integers, its \emph{standardization} is the permutation $\std\si\in\fS_k$ obtained by replacing the smallest element of $\si$ by $1$, the next smallest by $2$, and so forth. We say that permutation $\si$ \emph{contains permutation $\pi$ as a pattern} if there is a subsequence $\si'$ of (not necessarily consecutive) elements of $\si$ such that $\std\si'=\pi$. For example, $\si=5132746$ contains $\pi=231$ because of the subsequence $\si'=574$.
Permutation $\si$ \emph{avoids} $\pi$ if it does not contain $\pi$ as a pattern. Given a set of permutations $\Pi$ we let
\[
\fS_n(\Pi) =\{\si\in\fS_n \mid \text{$\si$ avoids every $\pi\in\Pi$}\}.
\]
For more information about permutation patterns, see the book of B\'ona~\cite{bon:cp}. Our object is to make a connection between the theory of patterns and the theory of quasisymmetric functions. First we will review some material concerning symmetric functions. Details about symmetric functions and related combinatorics such as the Robinson--Schensted map can be found in the texts of Macdonald~\cite{mac:sfh}, Sagan~\cite{sag:sym}, or Stanley~\cite{sta:ec2}.
Let $\bx=\{x_1,x_2,\dots\}$ be a countably infinite set of commuting variables and consider the algebra of formal power series over the rationals $\bbQ\llbracket \bx\rrbracket$. Consider a monomial $m=x_{i_1}^{n_1}\dots x_{i_k}^{n_k}$. The \emph{degree} of $m$ is $\sum_i n_i$, and the \emph{degree} of any $f\in\bbQ\llbracket \bx\rrbracket$ is the maximum degree of a monomial in $f$ if the maximum exists or infinity otherwise. We say that $f$ is \emph{symmetric} if it is of bounded degree and invariant under permutation of variables.
For example
\[
f = x_1^2 x_2 + x_1 x_2^2 + x_1^2 x_3 + x_1 x_3^2 + x_2^2 x_3 + x_2 x_3^2 + \dots
\]
is symmetric.
Let $\Sym_n$ denote the vector space of symmetric functions homogeneous of degree $n$. Bases for $\Sym_n$ are indexed by \emph{partitions of $n$}, which are weakly decreasing sequences of positive integers $\la=(\la_1,\dots,\la_k)$ with $\sum_i \la_i=n$.
If $\la$ is a partition of $n$ then we write $\la\ptn n$ or $|\la|=n$. The $\la_i$ are called the \emph{parts} of $\la$.
\looseness-1
We will be particularly interested in the important Schur basis for $\Sym_n$. Recall that a partition $\la=(\la_1,\dots,\la_k)$ has an associated \emph{Young diagram} consisting of $k$ left-justified rows of boxes with $\la_i$ boxes in row $i$. We will write our diagrams in English notation with the first row on top and often make no distinction between a partition and its diagram. Given $\la\ptn n$ then a \emph{standard Young tableau (SYT)}, $P$, of shape $\la$ is obtained by filling the boxes bijectively with the elements of $[n]$ so that rows and columns increase. In a \emph{semistandard Young tableau (SSYT)}, $T$, of shape $\la$ the entries are positive integers distributed so that rows weakly increase and columns strictly increase.
We write $\SYT(\la)$ or $\SSYT(\la)$ for the set of standard or semistandard Young tableaux of shape $\la$, respectively.
We also write $\sh P=\la$ or $\sh T=\la$ to indicate that $P$ or $T$ have shape $\la$.
The \emph{Schur function} corresponding to $\la$ is
\[
s_\la=\sum_T \prod_{i\in T} x_i.
\]
For example, the set $\SSYT(2,1)$ consists of
\begin{equation}
\label{21}
\ytableausetup{boxsize=1.37em}
\begin{ytableau} 1&1\\ 2 \end{ytableau}\ , \hspace{3pt}
\begin{ytableau} 1&2\\ 2 \end{ytableau}\ , \hspace{3pt}
\begin{ytableau} 1&1\\ 3 \end{ytableau}\ , \hspace{3pt}
\begin{ytableau} 1&3\\ 3 \end{ytableau}\ , \hspace{3pt}
\dots,\quad
\begin{ytableau} 1&2\\ 3 \end{ytableau}\ , \hspace{3pt}
\begin{ytableau} 1&3\\ 2 \end{ytableau}\ , \hspace{3pt}
\begin{ytableau} 1&2\\ 4 \end{ytableau}\ , \hspace{3pt}
\begin{ytableau} 1&4\\ 2 \end{ytableau}\ , \hspace{3pt}
\dots
\end{equation}
resulting in
\[
s_{(2,1)} = x_1^2 x_2 + x_1 x_2^2 + x_1^2 x_3 + x_1 x_3^2 + \cdots + 2 x_1 x_2 x_3 + 2 x_1 x_2 x_4 +\cdots
\]
as the corresponding Schur function.
Call a function $f\in\Sym_n$ \emph{Schur nonnegative} if its expansion in the $s_\la$ basis has nonnegative coefficients.
\looseness-1
Quasisymmetric functions refine symmetric functions. Call a formal power series $g$ of bounded degree \emph{quasisymmetric} if any two monomials $x_{i_1}^{n_1}\dots x_{i_k}^{n_k}$ where $i_1<\dots\pi_{i+1}\}\sbe[n-1].
\]
For example, $\Des(35716824)=\{3,6\}$.
Now given a set of patterns $\Pi$ we define the \emph{pattern quasisymmetric function}
\[
Q_n(\Pi)=\sum_{\si\in\fS_n(\Pi)} F_{\Des\si}.
\]
The basic questions we wish to ask about these functions are
\begin{enumerate}
\item When is $Q_n(\Pi)$ symmetric for all $n$?
\item In that case, when is $Q_n(\Pi)$ Schur nonnegative for all $n$?
\end{enumerate}
Note that we are asking about symmetry or Schur nonnegativity not for a single function, but rather for an infinite family of functions.
\begin{table}[htb]\centering
%\renewcommand{\arraystretch}{1.1}
$
\begin{array}{l|l}
\Pi & Q_n(\Pi) \text{ for $n\ge3$}\\
\hline
\emp &\dil \sum_\la f^\la s_\la \rule{0pt}{15pt}\\[15pt]
\{123\} &\dil\sum_{\la_1<3} f^\la s_\la\\[15pt]
\{321\} &\dil\sum_{\la_1^t<3} f^\la s_\la\\[15pt]
\{132,213\}; \{132,312\}; \{213,231\}; \{231,312\} &\dil\sum_{\text{$\la$ a hook}} s_\la\\[15pt]
\{123,132,312\}; \{123,213,231\}; \{123,231,312\} & s_{1^n} + s_{2,1^{n-2}}\\[5pt]
\{132,213,321\}; \{132,312,321\}; \{213,231,321\} & s_n + s_{n-1,1}\\[5pt]
\{132,213,231,312\} & s_n + s_{1^n}\\[5pt]
\{123,132,213,231,312\} & s_{1^n} \\[5pt]
\{132,213,231,312,321\} & s_n
\end{array}
$
\caption{The\vrule height5mm width0pt\ $\Pi$ for Theorem~\ref{main} along with the Schur expansions of $Q_n(\Pi)$ where $\la\ptn n$
\label{S3}}
\end{table}
We start with $\Pi\sbe\fS_3$ and will prove the following theorem for which we will need some preliminaries.
If $\{123,321\}\sbe \Pi$ then, by the Erd\H{o}s--Szekeres Theorem~\cite{es:cpg}, $\fS_n(\Pi)=\emp$ for $n\ge5$, which explains the hypothesis on $\Pi$. We use the notation $f^\la$ for the number of SYT of shape $\la$. The \emph{transpose} of $\la$ is the diagram $\la^t$ obtained by reflecting $\la$ in the main diagonal. Then $\la_1^t$ is the number of boxes in the first column of $\la$, which is also written as $\ell(\la)$ and called the \emph{length} of $\la$.
Also, a \emph{hook} is a partition of the form $(a,1^b)$ for nonnegative integers $a,b$ where $1^b$ denotes the part $1$ repeated $b$ times.
When using a partition as a subscript we often omit the parentheses.
\goodbreak
\begin{theo}
\label{main}
Suppose $\{123,321\}\not\sbe \Pi\sbe\fS_3$. The following are equivalent
\begin{enumerate}
\item $Q_n(\Pi)$ is symmetric for all $n$.
\item $Q_n(\Pi)$ is Schur nonnegative for all $n$.
\item $\Pi$ is an entry in Table~\ref{S3}.
\end{enumerate}
\end{theo}
We note that it is easy to compute examples to show that for any $\Pi$ not listed in Table~\ref{S3} we have $Q_n(\Pi)$ not being symmetric for some small value of $n$ depending on $\Pi$. Therefore it suffices to show that the $\Pi$ in the table have the claimed Schur expansions. In fact, we will show that these expansions are special cases of more general results or conjectures where $\Pi$ is not restricted to $\fS_3$.
The rest of this paper is structured as follows. In the next section we discuss what effect reversal and complementation have on $Q_n(\Pi)$ as well as using properties of the Robinson--Schensted correspondence to derive some of the results in Table~\ref{S3}. In Section~\ref{shu} we show how the quasisymmetric function for a shuffle of two pattern sets can be computed in terms of the ones for each individual component. Shuffles with increasing and decreasing permutations as well as full symmetric groups are used as examples. We define partial shuffles in Section~\ref{psh} as certain shuffles where the increasing permutation has been removed. We conjecture that in this case $Q_n(\Pi)$ has a nice Schur expansion and prove this in a special case. Clearly if $\fS_n(\Pi)$ is a union of Knuth classes then $Q_n(\Pi)$ is symmetric and Schur nonnegative. In Section~\ref{kc} we study when this can happen and, in particular, characterize the SYT such that the permutations avoiding its Knuth class have this property. We show in Section~\ref{ap} that avoiders of the arc permutations of Elizalde and Roichman~\cite{er:ap,er:sap} are in bijection with the permutations avoiding a certain set of shuffles. We end with a section of comments and open questions. We should note that several of our results were derived independently by Elizalde and Roichman~\cite{er:ssp} in the context of products and grid classes. For these, we provide a citation of their work in the corresponding proposition of this article. In this paper, they also find $Q_n(\Pi)$ for various sets of patterns not consideered here, for example when $\Pi=\{321,2143,2413\}$.
\section{Symmetries and the Robinson--Schensted bijection}
If one views a permutation as a permutation matrix, then the dihedral group $D_4$ of the square acts on $\fS_n$. We wish to investigate whether this action tells us anything about $Q_n(\Pi)$. In particular, if this function is symmetric and one acts on $\Pi$ with a dihedral symmetry then is the new quasisymmetric function symmetric? If so, what is its Schur expansion? As usual, we apply a symmetry to a set by applying it to each member of the set.
First we note that if $Q_n(\Pi)$ is a symmetric function then $Q_n(\Pi^{-1})$ need not be. For example, one can easily check that this is true if $n=3$ and $\Pi=\{132, 312\}$. Therefore we can expect the dihedral symmetries preserving symmetry of $Q_n$ to form a subgroup of order at most $4$ in $D_4$. We will now show that such a subgroup exists.
It is easy to describe two of the symmetries in $D_4$ directly in terms of the permutations in $\fS_n$. The permutation $\pi=\pi_1\pi_2\dots\pi_n$ has \emph{complement} $\pi^c = n+1-\pi_1, n+1-\pi_2,\dots,n+1-\pi_n$ where we have inserted commas between the elements for readability. Its \emph{reversal} is $\pi^r = \pi_n\pi_{n-1}\dots\pi_1$. For example, if $\pi=35716824$ then $\pi^c = 64283175$ and $\pi^r = 42861753$. Complementation and reversal are two of the reflections in $D_4$ and so $\pi^{rc}=\pi^{cr}$ is the permutation whose matrix is obtained by rotating the matrix of $\pi$ by $180^\circ$. To state our first dihedral symmetry result, recall that the transpose $\la^t$ of a Young diagram $\la$ is gotten by reflecting $\la$ in its main diagonal. We use the same notation for tableaux.
\begin{prop}
\label{c}
If $Q_n(\Pi)$ is symmetric then so is $Q_n(\Pi^c)$. In particular, if $Q_n(\Pi)=\sum_\la c_\la s_\la$ for certain coefficients $c_\la$ then
\[
Q_n(\Pi^c)=\sum_\la c_\la s_{\la^t}.
\]
\end{prop}
\begin{proof}
Using Theorem~\ref{ges} we can write
\[
\sum_{\si\in\fS_n(\Pi)} F_{\Des\si} = Q_n(\Pi) = \sum_\la c_\la s_\la= \sum_\la c_\la \sum_{P\in\SYT(\la)} F_{\Des P}.
\]
Note that for any permutation $\Des \pi^c =[n-1]-\Des\pi$ and $\fS_n(\Pi^c)=(\fS_n(\Pi))^c$. Also,
for any standard Young tableau $\Des P^t = [n-1]-\Des P$. Using these facts and the previous displayed equation gives
\[
Q_n(\Pi^c)=\sum_{\si\in\fS_n(\Pi)} F_{[n-1]-\Des\si} = \sum_\la c_\la \sum_{P\in\SYT(\la)} F_{[n-1]-\Des P}=\sum_\la c_\la s_{\la^t}
\]
as desired.
\end{proof}
In order to deal with reversals, we will need some background about the Robinson--Schensted map~\cite{rob:rsg,sch:lid}. This is a bijection
\[
\RS:\fS_n\ra\bigcup_{\la\ptn n} \SYT(\la)\times\SYT(\la).
\]
If $\RS(\pi)=(P,Q)$ then we will write $P=P(\pi)$ and $Q=Q(\pi)$ and call $P$ and $Q$ the \emph{$P$-tableau} and \emph{$Q$-tableau} of $\pi$, respectively.
If $\pi=\pi_1\dots\pi_n$ then $P$ is constructed using an operation called \emph{insertion} that sequentially inserts $\pi_1,\dots,\pi_n$ to form $P$. After the $k$th insertion, a $k$ is \emph{placed} in $Q$ so that one maintains $\sh P=\sh Q$ at all times. Although we are using $Q$ in both the notation $Q(\pi)$ and $Q_n(\Pi)$ the two different concepts should be distinguishable by context and the fact that the latter has a subscript while the former does not.
\looseness-1
We put an equivalence relation on $\fS_n$ by declaring that $\pi$ and $\si$ are \emph{Knuth equivalent}, written $\pi\sim\si$, if $P(\pi)=P(\si)$. Given an SYT $P$, the corresponding \emph{Knuth class} is
\[
K(P) = \{\pi \mid P(\pi)=P\}.
\]
\looseness-1
Given a partition $\la$ it will also be convenient to define an associated \emph{Knuth aggregate}~by
\[
K(\la) = \{\pi \mid \sh P(\pi) = \la\} =\bigcup_{\sh(P)=\la} K(P).
\]
We will need the following properties of the map $\RS$. For proofs of these results, see~\cite{sta:ec2}.
\begin{theo}
\label{RS}
Suppose $\RS(\pi)=(P,Q)$.
\begin{enumerate}
\item\label{theo2.2_a} %[(a)]
$\Des\pi=\Des Q$.
\item\label{theo2.2_b} %[(b)]
If $\sh P=\la$ then $\la_1$ is the length of a longest increasing subsequence of $\pi$.
\item\label{theo2.2_c} %[(c)]
$P(\pi^r) = (P(\pi))^t$.
\item\label{theo2.2_d} %[(d)]
$\RS(\pi^{-1}) = (Q,P)$. %\hqed
\end{enumerate}
\end{theo}
These results have interesting implications for our quasisymmetric functions. To state them conveniently we will use the notation
$F_\pi=F_{\Des\pi}$ for a permutation $\pi$. And for a set $\Pi$ of permutations we define $F_\Pi=\sum_{\pi\in\Pi} F_\pi$.
\begin{lemma}
\label{knuth}
Suppose $P\in\SYT(\la)$.
\begin{enumerate}
\item\label{lemma2.3_a} %[(a)]
$F_{K(P)} = s_\la$.
\item\label{lemma2.3_b} %[(b)]
$F_{K(\la)} = f^\la s_\la$.
\end{enumerate}
\end{lemma}
\begin{proof}
Using the fact that $\RS$ is a bijection, Theorem~\ref{ges}, and Theorem~\ref{RS}~\eqref{theo2.2_a} we have
\[
F_{K(P)} = \sum_{\pi\in K(P)} F_{\Des\pi} = \sum_{Q\in\SYT(\la)} F_{\Des Q} = s_\la
\]
which is~\eqref{lemma2.3_a}. For~\eqref{lemma2.3_b}, we use~\eqref{lemma2.3_a} to write
\[
F_{K(\la)} = \sum_{\sh(P)=\la} F_{K(P)} = \sum_{\sh(P)=\la} s_\la = f^\la s_\la
\]
as desired.
\end{proof}
We will now prove that Proposition~\ref{c} continues to hold if complement is replaced by reversal.
\begin{prop}
\label{r}
If $Q_n(\Pi)$ is symmetric then so is $Q_n(\Pi^r)$. In particular, if $Q_n(\Pi)=\sum_\la c_\la s_\la$ for certain coefficients $c_\la$ then
\[
Q_n(\Pi^r)=\sum_\la c_\la s_{\la^t}.
\]
\end{prop}
\begin{proof}
For each partition $\la$ pick a tableau $P_\la\in\SYT(\la)$. Then using Lemma~\ref{knuth}~\eqref{lemma2.3_a} we have
\[
\sum_{\si\in\fS_n(\Pi)} F_{\Des\si} = Q_n(\Pi) = \sum_\la c_\la s_\la= \sum_\la c_\la F_{K(P_\la)}.
\]
Combining this with Theorem~\ref{RS}~\eqref{theo2.2_c} yields
\[
Q_n(\Pi^r)=\sum_{\si\in\fS_n(\Pi)} F_{\Des\si^r} = \sum_\la c_\la F_{K((P_\la)^t)}=\sum_\la c_\la s_{\la^t}
\]
which is what we wished to prove.
\end{proof}
As an immediate corollary of Propositions~\ref{c} and~\ref{r} we get the following.
\begin{prop} [{cf.~\cite[Lemma 8.1]{er:ssp}}]
\label{cr}
If $Q_n(\Pi)$ is symmetric then so is $Q_n(\Pi^{cr})$. In particular, $Q_n(\Pi^{cr})=Q_n(\Pi)$.
%%%\hqed
\end{prop}
As an application of these ideas, we will now verify the expansions in the first three and last three rows of Table~\ref{S3}. For the first row, we use Lemma~\ref{knuth}~\eqref{lemma2.3_b} and the fact that $\RS$ is a bijection to write
\[
Q_n(\emp)=\sum_{\si\in\fS_n} F_\si = \sum_{\la\ptn n} F_{K(\la)} = \sum_{\la\ptn n} f^\la s_\la.
\]
The next two rows are special cases of the following result. In it and the sequel we eliminate the braces when writing out $Q_n(\Pi)$ for a specific $\Pi$. We will also use the notation
\[
\io_k = 12\dots k
\]
and
\[
\de_k = k \dots 21
\]
for the increasing and decreasing permutations of length $k$.
\begin{prop}
\label{iode}
For any $k\ge 1$ we have
\[
Q_n(\io_k) = \sum_{\la_1k$ it is automatic that the smallest $\ell$ elements of $\si$ contain the same copy of $\pi$. Similarly we have that the last $n-\ell$ elements of $\si$ must contain a copy of some element of $\Pi'$. And it is easy to check that the other elements can be arranged arbitrarily so that $\si\in\ofS_k(\Pi) \shuffle \fS_{\ell-k} \shuffle \ofS_{n-\ell}(\Pi')$. The reader should now be able to fill in the details of the reverse containment.
From~\ree{AcapA} it follows that if $k_1 < \cdots < k_{p}$, then $A_{k_1} \cap \cdots \cap A_{k_p} = A_{k_1} \cap A_{k_{p}}$. Applying this observation to~\ree{Phi(shu)} and then using the fact that $\sum_k (-1)^k \binom{n}{k}=\de_{n,0}$ gives
\begin{align*}
\Phi(\ofS_n(\Pi \shuffle \Pi'))
&= \sum_{k=1}^{n-1} \Phi(A_k) + \sum_{1 \leq k < \ell \leq n-1} \Phi(A_k \cap A_\ell) \sum_{p=2}^{n-1} (-1)^{p-1} \binom{\ell-k-1}{p-2}\\[10pt]
&= \sum_{k=1}^{n-1} \Phi(A_k) - \sum_{k=1}^{n-2} \Phi(A_k \cap A_{k+1}).
\end{align*}
Now using the definition of $A_k$, equation~\ree{AcapA}, and the fact that $\Phi$ is a homomorphism yields
\begin{align*}
\Phi(\ofS_n(\Pi \shuffle \Pi'))
&= \sum_{k=1}^{n-1} \Phi(\ofS_k(\Pi) \shuffle \ofS_{n-k}(\Pi')) - \sum_{k=1}^{n-2} \Phi (\ofS_k(\Pi) \shuffle \fS_1 \shuffle \ofS_{n-k-1}(\Pi'))\\%[10pt]
&= \sum_{k=1}^{n-1} \Phi(\ofS_k(\Pi)) \Phi(\ofS_{n-k}(\Pi')) - \sum_{k=1}^{n-2} \Phi (\ofS_k(\Pi))s_1\Phi(\ofS_{n-k-1}(\Pi')).
\end{align*}
Write $\Phi(\ofS_n(\Pi))= \Phi(\fS_n) - Q_n(\Pi) = s_1^n - Q_n(\Pi)$ and expand the binomials.
All terms will cancel except the products %$Q_k(\Pi)Q_{n-k}(\Pi')$
involving at most one factor of $s_1$ from the first sum and
$Q_k(\Pi)s_1Q_{n-k-1}(\Pi')$ from the second. Rearranging terms gives the formula in the theorem once one takes account of the fact that the initial $Q_n(\Pi')$ summand cancels into the $k=0$ term of the sum.
\end{proof}
We note that this theorem takes a nice form when expressed in terms of generating functions. In particular, if one lets
\[
Q(\Pi) = \sum_{n=0}^{\infty} Q_n(\Pi)t^n
\]
then the previous result becomes the following.
\begin{coro}
For any sets of permutations $\Pi$ and $\Pi'$,
\[
%\eqed{
Q(\Pi \shuffle \Pi') = Q(\Pi) + Q(\Pi') + (ts_1 - 1)Q(\Pi)Q(\Pi').
%}
\]
\end{coro}
We also have the following immediate corollary of Theorem~\ref{shu:thm}
\begin{coro}
For any sets of nonempty permutations $\Pi$ and $\Pi'$, if $Q_n(\Pi)$ and $Q_n(\Pi')$ are symmetric for all $n$ then then same is true of $Q_n(\Pi\shu\Pi')$.%\hqed
\end{coro}
Unfortunately, the theorem does not show that Schur nonnegativity is preserved. However computer evidence supports this conjecture.
\begin{conj}
\label{shu:non}
For any sets of nonempty permutations $\Pi$ and $\Pi'$, if $Q_n(\Pi)$ and $Q_n(\Pi')$ are Schur nonnegative for all $n$ then then same is true of $Q_n(\Pi\shu\Pi')$.
\end{conj}
Although we can not do so in general, we can still derive Schur nonnegativity under certain circumstances.
\begin{lemm}
\label{diff}
Suppose that, for all $n\ge0$
\[
G_n= \sum_{\la\ptn n} c_\la s_\la
\]
for certain constants $c_\la$. Define, for all $n\ge1$, a symmetric function $G_n'$ and constants $d_\la$ by
\[
G_n'=s_1 G_{n-1} - G_n = \sum_{\la\ptn n} d_\la s_\la.
\]
\begin{enumerate}
\item\label{lemma3.5_a}%[(a)]
We have
\[
d_\la = \left( \sum_{\la^-} c_{\la^-} \right) - c_\la
\]
where $\la^-$ ranges over all diagrams obtained by removing a box from the diagram of $\la$
\item\label{lemma3.5_b}%[(b)]
If $c_\la \le \sum_{\la^-} c_{\la^-} $ for all $\la\ptn n$ then $G_n'$ is Schur-nonnegative.
\end{enumerate}
\end{lemm}
\begin{proof}
Clearly~\eqref{lemma3.5_b} follows from~\eqref{lemma3.5_a}. And~\eqref{lemma3.5_a} itself follows easily from the Pieri rule for multiplying Schur functions.
\end{proof}
As an application, we will consider shuffles with $\io_k$, $\de_k$, and $\fS_k$.
\begin{coro}
If $Q_n(\Pi)$ is Schur-nonnegative for all $n\ge0$ then so are the following: $Q_n(\Pi\shuffle\io_k)$, $Q_n(\Pi\shuffle\de_k)$, and $Q_n(\Pi\shuffle \fS_k)$.
\end{coro}
\begin{proof}
We will only prove first statement as the others are similar.
Recall that the Littlewood--Richardson rule expresses the product of two Schur functions as a non-negative linear combination of Schur functions.
Then in view of Theorem~\ref{shu:thm}, it suffices to show that condition~\eqref{lemma3.5_b} of Lemma~\ref{diff} is satisfied where $G_n=Q_n(\io_k)$.
By Proposition~\ref{iode}, if $\la_1\ge k$ then $c_\la=0$ and so the inequality is immediate.
On the other hand, if $\la_1b>c>\dots>0$. We are using the term ``reverse'' because in this case $\pi^r$ is what is usually called a \emph{layered permutation}.
Also, let
\[
\cH_n=\{\la\ptn n \mid \text{$\la$ is a hook}\}
\]
and $\SYT(\cH_n)$ be the set of tableaux $P$ so that $\sh(P) \in \cH_n$.
\begin{prop} [{\cite[Corollary 4.11]{er:ssp}}]
\label{132,213}
We have
\[
Q_n(132,213)=Q_n(231,312)=\sum_{\la\in\cH_n} s_\la
\]
\end{prop}
\begin{proof}
By symmetry, it suffices to prove that $Q_n(132,213)$ is equal to the sum.
From the description~\ree{rlayer} it is clear that the map $\pi\mapsto\Des\pi$ gives a bijection $\fS_n(132,213)\ra 2^{[n-1]}$. Thus
\[
Q_n(132,213)=\sum_{S\sbe[n-1]} F_S.
\]
We will be done by Lemma~\ref{knuth}~\eqref{lemma2.3_a} if we can show that the map $P\mapsto\Des P$ is a bijection $\SYT(\cH_n)\ra 2^{[n-1]}$. But is is easy to see that this map has an inverse. In particular, given $S\sbe[n-1]$ we construct the hook tableau whose first column has elements $\{1\}\cup (S+1)$ where $S+1\sbs[n]$ is obtained by adding one to each element of $S$.
\end{proof}
To try and generalize the previous result, note that $\{132,213\}=(13\shu 2) - \{123\}$.
We will put a hat on an element of a permutation to indicate the sequence obtained by removing that element. For example, $3\hat{2}41=341$.
Now define the \emph{partial shuffle}
\[
(12\dots\widehat{n-1}n)\pshu (n-1) = [(12\dots\widehat{n-1}n)\shu (n-1)] - \{\io_n\}.
\]
To illustrate $13\pshu 2 = \{132,213\}$ and $124\pshu 3 = \{1243, 1324, 3124\}$.
For the generalization of hook diagrams, let $(i,j)$ denote the box of a Young diagram in row $i$ and column $j$.
And if $P$ is a Young tableau then $P_{i,j}$ will be the entry of $P$ in box $(i,j)$.
We will consider the set of of \emph{enlarged hooks}
\[
\cH_{n,j} = \{\la\ptn n \mid (2,j)\not\in\la\}.
\]
Note $\cH_{n,2}=\cH_n$. The following conjecture has Proposition~\ref{132,213} as the special case $j=3$.
\begin{conj}
\label{pshu}
For $j\ge3$ we have
\[
Q_n( (12\dots\widehat{j-1}j)\pshu (j-1) )=\sum_{\la\in\cH_{n,j-1}} f^{\lab} s_\la
\]
where $\lab$ is $\la$ with $\la_1$ replaced by $\min\{\la_1,j-2\}$.
\end{conj}
This conjecture has recently been proved by Bloom and Sagan~\cite{ajout}. Here we content ourselves with making some progress on the case $j=4$.
%While we have not been able to prove this conjecture, we have been able to make some progress on %the case $j=4$.
It follows from Theorem~\ref{RS}~\eqref{theo2.2_b} and~\eqref{theo2.2_c} that if $\pi$ avoids $\de_m$ then $P(\pi)$ has less than $m$ rows. In general it is \emph{not} true that if $Q_n(\Pi)=\sum_\la c_\la s_\la$ then we have $Q_n(\Pi\cup \{\de_m\})$ is the same sum restricted to $\la$ with $\ell(\la)M+1$. Suppose $\si\in\ofS_n(\Pi)$ contains a copy $\ka$ of some $\pi\in\Pi$. By Theorem~\ref{Kequiv}, it suffices to show that the result $\si'$ of performing a Knuth move on $\si$ will still be in $\ofS_n(\Pi)$. We will do this for a factor $acb$ where $a**m$ in which case a similar argument to the one just given with $A$ replaced by $B$ completes the proof.
\end{proof}
Combining this lemma and equation~\ree{ofs} we immediately see that Conjecture~\ref{shu:non} is true in the case when $\Pi$ and $\Pi'$ are pattern-Knuth closed. In fact, we only need to assume that one of $\Pi$ and $\Pi'$ is pattern-Knuth closed.
\begin{prop}
If $\Pi$ and $\Pi'$ are pattern-Knuth closed then so is $\Pi\shu\Pi'$. If $Q_n(\Pi)$ is Schur nonnegative for all $n$ and $\Pi'$ is pattern-Knuth closed, then $Q_n(\Pi\shu\Pi')$ is Schur nonnegative for all $n$. %\hqed
\end{prop}
\begin{proof}
The first sentence follows from Lemma~\ref{pkc:shu} and equation~\ree{ofs}. Under the hypotheses of the second sentence, Theorem~\ref{shu:thm} implies that $Q_n(\Pi \shu \Pi')$ will be Schur nonnegative for all $n$ if the same is true of $s_1 Q_{n-1}(\Pi') - Q_n(\Pi')$. Recalling the homomorphism $\Phi : \MaR \to \QSym$ sending $w \mapsto F_w$ from the proof of Theorem~\ref{shu:thm}, we have
\[
s_1 Q_{n-1}(\Pi') - Q_n(\Pi') = \Phi\left(\sum_{w \in A} w\right)
\]
where $A = (\fS_{n-1}(\Pi') \shu \iota_1) \setminus \fS_{n}(\Pi')$. But $A$ is a union of Knuth classes by Lemma~\ref{pkc:shu} and the assumption that $\Pi'$ is pattern-Knuth closed.
\end{proof}
We need one more result before we prove the main theorem of this section. For $J\sbe [n-1]$ we let
\[
D_J =\{\pi\in\fS_n \mid \Des\pi= J\}.
\]
Suppose that $\RS(\pi)=(P,Q)$. Then, by Theorem~\ref{RS}~\eqref{theo2.2_a}, we have $\pi\in D_J$ if and only if $\Des Q= J$. As with other operations, we apply the inverse operator to a set of permutations by applying it to each individual permutation. It now follows from what we have just said and Theorem~\ref{RS}~\eqref{theo2.2_d} that $\pi\in D_J^{-1}$ if and only if $\Des P = J$. Then $D_J^{-1}$ is a union of Knuth classes. Also, it follows easily from the definitions that $\Des(\pi^{-1})$ is the set of all $i$ such that $i+1$ appears to the left of $i$ in $\pi$. These two observations are important for the proof of the following result.
\begin{lemma}
\label{DJ-1}
For any $J$, the set $D_J^{-1}$ is pattern-Knuth closed.%\hqed
\end{lemma}
\begin{proof}
The proof is very similar to that of Lemma~\ref{pkc:M}. We only need to take some care with the last case for which we use the same notation as in that demonstration. Suppose first that the elements of $\pi$ corresponding to $a,c$ in $\ka$ are not consecutive in value. From the discussion before the lemma, switching them will result in $\ka'$ whose standardization has the same inverse descent set as $\ka$, namely $J$. Thus $\si'\in\ofS_n(D_J^{-1})$. Now suppose that $a$ and $c$ standardize respectively to $i$ and $i+1$ in $\pi$. It follows that the other elements of $\ka$ are all less than $a$ or greater than $c$. Now let $\ka'$ be $\ka$ with $c$ replaced by $b$. Since $a****1$ in its first column such that $a+1$ is in the first row of $P$. Let $a$ be the largest such element. Let $b>a+1$ be the next element in $P$'s first column so that we have the following situation
\[
P=
\raisebox{15mm}{\ytableausetup
{boxsize=1.7em}
\begin{ytableau}
1 & \cdots & \scriptstyle a{+}1 & \cdots\\
\vdots\\
a\\
b\\
\vdots\\
n
\end{ytableau}}
\]
with $b+1$ being in the first column if $bP_{i-1,2}$ then $K(P)$ is not pattern-Knuth closed.
\end{prop}
\begin{proof}
We will use the strategy and notation of the proof of the previous proposition. We can write $P$ in the following form
\[
\begin{tikzpicture}[scale=.5]
\node at (-1,-2) {$P=$};
\draw (0,0) to (6,0) to (6,-2) to (5,-2) to (5,-3) to (3,-3) to (3,-4) to (2,-4) to (2,0);
\draw (0,-1) to (2,-1);
\draw (1,0) to (1,-2);
\draw (0,0) to (0,-5) to (1,-5) to (1,-4) to (2,-4) to (2,-2) to (0,-2);
\node at (.5,-.5) {$1$};
\node at (.5,-1.5) {$2$};
\node at (1.5,-.5) {$c$};
\node at (1.5,-1.5) {$d$};
\node at (1,-3) {$R$};
\node at (3.5,-1.5) {$S$};
\end{tikzpicture}.
\]
It is easy to see that the insertion tableau of $\pi= \rho(R), 2, d, 1, c, \rho(S)$ is $P$. We consider
\[
\si = \rho(R), 2, d, 2^+, 1, c, \rho(S),
\]
which is Knuth equivalent to
\[
\si' = \rho(R), d, 2, 2^+, 1, c, \rho(S).
\]
Remove an element $k$ from $\si'$ to form $\ka$. There are two cases.
Suppose first that $k\not\in S_1 \cup \{2,2^+,c\}$ where $S_1$ is the first row of tableau $S$. It follows that $2, 2^+, c, S_1$ is an increasing subsequence of $\ka$ of length $\la_1+1$ where $\sh P = \la$. Thus, by Theorem~\ref{RS}~\eqref{theo2.2_b}, $P(\ka)$ has first row of length longer than $\la_1$ and so is not of the correct shape. If $k\in S_1 \cup \{2,2^+,c\}$ then $k\neq 1,d$. Let $i$ be an index with $P_{i,1}>P_{i-1,2}$ and note that $i\ge3$ so that $P_{i-1,2}\ge d$.
It follows that $P_{\ell(\la),1}, \dots, P_{i,1}, P_{i-1,2}, \dots, P_{3,2}, d, x, 1$ is a decreasing subsequence of $\ka$ where $x$ is either $2$ or $2^+$. But this subsequence has length $\ell(\la)+1$. If follows from Theorem~\ref{RS}~\eqref{theo2.2_b} and~\eqref{theo2.2_c} that $P(\ka)$ will have first column of length longer than $\ell(\la)+1$ and so, again, will not have the right shape. This finishes the proof.
\end{proof}
We can extend the definition of $P$ by letting $P_{i,j}=\infty$ for $i,j\ge1$ and $(i,j)$ outside $\la=\sh P$. In this case, the proof of the previous proposition still goes through in the case where $P$'s first two columns are of equal length since $P_{\ell(\la)+1,1}=\infty>P_{\ell(\la),2}$. We can now finish the proof of Theorem~\ref{pkc:main} with the following proposition.
\begin{prop}
Let $P$ be of non-hook shape. If $P_{i+1,1}0$ or $l>0$ since $C$ must contain an element less than $e$ to satisfy the hypothesis of this proposition.
Our proof splits into two cases.
\begin{figure}[htb]\centering
$
\ytableausetup
{boxsize=1.7em}
\begin{ytableau}
R_1 & R_2 & e\\
a & c \\
b_0 & d_1 \\
b_1\\
\vdots\\
b_k\\
c^-\\
d_2\\
\vdots\\
d_l\\
f_1\\
\vdots\\
f_p
\end{ytableau}
$
\caption{The insertion tableau for $\si'$ in Case 1.
\label{P(si')}}
\end{figure}
\begin{enonce*}[remark]{Case 1} $l > 0$.
Define
\[
\pi = \rho(C), b_0, e, a, c, \rho(R), \rho(S).
\]
It easy to check that $P(\pi) = P$.
Also let
\[
\si= f_p,\dots,f_1,d_l,\dots,d_2,c^-,d_1,b_k,\dots,b_0, e, a, c, \rho(R), \rho(S)
\]
which is obtained from $\pi$ by adding $c^-$. Apply a Knuth move to obtain
\[
\si'= f_p,\dots,f_1,d_l,\dots,d_2,c^-,b_k,d_1,b_{k-1},\dots,b_0, e, a, c, \rho(R), \rho(S)
\]
Remove any $h$ from $\si'$ to obtain $\ka$. We will show $P(\ka)\neq P$.
Consider the insertion tableau of $\si$ up to and including $\rho(R)$, which will have the form given in Figure~\ref{P(si')} where $R_1$ and $R_2$ are the two columns of $R$. If $h$ comes from the first column of this tableau then its removal will cause all the entries to shift up by one, making the first column too short. The only way to compensate for this is if the insertion of $\rho(S)$ causes $e$ to bump into the first column in row $r$ just below $b_0$. But then
\[
P(\ka)_{r,1}=e>d_1=P(\ka)_{r-1,2}
\]
which is a contradiction. On the other hand, if $h$ comes from the second column of Figure~\ref{P(si')} then $e$ will have to end up in the second column to preserve column lengths. And if $h$ comes from a column of $S$ then the first two columns in the figure must remain undisturbed. In either case the first column will contain more entries in the interval $[b_0,c]$ than $P$ does, which finishes this case.
\end{enonce*}
\begin{enonce*}[remark]{Case 2}
$l=0$ and $k>0$.
Now we consider
\[
\pi= f_p,\dots,f_1,b_k,e,b_{k-1},\dots,b_0, a, c, \rho(R), \rho(S).
\]
It is easily checked that since $k>0$ we have $P(\pi)=P$. Add $c^+$ to obtain
\[
\si= f_p,\dots,f_1,c^+,b_k,e,b_{k-1},\dots,b_0, a, c, \rho(R), \rho(S)
\]
and perform a Knuth move to yield
\[
\si'=f_p,\dots,f_1,c^+,e,b_k,b_{k-1},\dots,b_0, a, c, \rho(R), \rho(S).
\]
Define $h$, $\ka$, and $R_1$ as before with the goal of showing $P(\ka)\neq P$.
Note that there is a decreasing subsequence of $\si'$ of length $\ell(\la)+1$ consisting of the $f$'s, either $c^+$ or $e$, the $b$'s, $a$, and $\rho(R_1)$.
Therefore $h\in\{a,b_0,\dots,b_k,f_1,\dots,f_p\}\cup R_1$. If $h$ is one of the $f$'s then $P(\ka)$ will have more elements in the interval $[a,e]$ in its first column than $P$. If $h$ is any of the other possibilities, then $P(\ka)$ will have more elements greater than $c$ in its first column than $P$. Either way, we have our final contradiction.\qedhere
\end{enonce*}
\end{proof}
We conclude this section with two questions.
First of all, we know from Lemma~\ref{knuth} and Theorem~\ref{pkc:main} that when $P$ is superstandard of hook shape then %$Q_n(\Pi)$
$Q_n(K(P))$ is Schur nonnegative.
\begin{question}
Find a combinatorial interpretation for the coefficients in the Schur expansion for $Q_n(K(P))$ when $P$ is superstandard of hook shape.
\end{question}
It is also natrual to ask about generalizing Theorem~\ref{pkc:main} to pairs of tableaux.
\begin{question}
\label{c:2_knuth}
Let $P,Q$ be standard Young tableaux. Find a necessary and sufficient condition for $K(P) \cup K(Q)$ to be pattern-Knuth closed.
\end{question}
We note that if $\Pi,\Pi'$ are both pattern-Knuth closed then so is $\Pi\cup\Pi'$ since in this case $\ofS_n(\Pi\cup\Pi')$ is the union of the Knuth classes of $\ofS_n(\Pi)$ and $\ofS_n(\Pi')$. This together with Theorem~\ref{pkc:main} shows that if $P,Q$ are superstandard hooks then $K(P) \cup K(Q)$ is %pattern-Knuth.
pattern-Knuth closed. We also note that both of these questions have been answered by Bloom and Sagan~\cite{ajout}. In particular, they were able to deal with Question~\ref{c:2_knuth} by giving a more conceptual proof of Theorem~\ref{pkc:main}.
\section{Arc permutations}
\label{ap}
Elizalde and Roichman introduced and studied arc permutations in~\cite{er:ap,er:sap}. They are closely related to two of the permutation classes we have been considering and so we will be able to produce a bijection between the arc permutations and permutations avoiding a certain shuffle.
A permutation $\si\in\fS_n$ is in the set of \emph{arc permutations}, $\cA_n$, if each prefix $\si_1\si_2\dots\si_i$ is an interval in the integers modulo $n$. Equivalently, $\cA_n=\fS_n(\Pi_\cA)$ where
\[
\Pi_\cA=\{1324,1342,2413,2431,3124,3142,4213,4231\}.
\]
Recall that the permutations avoiding $\{132,312\}$ were those where each prefix was an interval of integers and a similar statement is true for suffixes when avoiding $\{213,231\}$. Define the \emph{pin shaped} permutations to be
\[
\cP_n=\fS_n(132,312)\cup\fS_n(213,231)\sbe \cA_n.
\]
(Elizalde and Roichman call these permutations \emph{unimodal} because their rotations are unimodal sequences, but we prefer to reserve unimodal for its original meaning.) We will also be using the complement $\cZ_n=\cA_n-\cP_n$.
In order to define the symmetric functions to describe $Q_n(\Pi_\cA)$ we will need a few more definitions. Consider the set of non-trivial hooks
\[
\cHb_n = \cH_n-\{(n), (1^n)\}
\]
as well as the diagrams one obtains from the elements of $\cHb_n$ by adding the $(2,2)$ box
\[
\cT_n = \{\la\cup (2,2) \mid \la\in\cHb_{n-1}\}.
\]
Define the corresponding generating functions $\Hb_n=\sum_{\la\in\cHb_n} s_\la$ and $T_n=\sum_{\la\in\cT_n} s_\la$. The following result is a consequence of~\cite[Theorem 7.7]{er:ap}.
\begin{theo}
\label{er}
For all $n\ge0$ we have
\[
%\eqed{
Q_n(\Pi_\cA) = T_n + 2\Hb_n + s_{n} + s_{1^n}.
\]
%}
\end{theo}
There is a shuffle class with the same expansion. Let
\[
\Pi_\cS = \{1\}\shu \{132,312\}= \{1243,1423,2143,4123,2413,4213,2431,4231\}.
\]
\begin{prop}
For all $n\ge0$ we have
\[
Q_n(\Pi_\cS)=Q_n(\Pi_\cA).
\]
\end{prop}
\begin{proof}
Applying Theorem~\ref{shu:thm} with $\Pi=\{1\}$ and $\Pi'=\{132,312\}$, then Proposition~\ref{132,312}, and finally the Pieri formula gives
\[
Q_n(\Pi_S) = Q_n(\Pi') + s_1 Q_{n-1}(\Pi') - Q_n(\Pi') = T_n + 2\Hb_n + s_{n} + s_{1^n}.
\]
Comparing this with the previous result completes the proof.
\end{proof}
Note that by reversal, complement, and Proposition~\ref{132,213}, the previous proposition is true if $\Pi_\cS$ is replaced by either $\{1\}\shu\Pi$ or $\Pi\shu\{1\}$ for any
\[
\Pi\in \{\; \{132,312\}, \{132,213\}, \{213,231\},\{231,312\}\;\}.
\]
However, there is no dihedral symmetry relating any of these shuffles to $\Pi_\cS$.
Elizalde and Roichman~\cite[Section 7.4]{er:ap} gave a bijective proof of Theorem~\ref{er}. In particular, they proved the following result.
\begin{theo}
For all $n\ge0$, there is an explicit bijection
\[
%\eqed{
\phi:\cZ_n\ra \bigcup_{\la\in\cT_n} \SYT(\la).
\]
%}
\end{theo}
As a consequence, we have the following.
\begin{coro}
For all $n\ge0$, there is an explicit bijection
\[
\psi:\fS_n(\Pi_\cA)\ra\fS_n(\Pi_\cS).
\]
\end{coro}
\begin{proof}
Note that by their descriptions in terms of prefixes and suffixes, we have
\[
\fS_n(132,312)\cap\fS_n(213,231)=\{\io_n,\de_n\}.
\]
For $\si\in\fS_n(\Pi_\cA)$ we define $\psi(\si)$ as follows, using $Q(\pi)$ as the Robinson--Schensted recording tableau.
\begin{enumerate}
\item\label{proof_coro6.4_a} %[(a)]
If $\si\in\fS_n(132,312)$ then let $\psi(\si)=\si$.
\item\label{proof_coro6.4_b} %[(b)]
If $\si\in\cZ_n$ then let $\psi(\si)=\tau$ where $\tau\in\fS_n(\Pi_\cS)$ is the unique permutation with $Q(\tau)=\phi(\si)$.
\item\label{proof_coro6.4_c} %[(c)]
If $\si\in \fS_n(213,231)-\{\io_n,\de_n\}$ then let $\psi(\si)=\tau$ where $\tau\in\fS_n(\Pi_\cS)-\fS_n(132,312)$ is the unique permutation with $Q(\tau)=Q(\si)$.
\end{enumerate}
Note that~\eqref{proof_coro6.4_b} is well defined by Lemma~\ref{pkc:shu} and the fact that $Q_n(\cZ_n)$ is Schur multiplicity free.
In a similar manner we see that~\eqref{proof_coro6.4_c} is well defined. The check that this is a bijection is now easily done.
\end{proof}
The construction of the map $\psi$ is hardly as illuminating as one would hope.
\begin{question}
Is there a direct description of a bijection between $\fS_n(\Pi_\cA)$ and $\fS_n(\Pi_\cS)$ on the level of permutations?
\end{question}
\section{Comments and open questions}
\label{coq}
We end with some comments and some questions that we hope the reader will be interested in answering.
%\vs{15pt}
%{\bf Symmetry vs nonnegativity.}
\subsection*{Symmetry \vs nonnegativity}
It is possible to construct $\Pi$ such that $Q_n(\Pi)$ is symmetric, but not Schur nonnegative. In particular, consider the following set of permutations where we have enclosed certain elements in parentheses for readability
\begin{multline*}
X_n=\{\io_n\} \cup \{2314\dots n,\ 12\dots(n-3)n(n-2)(n-1)\}\\%[5pt]
\cup\{2134\dots n,\ 1324\dots n,\ \dots,\ 12\dots (n-2)n(n-1)\}\\%[5pt]
\cup \{32145\dots n,\ 14325\dots n,\ \dots,\ 12\dots (n-3)n(n-1)(n-2)\}.
\end{multline*}
Let $\Pi = \fS_4-X_4$. Then one can verify that $\fS_n(\Pi)=X_n$ and so
\[
Q_n(\Pi)= s_n+2s_{n-1,1} + s_{n-2,1,1}-s_{n-2,2}.
\]
%\vs{15pt}
%{\bf Stability.}
\subsection*{Stability}
The following is a natural question given the results we have proved such as Lemma~\ref{pkc:M}.
\begin{question}
Suppose $\Pi$ is nonempty and $M$ is the maximum length of a permutation in $\Pi$. Is there an $N$, a function of $M$, such that $Q_n(\Pi)$ symmetric for $n\dots > a_m < \dots < a_p$. (Note that Adin and Roichman call such a sequence ``unimodal'' but that is at variance with standard practice.)
Say that $\pi\in\fS_n$ is \emph{$\al$-comodal} if each $\pi^{(i)}$ in its $\al$-decomposition is comodal. If $\Pi$ is a set of permutations then let $\Pi_\al$ denote the set of $\al$-comodal permutations in $\Pi$. Finally, call $\Pi\sbe\fS_n$ \emph{fine} if there is an $\fS_n$-character $\chi$ such that for all $\al\comp n$
\[
\chi(\al) = \sum_{\pi\in\Pi_\al} (-1)^{\des_\al \pi}
\]
where $\chi(\al)$ is the value of $\chi$ on the conjugacy class indexed by $\al$.
Adin and Roichman give a number of conditions equivalent to a set of permutations $\Pi\sbe\fS_n$ being fine, one of which is that $Q_n(\Pi)$ is symmetric and Schur nonnegative.
This approach has been continued in the work of Elizalde and Roichman~\cite{er:rss}.
%\vs{15pt}
%{\bf Other bases.}
\subsection*{Other bases}
A couple of the generating functions we have calculated are Schur $P$-functions. For example, if $\Pi=\{132,312\}$ then $Q_n(\Pi)=P_n$ by Proposition~\ref{132,312}, and
$Q(\Pi_\cA)=P_{n-1,1}$ by Theorem~\ref{er}.
\begin{question}
For which $\Pi$ is $Q_n(\Pi)$ Schur $P$-nonnegative for all $n$?
\end{question}
One could also change the set of quasisymmetric functions being used in $\QSym_n$. Let $\Th_{\Pk}$ be the peak fundamental quasisymmetric function associated with a subset $\Pk\sbe[2,n-1]$. Stembridge~\cite{ste:epp} developed a theory of enriched $P$-partitions ($P$ here is a partially ordered set), which allowed him to prove an analogue of Theorem~\ref{ges} where $s_\la$ is replaced by a Schur $P$-function and the $F_{\Des P}$ are replaced by $\Th_{\Pk(\si)}$ for certain permutations $\si$, where $\Pk(\si)$ is the peak set of $\si$. Schur $P$-functions are generating functions for certain shifted tableaux just as the usual Schur functions are for semistandard left-justified Young tableaux. Then it is natural to define for a set of permutations $\Pi$
\[
R_n(\Pi)=\sum_{\si\in\fS_n(\Pi)} \Th_{\Pk(\si)}
\]
and ask the question
\begin{question}
For which $\Pi$ is $R_n(\Pi)$ symmetric? In that case when is it Schur $P$-nonnegative?
\end{question}
%\vs{15pt}
%\emph{Acknowledgement.}
\longthanks{\looseness-1
We would like to thank the following people for helpful discussions: Alex Burstein, Vic Reiner, Yuval Roichman, John Stembridge, and Damir Yeliussizov.
We especially thank Alex Woo for the idea which inspired this paper.
Joel Lewis suggested several ideas that were critical in arriving at our results in Section~\ref{kc}.}
\bibliographystyle{amsplain-ac}
\bibliography{ALCO_Hamaker_245}
\end{document}**