\magnification=1200
\hsize=4in
\overfullrule=0pt
\nopagenumbers
\noindent
%
%
{\bf Aaron D. Jaggard}
%
%
\medskip
\noindent
%
%
{\bf Prefix Exchanging and Pattern Avoidance by Involutions}
%
%
\vskip 5mm
\noindent
%
%
%
%
Let $I_n(\pi)$ denote the number of involutions in the symmetric
group ${\cal S}_{n}$ which avoid the permutation $\pi$. We say that two
permutations $\alpha,\beta\in{\cal S}_{j}$ {\it may be exchanged} if
for every $n$, $k$, and ordering $\tau$ of $j+1,\ldots,k$, we have
$I_n(\alpha\tau)=I_n(\beta\tau)$. Here we prove that $12$ and
$21$ may be exchanged and that $123$ and $321$ may be exchanged.
The ability to exchange $123$ and $321$ implies a conjecture of
Guibert, thus completing the classification of ${\cal S}_{4}$ with
respect to pattern avoidance by involutions; both of these results
also have consequences for longer patterns.
Pattern avoidance by involutions may be generalized to rook
placements on Ferrers boards which satisfy certain symmetry
conditions. Here we provide sufficient conditions for the
corresponding generalization of the ability to exchange two
prefixes and show that these conditions are satisfied by $12$ and
$21$ and by $123$ and $321$. Our results and approach parallel
work by Babson and West on analogous problems for pattern
avoidance by general (not necessarily involutive) permutations,
with some modifications required by the symmetry of the current
problem.
\bye