
  
%ss.tex: A Snappy Proof That 123-Avoiding Words are Equinumerous
%with 132-Avoiding Words
%%a Plain TeX file by Doron Zeilberger (1/2 page)
 
%begin macros
\def\L{{\cal L}}
\baselineskip=14pt
\parskip=10pt
\def\Tilde{\char126\relax}
\def\halmos{\hbox{\vrule height0.15cm width0.01cm\vbox{\hrule height
 0.01cm width0.2cm \vskip0.15cm \hrule height 0.01cm width0.2cm}\vrule
 height0.15cm width 0.01cm}}
\font\eightrm=cmr8 \font\sixrm=cmr6 
\font\eighttt=cmtt8
\magnification=\magstephalf
\def\P{{\cal P}}
\def\Q{{\cal Q}}
\parindent=0pt
\overfullrule=0in
\nopagenumbers
\def\frac#1#2{{#1 \over #2}}
%\headline={\rm  \ifodd\pageno  \RightHead  \else  \LeftHead  \fi}
%\def\RightHead{\centerline{
%Title
%}}
%\def\LeftHead{ \centerline{Doron Zeilberger}}
%end macros
\bf
\centerline
{
A Snappy Proof That 123-Avoiding Words are Equinumerous
with 132-Avoiding Words
}
\rm
\bigskip
\centerline{ {\it 
Doron ZEILBERGER
}\footnote{$^1$}
{\eightrm  \raggedright
Department of Mathematics, Rutgers University (New Brunswick),
Hill Center-Busch Campus, 110 Frelinghuysen Rd., Piscataway,
NJ 08854-8019, USA.
%\break
{\eighttt zeilberg at math dot rutgers dot edu} , 
%\hfill \break
{\eighttt http://www.math.rutgers.edu/\Tilde zeilberg/.}
April 11, 2005.
Exclusively published in the Personal Journal of
Ekhad and  Zeilberger
\hfill\break
{\eighttt http://www.math.rutgers.edu/\Tilde zeilberg/pj.html} .
Supported in part by the NSF. Accompanied by Maple program
{\eighttt http://www.math.rutgers.edu/\Tilde zeilberg/tokhniot/A123.}
} 
}

Define a mapping $F$ on a word $w$ in the alphabet $\{1,2, \dots, n\}$
recursively as follows. If $w$ is empty, then $F(w):=w$.
Otherwise, $i:=w_1$, and let $W$ be the word obtained from
$w$ by first beheading it, and then replacing all letters
larger than $i+1$ by $i+1$, and let $s$ be the sub-sequence
of $w$ obtained by deleting the letters $\leq i$.
Let $\bar{s}$ be the reverse of $s$.
Let $V:=F(W)$, 
and let $U$ be the word obtained from $V$
by replacing (in order) the letters that are $i+1$ by the
members of $\bar{s}$. Finally let $F(w):=iU$.

$F$ is an involution that sends 123-avoiding words to 132-avoiding
ones, and vice versa. This follows from the fact that
$s$ above in then non-increasing and non-decreasing respectively.
Hence, for any vector of non-negative integers
$(a_1, \dots, a_n)$, 
amongst the $(a_1+ \dots +a_n)!/(a_1! \cdots a_n!)$ words
with $a_1$ $1$'s, \dots, $a_n$ $n$'s,
the number of those that avoid the pattern $123$ equals the
number of those that avoid $132$,
a result first proved by Albert, Aldred, Atkinson, Handley and Holton 
(Europ. J. Comb. {\bf 22} (2001), 1021-1031). 
For permutations (i.e. $a_1=\dots=a_n=1$), $F$ coincides with the classical
bijection of Rodica Simion and Frank Schmidt
(Europ. J. Comb. {\bf 6} (1985), 386-406), but my recursive 
formulation (that only works because we have the extra elbow-room
of words!) is more transparent.

It also follows that we have a quick recurrence 
that enables us to compute the number
of such words,
let's call it $A(a_1, \dots, a_n)$.
$$
A(a_1, \dots, a_n)=\sum_{i=1}^{n} A(a_1,\dots, a_{i-1},a_i -1, a_{i+1}+ \dots + a_n ) \quad.
$$
My brilliant student, Lara Pudwell, is currently exploring extensions and
ramifications.


\end

