\documentclass[12pt]{article}
\textwidth=6.5in
\textheight=8.75in
\topmargin=-.5in
\oddsidemargin=0in
\evensidemargin=0in


\usepackage{theorem}
\usepackage{latexsym}
\usepackage{amssymb}

\parskip=7pt
\parindent=0pt

\def\Bx{\hfill{$\Box$}}


\font\rms=cmr10  
\font\its=cmti8  
\font\bfs=cmbx8 


\newtheorem{thm}{Theorem}[section]
\newtheorem{lemma}[thm]{Lemma}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{defn}[thm]{Definition}





\begin{document}


\begin{center}
{\bf RESTRICTED PERMUTATIONS FROM CATALAN TO FINE AND BACK}
\vskip 15pt

{\sc Aaron Robertson\footnote{
Homepage:  {\tt http://math.colgate.edu/$\sim$aaron/}\vskip 0pt \hskip
9pt 2000 Mathematics Subject Classification:  05A15, 68R15}
}\\
{\rms Department of Mathematics,}
{\rms Colgate University,
Hamilton, NY 13346, U.S.A.}\\
{\tt aaron@math.colgate.edu}


\end{center}
 
 





%






\begin{abstract}
\noindent \footnotesize
We give some history and recent results in the area
of pattern restricted permutations.  We also present
a new bijection between certain pattern restricted
permutations.
\end{abstract}


%First page headline in AmS-LaTeX for S\'eminaire Lotharingien de Combinatoire
%--first part
\thispagestyle{myheadings}
\font\rms=cmr8
\font\its=cmti8
\font\bfs=cmbx8
\markright{\its S\'eminaire Lotharingien de
Combinatoire \bfs 50 \rms (2004), Article~B50g\hfill}
\def\thepage{}
%
%


\section*{\normalsize Introduction}
It was a great pleasure to have been given the opportunity
to speak at the landmark $50^{\mathrm{th}}$ meeting of the
S\'eminaire Lotharingien de Combinatoire, held 
in March 2003, at
Domaine Saint Jacques, near Ottrott, France.  The meeting was
a wonderful celebration, replete with wonderful company,
wonderful food, and, of course, wonderful mathematics.

This article is an expanded version of the talk that I
presented at the meeting.  We give some history and recent
results in the area of pattern restricted permutations,
as well as present a pertinent new  bijection.




\section*{\normalsize 1. Preliminaries}
We first get the definitions and notation out of the way.

Let $\pi \in S_n$ be a permutation of $\{1,2,\dots,n\}$ written
in one-line notation.
Let $\alpha \in S_m$.
We say that $\pi$ {\it contains the pattern $\alpha$} if there exist
indices $i_1<i_2<\dots<i_m$ such that $\pi_{i_1} \pi_{i_2} \dots
\pi_{i_m}$ is order-equivalent to $\alpha$.
By order-equivalent we mean that the usual order on
the integers is the same for both sequences.  For example,
$475$ is order-equivalent to $132$ since both have smallest
element first, largest element second, and middle element
last.
If $\pi$ does not contain a pattern $\beta$, we say that
$\pi$ is $\beta$-avoiding.  We write $S_n(\beta)$ for
the set of permutations of $S_n$ that are $\beta$-avoiding.

We next
extend this notation.  Let $\mathcal{S} = \bigcup_{n} S_n$.
Let $T \subseteq \mathcal{S}$
 and let $R$ be a multisubset of $\mathcal{S}$.
Then $S_n(T)$ is the set of permutations of $S_n$ that
avoid all patterns in $T$ while
 $S_n(T;R)$ is the set of permutations of $S_n(T)$ that
 contain each pattern
(including multiplicities)
in $R$ exactly once.  If $|T|=1$ or $|R|=1$ then
we drop the set notation. 

So, for example,
$S_n(132,\{123,123\})$ is the set of 
$132$-avoiding permutations in
$S_n$ that contain exactly two $123$ patterns.
As a concrete example, $124635 \in S_6(321;213)$.

One last bit of notation:  we let
$s_n(R) = |S_n(R)|$ and
$s_n(R;T) = |S_n(R;T)|$.



\section*{\normalsize 2. Some History}

In 1838, Catalan [3] defined what we now call the Catalan
numbers:
$$
\frac{1}{n+1}{2n \choose n} = C_n.
$$
In this paper he addressed the question
\begin{quote}
{\it De combien de mani\`eres peut-on effectuer le produit
de $n$ facteurs diff\'erents?
}
\end{quote}
and used essentially an argument that shows that
$
s_n(132)= C_n
$
by proving that 
$C_n = \sum_{i=1}^{n} C_{i-1}C_{n-i}.
$
This argument that shows $s_n(132)=C_n$  goes
as follows.  Let $\pi = \pi_1\pi_2 \dots \pi_n$
and let $\pi_i=n$.  Then $\pi_1 \dots \pi_{i-1}$
must consist of the elements $n-i+1,n-i+2,\dots,n-1$
and $\pi_{i+1} \dots \pi_n$ must consist of
the elements $1,2,\dots,n-i$, for otherwise
$\pi_j \, n \, \pi_k$ would be a $132$ pattern
for some $j,k$, $j<i<k$.  Next,
$\pi_1 \dots \pi_{i-1}$ and $\pi_{i+1} \dots \pi_n$
must each be $132$-avoiding permutations themselves.
Hence, we have
$$
s_n(132) = \sum_{i=1}^n s_{i-1}(132) s_{n-i}(132),
$$
which gives (using initial conditions)
$s_n(132)=C_n$.

%First page headline in AmS-LaTeX for S\'eminaire Lotharingien de Combinatoire
%--restoring the headers and pagenumbering
\pagenumbering{arabic}
\addtocounter{page}{1}
%\markboth{\SMALL TOUFIK MANSOUR}{\SMALL EQUIDISTRIBUTION AND SIGN-BALANCE
%ON $132$-AVOIDING PERMUTATIONS}
%
%

Of course, Catalan did not consider $s_n(132)$.  It was not
until 1915 that $s_n(\alpha)$ was determined for
the first time for some $\alpha \in S_3$.  
MacMahon [see 14] proved that
$s_n(123)=C_n$.  
This result also gives us $s_n(321)=C_n$ by reading
permutations from right-to-left instead of
left-to-right.  This re-reading is called the
reversal bijection, one of the three standard bijections.


\subsection*{\normalsize 2.1 Three Standard Bijections}
There are three standard bijections that allow us
to look at a smaller number of patterns when considering
pattern-avoiding permutations.  We define the following
bijections.

The
reversal bijection:  $r:S_n \rightarrow S_n$,
$\pi_1\pi_2\dots\pi_n \mapsto \pi_n \dots \pi_2 \pi_1$.

The
complement bijection: $c: S_n \rightarrow S_n$,
$\pi_1\pi_2\dots \pi_n \mapsto (n+1-\pi_1) (n+1-\pi_2)\dots (n+1-\pi_n)$.

The
inverse bijection $i: S_n \rightarrow S_n$,
$\pi \mapsto \pi^{-1}$ (group theoretic).

Using these bijections we see that $\pi \in S_n(\alpha)$
if and only if $x(\pi) \in S_n(x(\alpha))$ where
$x$ is one of $r,c,i$.


\subsection*{\normalsize 2.2 More Recent History}

It was not until 1973 that the first non-monotonic pattern
restricted permutations were considered.  Knuth [12]
showed that $s_n(231)=C_n$.  Now,
since $r(231)=132$, $c(231)=213$, and $i(231)=312$, 
Knuth's and MacMahon's results 
show that $s_n(\alpha)=C_n$ for any $\alpha \in S_3$.

This result leads us to the following definition.

{\bf Definition.} We say that two patterns $\alpha$ and $\beta$ are in
the same {\it Wilf class} or are
{\it Wilf equivalent} if and only if $s_n(\alpha)=s_n(\beta)$
for all $n$.


Hence, there is one Wilf class for patterns of length 3.
However, historically it was not shown that $s_n(123)=s_n(132)$
directly, rather that they are both equal to $C_n$.
This leads us into our next section.




\section*{\normalsize 3. Some Bijections}
Using the three standard bijections we have
$s_n(123)=s_n(321)$ and $s_n(132)=s_n(213) = s_n(231) = s_n(312)$.
The fact that $s_n(123)=s_n(132)$ as well is surprising.
Hence, we will look at some bijections from
$S_n(\overline{123})$ to $S_n(\overline{132})$,
where $\overline{123}$ means any element from $\{123,321\}$
and $\overline{132}$ means any element from $\{132,213,231,312\}$
since these are equivalent by the standard bijections.

The first bijection (1975) is due to Rotem [26].  He used
ballot sequences and binary trees as an intermediate step
from $S_n(321)$ to $S_n(231)$.  The first {\it direct}
bijection was given by Simion and Schmidt [27] in 1985.
In more recent years, West [30] has used generating trees while
Stanley [29] and Krattenthaler [13] have used Dyck paths.

\subsection*{\normalsize 3.1 A New Bijection}

We give a new {\it direct} bijection $\gamma: S_n(321)
\rightarrow S_n(132)$.  In order to present $\gamma$
we give a definition.

{\bf Definition.}  Let $k \geq 2$.  Let $\alpha
=\alpha_1\dots\alpha_k$ and $\beta=\beta_1\dots \beta_k$ be two
distinct occurrences of $1k (k-1) \dots 2$ in $\pi$.  We say
$\alpha$ is smaller than $\beta$ if there exists $i$, $1 \leq i \leq k$,
such that
$\pi^{-1}(\alpha_j) = \pi^{-1}(\beta_j)$ for
all $j<i$ and $\pi^{-1}(\alpha_i) <
\pi^{-1}(\beta_i)$.


We can now describe the bijection $\gamma: S_n(321) \rightarrow S_n(132)$.
Let $\pi_1 \pi_2 \dots \pi_n=\pi \in S_n(321)$ and let
$xzy=\pi_{p_1}\pi_{p_2}\pi_{p_3}$ be the smallest $132$ occurrence
in $\pi$.
If no such occurrence exists, $\gamma(\pi)=\pi$.  Otherwise, let
$\mathcal{M}$ be the operation that creates the permutation
$\mathcal{M}\pi$ where
$\mathcal{M}\pi_i=\pi_i$ if $i \not \in \{p_1,p_2,p_3\}$
and $\mathcal{M}\pi_{p_1}=z$, $\mathcal{M}\pi_{p_2}=y$,
and $\mathcal{M}\pi_{p_3}=x$.  Now let $xzy$ be the smallest
$132$ occurrence in $\mathcal{M}\pi$ and apply $\mathcal{M}$ again.
Repeat until the resulting permutation is $132$-avoiding.

{\bf Example.} Let
$\pi=35612487\in S_8(321)$, a permutation that 
has eight $132$ occurrences, the smallest one
being $354$.  
We apply $\mathcal{M}$ to get 
$
\mathcal{M}\pi = 54612387.
$  Notice that the $354$ is changed to $543$ in
the same positions and all other elements are
left untouched.
Now, in 
$
54612387,
$
$587$ is the smallest occurrence. 
Apply $\mathcal{M}$ again to get
$
\mathcal{M}^2\pi = 84612375.
$
Continuing, we get
$
\mathcal{M}^3 \pi=
86512374$ and
$
\mathcal{M}^4 \pi= 86572341
$.
Since $86572341 \in S_8(132)$, $\gamma(35612487)=86572341$.




Of course, we must prove that this {\it is} a bijection.
We start by showing that $\gamma$ is well-defined.  Our
approach is to show that, with respect to the
indices of elements, the smallest $132$ occurrence in
$\mathcal{M}\tau$ is larger than the smallest $132$
occurrence in $\tau$.  Hence, $\mathcal{M}^j\tau$ must
be $132$-avoiding for some finite $j$.


Write $\tau = \tau_1 \tau_2 \dots \tau_n$ and let
$\tau_i \tau_j \tau_k$ be the smallest $132$ occurrence.
Clearly, since $\tau$ has no $132$ occurrence $\tau_x \tau_y \tau_z$ with
$x<i$, $\mathcal{M}\tau$ could only possibly have
such an occurrence if $\{i,j,k\} \cap \{y,z\} \neq \emptyset$.
Since $\tau_i \tau_j \tau_k$ is the smallest $132$ occurrence in $\tau$,
$\tau_x>\tau_k$ and thus $i,k \not \in \{y,z\}$.
Hence, we must have $j \in \{y,z\}$.  From the minimality
of $\tau_i \tau_j \tau_k$, clearly $j \neq z$.
Thus, $\tau_x \tau_j \tau_z$ 
with $i<z<j$  is our only
possibility.
But, $\tau_z>\tau_x > \tau_k$ implies that $\tau_i \tau_z \tau_k$ is
a smaller $132$ occurrence in $\tau$ than $\tau_i \tau_j \tau_k$,
a contradiction. 



Next, assume, for a contradiction, that 
$\tau_j \tau_x \tau_y$ in $\mathcal{M}\tau$ is a
smaller
$132$ occurrence (with respect to the indices) than 
$\tau_i \tau_j \tau_k$ is in $\tau$.
This implies that $\tau_i \tau_x \tau_k$ is a smaller $132$
occurrence in $\tau$ than $\tau_i \tau_j \tau_k$,
contradicting the minimality of $\tau_i \tau_j \tau_k$.


We now show that $\gamma$ is a bijection;
it is enough to give $\gamma^{-1}$.  To do so,
we make the following definition.

{\bf Definition.}  Let $k \geq 2$.  Let $\alpha=\alpha_1\dots \alpha_k$
and
$\beta=\beta_1\dots \beta_k$ be two distinct occurrences of $k (k-1)
\dots 1$ in
$\pi$.  We say
$\alpha$ is larger that $\beta$ if there exists $i$, $1 \leq i \leq k$,
such that
$\pi^{-1}(\alpha_j) = \pi^{-1}(\beta_j)$ for
all $j>i$ and $\pi^{-1}(\alpha_i) >
\pi^{-1}(\beta_i)$.


We can now describe $\gamma^{-1}: S_n(132) \rightarrow S_n(321)$.
Let $\pi_1 \pi_2 \dots \pi_n=\pi \in S_n(132)$ and let
$zyx=\pi_{p_1}\pi_{p_2}\pi_{p_3}$ be the largest $321$ occurrence
in $\pi$.
If no such occurrence exists, $\gamma^{-1}(\pi)=\pi$.  Otherwise, let
$\mathcal{N}$ be the operation that creates the permutation
$\mathcal{N}\pi$ where
$\mathcal{N}\pi_i=\pi_i$ if $i \not \in \{p_1,p_2,p_3\}$
and $\mathcal{N}\pi_{p_1}=x$, $\mathcal{N}\pi_{p_2}=z$,
and $\mathcal{N}\pi_{p_3}=y$.  Now let $zyx$ be the largest
$321$ occurrence in $\mathcal{N}\pi$ and apply $\mathcal{N}$
again. Repeat until the resulting permutation is $321$-avoiding.

It is easy to check that $\gamma^{-1} \gamma(\pi) = \pi$
for any $\pi \in S_n(321)$.



We  can extend $\gamma$ to 
a bijection ${\Gamma_k} : S_n(k (k-1) \dots 1)
\rightarrow S_n(1k(k-1)\cdots 2)$ for any
$k \geq 2$.
Let $\pi_1 \pi_2 \dots \pi_n=\pi
\in  S_n(k(k-1)\dots 1)$
and let
$\alpha=\pi_{p_1}\pi_{p_2}\dots \pi_{p_k}$ be the smallest 
$1k (k-1) \dots 2$
occurrence in $\pi$.
If no such occurrence exists, ${\Gamma_k}(\pi)=\pi$.  Otherwise,
let
$\mathcal{P}$ be the operation that creates the permutation
$\mathcal{P}\pi$ where
$\mathcal{P}\pi_i=\pi_i$ if $i \not \in \{p_1,p_2,\dots,p_k\}$
and $\mathcal{P}\pi_{p_i}=\pi_{p_{i+1 \, (\mathrm{mod} \, k)}}$ for
$i=1,2,\dots,k$. 

  Now let $\alpha$ be the smallest
$1k (k-1) \dots 2$ occurrence in $\mathcal{P}\pi$ and apply
$\mathcal{P}$ again. Repeat until the resulting permutation avoids
the pattern
$1k (k-1) \dots 2$.

To prove that ${\Gamma_k}$ is well-defined we show that,
with respect to the indices of elements, the
smallest $1 k \dots 2$ occurrence in $\mathcal{P}\pi$ is
larger than the smallest $1 k \dots 2$ occurrence in $\pi$.
Hence, $\mathcal{P}^j \tau$ has no $1 k \dots 2$ occurrence
for some finite $j$.

Let $\tau$ be our permutation and let $\gamma_1 \dots \gamma_k$
be the smallest $1 k \dots 2$ occurrence in $\tau$.
Assume, for a contradiction, that $\mathcal{P}\tau$ has a
$1 k \dots 2$ occurrence $\sigma=\sigma_1 \dots \sigma_k$ with
$\sigma_1^{-1} <\gamma_1^{-1}$.  Since $\tau$ has no such occurrence, we
must have $$\{\sigma_1,\dots,\sigma_k \} \cap
\{\gamma_1,\dots,\gamma_k\} \neq \emptyset.$$

Let $\gamma_j$ be the minimal element in the above intersection
such that there exists $\ell \geq 1$, $\ell$ maximal, where we have
(in $\mathcal{P} \tau$)
\begin{equation}
\sigma = \sigma_1 \dots \sigma_{i-1} \gamma_j
\sigma_{i+1} \dots \sigma_{i+\ell} \sigma_{i+\ell+1} \dots \sigma_k
\end{equation}
with
\begin{equation}
\{\sigma_{i+1},\dots,\sigma_{i+\ell}\} \cap \{ \gamma_1,\dots,\gamma_k\}
= \emptyset
\end{equation}
(so that 
$
\{\sigma_{i+\ell+1},\dots,\sigma_k\} \subseteq \{\gamma_1,\dots,\gamma_k\}
$
where $\{\sigma_{i+\ell+1},\dots,\sigma_k\}$ is possibly
empty).
We may further require that there do not exist
$\gamma_{m+1},\dots,\gamma_{m+\ell}$ such that
\begin{equation}
\sigma_1 \dots \sigma_{i-1} \gamma_j
\gamma_{m+1} \dots \gamma_{m+\ell} \sigma_{i+\ell+1} \dots \sigma_k
\end{equation}
is also a $1 k \dots 2$ occurrence.

Since this is quite a bit to require of $\gamma_j$, we
must prove its existence.  Assume, for a contradiction,
that no such $\gamma_j$ exists.  Then, for all $\gamma_i$,
$1 \leq i \leq k$, we have no such $\ell$ satisfying
(1) and  (2), or there exist $\gamma_{m+1},\dots,\gamma_{m+\ell}$
such that (3) is also a $1 k \dots 2$ occurrence.
In either case, there exists a $1 k \dots 2$ occurrence of
the form $\sigma_1 \dots \sigma_x
\gamma_y \dots \gamma_z$ in $\mathcal{P} \tau$
with $\{\sigma_1,\dots,\sigma_x\} 
\cap \{\gamma_1,\dots,\gamma_k\} = \emptyset$ and hence,
$\sigma_1 \dots \sigma_x
\gamma_y \dots \gamma_z$ is also in $\tau$, a contradiction
since such an occurrence is smaller than $\gamma_1 \dots \gamma_k$.


We rewrite (1) as
\begin{equation}
\sigma_1 \dots \sigma_{i-1} \gamma_j
\sigma_{i+1} \dots \sigma_{i+\ell} \gamma_{j+m+1} \dots \sigma_k.
\end{equation}

From (4) we must have, by 
assumption (3),
$
|\{\gamma_{j+1},\dots,\gamma_{j+m}\}| < |\{\sigma_{i+1},\dots,\sigma_{i+
\ell}
\}|.
$
But then
$$
\gamma_1 \dots \gamma_{j-1} \sigma_{i+1} \dots \sigma_{i+\ell}
\gamma_{j+m+1} \dots \gamma_k
$$
contains a smaller $1k \dots 2$ occurrence in $\tau$ than
$\gamma_1 \dots \gamma_k$, a contradiction.
Thus, $\mathcal{P}\tau$ contains no $1 k \dots 2$ occurrence
$\sigma_1 \dots \sigma_k$ with $\sigma_1^{-1} < \gamma_2^{-1}$
(order in $\mathcal{P}\tau$).

To finish proving that
$\Gamma_k$ is well-defined, assume, for a contradiction, that
$\gamma_2 \beta_1 \dots \beta_{k-1}$ in $\mathcal{P}\tau$ is a smaller
$1k \dots 2$ occurrence (with respect to the indices) than 
$\gamma_1 \dots \gamma_k$ is in $\tau$.
Then we must have
$\beta_1^{-1}<\gamma_3^{-1}$ (order in $\mathcal{P}\tau$).   However,
this implies that $\gamma_1 \beta_1 \gamma_3
\dots \gamma_k$ is a smaller $1k \dots 2$
occurrence in $\tau$ than $\gamma_1 \dots \gamma_k$,
a contradiction.  This concludes the proof that
$\Gamma_k$ is well-defined.



To show that $\Gamma_k$ is a bijection, note
that
${\Gamma_k}^{-1}$ is found by  using the
operation $\mathcal{Q}$  where
$\mathcal{Q}\pi_i=\pi_i$ if $i \not \in \{p_1,p_2,\dots,p_k\}$
and $\mathcal{Q}\pi_{p_i}=\pi_{p_{i-1 \, (\mathrm{mod} \, k)}}$ for
$i=1,2,\dots,k$. 

Using ${\Gamma_k}$,
along with the standard bijections, we immediately have the following
theorem.

{\bf Theorem.}  Let $k \geq 2$.  The following patterns
are Wilf equivalent.

$$
\begin{array}{ll}
A. \,\,\,\,  k (k-1) \cdots 1&
B. \,\,\,\,  1k(k-1) \cdots 2\\
C. \,\,\,\, 12 \cdots k
&
D.\,\,\,\,  2 3 \cdots k 1 \\
E. \,\,\,\, k 1 2 \cdots (k-1)&
F.\,\,\,\,  (k-1) (k-2) \cdots 1 k
\\
\end{array}
$$

{\it Remark.}  ${\Gamma_4}$  proves
the Wilf equivalence of $1234$ and $4123$,
a result of Stankova [28].



\section*{\normalsize 4. Enumeration Results}
In this section we give some enumeration results
along with their relevant references.  The first
table gives the number of permutations that avoid
a single pattern.

\begin{center}
\centerline{{\bf Avoid 1}}
\renewcommand{\arraystretch}{.5}
\begin{tabular}{|l|l|l|} \hline
\multicolumn{1}{|c|}{$\!\!$Class $\cal{W} \!\!$}&
\multicolumn{1}{c|}{$s_n(T), T \in \cal{W}$}&
\multicolumn{1}{|c|}{References}\\ \hline
 &&\\
$\overline{(123)}$&$C_n=\frac{1}{n+1} {2n \choose n}$ 
&[14], [12]\\
   &&\\   
   
$\overline{(1234)}$&$2\sum_{k=0}^n {2k \choose k} {n \choose k}^2
\frac{3k^2-(2k+1)(n-1)}{(k+1)^2(k+2)(n-k+1)}$ 
&[10]\\
   &&\\      
$\overline{(1342)}$&$ \frac{(-1)^{n-1}(7n^2-3n-2)}{2}
+3 \sum_{k=2}^n (-1)^{n-k}2^{k}{2k-4 \choose k-2} \frac{(n-k+2)(n-k+1)}
{k(k+1)}$
&[1]\\
   &&\\ 
$\overline{(1324)}$&$?$ 
&open\\
&&\\
\hline
\end{tabular}


\end{center}
\footnotesize
\baselineskip=10pt
$\overline{(123)} = S_3$;
$\overline{(1234)} = \{1234,1243,2134,2143,3412,3421,4312,4321\}$;
$\overline{(1342)} =\{1342,1423,2341,2413,$ \\
$2431,3124,3142,3241,4132,4213\}
$;
$\overline{(1324)} = \{1324, 4231\}$.

\normalsize



We continue with a table giving the number of permutations that
contain a given pattern exactly once.
\begin{center}
\centerline{{\bf Contain 1}}

\begin{tabular}{|l|l|l|} \hline
\multicolumn{1}{|c|}{Class $\cal{W}$}   &
\multicolumn{1}{c|}{$s_n(T), T \in \cal{W}$}&
\multicolumn{1}{|c|}{Reference}\\ \hline
 &&\\
$\overline{(\emptyset;123)}$&$\frac{3}{n} {2n \choose n-3}$ for $n \geq
3$&[20]\\
     &&\\    
$\overline{(\emptyset;132)}$&${2n-3 \choose n-3}$ for $n \geq 3$&[2]\\
&&\\
\hline
\end{tabular}
\end{center}


\footnotesize
$\overline{(\emptyset;123)} =\{(\emptyset;123),(\emptyset;321)\}$;
$\overline{(\emptyset;132)} =
\{(\emptyset;132),(\emptyset;213),(\emptyset;231),(\emptyset;312)\}$.


\normalsize
\vskip 10pt
The penultimate table gives the number of permutations that avoid
a given pattern and contain a different given pattern
exactly once.  
The last table gives the number of
permutations that contain each of two given (not necessarily
distinct) patterns exactly once.
\begin{center}

\centerline{{\bf Avoid 1, Contain 1}}

\begin{tabular}{|l|l|l|} \hline
\multicolumn{1}{|c|}{Class $\cal{W}$}   &
\multicolumn{1}{c|}{$s_n(T), T \in \cal{W}$}&
\multicolumn{1}{|c|}{Reference}\\ \hline

&&\\
$\overline{(123;321)}$&0  for $ n \geq 6$&-----\\
    &&\\    
$\overline{(123;132)}$&$(n-2)2^{n-3}$ for $n \geq 3$&[20]\\
     &&\\    
$\overline{(123;231)}$&$2n-5$ for $n \geq 3$&[17]\\
     &&\\ 
$\overline{(132;213)}$&$n2^{n-5}$ for $n \geq 4$&[16]\\
     &&\\    
$\overline{(132;231)}$&$2^{n-3}$ for $n \geq 3$&[16]\\
&&\\
\hline

\end{tabular}



\end{center}
\footnotesize
\baselineskip=10pt
$\overline{(123;321)}= \{(123;321), (321;123)  \}$;
$\overline{(123;132)}=\{(123;132), (123;213), (132;123),
(213;123), (231;321),$ \\$ (312;321), (321;231),(321;312)\}$;
$\overline{(123;231)}=\{(123;231),(123;312),(132;321),(213;321),(231;123),$
\\
$(312;123),(321;132),(321;213)\}$;
$\overline{(132;213)}=\{(132;213), (213;132), (231;312),
(312;231)  \}$;
\\
$\overline{(132;231)}=\{(132;231),(132;312), (213;231),(213;312),
(231;132), (231;213), (312;132),(312;213)\}$.


\normalsize
\baselineskip=15pt

\begin{center}

\centerline{{\bf Contain 2}}

\begin{tabular}{|l|l|l|} \hline
\multicolumn{1}{|c|}{Class $\cal{W}$}   &
\multicolumn{1}{c|}{$s_n(T), T \in \cal{W}$}&
\multicolumn{1}{|c|}{Reference}\\ \hline
 &&\\   
$\overline{(\emptyset;\{123,321\})}$&$0$ for $n \geq 6$&-----
\\
    &&\\   
$\overline{(\emptyset;\{123,231\})}$&$2n-5$ for $n \geq 5$&[23]\\
    &&\\    
$\overline{(\emptyset;\{123,132\})}$&${{n-3} \choose 2}2^{n-4}$ for
$n
\geq 5$&[22] \\
     &&\\    
$\overline{(\emptyset;\{132,213\})}$&$(n^2+21n-28)2^{n-9}$ for $n
\geq
7$&[23]\\
    &&\\    
$\overline{(\emptyset;\{132,231\})}$&$2^{n-3}$ for $n \geq 4$
&[23]\\
     &&\\   
$\overline{(\emptyset;\{123,123\})}$&$\frac{59n^2+117n+100}
{2n(2n-1)(n+5)}
{2n \choose n-4}$
for
$n
\geq 4$&[9]\\  
    &&\\    
$\overline{(\emptyset;\{132,132\})}$&$\frac{(n-2)^2(n+21)-4}{2n(n-1)}
{{2n-6} \choose {n-4}}$ for $n \geq 4$
&[15]\\
  
&&\\
\hline
\end{tabular}

\end{center}
\footnotesize
\baselineskip=10pt
$\overline{(\emptyset;\{123,\!321\})}=\{(\emptyset;\{123,321\}),
(\emptyset;\{321,123\})  \}$;
$\overline{(\emptyset;\{123,231\})}=\{(\emptyset;\{123,231\}),
(\emptyset;\{123,312\}),$ \\
$(\emptyset;\{132,321\}),(\emptyset;\{213,321\})\}$;
$\overline{(\emptyset;\{123,132\})}=\{(\emptyset;\{123,132\}),
(\emptyset;\{123,213\}),
(\emptyset;\{231,321\}),$ \\ $(\emptyset;\{312,321\})\}$;
$\overline{(\emptyset;\{132,213\})}=\{(\emptyset;\{132,213\}),
(\emptyset;\{231,312\})\}$; 
$\overline{(\emptyset;\{132,231\})}=\{(\emptyset;\{132,231\}),$ \\
$(\emptyset;\{132,312\}),
(\emptyset;\{213,231\}),(\emptyset;\{213,312\})\}$; 
$\overline{(\emptyset;\{123,123\})} = \{(\emptyset;\{123,123\}),
(\emptyset;\{321,321\})\}$;\\
$\overline{(\emptyset;\{132,132\})} = \{
{(\emptyset;\{132,132\})},{(\emptyset;\{213,213\})},
{(\emptyset;\{231,231\})},{(\emptyset;\{312,312\})} \}.$


\normalsize
\baselineskip=15pt

\section*{\normalsize 5. An Interesting Generating Function}

An interesting generating function can be obtained
when we consider $\{s_n(132;\{(123)^r\})\}_n$.   To
this end,
let $$f(x,y;k) = \sum_{n,r} s_n(132,\{(123\dots k)^r\})x^ny^r.$$

In [25], the authors show that
$$
f(x,y;3)
={1\over\displaystyle 1-{\strut x\over\displaystyle 1-{\strut
x\over\displaystyle 1-{\strut xy\over\displaystyle 1-{\strut
xy^3\over\displaystyle 1-{\strut xy^6\over\displaystyle
\hskip 15pt\ddots}}}}}}
$$
in which the $n^{\mathrm{th}}$ numerator is $xy^{{n-1\choose 2}}$.
This result was the apparent impetus for several papers, of which we note
a few.

Let $F_r(x;k) = [y^r]f(x,y;k),$
i.e., the coefficient of $y^r$ in $f(x,y;k)$.
Let $U_n(x)$ denote the Chebyshev polynomials
of the second kind, defined by
$$U_n(\cos(x)) = \frac{\sin((n+1)x)}{\sin(x)}.$$



{Mansour and Vainshtein [18]} show that
for any $k\ge 1$ and $1\le r\le k(k+3)/2$,


$$ 
F_r(x;k)=\frac{x^{\frac {r-1}2}U_{k-1}^{r-1}\left(\frac1{2\sqrt{x}}\right)}
{U_{k}^{r+1}\left(\frac1{2\sqrt{x}}\right)}\sum_{j=0}^{\lfloor(r-1)/k\rfloor}
{r-kj+j-1\choose j}\left(\frac{U_k\left(\frac1{2\sqrt{x}}\right)}
{x^{\frac{k-2}{2k}}U_{k-1}\left(\frac1{2\sqrt{x}}\right)}\right)^{kj}.
$$

(The case $F_0(x;k)$ had already been determined in terms
of Chebyshev polynomials by Chow and West [4].)

This result was followed closely by a result of
{Jani and Rieper [11]}, who give
a bijection between ordered trees
and $S_n(132;\{(123\dots k)^r\})$.

We then come to a quote found in [13]:

\begin{quote}{\it
Whenever you encounter generating functions which can be expressed in
terms of continued fractions or Chebyshev polynomials, then
expect that Dyck or Motzkin paths are at the heart of your problem,
and will help to solve it.}\vskip 2pt
\hfill - Krattenthaler
\end{quote}

In this paper, Krattenthaler  reproves and extends all 
the above results as
well as proves new ones with continued fractions,
Chebyshev polynomials of the second kind, and
Dyck and Motzkin paths.


\section*{\normalsize 6. Refined Restricted Permutations}

\begin{quote}{\it 
Combinatorics without algebra ... is like sex
without love.\vskip 0pt} \hfill - Anthony Joseph 
\end{quote}


We now move on to some very recent results
on restricted permutations.  In [24], the study
of restricted permutations refined by the number
of fixed points was initiated (to the best
of my knowledge)
in an attempt  to combine the ``purely combinatorial" with the algebraic
properties of permutations.

We first look at restricted permutations
classified by cycle structure.

\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|}
{Cycle  structure}&$S_6(123)$&$S_6(132)$&$S_6(213)$
&$S_6(321)$
&$S_6(231)$&$S_6(312)$\\ \hline
$1^6$&0&   1 &1&1&1&1\\
$1^42^1$&0&  5 &5&5&9&9\\
$1^33^1$&0&  8 &8&8&12&12\\
$1^22^2$&10&   9&9&9&18&18\\
$1^24^1$& 8& 12&12&12&17&17\\
$1^12^13^1$&24&  20 &20&20&24&24\\
$1^15^1$&24&  20&20&20&20&20\\
$2^3$& 10&  5 &5&5&4&4\\
$2^14^1$&26&  20 &20&18&12&12\\
$3^2$&6&  8 &8&10&3&3\\
$6^1$& 24& 24 &24&24&12&12\\ \hline
{Sum}&132&132&132&132
&132&132\\
\end{tabular}

\vskip -218pt
\hskip -20pt
\setlength{\unitlength}{1.5mm}
\begin{picture}(0,45.7)(44,0)
\linethickness{.5mm}
\put(33,10){{\line(1,0){35}}}
\put(33,4){{\line(1,0){35}}}
\put(33,4){{\line(0,1){6}}}
\put(68,4){{\line(0,1){6}}}
\end{picture}
\end{center}



\vskip 20pt

In this table, we see that
$S_6(132)   $  and $  S_6(213)$
have the same cycle structure
breakdown, and that the same holds
true for
$S_6(231) $ and $ S_6(312)$.
This is fairly easy to explain.  

{\bf Theorem} (Robertson, Saracino, Zeilberger [24])
 Let $\gamma \in S_n$ be
given by
$\gamma_i =n+1-i$ for $1 \leq i \leq n$.  For $\pi \in S_n$, let
$\pi^\star = \gamma
\pi
\gamma^{-1}$. The number of occurrences
of the pattern $213$ (resp. $312$) in $\pi$ equals
the number of occurrences of the pattern $132$ (resp. $231$)
in $\pi^\star$.


This is just the reversal bijection followed by the complement
bijection.  However, written in the above form
as a conjugation, we see that the
cycle structure is preserved.

Digging a little deeper into the cycle structure
breakdown, we
notice that $S_6(321)$ has a breakdown very
close to that of $S_6(132)$.  In fact, the only place
where a difference occurs in the table is boxed in.
And,
if we
look at the number of fixed points,
we have the
same breakdown according to the number of
fixed points.

 
Let $S_n^k(S;T)$  be the elements of $S_n(S;T)$
with exactly $k$ fixed points
and let $s_n^k(T)=|S_n^k(T)|$.


Robertson, Saracino, and Zeilberger [24] prove that
for all $n$ and all $k$, $0 \leq k \leq n$,

\begin{itemize}
\item $s_n^k(132)=s_n^k(231)=s_n^k(321)$
\item $s_n^k(231) = s_n^k(312)$
\item $s_n^k(123)$
\end{itemize}
are the three classes,
where we have

\footnotesize 
\setlength{\arraycolsep}{1.5pt}
\renewcommand{\arraystretch}{.85}

$$
\begin{array}{ccccc}
\begin{array}{lcccccccccccc} 
{}_n \diagdown^k \!\! &\vline&^0&^1&^2&^3&^4&^5&^6&^7&^8 \\
\hline 
_0&\vline&1\\
_1&\vline&0&1\\
_2&\vline&1&0&1\\
_3&\vline&2&2&0&1\\
_4&\vline&6&4&3&0&1\\
_5&\vline&18&13&6&4&0&1\\
_6&\vline&57&40&21&8&5&0&1\\
_7&\vline&186&130&66&30&10&6&0&1\\
_8&\vline&622&432&220&96&40&12&7&0&1\\ 
\end{array}
& \hskip 10pt &
\begin{array}{lcccccccccccc} 
{}_n \diagdown^k \!\! &\vline&^0&^1&^2&^3&^4&^5&^6&^7&^8 \\
\hline 
_0&\vline&1\\
_1&\vline&0&1\\
_2&\vline&1&0&1\\
_3&\vline&1&3&0&1\\
_4&\vline&4&4&5&0&1\\
_5&\vline&10&16&8&7&0&1\\
_6&\vline&31&44&35&12&9&0&1\\
_7&\vline&94&146&102&59&16&11&0&1\\
_8&\vline&303&464&362&180&87&20&13&0&1\\ 
\end{array} 
& \hskip 10pt &
\begin{array}{lcccccccccccc} 
{}_n \diagdown^k \!\! &\vline&^0&^1&^2&^3&^4&^5&^6&^7&^8 \\
\hline 
_0&\vline&1\\
_1&\vline&0&1\\
_2&\vline&1&0&1\\
_3&\vline&2&3&0&0\\
_4&\vline&7&4&3&0&0\\
_5&\vline&20&20&2&0&0&0\\
_6&\vline&66&48&18&0&0&0&0\\
_7&\vline&218&183&28&0&0&0&0&0\\
_8&\vline&725&552&153&0&0&0&0&0&0\\ 
\end{array}\\ \\
\mathbf{s_n^k(132)=s_n^k(213)=s_n^k(321)}
& &
\mathbf{s_n^k(231)=s_n^k(312)}
& &
\mathbf{s_n^k(123)}
\end{array}
$$

\normalsize

It is quite amazing that $s_n^k(132) = s_n^k(321)$.
Robertson, Saracino, and Zeilberger [24] give a
fairly technical proof.
This was followed by a proof due to 
Elizalde [7], a student of Stanley, who refines 
this result further by
 showing that we have
``number of excedances" in addition
to the number of fixed points.
Pak and Elizalde [21] follow this up by giving a
nice bijective proof.

An interesting sequence appears when we consider $132$-avoiding
derangements.  We see that
$$\{s_n^0(132)\}_{n \geq 0}=1,0,1,2,6,18,57,186,622,\dots.$$
This is
Fine's sequence,
initially given in [8], which stems from
similarity relations.
(For a good survey of Fine's sequence, see [6].)
Fine's sequence
$\{F_n\}_{n \geq 0}$ is characterized by
\begin{equation}
2F_n+F_{n-1}=C_n,
\end{equation}
which may be thought of as the defining equation
for the sequence.

We now take a very brief sidestep to look at similarity
relations.

{\bf Definition.}
A similarity relation, $R$, is a binary relation
on an ordered set
which is reflexive, symmetric, but not necessarily 
transitive, with the condition that if $iRk$
and $i<j<k$ then $iRj$ and $jRk$.  
$R$ is said to have $k$
isolated points if
$k$ is the number of $i \in \{1,2,\dots,n\}$ such that
there does not exist $j \neq i$ with $iRj$.  If $k=0$,
we say that the similarity relation is nonsingular.
We denote by $SR_n(k)$ the set of similarity
relations on $\{1,2,\dots,n\}$ with $k$ isolated points.


In [24], the authors show that, 
 $s_n^k(321)=|SR_n(k)|$, a somewhat
unexpected connection between two at-first-sight
unrelated structures.

Stepping back to refined restricted permutations,
in [24] we find that, for $\alpha \in \{132,213,321\}$, 
$0 \leq k \leq n$:
$$
s_n^k(\alpha) = \sum_{j=0}^{n-k} (-1)^j
\left(\frac{j+k+1}{n+1}\right)
{2n-k-j \choose n} {j+k \choose k}.
$$

In particular we obtain a formula for the Fine numbers:
$$F_n  = \sum_{j=0}^{n} (-1)^j
\left(\frac{j+1}{n+1}\right)
{2n-j \choose n}.
$$
 
\vskip 30pt
\begin{quote}{\it
The worst thing you can do to a problem is solve it completely.}
\vskip 2pt
\hfill - Dan Kleitman
\end{quote}

As such, there are no nontrivial enumerations of
$s_n^k(\alpha)$ for $\alpha \in \{123,231,312\}$
in [24]. 


Another unanswered question, begging for a solution, follows.
For $\beta \in \{132,213,321\}$ we have from (5)
$$
2s_n^0(\beta) + s_{n-1}^0(\beta) = s_n(\delta)
$$
for any $\delta \in S_3$.
Can this be explained bijectively by letting $\delta = \beta$?

The next set of results on refined restricted permutations
comes from [19]:
following the steps of Simion and Schmidt,
Mansour and Robertson [19] provide
enumerative results for
$S_n^k(S)$ for all 
 $S \subseteq S_3$, $|S| \geq 2$.

\subsection*{\normalsize 6.1 Refined Restricted Involutions}

From the cycle structure breakdown table we notice
that if we restrict our attention to
involutions it appears that we may have some
more unexpected structure.

 Define $i_n^k(S;T)$ to
be the number of elements of $S_n^k(S;T)$ that are
involutions. 


Deutsch, Robertson, and Saracino [5] prove that
\begin{itemize}
\item $i_n^k(132)=i_n^k(231)=i_n^k(321)$
\item $i_n^k(231) = i_n^k(312)$
\item $i_n^k(123)$
\end{itemize} 
are the three classes.  The proofs use the RSK
correspondence as well as provide new bijections
with Dyck paths.

One particularly nice formula follows. 
For $\alpha \in \{132,213,321\}$,
$0 \leq k \leq n$,

$$
i_n^k(\alpha) = \left\{
\begin{array}{ll}
 \frac{k+1}{n+1} {n+1 \choose \frac{n-k}{2}}&\quad \mathit{for
\,\,} n+k \,\, \mathit{even}\\ 
 0&\quad \mathit{for \,\,}
n+k \,\, \mathit{odd}.
\end{array}
\right.
$$


Catalan strikes again!
$$i_{2n}^0(132)=C_n = i_{2n-1}^1(132).$$

Hence,
 the number of $132$-avoiding permutations on
$n$ letters is the Catalan number;
the number of $132$-avoiding derangements
on $n$ letters is the Fine number; and
the number
of $132$-avoiding derangement involutions on
$2n$ letters is the Catalan number.

Having gone from Catalan to Fine and back, we stop.


\section*{\normalsize References}

\footnotesize


[1] M. B\'ona, Exact Enumeration of $1342$-avoiding
Permutations; A Close Link with Labeled Trees and
Planar Maps, {\it J. Comb.
Theory, Series A} {\bf 175} (1997), 55-67.

[2] M. B\'ona, Permutations with One or Two
$132$-sequences, {\it Discrete Math.} {\bf 181} (1998), 267-274.

[3] E. Catalan, Note sur une \'Equation aux Differences Finies,
{\it J. Math. Pures et Appliqu\'es}
{\bf 3} (1838), 508-516.

[4] T. Chow and J. West, Forbidden Subsequences and Chebyshev
Polynomials, {\it Discrete Math.} {\bf 204} (1999), 119-128.


[5] E. Deutsch, A. Robertson, and D. Saracino, 
Refined Restricted Involutions, 
ar$\chi$iv: {\tt math.CO/0212267}.

[6] E. Deutsch and L. Shapiro, A Survey of the Fine
Numbers, {\it Discrete Math.} {\bf 241} (2001),
241-265.

[7] S. Elizalde,  Fixed Points and Excedances in Restricted Permutations,
ar$\chi$iv: {\tt math.CO/0212221}.



[8] T. Fine, Extrapolation when Very Little is Known,
{\it Information and Control} {\bf 16} (1970),
331-359.

[9] M. Fulmek, Enumeration of Permutations Containing a Prescribed Number
of Occurrences of a Pattern of Length Three,
{\it Adv. Appl. Math.} {\bf 30} (2003), 607-632.

[10] I. Gessel, Symmetric Functions and P-recursiveness,
{\it J. Comb. Theory, Series A} {\bf 53}
(1990), 257-285.

[11] M. Jani and R. Rieper, Continued Fractions and Catalan Problems,
{\it Electron. J.  Comb.} {\bf 7} (2000), R45.


[12] D. Knuth, \underline{The Art of Computer Programming}, vol. 3,
Addison-Wesley, Reading, MA, 1973.

[13] C. Krattenthaler, Restricted Permutations, Continued Fractions,
and Chebyshev Polynomials, {\it Adv.  Appl. Math.} {\bf 27} (2001), 
510-530.



[14] P. MacMahon, 
\underline{Combinatory Analysis},
Chelsea Publishing Co., New York, 1960.

[15] T. Mansour and A. Vainshtein, Counting Occurrences of 132 in a
Permutation, {\it Adv. Appl. Math.} {\bf 28}
(2002), 185-195.


[16] T. Mansour and A. Vainshtein, Restricted $132$-avoiding
Permutations, {\it Adv. Appl. Math.} {\bf 26} (2001), 258-269. 

[17]  T. Mansour and A. Vainshtein, Restricted Permutations and
Chebyshev Polynomials, {\it S\'em. Lothar. Combin.} {\bf 47} (2001/02),
Article~B47c.



[18] T. Mansour and A. Vainshtein, Restricted Permutations, Continued
Fractions, and Chebyshev Polynomials, {\it Electron.
J. Comb.} {\bf 7} (2000), R17.


[19] T. Mansour and A. Robertson,
Refined Restricted Permutations
 Avoiding Subsets of Patterns of Length Three,
ar$\chi$iv: {\tt math.CO/0204005}.



[20] J. Noonan, The Number of Permutations Containing Exactly
One Increasing Subsequence of Length Three, {\it Discrete Math.}
{\bf 152} (1996), 307-313.

[21] I. Pak and S. Elizalde,  Bijections for Refined Restricted
Permutations, ar$\chi$iv: {\tt math.CO/0212328}.


[22] A. Robertson, Permutations Containing and Avoiding
$123$ and $132$ Patterns, {\it Discrete Math.
and Theoretical Comp. Sci.} {\bf 4} (1999),
151-154.

[23] A. Robertson, Permutations Restricted by Two Distinct
 Patterns of Length Three, {\it Adv. Appl. Math.}
{\bf 27} (2001), 548-561.


[24] A. Robertson, D. Saracino, and D. Zeilberger,
Refined Restricted Permutations, 
ar$\chi$iv: {\tt math.CO/0203033}.


[25] A. Robertson, H. Wilf, and D. Zeilberger,
Permutation Patterns and Continued Fractions,
{\it Electron. J.  Comb.}
{\bf 6} (1999), R38.



[26] D. Rotem, On a Correspondence Between Binary Trees
and a Certain Type of Permutation,
{\it Information Processing Letters} {\bf 4} (1975),
58-61.



[27] R. Simion and F. Schmidt, Restricted Permutations,
{\it Europ. J. Comb.} {\bf 6} (1985), 383-406.

[28] Z. Stankova,
Classification of Forbidden Subsequences of Length $4$,
{\it Europ. J. Comb.} {\bf 17} (1996), 501-517.


[29] R. Stanley, \underline{Enumerative Combinatorics}, vol. 2,
Cambridge University Press, 1999.


[30] J. West, Generating Trees and the Catalan and Schr\"oder Numbers,
{\it Discrete Math.} {\bf 146} (1995), 247-262.



\end{document}
