\documentclass[12pt]{amsart}
%\input{epsf}
\usepackage{amssymb,latexsym}
  \setlength{\unitlength}{1mm}

\topmargin 0 pt \textheight 46\baselineskip \advance\textheight by
\topskip \setlength{\parindent}{0pt} \setlength{\parskip}{5pt plus
2pt minus 1pt} \setlength{\textwidth}{155mm}
\setlength{\oddsidemargin}{5.6mm}
\setlength{\evensidemargin}{5.6mm}
%\setcounter{section}{-1}

\newcommand{\light}[1]{{#1}}
\newcommand{\bulletcolor}[1]{{#1}}

\numberwithin{equation}{section}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{example}[theorem]{Example}
\newtheorem{axiom}[theorem]{Axiom}
\newtheorem{property}[theorem]{Property}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{notation}[theorem]{Notation}
\begin{document}

\pagenumbering{arabic} \pagestyle{headings}
\def\sof{\hfill\rule{2mm}{2mm}}
\def\ls{\leq}
\def\gs{\geq}
\def\SS{\mathcal S}
\def\qq{{\bold q}}
\def\txx{{\frac1{2\sqrt{x}}}}
\def\sof{\hfill\rule{2mm}{2mm}}
\def\ls{\leq}
\def\gs{\geq}
\def\SS{\mathcal S}
\def\qq{{\bold q}}
\def\aa{{\overline{1}}}
\def\ab{{\overline{2}}}
\def\an{{\overline{n}}}
\def\as{{\overline{s}}}

\newbox\Adr
\setbox\Adr\vbox{
\centerline{\small\uppercase{T. Mansour$^{\rm a}$ and J. West$^{\rm b}$}}
\vskip12pt
\begin{center}
{\small $^A$ LaBRI (UMR 5800), Universit\'e Bordeaux 1,
       351 cours de la Lib\'eration, \\
       33405 Talence Cedex, France}\\[4pt]
{\tt toufik@labri.fr}\\ \ \\

{\small $^B$ University of Victoria,
PO Box 1700 STN CSC, \\ Victoria, BC V8W 2Y2 Canada}\\[4pt]
{\tt westj@mala.bc.ca}

\end{center}
}

\title{ {\sc avoiding $2$-letter signed patterns}}

\author[Toufik Mansour and Julian West]
{\box\Adr}

%\date{\today}

\begin{abstract}
Let $B_n$ be the hyperoctahedral group, the set of all signed
permutations on $n$ letters, and let $B_n(T)$ be the set of all
signed permutations in $B_n$ which avoid a set $T$ of signed
patterns. In this paper, we find all the cardinalities of the sets
$B_n(T)$ where $T\subseteq B_2$.  Some of the cardinalities
encountered involve inverse binomial coefficients, binomial
coefficients, Catalan numbers, and Fibonacci numbers.
\end{abstract}

\maketitle




%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 49 \rms (2002), Article~B49a\hfill}
\def\thepage{}
%
%


%===========================================================================
\section{Introduction}

Pattern avoidance has proven to be a useful language in a variety
of seemingly unrelated problems, from stack sorting \cite{Kn,Rt,W}
to the theory of Kazhdan--Lusztig polynomials ~\cite{Fb},
singularities of Schubert varieties \cite{LS,SCb}, Chebyshev
polynomials \cite[and references therein]{MV1}, and rook polynomials
\cite{MV2}. On the other hand, signed pattern avoidance has proven
to be a useful language in combinatorial statistics defined in
type-$B$ noncrossing partitions, enumerative combinatorics,
algebraic combinatorics, geometric combinatorics and singularities
of Schubert varieties; see \cite{Be, BK, Cm, FK, MbRs, Rs, Vr}.

{\bf Restricted permutations.} Let $S_{\{a_1,\dots,a_n\}}$ be the
set of all permutations of the numbers $a_1,\dots,a_n$. For
simplicity, let us denote by $S_n$ the set $S_{\{1,2,\dots,n\}}$.
Let $\pi\in S_n$ and $\tau\in S_k$ be two permutations. An {\it
occurrence} of $\tau$ in $\pi$ is a subsequence $1\leq
i_1<i_2<\dots<i_k\leq n$ such that $(\pi_{i_1},\dots,\pi_{i_k})$
is order-isomorphic to $\tau$; in such a context $\tau$ is usually
called a {\it pattern}. We say that $\pi$ {\it avoids} $\tau$, or
is $\tau$-{\it avoiding}, if there is no occurrence of $\tau$ in
$\pi$. The set of all $\tau$-avoiding permutations in $S_n$ is
denoted $S_n(\tau)$. For an arbitrary finite collection of
patterns $T$, we say that $\pi$ avoids $T$ if $\pi$ avoids any
$\tau\in T$; the corresponding subset of $S_n$ is denoted
$S_n(T)$.

{\bf Restricted signed permutations.} We will regard the elements
of the hyperoctahedral group $B_n$ as signed permutations written
as $\alpha=\alpha_1\alpha_2\dots\alpha_n$ in which each of the
symbols $1,2,\dots,n$ appears, possibly barred. Clearly, the
cardinality of $B_n$ is $2^nn!$. We define the {\em barring
operation} as the one which changes the symbol $\alpha_i$ to
$\overline{\alpha_i}$ and $\overline{\alpha_i}$ to $\alpha_i$. It
is thus an involution, i.e., $\overline{\overline{\alpha_i}}=\alpha_i$.
Furthermore, we define the absolute value 
$|\alpha_i|$ of $\alpha_i$ to be $\alpha_i$ if the symbol 
$\alpha_i$ is not barred,
and $\overline{\alpha_i}$ otherwise.

Now let $\tau\in B_k$ and $\alpha\in B_n$; we say {\em $\alpha$
contains the signed pattern $\tau$}, 
if there is a sequence of $k$ indices, $1\leq
i_1<i_2<\dots<i_k\leq n$ such that two conditions hold: $(1)$
$\alpha$ with all bars removed has an occurrence of the pattern
$\tau$ with all bars removed, i.e.,
$|\alpha_{i_p}|>|\alpha_{i_q}|$ if and only if $|\tau_p|>|\tau_q|$,
for all $k\geq p>q\geq 1$; and $(2)$ in this occurrence,
$\alpha_{i_j}$ is barred if and only if $\tau_j$ is barred, for all
$1\leq j\leq k$. For example,
$\alpha=21\overline{3}\overline{4}\in B_4$ contains the signed
patterns $\aa\ab$ and $21$. If $\alpha$ does not contain the
signed pattern $\tau$, then we say that $\alpha$ {\em avoids the signed
pattern} $\tau$ or, alternatively, that $\alpha$ 
is a $\tau$-{\em avoiding signed permutation}. The
set of $\tau$-avoiding signed permutations in $B_n$ will be
denoted by $B_n(\tau)$. More generally we define
$B_n(T)=\bigcap_{\tau\in T} B_n(\tau)$. We denote the cardinality of $B_n(T)$
by $b_n(T)$.

\begin{proposition} {\rm (see \cite[Section~3]{Rs})}
\label{sym} We define three simple operations on signed
permutations: the reversal (i.e., reading the permutation
right-to-left:
$\alpha_1\alpha_2\cdots\alpha_n\mapsto\alpha_n\alpha_{n-1}\cdots\alpha_1$),
the barring (i.e., $\alpha_1\alpha_2\cdots\alpha_n
\mapsto\overline{\alpha_1}\overline{\alpha_2}\cdots\overline{\alpha_n}$)
and the complement (i.e., $\alpha_1\alpha_2\cdots\alpha_n
\mapsto\beta_1\beta_2\cdots\beta_n$ where $\beta_i=n+1-\alpha_i$
if $\alpha_i$ not barred, otherwise
$\beta_i=\overline{n+1-|\alpha_i|}$). Let us denote by
$G_b$ the group which is generated by these three 
operations. Then every element $g\in G_b$ is a bijection,
which shows that if $T$ and $T'$ are both sets of signed patterns
in $B_n$ such that $T'=g(T)=\{g(\alpha)\mid \alpha\in T\}$, then
$b_n(T)=b_n(T')$.
\end{proposition}

%This proposition invite us to define the following.
%
%\begin{definition}
%We denote the {\em symmetric class} of set $T$
%by $Sym(T)$ which is contain all the sets $T'$ where
%there exist $g\in G_b$ such that $g(T')=T$.
%\end{definition}
%
In the symmetric group $S_n$, for every $2$-letter pattern $\tau$
the number of $\tau$-avoiding permutations is 1, and for every
pattern $\tau\in S_3$ the number of $\tau$-avoiding permutations
is given by the Catalan numbers ~\cite{Kn}. Simion
~\cite[Section~3]{Rs} proved that there are similar results for the
hyperoctahedral group $B_n$ (generalized by Mansour \cite{M}): for
every $2$-letter signed pattern $\tau$ the number of
$\tau$-avoiding signed permutations is given by $\sum_{j=0}^n
\binom{n}{j}^2j!$. In the present note, we find all the
cardinalities $b_n(T)$ where $T\subseteq B_2$. (This exhaustive
treatment of cases was suggested by the influential paper of
Simion and Schmidt \cite{SS}, which followed a similar program for
the cardinalities $s_n(T)$ where $T\subseteq S_3$).

The paper is organized as follows. In Section~$2$ we find the
cardinalities $b_n(T)$ where $T\subseteq B_2$ and $|T|\leq 2$. In
Section~$3$ we deal with the case that $|T|=3$; 
in Section~$4$ we deal with the case that $|T|=4$; and, finally, in
Section~$5$ we deal with the case that $5\leq|T|\leq 8$.

%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 AND JULIAN WEST}{\SMALL AVOIDING
2-LETTER SIGNED PATTERNS}
%
%


%=======================================================================================
\section{Two signed patterns}
By taking advantage of Proposition~\ref{sym}, the question of
determining the values $b_n(\tau)$ for the $8$ choices of one
$2$-letter signed pattern, can be reduced to $2$ cases, which are
$\tau=12$ and $\tau=1\ab$. Simion \cite[Proposition~3.2]{Rs}
proved for any $n\geq 0$ that
\begin{equation}
b_n(12)=b_n(1\ab)=\sum_{k=0}^n{\binom n k}^2k!. \label{eq1}
\end{equation}

Similary, the second question of determining the values
$b_n(\tau,\tau')$ for the $28$ choices of two $2$-letter signed
patterns reduces to $8$ cases.

\begin{remark}
\cite[Proposition~3.4]{Rs} asserted that $b_n(\{12,21\})=2n!$ and
$b_n(\{1\ab,\aa2\})=(n+1)!$. However, in fact, $b_2(\{12,21\})=6$ and
$b_3(\{1\ab,\aa2\})=22$. Below we present the correction of Simion's
assertions.
\end{remark}

\begin{theorem}
Given two $2$-letter signed patterns $\tau$, $\tau'$, the value
$b_n(\tau,\tau')$ for $n\geq 1$ can be determined from one of the following
relations, depending on the orbit (under reversal, barring,
complementation) to which the pair $\tau$, $\tau'$ belongs:
\begin{equation}
b_n(\{12,21\})=b_n(\{12,1\ab\})=b_n(\{2\aa,1\ab\})=b_n(\{2\aa,\aa2\})=(n+1)!;
\label{eq2}
\end{equation}
\begin{equation}
b_n(\{12,\aa\ab\})=b_n(\{12,\ab\aa\})={\binom {2n} n}; \label{eq3}
\end{equation}
\begin{equation}
b_n(\{12,\ab1\})=n!+n!\sum\limits_{i=1}^n\left(\dfrac{1}{i}\sum\limits_{j=0}^{i-1}\dfrac{1}{j!}\right);
\label{eq4}
\end{equation}
\begin{equation}
b_n(\{1\ab,\aa2\})=2\sum\limits_{l=1}^n \sum\limits_{\
i_1+i_2+\dots+i_l=n,\ i_j\geq 1\ } \prod\limits_{j=1}^l i_j!.
\label{eq5}
\end{equation}
\end{theorem}
\begin{proof}
The assertion that
$b_n(\{12,21\})=(n+1)!$ follows immediately from
\cite[Theorem~1]{M}. The other results in \eqref{eq2} follow from
\cite[Proposition~3.4]{Rs}. By \cite[Example~4.8]{M} we get
\eqref{eq3}.
%To verify $(3)$ we observe
%that if $\alpha\in B_n(12,\aa\ab)$ ($\alpha\in B_n(12,\ab\aa)$)
%then $\alpha$ is determined by the choice of which symbols in it
%are barred and where they are located. It is a shuffle of the
%barred and unbarred symbols, each of which are ordered
%decreasingly by absolute value (respectively, the barred symbols
%are increasingly and unbarred symbols are decreasingly). For each
%$0\leq j\leq n$, there are ${\binom n j}$ choices of the values to
%be barred, and again ${\binom n j}$ choices for their placement in
%$\alpha$. Thus $(3)$ follows by direct counting.\\

To verify \eqref{eq4}, let us consider the number of signed
permutations $\alpha\in B_n(\{12,\ab1\})$. If $\alpha_n$ is barred
then $\alpha$ avoids $\{12,\ab1\}$ if and only if
$(\alpha_1,\dots,\alpha_{n-1})$ avoids $\{12,\ab1\}$. Hence,
there are $nb_{n-1}(\{12,\ab1\})$ such signed permutations. If $\alpha_n=i$
is unbarred then the smaller symbols $1,\dots,i-1$ must be barred
in $\alpha$ and the larger symbols $i+1,\dots,n$ must be unbarred,
hence the smaller symbols can be permuted and placed in any
of the positions $1,2,\dots,n-1$. This gives
$b_n(\{12,\ab1\})=nb_{n-1}(\{12,\ab1\})+\sum_{i=0}^{n-1} {\binom {n-1}
i}i!$ for $n\geq 1$. With the base case $b_0(T)=1$, Equation~\eqref{eq4}
follows by induction on $n$.

To verify \eqref{eq5}, let us consider $\alpha\in B_n(1\ab,\aa2)$.
By induction on $n$, it is easy to prove there exists a partition
$\alpha=(\alpha^1,\dots,\alpha^l)$ such that the following
conditions hold:
\begin{enumerate}
\item Every absolute symbol in $\alpha^j$ is greater than every absolute symbol
        in $\alpha^{j+1}$ for all $j=1,\dots, l-1$;
\item Either all the symbols of $\alpha^j$ are barred, or else all are unbarred;
\item The symbols in $\alpha^j$ are barred if and only if the symbols in
    $\alpha^{j+1}$ are unbarred.
\end{enumerate}
Equation \eqref{eq5} follows now immediately.
\end{proof}
%=======================================================================================
\section{Three signed patterns}
By taking advantage of Proposition~\ref{sym}, the question of
determining the values $b_n(T)$ where $T\subset B_2$ and $|T|=3$,
for the $56$ choices of three $2$-letter signed patterns, can be
reduced to the following $10$ cases:
$$\begin{array}{llll}
    T_1=\{12,1\ab,\aa2\};&\ \   T_2=\{12,1\ab,\aa\ab\};&\ \     T_3=\{12,1\ab,21\};&\ \   T_4=\{12,1\ab,2\aa\};\\
    T_5=\{12,1\ab,\ab1\};&\ \   T_6=\{12,1\ab,\ab\aa\};&\ \     T_7=\{12,\aa\ab,21\};&\ \ T_8=\{12,\aa\ab,2\aa\};\\
                 &\ \   T_9=\{12,2\aa,\ab1\};  &\ \     T_{10}=\{1\ab,\aa2,2\aa\}.&
\end{array}$$

\begin{theorem}
Given a set $T$ of three $2$-letter signed patterns, the value
$b_n(T)$ for $n\geq 1$ can be determined from one of the following relations,
depending on the orbit (under reversal, barring, complementation)
to which $T$ belongs:
\begin{equation}
b_n(T_1)=\sum\limits_{d=0}^n \sum\limits_{\ i_0+i_1+\dots+i_d=n-d\
} \prod\limits_{j=0}^d i_d!; \label{eq6}
\end{equation}
\begin{equation}
b_n(T_2)=C_{n+1}; \label{eq7}
\end{equation}
\begin{equation}
b_n(T_3)=n!+ n! \sum\limits_{j=1}^{n} \dfrac{1}{j}; \label{eq8}
\end{equation}
\begin{equation}
b_n(T_4)=b_n(T_5)=n!\sum\limits_{j=0}^n \frac{1}{j!}; \label{eq9}
\end{equation}
\begin{equation}
b_n(T_6)=F_{2n+1}; \label{eq10}
\end{equation}
\begin{equation}
b_n(T_7)=n^2+1; \label{eq11}
\end{equation}
\begin{equation}
b_n(T_8)=2^{n+1}-(n+1); \label{eq12}
\end{equation}
\begin{equation}
b_n(T_9)=b_n(T_{10})=n!\sum\limits_{j=0}^n
\binom{n}{j}^{-1},\label{eq13}
\end{equation}
where $C_m$ and $F_m$ are the $m$th Catalan and Fibonacci numbers,
respectively.
\end{theorem}
%\subsubsection*{\bf Proof \eqref{eq6}}
\begin{proof}[Proof of Equation~\eqref{eq6}]
Let $\alpha\in B_n(T_1)$, and let $m_0$ be the first unbarred symbol,
reading $\alpha$ from left-to-right. Since $\alpha\in B_n(T_1)$ we
see that $\alpha=(\alpha^0,m_0,\beta)$, where $\beta\in
B_{m_0-1}(T_1)$ and $\alpha^0$ is a permutation of the symbols
$\overline{m_0+1},\dots,\an$. By induction it follows that for
any $\alpha\in B_n(T_1)$ there exist $0\leq d\leq n$ and
permutations $\alpha^{j}$ of the symbols
$\overline{m_{j}+1},\overline{m_j+2},\dots,\overline{m_{j-1}-1}$
for all $0\leq j\leq d+1$, where $m_{-1}=n+1$, $m_{d+1}=0$, $0\leq
m_d<m_{d-1}<\dots<m_0\leq n$ such that
$\alpha=(\alpha^0,m_0,\alpha^1,m_1,\dots,\alpha^d,m_d,\alpha^{d+1})$.
Equation~\eqref{eq6} follows now immediately.
%\qed
\end{proof}

\begin{corollary}
\label{extu2} We have that $b_n(T_1\cup\{\aa\ab\})=2^n$ for all $n\geq 0$, and
$b_n(T_1\cup\{\ab\aa\})=1+{\binom {n+1} 2}$ for all $n\geq 2$.
\end{corollary}
\begin{proof}
This follows immediately, following the argument of the proof of
\eqref{eq6}.
\end{proof}
%=================================
\begin{proof}[Proof of Equation~\eqref{eq7}]
A {\em split permutation} is a permutation $\pi=(\pi',\pi'')\in
S_n$, where $\pi'$ and $\pi''$ are nonempty such that every entry
of $\pi'$ is greater than every entry of $\pi''$. For example,
$231$, $312$, and $321$ are the split permutations in $S_3$.

We first check that the number of non-split $123$-avoiding
permutations in $S_n$ (which we denote by $N_n$) is the $(n-1)$th Catalan
number, $C_{n-1}$.  We do this by using induction on $n$. 

It is
easy to check the base case. Now, suppose that $N_j=C_{j-1}$ for
$j<n$.
Take the $C_n$ $123$-avoiding permutation (see \cite{Kn}) and
classify them according to the first place where they split. Since
each permutation in $S_n$ thus decomposes into a direct sum of a
non-split $123$-avoiding permutation and an arbitrary
$123$-avoiding permutation, we have that
$$C_n=\sum_{j=1}^n N_jC_{n-j}=N_n+\sum_{j=0}^{n-2} C_jC_{n-1-j}.$$
By the well-known standard Catalan recurrence 
$C_n=\sum_{j=0}^{n-1} C_jC_{n-1-j}$, it follows that $N_n=C_{n-1}$,
which completes the induction step.

Now, suppose we have a signed permutation $\pi$ which avoids
$T_2$. Then the permutation $|\pi|$ must avoid $123$. 

Thus it remains to consider all $123$-avoiding permutations and
assign signs to their elements, respecting the condition that if
one element precedes and is smaller than a second element, then
the first one must be barred while the second one is unbarred.

Take a $123$-avoiding permutation $\pi$, and suppose that one of
its elements can be coloured freely, either barred or not. Then
this element cannot be both to the left of and smaller than any
other element; neither can it be both to the right of and larger
than any other element. That is, if our freely-colourable element
is denoted by $s$, we have $\pi=(\pi',s,\pi'')$ where each element
of $\pi'$ is greater than $s$, and each element of $\pi''$ is less
than $s$.  But this means that each element of the block $\pi'$ is
greater than each element of the block $s,\pi''$, which means that
the permutation splits at $s$.

Since the existence of a freely-colourable element leads to
a split of the permutation, it follows that any permutation
which is non-split is also uniquely colourable. There is one
exception, which is that the single 1-permutation can be coloured
in two ways, i.e., either barred or unbarred.

Now we are ready to find $b_n(T_2)$ by induction on $n$.
For the induction step we assume that $b_j(T_2)=C_{j+1}$ for $j<n$.

We count $b_n(T_2)$ according to the position of the first split.
Let $a_n$ be the number of non-split signed permutations which
avoid $T_2$; so, $a_1= 2$, while $a_j = N_j = C_{j-1}$ for $j>1$.

Note that if such a signed permutation splits, then each ``half" can
be assigned signs independently according to the pattern-avoidance
conditions. This implies that

$$b_n(T_2) =\sum_{j=1}^{n-1} a_jb_{n-j}+a_n
= 2C_n + \sum_{j=1}^{n-2} C_jC_{n-j} + C_{n-1}=\sum_{j=0}^{n}
C_jC_{n-j}=C_{n+1}.$$
%\qed
\end{proof}

%=================================
%\subsubsection*{\bf Proof \eqref{eq8}.}

\begin{proof}[Proof of Equation~\eqref{eq8}]
Let $\alpha\in B_n(T_3)$; if the symbol $n$ is unbarred in
$\alpha$, then since $\alpha$ avoids $12$ and $21$ we get that all
other symbols of $\alpha$ are barred. Thus there are $n!$ such signed 
permutations. Now let $\alpha_j=\an$. Since $\alpha$ avoids $1\ab$,
the symbol $\alpha_i$ is barred for $i\leq j$. Thus, in this case
there are $\sum_{j=1}^n {\binom {n-1} {j-1}}(j-1)!\, b_{n-j}(T_3)$ such
signed permutations. Hence, we have
    $$b_n(T_3)=n!+(n-1)!\sum_{j=1}^{n} \frac{b_{n-j}(T_3)}{(n-j)!}.$$
Now let $b'_n=b_n(T_3)/n!$. Thus we have $b'_n=1+\frac{1}{n}\sum_{j=0}^{n-1}
b'_j$, which implies that $b'_n-b'_{n-1}=\frac{1}{n}$. Because of
$b'_1=2$, we infer $b'_n=1+\sum_{j=1}^n \frac{1}{j}$, hence
\eqref{eq8} follows.
\end{proof}

\begin{corollary}
\label{extu3} We have that $b_n(T_3\cup\{\aa\ab\})=1+{\binom {n+1} 2}$ for
all $n\geq 0$.
\end{corollary}
\begin{proof}
This is immediate if one uses the argument of the proof of \eqref{eq8}.
\end{proof}
%==================================
%\subsubsection*{\bf Proof \eqref{eq9}.}

\begin{proof}[Proof of Equation~\eqref{eq9}, first case]
Let $\alpha\in B_n(T_4)$. Since $\alpha$ avoids $12$ and $1\ab$ we
have $\alpha_1=n$ or $\alpha_1=\overline{i}$ for some $i$. In the first case,
since $\alpha$ also avoids $2\aa$, we must have
$\alpha=(n,n-1,\dots,1)$. In the second case there are
$b_{n-1}(T_4)$ such signed permutations. Therefore,
$b_n(T_4)=1+nb_{n-1}(T_4)$ for all $n\geq3$, with $b_2(T_4)=5$.
Hence, by induction on $n$, we obtain the formula for $b_n(T_4)$.
\end{proof}

\begin{corollary}
\label{extu4} We have that $b_n(T_4\cup\{\aa\ab\})=b_n(T_4\cup\{\ab\aa\})=2^n$
and $b_n(T_4\cup\{21\})=2\cdot n!$ for all $n\geq1$.
\end{corollary}
\begin{proof}
By the above argument (proof of the formula for $b_n(T_4)$) we obtain the
following:
\begin{enumerate}
\item $b_n(T_4\cup\{21\})=nb_{n-1}(T_4\cup\{21\})$ for all $n\geq2$,
    with $b_1(T_4\cup\{21\})=2$. Hence, $b_n(T_4\cup\{21\})=2\cdot n!$
    for $n\geq 1$.
\item   Suppose $\alpha$ avoids $T_4$ and $\{\aa\ab\}$. 
Again there are two cases. In the first
    case $\alpha=(n,\dots,2,1)$. In the second case, we have that
    $\alpha=(\overline{i},\beta,n,\dots,i+1,\gamma)$, where all symbols of
    $\beta$ are barred and decreasing, and all symbols of $\gamma$ are unbarred and decreasing.
    So $b_n(T_4\cup\{\aa\ab\})=1+\sum_{i=1}^n 2^{i-1}$, which implies that
    $b_n(T_4\cup\{\aa\ab\})=2^n$.
\item   In a manner similar to the second case, we get that
    $b_n(T_4\cup\{\ab\aa\})=2^n$.
\end{enumerate}
\end{proof}

\begin{proof}[Proof of Equation~\eqref{eq9}, second case]
Let $\alpha\in B_n(T_5)$. As in the proof of the first case of \eqref{eq9}, 
we obtain that either
$\alpha_1=n$ or $\alpha_1=\overline{i}$ for some $i$. In the first case there
are $b_{n-1}(T_5)$ such signed permutations. In the second case, since
$\alpha$ avoids $\ab1$, all the symbols $1,2,\dots,i-1$ are
barred, so that there are $\sum_{i=1}^n
{\binom {n-1} {i-1}}(i-1)!b_{n-i}(T_5)$ such signed permutations. Hence
$$b_n(T_5)=b_{n-1}(T_5)+(n-1)!\sum_{i=0}^{n-1}\frac{b_i(T_5)}{i!}$$
for $n\geq 1$. Let $b'_n=b_n(T_5)/n!$, so that
$n(b'_n-b'_{n-1})=b'_{n-1}-b'_{n-2}$ for all $n\geq 2$. Because of
$b'_1=2$ and $b'_0=1$, we obtain that $b'_n=\sum_{j=0}^n \frac{1}{j!}$, as
claimed in the second part of \eqref{eq9}.
\end{proof}

\begin{corollary}
\label{extu5} We have that $b_n(T_5\cup\{\ab\aa\})=2^n$ for all $n\geq 0$.
\end{corollary}
\begin{proof}
By using the argument in the proof of the formula for $b_n(T_5)$, we get
that
$$b_n(T_5\cup\{\ab\aa\})=b_{n-1}(T_5\cup\{\ab\aa\})+b_{n-1}(T_5\cup\{\ab\aa\}).$$
If this is combined with the initial condition 
$b_1(T_5\cup\{\ab\aa\})=2$, the corollary follows immediately.
\end{proof}

%==============================

%\subsubsection*{\bf Proof \eqref{eq10}.}

\begin{proof}[Proof of Equation~\eqref{eq10}]
Let $\alpha\in B_n(T_6)$. It is easy to see that $\alpha_1=n$ or
$\alpha_1=\overline{i}$ for some $i$. In the first case there are
$b_{n-1}(T_6)$ such signed permutations. In the second case, since
$\alpha$ avoids $\ab\aa$, all the symbols $1,\dots, i-1$
must be unbarred, and since $\alpha$ avoids $12$, $\alpha$ contains
$(i-1,i-2,\dots,1)$. Furthermore, since $\alpha$ avoids $12$ and $1\ab$, we
get that $\alpha=(\overline{i},\beta,i-1,\dots,1)$. Hence there are
$b_{n-i}(T_6)$ such signed permutations for $1\leq i\leq n$. Therefore,
for all $n\geq 3$, we have
    $$b_n(T_6)=b_{n-1}(T_6)+b_{n-1}(T_6)+b_{n-2}(T_6)+\dots+b_0(T_6).$$
This implies that $b_n(T_6)=3b_{n-1}(T_6)-b_{n-2}(T_6)$. If this is
combined with the initial condition
$b_2(T_6)=5$, Equation~\eqref{eq10} follows immediately.
\end{proof}
%==============================
%\subsubsection*{\bf Proof \eqref{eq11}.}
\begin{proof}[Proof of Equation~\eqref{eq11}]
This follows from \cite[Theorem~4.4]{M}.
%Let $\alpha\in B_n(T_7)$ such that $|\alpha_j|=n$. It is easy to see, there
%are one signed permutation if $\alpha_j=n$, $1\leq j\leq n$, and
%if $\alpha_j=\an$, then there are $b_{n-1}(T_7)$, $n-1$, and $0$ signed permutations where $j=1$, $j=2$, and
%$j\geq 3$; respectively. Therefore $b_n(T_7)=b_{n-1}(T_7)+2n-1$ for $n\geq 1$.
%Besides $b_1(T_7)=2$, hence $(11)$ holds.
\end{proof}
%==============================
%\subsubsection*{\bf Proof \eqref{eq12}.}
\begin{proof}[Proof of Equation~\eqref{eq12}]
Let $\alpha\in B_n(T_8)$. If $\alpha_1$ unbarred, then it is easy
to see that $(\alpha_2,\dots,\alpha_n)$ decomposes into two
decreasing subsequences such that all the symbols
$|\alpha_1|+1,\dots,n$ are barred and the other symbols are
unbarred. Hence, there are $2^{n-1}$ such signed permutations. If
$|\alpha_1|<n$ and $\alpha_1$ is barred, then (similarly) there are
$\sum_{i=1}^{n-1} 2^{i-1}$ such signed permutations. Finally, if
$\alpha_1=\an$ then by definition there are $b_{n-1}(T_8)$ such signed
permutations. Everything combined, we have 
$b_n(T_8)=b_{n-1}(T_8)+2\cdot 2^{n-1}-1$. The initial conditions are
$b_2(T_8)=5$, $b_1(T_8)=2$, and $b_0(T_8)=1$, hence \eqref{eq12}
follows.
\end{proof}

\begin{corollary}
\label{extu1} Let $\tau\in\{21,\ab1\}$. Then $b_n(T_8\cup\{\tau\})=2n$
for all $n\geq 1$.
\end{corollary}
\begin{proof}
This is immediate if one uses the argument in the proof of \eqref{eq12}.
\end{proof}
%==============================
%\subsubsection*{\bf Proof \eqref{eq13}.}
\begin{proof}[Proof of Equation~\eqref{eq13}, first case]
Let $\alpha\in B_n(T_9)$. Let $\alpha_i$ be the first unbarred entry
in $\alpha$ ($i$ minimal), and let $\alpha_j$ be the last unbarred
entry in $\alpha$ ($j$ maximal). Since $\alpha$ avoids
$12$, all the symbols which are not barred are decreasing, and
since $\alpha$ avoids $2\aa$ and $\ab1$, we can write
$\alpha=(\beta,\gamma,\delta)$, where $\beta$ is a permutation of the
numbers $\aa,\dots,\overline{i}$, $\gamma=(n-j,n-1-j,\dots,i+1)$,
and $\beta$ is a permutation of the numbers
$\overline{n-j+1},\dots,\an$. Hence $b_n(T_9)=\sum_{j=0}^n
(n-j)!j!$, as claimed in the first part of \eqref{eq13}. 
\end{proof}

\begin{proof}[Proof of Equation~\eqref{eq13}, second case]
Let $\alpha\in B_n(T_{10})$. Let $j$ be maximal such that
$\alpha_j$ is barred. Since $\alpha$ avoids $T_{10}$, we can write
$\alpha=(\beta,\gamma)$, where all symbols of $\beta$ are barred,
all symbols of $\gamma$ are unbarred, and $|\beta_j|>|\gamma_i|$
for all $i$ and $j$. Hence $b_n(T_{10})=\sum_{j=0}^n (n-j)!j!$, as
claimed in the second part of \eqref{eq13}.
\end{proof}
%=======================================================================================
\section{Four signed patterns}
%By taking advantage of Proposition~\ref{sym}, the question of
%determining the values $b_n(T)$ where $T\subset B_2$ and $|T|=4$, for
The $70$ choices of four $2$-letter signed patterns reduce to
the following $16$ cases:
$$\begin{array}{lll}
U_1=\{12,1\ab,\aa2,\aa\ab\};&\ \    U_2=\{12,1\ab,\aa2,21\};&\ \        U_3=\{12,1\ab,\aa2,2\aa\};\\
U_4=\{12,1\ab,\aa2,\ab\aa\};&\ \    U_5=\{12,1\ab,\aa\ab,21\};&\ \      U_6=\{12,1\ab,\aa\ab,2\aa\};\\
U_7=\{12,1\ab,\aa\ab,\ab1\};&\ \    U_8=\{12,1\ab,21,2\aa\};&\ \        U_9=\{12,1\ab,21,\ab1\};\\
U_{10}=\{12,1\ab,21,\ab\aa\};&\ \   U_{11}=\{12,1\ab,2\aa,\ab1\};&\ \   U_{12}=\{12,1\ab,2\aa,\ab\aa\};\\
U_{13}=\{12,1\ab,\ab1,\ab\aa\};&\ \ U_{14}=\{12,\aa\ab,21,\ab\aa\};&\ \ U_{15}=\{12,\aa\ab,2\aa,\ab1\};\\
U_{16}=\{1\ab,\aa2,2\aa,\ab1\}.& &
\end{array}$$

\begin{theorem}
\label{thh4} Given $n$ and a set $T$ of $2$-letter signed
patterns such that $|T|=4$, the value $b_n(T)$ for $n\geq3$
can be determined from one of the following relations, depending on the orbit
(under reversal, barring, complementation) to which $T$ belongs:

\noindent $\begin{array}{ll}
(4.1)  &b_n(U_{14})=0;\\
(4.2)\ &b_n(U_{10})=b_n(U_{15})=2n;\\
(4.3)  &b_n(U_4)=b_n(U_5)=b_n(U_7)=1+{\binom {n+1} 2};\\
(4.4)  &b_n(U_1)=b_n(U_6)=b_n(U_{12})=b_n(U_{13})=2^n;\\
(4.5)  &b_n(U_8)=b_n(U_9)=b_n(U_{16})=2n!;\\
(4.6)  &b_n(U_3)=b_n(U_{11})=\sum_{j=0}^n j!;\\
(4.7)  &b_n(U_2)=n!\left( 1+\sum_{j=1}^n \frac{1}{j}{\binom n
j}^{-1}\right).
\end{array}$
\end{theorem}
\begin{proof}
Equation (4.1) is obvious, while Equation~(4.2) follows by 
Corollary~\ref{extu1}, and Equation~(4.4) holds by 
Corollaries~\ref{extu4} and \ref{extu5}.

To verify (4.3), by Corollaries \ref{extu2} and \ref{extu3} it is
sufficient to prove $b_n(U_7)=1+{\binom {n+1} 2}$. Let $\alpha\in
B_n(U_7)$. If $\alpha_1$ is unbarred, then since $\alpha$ avoids
$\{12,1\ab\}$ we have $\alpha_1=n$, and in this case there are
$b_{n-1}(U_7)$ such signed permutations. If $\alpha_1$ is barred, then
since $\alpha$ avoids $\aa\ab$, all the symbols
$|\alpha_1|+1,\dots,n$ are unbarred and decreasing (since $\alpha$
avoids $12$), and since $\alpha$ avoids $\ab1$ all the symbols
$|\alpha_1|-1,\dots,1$ are barred and decreasing (since $\alpha$
avoids $\aa\ab$). Therefore, since $\alpha$ avoids $1\ab$ and $\ab1$, we
have $\alpha=(\overline{i},n,\dots,i+1,\overline{i-1},\dots,\aa)$.
Thus there are $n$ such signed permutations. This implies the recurrence
$b_n(U_7)=b_{n-1}(U_7)+n$ for $n\geq 1$. If this is combined with the 
initial conditions $b_0(U_7)=1$ and
$b_1(U_7)=2$, Equation~(4.3) follows.

To find $b_n(U_9)$, note that $\alpha\in B_n(U_9)$ has two cases.
The first case occurs when
    the symbol $n$ is unbarred in $\alpha$; since $\alpha$ avoids $\{12,21\}$
    all symbols of $\alpha$ are barred, so there are $n!$ signed permutations.
    The second case occurs when the symbol $n$ is barred in $\alpha$; since $\alpha$
    avoids $\{\ab1,1\ab\}$, all other symbols are barred, so there are $n!$ signed permutations.
    Therefore $b_n(U_9)=2n!$ for $n\geq 1$. Similarly $b_n(U_{16})=2n!$ for $n\geq 1$.
    By Corollary~\ref{extu4} $b_n(U_8)=2n!$ for $n\geq 1$, yielding (4.5).

To find $b_n(U_3)$, we distinguish again between two cases.
Let $\alpha\in B_n(U_3)$.
The first case arises if $\alpha_n$ is unbarred. Then, since $\alpha$
avoids $\{12,\aa2\}$, we must have $\alpha_n=1$.
Thus, there are $b_{n-1}(U_3)$ such signed permutations. 
The second case arises if $\alpha_n$
    is barred. Since $\alpha$ avoids $\{1\ab,2\aa\}$, all symbols of $\alpha$ are
    barred, which implies that there are $n!$ such signed permutations. 
Accordingly,
    $b_n(U_3)=b_{n-1}(U_3)+n!$ for $n\geq 1$. Since $b_0(U_3)=1$, 
it follows that
    $b_n(U_3)=\sum_{j=0}^n j!$.

To find $b_n(U_{11})$, note that for any $\alpha\in B_n(U_{11})$ we
can write $\alpha=(\beta,\gamma)$, where $\gamma=(n,\dots,n-j+1)$
and $\beta$ is a
    permutation of $\aa,\ab,\dots,\overline{n-j}$. Thus 
$b_n(U_{11})=0!+1!+\dots+n!$
    for all $n\geq 0$, as claimed in (4.6).

To verify (4.7), we distinguish again between two cases.
Let $\alpha\in B_n(U_2)$.
Either $\alpha$ contains one unbarred symbol, or all the symbols of
$\alpha$ are barred. In the second case there are $n!$ such signed
permutations. In the first case, let $\alpha=(\beta,i,\gamma)$,
where $\beta$ and $\gamma$ are permutations of subsets of
$\aa,\ab,\dots,\an$.  By definition, we get
that $|\beta_p|>i>|\gamma_j|$, hence there are 
$$\sum_{i=1}^n
(n-i)!(i-1)!=n!\sum_{i=1}^n\frac{1}{i}\binom{n}{i}^{-1}$$ 
such signed
permutations. Thus, Equation~(4.7) is established.
\end{proof}

\begin{corollary}
\label{co1} We have that $b_n(U_7\cup\{21\})=b_n(U_7\cup\{2\aa\})=n+1$ for all
$n\geq 0$.
\end{corollary}
\begin{proof}
Let $\tau\in\{21,2\aa\}$. By the proof of Theorem~\ref{thh4} 
(Case $b_n(U_7)$), we obtain
$b_n(U_7\cup\{\tau\})=b_{n-1}(U_7\cup\{\tau\})+1$. Furthermore,
$b_n(U_7\cup\{\tau\})=n+1$ for $n=0,1,2$, hence the corollary
follows.
\end{proof}
%=======================================================================================
\section{More than four signed patterns}
%By taking advantage of Proposition~\ref{sym}, the question of
%determining the values $b_n(T)$ for $n\geq3$ where $T\subset B_2$
%and $|T|=5$, for
The $56$ choices of five $2$-letter signed patterns reduce to
the following $10$ cases: {\small
$$\begin{array}{lll}
W_1=\{12,1\ab,\aa2,\aa\ab,21\};&\ \     W_2=\{12,1\ab,\aa2,\aa\ab,2\aa\};\ \    & W_3=\{12,1\ab,\aa2,21,2\aa\};\\
W_4=\{12,1\ab,\aa2,21,\ab\aa\};&\ \     W_5=\{12,1\ab,\aa2,2\aa,\ab1\};\ \  & W_6=\{12,1\ab,\aa2,2\aa,\ab\aa\};\\
W_7=\{12,1\ab,\aa\ab,21,2\aa\};&\ \     W_8=\{12,1\ab,\aa\ab,21,\ab1\};\ \  & W_9=\{12,1\ab,\aa\ab,21,\ab\aa\};\\
W_{10}=\{12,1\ab,\aa\ab,2\aa,\ab1\}.&                       &
\end{array}$$}

%With the aid of a computer we have calculated the cardinality of
%$B_n(W_j)$ for $j=1,2,\cdots,10$. From these results we arrived at
%the plausible conjecture of Theorem~\ref{th5} (some of which are
%trivially true).

\begin{theorem}
\label{th5} Given $n$ and a set $T$ of $2$-letter signed patterns
such that $|T|=5$, the value $b_n(T)$ can be determined from one of the
following relations, depending on the orbit (under reversal,
barring, complementation) to which $T$ belongs:

\noindent $\begin{array}{ll}
(5.1)\  & b_n(W_9)=0\ \mbox{for}\ n>2;\\
(5.2)   & b_n(W_4)=3;\\
(5.3)   & b_n(W_1)=b_n(W_2)=b_n(W_6)=b_n(W_7)=b_n(W_8)=b_n(W_{10})=n+1;\\
(5.4)   & b_n(W_5)=1+n!;\\
(5.5)   & b_n(W_3)=(n+1)(n-1)!.
\end{array}$
\end{theorem}
\begin{proof}
Equation~(5.1) follows from the simple observation that no
signed permutation containing more than one unbarred symbol can
avoid both 12 and 21, and similarly no signed permutation
containing more than one barred symbol can avoid both $\aa\ab$ and
$\ab\aa$.

Equation~(5.2) can be established by checking that
$$B_n(W_4)=\{(\aa,\ab,\dots,\an),
(\ab,\dots,\an,1),(\aa,\ab,\dots,\overline{n-1},n)\}.$$

Now we address Equation~(5.3). We found $b_n(W_8)$ and $b_n(W_{10})$ 
already in 
Corollary~\ref{co1}. A permutation in $B_n(W_1)$ can only contain one
unbarred symbol, while {\em all} the
symbols must decrease in absolute value from left to
right in order to avoid $12$, $1\ab$, $\aa2$ and $\aa\ab$.  There are $n+1$
ways to put at most one bar on the all-decreasing permutation. The
remaining three cases are similarly easy to check.

Next we address Equation~(5.4). 
The set $W_5$ contains all four patterns combining one barred
symbol with one unbarred symbol.  This means that any permutation
avoiding $W_5$ must be entirely barred or entirely unbarred.  The
restriction $12$ reduces the possibilities on the ``unbarred side" to
just one, the all-descending permutation; while on the ``barred side"
there is no restriction. Thus we have $n!$ possibilities.
%let $\alpha\in B_n(W_5)$ such that $\alpha_1=s$.
%If $s$ unbarred then, similarly as $3.3$, we have that $\alpha=(n,n-1,\dots,1)$.
%If $s$ barred, then since $\alpha$ avoids $\aa2$ and $\ab1$
%we get all the symbols of $\alpha$ are barred, so there are $(n-1)!$ signed permutations
%for all $s=\aa,\ab,\dots,\an$. Therefore, $b_n(T_5)=n!+1$ for all $n\geq 0$.\\

To verify Equation~(5.5), let $\alpha\in B_n(W_3)$ such that
$|\alpha_j|=1$. If $\alpha_j=1$, then, since $\alpha$ avoids
$\{12,21\}$, all symbols of $\alpha$ except $1$ are barred,
and since $\alpha$ avoids $1\ab$, we get $j=n$. Thus there are
$(n-1)!$ such signed permutations. If $\alpha_j=\aa$, then, since
$\alpha$ avoids $\{\aa2$,$2\aa\}$, all symbols of $\alpha$ are
barred. Thus there are $n!$ such signed permutations. Hence,
$b_n(W_3)=(n+1)(n-1)!$.
\end{proof}

The question of determining the values $b_n(T)$
where $T\subset B_2$ and $|T|=6$, with $28$ possible choices for $T$, 
reduces to the following $8$ cases:
{\small $$\begin{array}{lll}
V_1=\{12,1\ab,\aa2,\aa\ab,21,2\aa\};\, &   V_2=\{12,1\ab,\aa2,\aa\ab,21,\ab\aa\};\, & V_3=\{12,1\ab,\aa2,\aa\ab,2\aa,\ab1)\};\\
V_4=\{12,1\ab,\aa2,21,2\aa,\ab1\};      &   V_5=\{12,1\ab,\aa2,21,2\aa,\ab\aa\};      & V_6=\{12,1\ab,\aa2,2\aa,\ab1,\ab\aa\};\\
V_7=\{12,1\ab,\aa\ab,21,2\aa,\ab\aa\};  &
V_8=\{12,1\ab,\aa\ab,21,\ab1,\ab\aa\}.  &
\end{array}$$}

\begin{theorem}
\label{th6} Given $n$ and set $T$ of $2$-letter signed patterns
such that $|T|=6$, the value $b_n(T)$ for $n\geq2$ can be determined from one
of the following relations, depending on the orbit (under
reversal, barring, complementation) to which $T$ belongs:

\noindent $\begin{array}{ll}
(5.6)\ & b_n(V_2)=b_n(V_7)=b_n(V_8)=0;\\
(5.7)  & b_n(V_1)=b_n(V_3)=b_n(V_5)=b_n(V_6)=2;\\
(5.8)  & b_n(V_4)=n!\mbox{ for all } n\geq 2.
\end{array}$
\end{theorem}
\begin{proof}
Equation (5.6) is an immediate consequence of Equation~(5.1) 
in Theorem~\ref{th5}.

In order to prove Equation (5.7), we verify that
$$\begin{array}{l}
B_n(V_1)=\{(\an,\dots,\ab,\aa), (\an,\dots,\ab,1)\},\\
B_n(V_3)=\{(\an,\dots,\ab,\aa), (n,\dots,2,1)\},\\
B_n(V_5)=\{(\aa,\ab,\dots,\an), (\ab,\dots,\an,1)\},\\
B_n(V_6)=\{((n,\dots,2,1), (\aa,\ab,\dots,\an)\},
\end{array}$$
which is easy to do.

Finally, Equation~(5.8) follows from the argument given in the proof of
Theorem~\ref{th5},
Equation~(5.4).
\end{proof}

Finally, the $8$ choices of seven patterns reduce to $2$, which we
present together with the final case, in which we forbid all eight
patterns:
$$U_1=B_2,\ U_2=\{12,1\ab,\aa2,\aa\ab,21,2\aa,\ab\aa\},\
U_3=\{12,1\ab,\aa2,\aa\ab,21,2\aa,\ab1\}.$$

\medskip
\begin{theorem}\label{th7}
Given $n$ and set $T$ of $2$-letter signed patterns such that
$|T|=7,8$, the value $b_n(T)$ for $n\geq3$ can be determined from one of the
following relations, depending on the orbit (under reversal,
barring, complementation) to which $T$ belongs:

\noindent $\begin{array}{ll}
(5.9)\   &b_n(U_1)=b_n(U_2)=0;\\
(5.10)\ & b_n(U_3)=1.
\end{array}$
\end{theorem}
\begin{proof}
Equation (5.9) follows from the same arguments as
above. Equation~(5.10) follows easily from the fact that
$B_n(U_3)=\{\an,\dots,\ab,\aa\}$.
\end{proof}

{\bf Acknowledgments}. The authors are grateful to the referees
for careful reading of the manuscript. 
The final version of this paper was written
during the first author's (T.M.) stay at Chalmers University of Technology in
G\"oteborg, Sweden. T.M. wants to express his gratitude to Chalmers University 
of Technology for the support.
%=======================================================================================
\begin{thebibliography}{99}
\bibitem[Be]{Be}
{\sc D.A. Beck}, The combinatorics of symmetric functions and
permutation enumeration of the hyperoctahedral group, {\em Discr.\
Math.} {\bf 163} (1997), 13--45.

\bibitem[Bi]{SCb}
{\sc S.C. Billey}, Pattern avoidance and rational smoothness of
Schubert varieties, {\it Adv.\ in Math.} {\bf 139} (1998), 141--156.

\bibitem[BK]{BK}
{\sc S. Billey and T.K. Lam}, Vexillary elements in the
hyperoctahedral group, {\em J. of Alg.\ Combin.} {\bf 8} (1998),
139--152.

\bibitem[BS]{MbRs}
{\sc M. Bona and R. Simion}, A self-dual poset on objects counted
by the Catalan numbers and a type-$B$ analogue, {\it Discr.\ Math.}
{\bf 220} (2000), 35--49.

\bibitem[Br]{Fb}
{\sc F. Brenti}, Combinatorial properties of the Kazhdan--Lusztig
$R$-polynomials for $S_n$, {\it Adv.\ in Math.} {\bf 126} (1997),
21--51.

\bibitem[FK]{FK}
{\sc S. Fomin and A.N. Kirillov}, Combinatorial $B_n$-analogues of
Schubert polynomials, {\it Trans.\ Amer.\ Math.\ Soc.} {\bf 348} 
(1996), 3591--3620.

\bibitem[K]{Kn}
{\sc D.E. Knuth}, {\it The Art of Computer Programming}, 2nd ed.
Addison Wesley, Reading, MA (1973).

\bibitem[LS]{LS}
{\sc V. Lakshmibai and B. Sandhya}, Criterion for smoothness of
Schubert varieties in ${Sl}(n)/B$, {\it Proc.\ Indian Acad.\ Sci.},
{\bf 100} (1990), 45--52.

\bibitem[Mo]{Cm}
{\sc C. Montenegro}, The fixed point non-crossing partition
lattices, manuscript, (1993).

\bibitem[M]{M} {\sc T. Mansour}, Pattern avoidance in coloured
permutations, {\em S\'eminaire Lotharingien de Combinatoire}, {\bf
46} (2001), Article B46g.

\bibitem[MV1]{MV1}
{\sc T. Mansour and A. Vainshtein,} Restricted $132$-avoiding
permutations, {\em Adv.\ Appl.\ Math.}  {\bf 26} (2001), 258--269.

\bibitem[MV2]{MV2}
{\sc T. Mansour and A. Vainshtein,} Avoiding maximal parabolic
subgroups of $S_k$, {Discr.\ Math.\ and Theor.\ Comp.\ Sci.} {\bf 4:1}
(2000), 67--77.

\bibitem[R]{Vr}
{\sc V. Reiner}, Non-crossing partitions for classical reflection
groups, {\it Discr.\ Math.} {\bf 177} (1997), 195--222.

\bibitem[Ri]{Ri}
{\sc J. Riordan}, Combinatorial Identities, John Wiley, New York,
1968.

\bibitem[S]{Rs}
{\sc R. Simion}, Combinatorial statistics on type-$B$ analogues of
noncrossing partitions and restricted permutations, {\it
Electronic J. of Comb.} {\bf 7} (2000), Article~\#R9.

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

\bibitem[T]{Rt}
{\sc R. Tarjan}, Sorting using networks of queues and stacks, {\it
J. Assoc.\ Comput.\ Mach.} {\bf 19} (1972), 341--346.

\bibitem[W]{W}
{\sc J. West}, Permutations with forbidden subsequences and
stack-sortable permutations, Ph.D. thesis, Massachusetts Institute
of Technology, Cambridge (1990).
\end{thebibliography}
\end{document}