\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}

\newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\begin{center}
\vskip 1cm{\LARGE\bf 
Enumerating Permutations Avoiding More \\
\vskip .1in
Than Three Babson-Steingr\'{\i}msson Patterns
}
\vskip 1cm
\large
Antonio Bernini and Elisa Pergola\\
Dipartimento di Sistemi e Informatica \\
Universit\`a di Firenze \\
viale G. B. Morgagni 65 \\
50134 Firenze\\
Italy \\
\href{mailto:bernini@dsi.unifi.it}{\tt bernini@dsi.unifi.it} \\
\href{mailto:elisa@dsi.unifi.it}{\tt elisa@dsi.unifi.it} \\
\end{center}

\vskip .2 in

\begin{abstract}
Claesson and Mansour recently proposed some conjectures about
the enumeration of the permutations avoiding more than three
Babson-Steingr\'{\i}msson patterns (generalized patterns of type
$(1,2)$ or $(2,1)$). The avoidance of one, two or three patterns
has already been considered. Here, the cases of four and five
forbidden patterns are solved and the exact enumeration of the
permutations avoiding them is given, confirming the conjectures of
Claesson and Mansour. The approach we use can be easily extended
to the cases of more than five forbidden patterns.
\end{abstract}

\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{conjecture}[theorem]{Conjecture}




\newtheorem{prop}{Proposition}[section]
%\newtheorem{proof}{Proof:}
\newtheorem{teo}{Theorem}[section]
\newtheorem{rem}{Remark}[section]
\newtheorem{defi}{Definition}%[section]
%\newcommand{\qed}{\begin{flushright}$\square$\end{flushright}}

\section{Introduction}

The results of the present paper concern the exact enumeration of the permutations, according to
their length, avoiding any set of four or five generalized patterns of type $(1,2)$ or $(2,1)$
\cite{BS}. The cases of the permutations avoiding one, two or three generalized patterns (of the
same types) were solved by Claesson \cite{C}, Claesson and Mansour \cite{CM}, and Bernini, Ferrari
and Pinzani \cite{BFP}, respectively. In particular, Claesson and Mansour \cite{CM} conjectured
the plausible sequences enumerating the permutations of $S_n(P)$, for any set $P$ of three or more
patterns.

Substantially, Bernini, Ferrari and Pinzani \cite{BFP} conducted the proofs by finding the ECO
construction \cite{BDPP} for the permutations avoiding three generalized patterns of type $(1,2)$
or $(2,1)$, encoding it with a succession rule and, finally, checking that this one leads to the
enumerating sequence conjectured by Claesson and Mansour \cite{CM}. This approach could surely be
used also for the investigation of the avoidance of four or five generalized patterns of type
$(1,2)$ or $(2,1)$ and, maybe, it would allow to find some nice and interesting results: we think
that, for instance, in some case new succession rules for known sequences would appear. However,
this approach has one obstacle: the large number of cases to consider in order to exhaust all the
conjectures. The line we are going to follow (see below) is simple and allows us to reduce the
number of cases to be considered. Most of the results are summarized in several tables which are
presented in Section \ref{tables}. Really, the paper could appear an easy exercise, but we believe
that it is a valuable contribute to the classification of permutations avoiding generalized
patterns, started with Claesson, Mansour, Elizalde and Noy \cite{EN}, Kitaev \cite{K}. Moreover,
it can be seen as the continuation of the work started by Bernini, Ferrari and Pinzani \cite{BFP}
for the fulfillment of the proofs of the conjectures presented by Claesson and Mansour \cite{CM}.

\subsection{Preliminaries}

A (classical) \emph{pattern} is a permutation $\sigma\in S_k$ and a permutation $\pi\in S_n$
\emph{avoids} $\sigma$ if there is no any subsequence $\pi_{i_1}\pi_{i_2}\ldots\pi_{i_k}$ with
$1\leq i_1<i_2<\ldots<i_k\leq n$ which is order-isomorphic to $\sigma$. In other words, $\pi$ must
contain no subsequences having the entries in the same relative order of the entries of $\sigma$.
\emph{Generalized patterns} were introduced by Babson and Steingr\'imsson for the study of the
mahonian statistics on permutations \cite{BS}. They are constructed by inserting one or more
dashes among the elements of a classical pattern (two or more consecutive dashes are not allowed).
For instance, $216-4-53$ is a generalized pattern of length $6$. The \emph{type}
$(t_1,t_2,\ldots,t_{h+1})$ of a generalized pattern containing $h$ dashes records the number of
elements between two dashes (we suppose a dash at the beginning and at the end of the generalized
pattern, but we omit it): the type of $216-4-53$ is $(3,1,2)$. A permutation $\pi$ \emph{contains}
a generalized pattern $\tau$ if $\pi$ contains $\tau$ in the classical sense and if any pair of
elements of $\pi$ corresponding to two adjacent elements of $\tau$ (not separated by a dash) are
adjacent in $\pi$, too. For instance, $\pi=153426$ contains $32-14$ in the entries
$\pi_2\pi_3\pi_5\pi_6=5326$ or the pattern $3-214$ in the entries $\pi_2\pi_4\pi_5\pi_6=5426$. A
permutation $\pi$ \emph{avoids} a generalized pattern $\tau$ if it does not contain $\tau$. If $P$
is a set of generalized patterns, we denote $S_n(P)$ the permutations of length $n$ of $S$
(symmetric group) avoiding the patterns of $P$.

In the paper, we are interested in the generalized patterns of length three, which are of type
$(1,2)$ or $(2,1)$. They are those ones specified in the set
$$
\begin{array}{ll}
\mathcal M =& \{1-23,12-3,1-32,13-2,3-12,31-2,2-13,21-3,\\
&\mbox{  } \mbox{  } 2-31,23-1,3-21,32-1\}.\\
\end{array}
$$
In the sequel, sometimes we can refer to a \emph{generalized
pattern of length three} more concisely with \emph{pattern}.


\bigskip\noindent
If $\pi\in S$, we define its \emph{reverse} and its \emph{complement} to be the permutations
$\pi^r$ and $\pi^c$, respectively, such that $\pi^r_i=\pi_{n+1-i}$ and $\pi_i^c=n+1-\pi_i$. We
generalize this definition to a generalized pattern $\tau$ obtaining its reverse $\tau^r$ by
reading $\tau$ from right to left (regarding the dashes as particular entries) and its complement
$\tau^c$ by considering the complement of $\tau$ regardless of the dashes which are left unchanged
(e.g., if $\tau=216-4-53$, then $\tau^r=35-4-612$ and $\tau^c=561-3-24$). It is easy to check
$\tau^{rc}=\tau^{cr}$. If $P\subseteq\mathcal M$, the set $\{P,P^r,P^c,P^{rc}\}$ is called the
\emph{symmetry class} of $P$ ($P^r,P^c\ \mbox{and}\ P^{rc}$ contain the reverses, the complements
and the reverse-complements of the patterns specified in $P$, respectively). We have that
$|S_n(P)|$=$|S_n(P^r)|$=$|S_n(P^c)|$=$|S_n(P^{rc})|$ \cite{SS}, therefore we can choose one of the
four possible sets as the \emph{representative} of a symmetry class, as far as the enumeration of
$S(R),\ R\in\{P,P^r,P^c,P^{rc}\}$, is concerned.


\subsection{The strategy}\label{strategy}
Looking at the table of the conjectures by Claesson and Mansour \cite{CM}, it is possible to note
that most of the sequences enumerating the permutations avoiding four patterns are the same of
those ones enumerating the permutations avoiding three patterns. A similar fact happens when the
forbidden patterns are four and five. This suggests to use the results for the case of three
forbidden patterns (at our disposal) to deduce the proof of the conjectures for the case of four
forbidden patterns and, similarly, use the results for the case of four forbidden patterns to
solve the case of five forbidden patterns. Indeed, it is obvious that $S(p_1,p_2,p_3,p_4)\subseteq
S(p_{i_1},p_{i_2},p_{i_3})$ (with $i_j\in \{1,2,3,4\}$ and $p_l\in \mathcal M$). If the inverse
inclusion can be proved for some patterns, then the classes $S(p_1,p_2,p_3,p_4)$ and
$S(p_{i_1},p_{i_2},p_{i_3})$ coincide and they are enumerated by the same sequence (a similar
argument can be used for the cases of four and five forbidden patterns).

To this end, the following eight propositions are useful: each of them proves that if a
permutation avoids certain patterns, then it avoids also a further pattern. Therefore, it is
possible to apply one of them to a certain class $S(p_{i_1},p_{i_2},p_{i_3})$ to prove that
$S(p_{i_1},p_{i_2},p_{i_3})\subseteq S(p_1,p_2,p_3,p_4)$ (the generalization to the case of four
and five forbidden pattern is straightforward). The proof of the first one can be recovered in the
paper of Claesson \cite{C}, where he proves that $S(2-13)=S(213)$, and the three similar ones
follow by symmetry.
\begin{prop}\label{2}
If $\pi\in S(2-13)$, then $\pi\in S(2-13,21-3)$.
\end{prop}

\begin{prop}\label{3}
If $\pi\in S(31-2)$, then $\pi\in S(31-2,3-12)$.
\end{prop}

\begin{prop}\label{4}
If $\pi\in S(2-31)$, then $\pi\in S(2-31,23-1)$.
\end{prop}

\begin{prop}\label{5}
If $\pi\in S(13-2)$, then $\pi\in S(13-2,1-32)$.
\end{prop}

\begin{prop}\label{u1}
If $\pi\in S(1-23,2-13)$, then $\pi\in S(1-23,2-13,12-3)$.
\end{prop}

\emph{Proof.} Suppose that $\pi$ contains a $12-3$ pattern in the
entries $\pi_i$, $\pi_{i+1}$ and $\pi_k$ ($k>i+1$). Let us
consider the entry $\pi_{i+2}$. It can be neither
$\pi_{i+2}>\pi_{i+1}$ (since $\pi_i\ \pi_{i+1}\ \pi_{i+2}$ would
show a pattern $1-23$) nor $\pi_{i+2}<\pi_{i+1}$ (since
$\pi_{i+1}\ \pi_{i+2}\ \pi_{k}$ would show a pattern $21-3$ which
is forbidden thanks to Proposition \ref{2}).\qed

\noindent(The proof of the following proposition is very similar
and is omitted.)

\begin{prop}\label{u2}
If $\pi\in S(1-23,21-3)$, then $\pi\in S(1-23,21-3,12-3)$.
\end{prop}

\begin{prop}\label{u3}
If $\pi\in S(1-23,2-31)$, then $\pi\in S(1-23,2-31,12-3)$.
\end{prop}

\emph{Proof.} Suppose that a pattern $12-3$ appear in $\pi_i$, $\pi_{i+1}$ and $\pi_k$. If we
consider the entry $\pi_{k-1}$, then it is easily seen that it can be neither
$\pi_i<\pi_{k-1}<\pi_k$ (the entries $\pi_i\ \pi_{k-1}\ \pi_k$ would form a $1-23$ pattern) nor
$\pi_{k-1}<\pi_i$ (the entries $\pi_i\ \pi_{i+1}\ \pi_{k-1}$ would show a pattern $23-1$ which is
forbidden thanks to Proposition \ref{4}). Hence, $\pi_{k-1}>\pi_k$. We can repeat the same above
argument for the entry $\pi_j$, $j=k-2,k-3,\ldots,i+2$, concluding each time that
$\pi_j>\pi_{j+1}$. When $j=i+2$ a pattern $1-23$ is shown in $\pi_i\ \pi_{i+1}\ \pi_{i+2}$, which
is forbidden.\qed

\begin{prop}\label{u4}
If $\pi\in S(1-23,23-1)$, then $\pi\in S(1-23,23-1,12-3)$.
\end{prop}
This last proposition can be be proved by simply adapting the
argument of the proof of the preceding one.


\section{Permutations avoiding four patterns}

First of all we recall the results relating to the case of three forbidden patterns \cite{BFP} in
Tables \ref{3mot1} and \ref{3mot2}. For the sake of brevity, for each symmetry class only a
representative is reported. In the first column of these tables, a name to each symmetry class is
given, the second one shows the three forbidden patterns (the representative) and the third one
indicates the sequence enumerating the permutations avoiding the specified patterns.

Having at our disposal the results for the permutations avoiding three patterns, the proofs for
the case of four forbidden patterns are conducted following the line indicated in the previous
section. These proofs are all summarized in tables. Tables \ref{4mot_n}, \ref{4mot_F_n} and
\ref{4mot_2^n-1} are related to the permutations avoiding four patterns enumerated by the
sequences $\{n\}_{n\geq1}$, $\{F_n\}_{n\geq1}$ and $\{2^{n-1}\}_{n\geq1}$, respectively (the
sequence $\{F_n\}_{n\geq1}$ denotes the Fibonacci numbers). The empty permutation with length
$n=0$ is not considered, therefore the length is $n\geq1$. The Tables have to be read as follows:
consider the representative of the symmetry class specified in the rightmost column of each table;
apply the proposition indicated in the preceding column to the three forbidden patterns which one
can find in Tables \ref{3mot1} and \ref{3mot2} to obtain the four forbidden patterns written in
the column named \emph{avoided patterns}. At this point, as we explained in the previous section,
the permutations avoiding these four patterns are enumerated by the same sequence enumerating the
permutations avoiding the three patterns contained in the representative of the symmetry class
indicated in the rightmost column.

The first column of Table \ref{4mot_n} and \ref{4mot_F_n} specifies a name for the the symmetry
class represented by the four forbidden patterns of the second column. This name is useful in the
next section. Table \ref{4mot_varie} indicates in the first column the sequence enumerating the
permutations avoiding the patterns of the second column, which are obtained as in the above
tables.

\subsection{Classes enumerated by $\{0\}_{n\geq k}$.}\label{valore k}

The classes of four patterns avoiding permutations enumerated by the ultimately constant sequence
$\{0\}_{n\geq k}$ can be handled in a very simple way (the value of $k\in \mathbb N$ depends on
the considered patterns, however it is never greater than $4$). If $S(q_1,q_2,q_3)$, $q_i\in
\mathcal M$, is a class of permutations avoiding three patterns such that $|S_n(q_1,q_2,q_3)|=0$,
for $n\geq k$, then it is easily seen that $S(q_1,q_2,q_3,r)$, $\forall r\in \mathcal M$, is also
enumerated by the same sequence. Then, each symmetry class from $C1$ to $C7$ (see Table
\ref{3mot2}) generates nine symmetry classes by choosing the pattern $r\neq q_i$, $i=1,2,3$. It is
easy to see that some of the classes we obtain in this way are equal, thanks to the operations of
reverse, complement and reverse-complement. In Table \ref{4mot_0}, only the different possible
cases are presented. Here, the four forbidden patterns are recovered by adding a pattern of a box
of the second column to the three patterns specified in the box to its right at the same level
(rightmost column). The representative so obtained is recorded in the leftmost column with a name,
which will be useful in the next section.

\subsection{Classes enumerated by $\{2\}_{n\geq 2}$.}

The enumerating sequences encountered till now (see Tables \ref{4mot_n}, \ref{4mot_F_n},
\ref{4mot_2^n-1}, \ref{4mot_varie}, \ref{4mot_0}) are all involved in the enumeration of some
class of permutations avoiding three patterns (Tables \ref{3mot1}, \ref{3mot2}). Therefore,
applying the eight propositions of the previous section to the classes of Table \ref{3mot1} and
\ref{3mot2}, the three forbidden patterns have been increased by one pattern, obtaining Table
\ref{4mot_n}, \ref{4mot_F_n}, \ref{4mot_2^n-1}, \ref{4mot_varie} and \ref{4mot_0}. For the classes
enumerated by the sequence $\{2\}_{n\geq 2}$ it is not possible to use the same strategy, since
there are no classes of permutations avoiding three patterns enumerated by that sequence. The
proofs, in this case, use four easy propositions whose proofs can be directly derived from the
statement of the first four propositions of the Introduction. We prefer to explicit them the same.

\begin{prop}\label{contiene_1}
If a permutation $\pi$ contains the pattern $23-1$, then it contains the pattern $2-31$, too.
\end{prop}

Taking the reverse, the complement and the reverse-complement of the patterns involved in Prop.
\ref{contiene_1}, the following propositions are obtained:

\begin{prop}\label{contiene_2}
If a permutation $\pi$ contains the pattern $1-32$, then it contains the pattern $13-2$, too.
\end{prop}

\begin{prop}\label{contiene_3}
If a permutation $\pi$ contains the pattern $21-3$, then it contains the pattern $2-13$, too.
\end{prop}

\begin{prop}\label{contiene_4}
If a permutation $\pi$ contains the pattern $3-12$, then it contains the pattern $31-2$, too.
\end{prop}

In Table \ref{4mot_2} the results relating to the enumeration of the permutations avoiding four
patterns enumerated by the sequence $\{2\}_{n\geq 2}$ (whose proofs are contained in the six next
propositions) are summarized. The four forbidden patterns can be recovered by choosing one pattern
from each column, in the same box-row of the table.

 In the sequel, $p_i\in A_i$ with $i=1,2,3,4$ where $A_i$ is a subset of generalized patterns.
\begin{prop}
Let $A_1=\{1-23\}$, $A_2=\{2-31,23-1\}$, $A_3=\{1-32,13-2\}$ and $A_4=\{3-12,31-2\}$. Then
$|S_n(p_1,p_2,p_3,p_4)|=2$ and $S_n=\{n\ (n-1)\ldots 3\ 2\ 1 ,\ (n-1)\ (n-2)\ldots 3\ 2\ 1\ n \}$.
\end{prop}

\emph{Proof.} Let $\sigma\in S_n(p_2,p_3)$. Then, $\sigma_1=n$ or $\sigma_n=n$, otherwise, if
$\sigma_i=n$ with $i\neq 1,n\ $, the entries $\sigma_{i-1}\sigma_{i}\sigma_{i+1}$ would be a
forbidden pattern $p_2$ or $p_3$.

If $\rho\in S_n(p_1,p_3)$, then $\rho_{n-1}=1$ or $\rho_n=1$, otherwise, if $\rho_i=1$ with
$i<n-1$, then the entries $\rho_i\rho_{i+1}\rho_{i+2}$, would be a forbidden pattern $p_1$ or
$p_3$.

Therefore, if $\pi\in S_n(p_1,p_2,p_3)$, then there are only the following three cases for $\pi$:
\begin{enumerate}
    \item $\pi_n=n$ and $\pi_{n-1}=1$. In this case $\pi=(n-1)\ (n-2) \ldots
    2\ 1\ n$, otherwise, if an ascent appears in $\pi_j\pi_{j+1}$ with
    $j=1,2,\ldots, n-3$, the entries $\pi_j\pi_{j+1}\pi_{n-1}$
    would show the pattern $23-1$ and $\pi$ would contain the pattern
    $2-31$, too (see Prop. \ref{contiene_1}).
    \item $\pi_1=n$ and $\pi_n=1$. In this case $\pi=n\ (n-1)\ldots 3\ 2\
    1$, otherwise, if an ascent appears in $\pi_j\pi_{j+1}$ with
    $j=2,3,\ldots, n-2$, the entries $\pi_j\pi_{j+1}\pi_n$ would
    show the pattern $23-1$ and $\pi$ would contain the pattern
    $2-31$, too (see Prop. \ref{contiene_1}).
    \item $\pi_1=n$ and $\pi_{n-1}=1$ (and $\pi_n=k<n$).
\end{enumerate}

If $\pi$ has to avoid the pattern $p_4$, too ($\pi\in S_n(p_1,p_2,p_3,p_4)$), then the third above
case is not allowed since $\pi_1\pi_{n-1}\pi_n$ are a $3-12$ pattern which induces an occurrence
of $31-2$ in $\pi$ (Prop. \ref{contiene_4}). \qed

\begin{prop}
Let $A_1=\{1-23\}$, $A_2=\{2-13,21-3\}$, $A_3=\{1-32,13-2\}$ and $A_4=\{3-12,31-2\}$. Then
$|S_n(p_1,p_2,p_3,p_4)|=2$ and $S_n=\{n\ (n-1)\ldots 3\ 2\ 1,\ (n-1)\ n\ (n-2)\ (n-3)\ldots 2\
1\}$.
\end{prop}

\emph{Proof.} If $\sigma\in S_n(p_1,p_2)$, then $\pi_1=n$ or $\pi_2=n$. If $\rho\in S_n(p_1,p_3)$,
then $\pi_n=1$ or $\pi_{n-1}=1$. Then, if $\pi\in S_n(p_1,p_2,p_3)$, there are only the four
following cases:
\begin{enumerate}
    \item $\pi_1=n$ and $\pi_n=1$.
    \item $\pi_2=n$ and $\pi_n=1$. In this case $\pi_1=n-1$,
    otherwise if $\pi_k=n-1$ with $k>3$, then $\pi_{k-2}\pi_{k-1}\pi_k$ is
    a $1-23$ pattern or a $21-3$ pattern which induces an occurrence of
    $2-13$ (Prop. \ref{contiene_3}). If $k=3$, then $\pi_1\pi_2\pi_3$ is a
    $1-32$ or $13-2$ pattern which are forbidden.
    \item $\pi_1=n$ and $\pi_{n-1}=1$.
    \item $\pi_2=n$ and $\pi_{n-1}=1$. For the same reasons of
    case 2, it is $\pi_1=n-1$.
\end{enumerate}

If $\pi$ has to avoid $p_4$, too ($\pi\in S_n(p_1,p_2,p_3,p_4)$), then the third and the fourth
above cases are not allowed since $\pi_1\pi_{n-1}\pi_n$ are a $3-12$ pattern which induces an
occurrence of $31-2$ (Prop. \ref{contiene_4}). Moreover, the permutations of the above cases $1$
and $2$, must be such that there are not ascents $\pi_i\pi_{i+1}$ between $n$ and $1$ in order to
avoid $p_4$. Then, $\pi=n\ (n-1)\ldots 3\ 2\ 1 $ or $\pi=(n-1)\ n\ (n-2)\ldots 3\ 2\ 1$. \qed

\begin{prop}\label{16classi}
Let $A_1=\{2-13,21-3\}$, $A_2=\{2-31,23-1\}$, $A_3=\{1-32,13-2\}$ and $A_4=\{3-12,31-2\}$. Then
$|S_n(p_1,p_2,p_3,p_4)|=2$ and $S_n=\{n\ (n-1)\ldots 2\ 1,\ 1\ 2\ldots n\}$.
\end{prop}

\emph{Proof.} It is easily seen that each three consecutive elements of $\pi$ can only be in
increasing or decreasing order. \qed

\begin{prop}
Let $A_1=\{12-3\}$, $A_2=\{2-13,21-3\}$, $A_3=\{2-31,23-1\}$ and $A_4=\{32-1\}$. Then
$|S_n(p_1,p_2,p_3,p_4)|=2$ and $S_n=\{1\ n\ 2\ (n-1)\ldots,\ n\ 1\ (n-1)\ 2\ldots\}$.
\end{prop}

\emph{Proof.} If $\pi\in S_n(p_1,p_2,p_3,p_4)$, then it is easy to see that $\pi_1\pi_2=1\ n$ or
$\pi_1\pi_2=n\ 1$. Considering the sub-permutation $\pi_2\pi_3\ldots \pi_n$, in the same way we
deduce $\pi_2\pi_3=2\ (n-1)$ or $\pi_2\pi_3=(n-1)\ 2$. The thesis follows by recursively using the
above argument. \qed

\begin{prop}
Let $A_1=\{1-23\}$, $A_2=\{2-13,21-3\}$, $A_3=\{2-31,23-1\}$ and $A_4=\{3-12,31-2\}$. Then
$|S_n(p_1,p_2,p_3,p_4)|=2$ and $S_n=\{n\ (n-1) \ldots 1,\ 1\ n\ (n-1) \ldots 3\ 2\}$.
\end{prop}

\emph{Proof.} Let $\pi\in S_n(p_1,p_2,p_3,p_4)$. It is $\pi_1=n$ or $\pi_2=n$, otherwise a $1-23$
or $p_2$ pattern would appear.

If $\pi_1=n$, then $\pi=n\ (n-1) \ldots 1$ since if an ascent appears in $\pi_i\pi_{i+1}$, the
entries $\pi_1\pi_i\pi_{i+1}$ are a $p_4$ pattern.

If $\pi_2=n$, then $\pi_1=1$ since the $p_3$ pattern has to be avoided. Moreover, in this case, it
is $\pi_j>\pi_{j+1}$ with $j=3,4,\ldots,(n-1)$ in order to avoid $1-23$. Then $\pi=1\ n\
(n-1)\ldots 2\ 1$. \qed

\begin{prop}
Let $A_1=\{1-23\}$, $A_2=\{2-13,21-3\}$, $A_3=\{2-31,23-1\}$ and
$A_4=\{1-32,13-2\}$. Then $|S_n(p_1,p_2,p_3,p_4)|=2$ and $S_n=\{n\
(n-1) \ldots 3\ 2\ 1,\ n\ (n-1) \ldots 3\ 1\ 2\}$.
\end{prop}

\emph{Proof.} Let $\pi\in S_n(p_1,p_2,p_3,p_4)$. The entries $1$
and $2$ have to be adjacent in order to avoid $p_3$ and $p_4$ and
$\pi_n=1$ or $\pi_{n-1}=1$ in order to avoid $p_1$ and $p_4$. So,
$\pi_{n-1}\pi_n=1\ 2$ or $\pi_{n-1}\pi_n=2\ 1$. Moreover, each
couple of adjacent elements $\pi_j\pi_{j+1}$ must be a descent,
otherwise a $23-1$ pattern (which induces an occurrences of
$2-31$) would appear. Then $\pi=n\ (n-1) \ldots 3\ 2\ 1$ or $\pi=
n\ (n-1) \ldots 3\ 1\ 2$. \qed

The conjecture stated by Claesson and Mansour \cite{CM} about the permutations enumerated by
$\{2\}_{n\geq2}$ declares that there are $42$ symmetry classes of such permutations, while from
Table \ref{4mot_2} it is possible to deduce $52$ symmetry classes. However, some of them represent
the same class: for example the symmetry class $\{2-13,2-31,1-32,31-2\}$ is the same of
$\{2-13,23-1,13-2,31-2\}$ (the second one is the reverse of the first one). Note that the
repetitions come out only from the third box-row of Table \ref{4mot_2}.



\section{Permutations avoiding five patterns}


\subsection{Classes enumerated by $\{1\}_{n\geq 1}$}

The sequence $\{1\}_{n\geq 1}$ does not enumerate any class of permutations avoiding four
patterns, so that we can not apply the same method of the previous section using the propositions
of the Introduction.

Referring to Proposition \ref{16classi}, we deduce that there are sixteen different classes
$S_n(p_1,p_2,p_3,p_4)$ such that $p_i \in A_i$ with $i=1,2,3,4$. We recall that
$|S_n(p_1,p_2,p_3,p_4)|=2$ and $S_n(p_1,p_2,p_3,p_4)=\{n\ (n-1)\ldots 2\ 1,\ 1\ 2\ldots n\}$. If a
permutation $\pi\in S_n(p_1,p_2,p_3,p_4)$ has to avoid the pattern $1-23$, too, then $\pi=n\
(n-1)\ldots 2\ 1$ and $|S_n(p_1,p_2,p_3,p_4,1-23)|=1$. Then, the five forbidden patterns avoided
by the permutations enumerated by $\{1\}_{n\geq 1}$ can be recovered by considering the four
patterns chosen from the third box-row of Table \ref{4mot_2} (one pattern from each column) and
the pattern $1-23$. We do not present the corresponding table.

\subsection{Classes enumerated by $\{0\}_{n\geq 4}$}

This case is treated as the case of the permutations avoiding four
patterns. It is sufficient to add a pattern $r\in\mathcal M$ to
each representative (from O1 to O37 in Table \ref{4mot_0}) of four
forbidden patterns of Table \ref{4mot_0} in order to obtain a
representative $T$ of five forbidden patterns such that
$|S_n(T)|=0, n\geq4$. In Table \ref{5mot_0} we present the
different representatives $T$ which can be derived from Table
\ref{4mot_0}. The five forbidden patterns of each representative
are a pattern chosen in a box of the first column and the four
patterns indicated by the representative (which refer to Table
\ref{4mot_0}) in the second box at the same level. In the table,
only the different representatives of five patterns are presented.

\subsection{Classes enumerated by $\{2\}_{n\geq 2}$,
$\{n\}_{n\geq 1}$, $\{F_n\}_{n\geq 1}$}

Tables \ref{5mot_2(1)} and \ref{5mot_2(2)} summarize the results related to the permutations
avoiding five patterns enumerated by $\{2\}_{n\geq 2}$. The five forbidden patterns are obtained
by considering a representative of four forbidden patterns of the rightmost column and the pattern
specified in the corresponding box of the preceding column. The first column indicates which is
the proposition to apply. Note that each representative of four patterns (rightmost column) can be
found in Table \ref{4mot_2}.

The reading of Tables \ref{5mot_n} and \ref{5mot_F_n} (related to
the sequences $\{n\}_{n\geq 1}$ and $\{F_n\}_{n\geq 1}$,
respectively) is as usual: apply the proposition specified in the
first column to recover the representative of five forbidden
patterns which is composed by the pattern of the second column and
the four patterns of the representative indicated in the rightmost
column. Here, the names of the representatives refer to Tables
\ref{4mot_n} and \ref{4mot_F_n}.

%%%%%%%%%%
%%%%%%%%%%
%%%%%%%%%%
%%SEZIONE[TAVOLE]
%%%%%%%%%%
%%%%%%%%%%

\include{3mot_prima_tavola}
\input{3mot_seconda_tavola}
\input{4mot_seq_n}
\input{4mot_seq_F_n}
\input{4mot_seq_2_n-1}
\input{4mot_seq_varie}
\input{4mot_seq_0_bis}
\input{4mot_seq_2}
\include{5mot_seq_0}
\include{5mot_seq_2}
\input{5mot_seq_n}
\input{5mot_seq_F_n}

\section{Conclusion: the cases of more than five patterns}
Looking at the table of the conjectures by Claesson and Mansour \cite{CM}, one can see that the
case of six patterns is the unique, among the remaining ones, which presents some enumerating
sequences not ultimately constant. More precisely, in this case there are three classes enumerated
by the sequence $\{n\}_{n\geq1}$ and one class enumerated by $\{F_n\}_{n\geq1}$. In order to find
a representative for each of these classes, it is possible to consider the classes of permutations
avoiding five patterns enumerated by the same sequence and apply one of the propositions in the
Introduction. As far as the class enumerated by $\{F_n\}_{n\geq1}$ is concerned, the
representative set $U=\{1-23,2-13,13-2,21-3,12-3,1-32\}$ is obtained by considering the patterns
arising from the second line of Table \ref{5mot_F_n} and applying Proposition \ref{5}. Note that
the same above representative set can be obtained by considering the patterns of the third line of
Table \ref{5mot_F_n} and applying Proposition \ref{u2}.

Starting from the set $V=\{1-23,2-13,1-32,21-3,12-3\}$, which are the forbidden patterns specified
in the first line of Table \ref{5mot_F_n}, it is not possible to apply anyone of the propositions
in the Introduction. Nevertheless, if $\pi\in S(V)$, then in particular $\pi$ avoids the patterns
$1-23$ and $1-32$. Next, it is simple to see that such a permutation $\pi$ avoids also $13-2$,
therefore $\pi\in S_n(U)$ and $|S_n(U)|=F_n$.

The propositions in the Introduction are not even useful when the set of patterns
$Z=\{1-23,1-32,3-12,31-2,13-2\}$, arising from the fourth line of Table \ref{5mot_F_n}, is
considered. In this case, if a pattern $x\in \mathcal M\backslash Z$ is added to $Z$, then it can
be proved that either $|S_n(Z,x)|=n$, or $|S_n(Z,x)|=0\ (n\geq5)$, or $|S_n(Z,x)|=n\ (n\geq2)$. A
possible way to menage these proofs (one for each $x\in \mathcal M\backslash Z$) uses the ECO
method, as Bernini, Ferrari and Pinzani made \cite{BFP}. This is what we did but we do not show
the details of the permutations' construction, which can be easily recovered by the reader.

In order to prove the truth of the conjecture relating to the sequence $\{F_n\}_{n\geq1}$, we
observe that if $a_n$ and $b_n$ are the sequences enumerating $S_n(A)$ and $S_n(B)$, respectively,
with $A\subseteq B\subseteq \mathcal M$, then $a_n\geq b_n$. Therefore, using the strategy
mentioned in Subsection \ref{strategy}, the patterns specified in $U$ can be obtained only from
the forbidden patterns arising from Table \ref{5mot_F_n}.

\bigskip

A similar discussion should be carried out for the permutations avoiding six patterns enumerated
by the sequence $\{n\}_{n\geq 1}$, starting from the patterns of Table \ref{5mot_n}. We omit it
since it can simply be done by following the line of the case of the sequence $\{F_n\}_{n\geq1}$.
The complete solution of the conjectures of Claesson and Mansour requires that the same argument
has to be applied for the ultimately constant sequences $\{0\}$ and $\{1\}$, enumerating
permutations avoiding six or more patterns. It should not be difficult to write down the tables
summarizing the results relating to the permutations avoiding six patterns and use them, according
to the usual strategy, for the results of the case of seven forbidden patterns. Then, the tables
relating to the case of seven patterns should be used for the case of eight patterns, and so on.

Actually, we note that if the tables of the case of six patterns are not at our disposal it could
be quite long to solve the case of seven forbidden patterns using the same strategy. Nevertheless,
it does not seem necessary to provide the tables for all the remaining cases, since it is easy,
given a set $D\subseteq \mathcal M$ of six or more forbidden patterns, to find the enumerating
sequence of $S(D)$. This sequence should be ultimately constant according to the conjectures by
Claesson and Mansour \cite{CM} (aside from the already examined sequences $\{F_n\}_{n\geq1}$ and
$\{n\}_{n\geq 1}$ for the case of six forbidden patterns). Therefore, by means of the ECO method,
for instance, it is straightforward to generate all the permutations of $S(D)$, following the line
which Bernini, Ferrari and Pinzani used in their paper \cite{BFP}, and find the relating sequence.
Unless the conjectures of Claesson and Mansour are wrong, this kind of approach is quite fast
every time $|S(D)|$ is required.

\bigskip

We conclude with a hint for a possible further work. Mansour and Vainshtein \cite{MV} showed that
the generating function for permutations avoiding 132 and any other classical pattern is rational.
It should be interesting to generalize this result to some set of generalized patterns (the
results of Claesson \cite{C} stating that $S(132)=S(13-2)$ or $S(213)=S(2-13)$ could be used for a
first effort in this direction). With a similar approach it should be possible to handle this kind
of analysis mechanically.

\section*{Acknowledgments}

A part of this paper has been written during a visit to the Centre de Recerca Matem\'atica (CRM)
in Barcelona. The hospitality and support of this institution is gratefully acknowledged.


\begin{thebibliography}{99}

\bibitem{BDPP} E. Barcucci, A. Del Lungo, E. Pergola, R.
Pinzani, ECO: A Methodology for the Enumeration of Combinatorial Objects, {\it J. Difference Equ.
Appl.} {\bf 5} (1999), 435--490.

\bibitem{BS} E. Babson, E. Steingr\'imsson, Generalized permutation patterns and a classification of the
Mahonian statistics, {\it S\'em. Lothar. Combin.} {\bf 44} (2000), B44b.

\bibitem{BFP} A. Bernini, L. Ferrari, R. Pinzani, Enumerating permutations avoiding three
Babson-Steingr\'imsson patterns, {\it Ann. Comb} {\bf 9} (2005), 137--162.

\bibitem{C} A. Claesson, Generalized pattern avoidance, {\it European J. Combin.} {\bf 22} (2001), 961--971.

\bibitem{CM} A. Claesson, T. Mansour, Enumerating permutations avoiding a pair of Babson-Steingr{\'Y}msson patterns,
{\it Ars Combin.} {\bf 77} (2005), 17--31.

\bibitem{EN} S. Elizalde, M. Noy, Consecutive patterns in permutations, {\it Adv. in Appl. Math.} {\bf 30} (2003),
110--125.

\bibitem{MV} T. Mansour, A. Vainshtein, Restricted 132-avoiding permutations, {\it Adv, in Appl. Math}
{\bf 26} (2001), 258--269.

\bibitem{K} S. Kitaev, Generalized patterns in words and permutations,\quad Ph. D. Thesis,
\quad Chalmers University of Technology and G\"oteborg Univerity
(2003).

\bibitem{SS} R. Simion, F. W. Schmidt, Restricted
permutations, {\it European J. Combin.} {\bf 6} (1985), 383--406.

\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2000 {\it Mathematics Subject Classification}: Primary 05A15; Secondary 05A05.

\noindent \emph{Keywords: } generalized pattern avoidance, Babson-Steingr\'\i msson patterns,
permutations.


\bigskip
\hrule
\bigskip


\noindent (Concerned with sequences
\seqnum{A000027},
\seqnum{A000045},
\seqnum{A000079},
\seqnum{A000124},
\seqnum{A001405}, and
\seqnum{A094373}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received April 27 2007;
revised version received June 11 2007.
Published in {\it Journal of Integer Sequences}, June 11 2007.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}