\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}
\newcommand{\emptyword}{\varepsilon}

\begin{document}
\def\JJ{\mathfrak L}
\def\II{\mathfrak I}
\def\SS{\mathfrak S}
\def\ttx{\left(\frac{1}{2\sqrt{x}}\right)}
\def\txx{\left(\frac{1}{2x}\right)}
\def\ax{\overline{x}}
\def\send{\mbox{\~{ }}}



\newbox\Adr
\setbox\Adr\vbox{
\begin{center}
{\small LABRI (UMR 5800), Universit\'e Bordeaux 1,
       351 cours de la Lib\'eration, 33405 Talence Cedex, France}\\[4pt]
{\tt guibert@labri.fr}, {\tt toufik@labri.fr}
\end{center}
}

\title{ Restricted $132$-involutions}

\author[Olivier Guibert and Toufik Mansour]
{O. Guibert and T. Mansour \\
[18pt]\box\Adr} 


%===========================================================================
\begin{abstract}

We study generating functions for the number of involutions of length $n$
avoiding (or containing exactly once) $132$ and avoiding
(or containing exactly once) an arbitrary permutation $\tau$
of length $k$. In several interesting cases these generating functions
depend only on $k$ and can be expressed via Chebyshev polynomials of
the second kind. In particular, we show that involutions of length $n$
avoiding both $132$ and $12\ldots k$ are equinumerous with involutions of length $n$ avoiding both $132$ and any {\em extended double-wedge pattern} of length $k$.
We use combinatorial methods to prove several of our results.
\end{abstract}

\maketitle

%===========================================================================
%First page headline in 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 48 \rms (2002), Article~B48a\hfill}
\def\thepage{}
%


\section{Introduction}
The main goal of this paper is to give analogues of enumerative results
on certain classes of permutations characterized by
pattern-avoidance in the symmetric group $\SS_n$. In
$\II_n=\{\pi\in \SS_n : \pi=\pi^{-1}\}$ we identify classes of
restricted involutions with enumerative properties analogous to
results on permutations. More precisely, we study generating functions
for the number of $n$-involutions (that is, involutions of length $n$)
avoiding (or containing exactly once) $132$, and
avoiding (or containing exactly once) an arbitrary pattern $\tau\in\SS_k$.
In the remainder of this
section, we present a brief account of earlier works which
motivated our investigation, we give the basic definitions used throughout
the paper, and we summarize our main results.

Let $\pi\in\SS_n$ and $\tau\in\SS_k$ be two permutations. We say
that $\pi$ {\em contains\/} $\tau$ whenever there exists a subsequence
$1\leq i_1<i_2<\cdots<i_k\leq n$ such that
$(\pi_{i_1},\pi_{i_2},\ldots,\pi_{i_k})$ is order-isomorphic to $\tau$; in
such a context $\tau$ is usually called a {\em pattern\/}. We say
that $\pi$ {\em avoids\/} $\tau$, or is $\tau$-{\em avoiding\/},
whenever no such subsequence exists. The set of all
$\tau$-avoiding $n$-permutations is denoted $\SS_n(\tau)$.
For an arbitrary finite collection of patterns $T$, we say that
$\pi$ avoids $T$ whenever $\pi$ avoids every $\tau\in T$; the
corresponding subset of $\SS_n$ is denoted $\SS_n(T)$. For
example, $562314\in\SS_6(132)$ whereas $51243\not\in\SS_5(132)$
because it contains two subsequences (which are $143$ and $243$)
order-isomorphic to $132$; moreover, $453612\in\SS_6(132,1234)$.

While the case of permutations avoiding a single pattern has
attracted much attention, the case of multiple pattern avoidance
remains less investigated. In particular, a natural next step is
to consider permutations avoiding pairs of patterns
$\tau_1$, $\tau_2$. This problem has been solved completely for
$\tau_1,\tau_2\in\SS_3$ (see \cite{SS}), for $\tau_1\in\SS_3$ and
$\tau_2\in\SS_4$ (see \cite{W}), and for $\tau_1,\tau_2\in\SS_4$
(see \cite{B1,Km} and references therein). Several recent papers
\cite{CW,MV1,Kr,MV2,MV3,MV4} deal with the case $\tau_1\in\SS_3$,
$\tau_2\in\SS_k$ for various pairs $\tau_1,\tau_2$. Another
natural question is to study permutations avoiding $\tau_1$ and
containing $\tau_2$ exactly $r$ times. This problem has been
investigated for certain $\tau_1,\tau_2\in\SS_3$ and $r=1$ in \cite{R},
and for certain $\tau_1\in\SS_3$, $\tau_2\in\SS_k$ in
\cite{RWZ,MV1,Kr,MV3,MV4}. The tools involved in these papers
include continued fractions, Chebyshev polynomials, and Dyck
words. We now recall some of these tools in more detail, along
with the method of generating trees.


%First page headline in LaTeX for S\'eminaire Lotharingien de Combinatoire
%--restoring the headers and pagenumbering
\pagenumbering{arabic}
\addtocounter{page}{1}
\markboth{\SMALL OLIVIER GUIBERT AND TOUFIK MANSOUR}{\SMALL 
RESTRICTED $132$-INVOLUTIONS}
%
%


{\em Chebyshev polynomials of the
second kind\/} (or Chebyshev polynomials, for short) are
defined by
\begin{equation}
U_r(\cos\theta)=\frac{\sin(r+1)\theta}{\sin\theta}
\end{equation}
for $r\geq0$. The Chebyshev polynomials satisfy the
recurrence
\begin{equation}
U_r(t)=2tU_{r-1}(t)-U_{r-2}(t)
\end{equation}
for $r\geq2$ together with $U_0(t)=1$ and $U_1(t)=2t$. Evidently,
$U_r(x)$ is a polynomial of degree $r$ in $x$ with integer
coefficients. Chebyshev polynomials were invented to meet the needs of
approximation theory, but are also widely used in various other
branches of mathematics, including algebra, combinatorics, and
number theory (see \cite{Ri}). The
relationship between restricted permutations and Chebyshev polynomials
was first discovered by Chow and West \cite{CW}, and later by
Mansour and Vainshtein \cite{MV1,MV2,MV3,MV4} and Krattenthaler
\cite{Kr}. These results are related to the rational function
\begin{equation}
R_k(x)=\frac{U_{k-1}\ttx}{\sqrt{x}U_k\ttx}
\label{rk}
\end{equation}
for all $k\geq 1$. For example, $R_1(x)=1$,
$R_2(x)=\frac{1}{1-x}$, and $R_3(x)=\frac{1-x}{1-2x}$. It is easy
to see that for any $k$, $R_k(x)$ is rational in $x$ and satisfies
the following equation (see \cite{MV1,MV3,MV4})
\begin{equation}
R_k(x)=\frac{1}{1-xR_{k-1}(x)}. \label{eqrk}
\end{equation}

Following \cite{Chung} (see also the
Ph.D.-theses \cite{GireThese,GuibertThese,PergolaThese,WestPHD}), a
{\em generating tree} for a set of objects is a tree subject to the
conditions that each object of length $n$ appears once and only
once on a vertex of level $n$, and that the edges correspond to the
manner in which the objects increase. In order to characterize a generating
tree by a {\em succession system}, we associate to each object a
label such that any two nodes have the same label if and only if their
subtrees are isomorphic. Therefore to characterize a generating tree
it suffices to specify the label of the root and a set of
{\em succession rules} explaining how to derive from the label of
a parent the labels of all of its children.

\begin{example}\label{aex1}{\rm (see \cite{W})}
The generating tree of $132$-avoiding permutations can be
characterized by the following succession system:
\begin{itemize}
\item[]  {\bf Root}: $(2)$
\item[]  {\bf Succession rule}: $(t)\leadsto (2),(3),\ldots,(t+1)$.
\end{itemize}
Here $t = 1+|\{\pi_i, 1 \leq i \leq n : \pi_i > \pi_j, \forall i
< j \leq n\}|$ for any $\pi\in\SS_n(132)$,
and the children of a given permutation of length $n$ are the permutations
obtained by inserting an $n+1$ in all locations which do not result in a forbidden pattern.
\end{example}

The Catalan sequence is the sequence
$\{C_n\}_{n\geq0}$, where $C_n=\frac{1}{n+1}\binom{2n}{n}$ is
called the $n$th {\em Catalan number}. The generating function for
the Catalan numbers is given by
\begin{equation}
C(x)=\frac{1-\sqrt{1-4x}}{2x}.\label{cat}
\end{equation}
The Catalan numbers provide a complete answer to the problem of
counting more than $66$ different families of
combinatorial structures (see Stanley \cite[Page~219 and
Exercise~6.19]{St}).
As an example, we consider Dyck words and $132$-avoiding permutations.

Let $L$
be a set of letters; we write $L^*$ to denote the set of all words on $L$.
We write $|w|$ to denote the length of a word $w$, which is the number of letters in $w$.
We write $|w|_l$ to denote the number of occurences of a given letter $l \in L$ in $w$.
We write $\epsilon$ to denote the empty word (which has length $0$).

Let $P_{x,\ax}=\{ w \in \{x,\ax\}^* :
\mbox{ for all } w = w' w'', |w'|_x \geq |w'|_{\ax} \}$
be the set of all {\em Dyck word prefixes}.
%(we consider all possible splits of $w$ into
%a prefix $w'$ concatenated to a suffix $w''$)
For example, $xxxx$,
$xxx\ax$, $xx\ax x$, $xx\ax\ax$, $x\ax xx$, and $x\ax x\ax$ are the
Dyck word prefixes of length $4$. Dyck word prefixes in
$P_{x,\ax}$ of length $n$ are enumerated by the central binomial
coefficient $\binom{n}{[n/2]}$ for all $n \geq 0$.
{\em Dyck words} are Dyck word prefixes $w$ in $\{x,\ax\}^*$ such
that $|w|_x=|w|_{\ax}$. For example, $xx\ax\ax$ and $x\ax x\ax$
are the two Dyck words of length $4$. Dyck words of length $2n$
are enumerated by $C_n$, the $n$th Catalan number.

One of the numerous bijections between $132$-avoiding permutations
and Dyck words can be obtained by characterizing the generating tree for Dyck words
by the same succession system given in Example~\ref{aex1}.  Guibert
\cite[Example~2.1]{GuibertThese} has exhibited such a characterization,
in which the label $t$ of any Dyck word $w$ satisfies $w = x w_1 \overline{x} x w_2 \ax \ldots x w_{t-1} \ax$, where
$w_i$ is a Dyck word for all $1 \leq i < t$.

We also consider words in $\{a,b^2\}^*$
of length $n$, which are enumerated by the $n$th Fibonacci number $F_n$.
Recall that the Fibonacci numbers are given by
$F_0=F_1=1$ and $F_{n}=F_{n-1}+F_{n-2}$, and have the generating function $F(x)=\frac{1}{1-x-x^2}$.

An {\em involution} $\pi$ is a permutation such
that $\pi=\pi^{-1}$;  let $\II_n$ denote the set of all $n$-involutions.
Several authors have given enumerations of sets of involutions which avoid certain patterns. In
\cite{Regev} Regev provided an asymptotic formula for $\II_n(12\ldots k)$
and showed that $\II_n(1234)$ is
enumerated by the $n$th Motzkin number
$\sum_{i=0}^{[n/2]}\binom{n}{2i}C_i$. In \cite{Gessel} Gessel
enumerated $\II_n(12\ldots k)$.
In \cite{GouyouBYoung} Gouyou--Beauchamps
gave an entirely bijective proof of some very nice exact formulas
for $\II_n(12345)$ and $\II_n(123456)$.

Pattern-avoiding involutions have also been linked with other combinatorial objects.
Gire \cite{GireThese} has established a one-to-one correspondence
between 1-2 trees having $n$ edges and
$\SS_n(321,3\overline{1}42)$ (this is the set of $n$-permutations avoiding
patterns $321$ and $231$, except that the latter is allowed
when it is a subsequence of the pattern $3142$). On the
other hand, Guibert \cite{GuibertThese} has established bijections
between 1-2 trees having $n$ edges and each of the sets
$\SS_n(231,4\overline{1}32)$, $\II_n(3412)$, and $\II_n(4321)$
(and therefore with $\II_n$(1234), by transposing the corresponding Young
tableaux obtained by applying the Robinson-Schensted algorithm).
In addition, Guibert \cite{GuibertThese} has established a bijection between
$\II_n(2143)$ (these involutions are sometimes called vexillary involutions) and $\II_n(1243)$.
More recently, Guibert, Pergola, and Pinzani \cite{GPP}
have given a one-to-one correspondence between 1-2 trees having
$n$ edges and vexillary  $n$-involutions. It follows that all these
sets are enumerated by the $n$th Motzkin number. It remains an
open problem to prove the conjecture of Guibert (in \cite{GuibertThese}) that
$\II_n(1432)$ is also enumerated by the $n$th Motzkin number.

In this paper we present a general approach to the study of
$n$-involutions avoiding $132$ (or containing $132$ exactly
once), and avoiding (or containing exactly once) an arbitrary
pattern $\tau\in\SS_k$. As a consequence, we derive all of the
previously known results for this kind of problem, as well as
many new results. We also prove many of our results using
combinatorial (sometimes entirely bijective) methods.

The paper is organized as follows. The case of involutions
avoiding both $132$ and $\tau$ is treated in Section~\ref{sec2}, where we derive
a simple structure for any given $132$-avoiding involution. This
structure gives a complete answer for several interesting cases of
$\tau$, including the cases $\tau = 12\ldots k$ (see Subsection~\ref{subsec21}),
$\tau = 2134\ldots k$ (see Subsection~\ref{subsec23}),
$\tau$ is an extended double-wedge pattern
(see Subsection~\ref{dwp}), and $\tau = (d+1)(d+2)\ldots k12\ldots d$ (see Subsection~\ref{sub2lay}).
In particular, we give a bijection between involutions avoiding
both $132$ and $12\ldots k$ and involutions avoiding both $132$ and
$2134\ldots k$ (see Subsection~\ref{subsec23}).
We also show that involutions
avoiding both $132$ and any extended double-wedge pattern of length $k$
(see Subsection~\ref{dwp})
are equinumerous with involutions avoiding $132$ and $12\ldots k$.

We treat the case of involutions avoiding $132$ and containing $\tau$
exactly once in Section~\ref{sec3}. Here again we start with a
general structure for $132$-avoiding involutions, and then obtain a
complete answer for several particular cases. For instance, we
find a recurrence relation for the generating function for the number of
involutions avoiding $132$ and containing $12\ldots k$ exactly $r$
times (see Theorem~\ref{th12kr}).

In Sections~\ref{sec4} and
\ref{sec5} we consider those involutions which contain $132$ exactly once.
In particular, we establish by bijective arguments that
$n$-involutions
containing $132$ exactly once and having $p$ fixed
points are equinumerous with $(n-2)$-involutions
avoiding $132$ and having $p$ fixed points (see
Theorem~\ref{bij132once-132}).
%=======================================================================================
\section{Avoiding $132$ and another pattern}
\label{sec2} Let $\II_T(n)=|\II_n(132,T)|$,
and let $\II_T(x)=\sum_{n\geq 0}\II_T(n)x^n$ be
the corresponding generating function. The following proposition
is the basis for all of the other results in this section;
it follows immediately from our definitions.
%---------------------------------------------------------------------------
% In(132) : proposition and theorem
%---------------------------------------------------------------------------
\begin{proposition}\label{prom}
For any $\pi\in\II_n(132)$ such that $\pi_j=n$, exactly one of the
following holds:
\begin{enumerate}
\item   if $1\leq j\leq [n/2]$ then $\pi=(\beta,n,\gamma,\delta,j)$, where
    \begin{itemize}
    \item[$(1.1)$] $\beta$ is a $132$-avoiding permutation of the numbers
$n-j+1,\dots,n-2,n-1$,

    \item[$(1.2)$] $\delta\in\SS_{j-1}(132)$ such
    that $\delta\cdot\beta=12\ldots(j-1)$;
    sometimes we will write $\delta^{-1}+n-j$ for $\beta$,

    \item[$(1.3)$] $\gamma$ is a $132$-avoiding involution of the numbers
$j+1,\dots,n-j-1,n-j$;
    \end{itemize}

\item   if $j=n$ then $\pi=(\beta,n)$ where $\beta\in\II_{n-1}(132)$.
\end{enumerate}
\end{proposition}

For example, $\pi = 18 \ 16 \ 17 \ 19 \ 12 \ 13 \ 10 \ 9 \ 8 \ 7 \
11 \ 5 \ 6 \ 14 \ 15 \ 2 \ 3 \ 1 \ 4$ is a $132$-avoiding
involution for which case $(1)$ occurs: $n=19$, $j=4$, $\beta = 18 \
16 \ 17$, $\gamma = 12 \ 13 \ 10 \ 9 \ 8 \ 7 \ 11 \ 5 \ 6 \ 14 \
15$ and $\delta = 2 \ 3 \ 1$. In particular, $\beta = \delta^{-1}
+ 15 = (3\!\!+\!\!15) \ (1\!\!+\!\!15) \ (2\!\!+\!\!15)$.

Observe that applying Proposition~\ref{prom} repeatedly leads
to the following decomposition of a given
$132$-avoiding involution: $$\pi = (\beta_1, \linebreak[0]n_1,
\linebreak[0]\beta_2, \linebreak[0]n_2, \linebreak[0]\ldots,
\linebreak[0]\beta_k, \linebreak[0]n_k, \linebreak[0]\alpha_{k+1},
\linebreak[0]\delta_k, \linebreak[0]j_k, \linebreak[0]\alpha_k,
\linebreak[0]\ldots, \linebreak[0]\delta_2, \linebreak[0]j_2,
\linebreak[0]\alpha_2, \linebreak[0]\delta_1, \linebreak[0]j_1,
\linebreak[0]\alpha_1).$$
Here $n_i$ and $j_i$ form a cycle for
all $1 \leq i \leq k$, the elements of $\beta_i$ form cycles
with the elements of $\delta_i$ for all $1 \leq i \leq k$, and
the elements of $\alpha_i$ are fixed points for $1 \leq i
\leq k+1$.
For the permutation $\pi$ given in the previous example we find that $\beta_1 =
18 \ 16 \ 17$, $n_1 = 19$, $\beta_2 = 12$, $n_2 = 13$,
$\beta_3=\emptyword$, $n_3 = 10$, $\beta_4=\emptyword$, $n_4 = 9$,
$\alpha_5=\emptyword$, $\delta_4=\emptyword$, $j_4 = 8$,
$\alpha_4=\emptyword$, $\delta_3=\emptyword$, $j_3 = 7$, $\alpha_3
= 11$, $\delta_2 = 5$, $j_2 = 6$, $\alpha_2 = 14 \ 15$, $\delta_1
= 2 \ 3 \ 1$, $j_1 = 4$, and $\alpha_1=\emptyword$.

\subsection{Avoiding $132$}\label{subs11}
We will use the following remark.
\begin{remark}\label{genll}
Let $\{y_n\}_{n\geq0}$ and $\{z_n\}_{n\geq0}$ be two sequences, and
denote the corresponding generating functions by $y(x)$ and
$z(x)$ respectively. Then
$$\begin{array}{l}
\sum\limits_{n\geq0}\sum\limits_{j=0}^n y_j z_{2n-2j}x^{2n} =
\frac{1}{2}y(x^2)(z(x)+z(-x));\\
\sum\limits_{n\geq0}\sum\limits_{j=0}^n y_j z_{2n+1-2j}x^{2n+1} =
\frac{1}{2}y(x^2)(z(x)-z(-x)).
\end{array}$$
\end{remark}

As a corollary of Proposition~\ref{prom}, we obtain the generating
function for $|\II_n(132)|$.

\begin{theorem} {\rm (see \cite[Proposition~5]{SS})} The generating
function for the number of $132$-avoiding $n$-involutions is given by
                  $$\II_\varnothing(x)=\frac{1}{1-x-x^2C(x^2)}.$$
\end{theorem}
\begin{proof}
Knuth \cite{Kn} proved that $|\SS_n(132)|=C_n$, where $C_n$ is the $n$th Catalan number,
and by Proposition~\ref{prom} we find that for all $n\geq1$,
   $$\II_\varnothing(n)=\sum_{j=1}^{[n/2]} C_{j-1}\II_\varnothing(n-2j)+\II_\varnothing(n-1).$$
Moreover, $\II_\varnothing(0)=1$.
Restating this in terms of generating functions and using Remark~\ref{genll}, we find that
   $$\II_\varnothing(x)=1+x^2C(x^2)\II_\varnothing(x)+x\II_\varnothing(x).$$
\end{proof}

We can also prove this result bijectively.
%---------------------------------------------------------------------------
% Dyck word prefixes
%---------------------------------------------------------------------------
The number of Dyck word prefixes of length $n$ is the central
binomial coefficient $\binom{n}{[n/2]}$ when $n \geq 0$. Indeed,
for any Dyck word prefix $w\in P_{x,\ax}$ there exist unique Dyck
words $w_i$ such that $w=w_0 x w_1 x \ldots x w_p$,
and $w$ is in bijection
(see the Catalan factorization of any word in $\{x,\ax\}^*$ due to
Chottin and Cori~\cite{CC}) with
    $w_0 \ax w_1 \ax \ldots \ax w_{[(p-1)/2]}
    \ax w_{[(p+1)/2]} x w_{[(p+3)/2]} x \ldots x w_p.$
Therefore Dyck word prefixes of length $n$ are in
bijection with {\em bilateral words} of length $n$ in
$$\{w\in\{x,\ax\}^* : |w|_x=|w|_{\ax} \mbox{ or } |w|_x=|w|_{\ax}-1\},$$
which are trivially enumerated
by $\binom{n}{[n/2]}$.

%---------------------------------------------------------------------------
% Phi : 132 == Dyck prefix
%---------------------------------------------------------------------------

\begin{theorem}
\label{Phi} There is a bijection $\Phi$ between $132$-avoiding
$n$-involutions and Dyck word prefixes in $P_{x,\overline{x}}$ of
length $n$. Moreover, the number of fixed points of the involution
corresponds to the difference between the number of letters $x$
and $\ax$ in the Dyck word prefix.
\end{theorem}
\begin{proof}
Let $\pi\in\II_n(132)$ have $p$ fixed points. By
Proposition~\ref{prom} (and the associated remark), we have
$\pi=\pi'\pi''x\pi'''$ with $|\pi'|=\frac{n-p}{2}$ ($\pi'$ has no
fixed points and consists of cycles with $\pi''$ or $\pi'''$),
$\pi''$ does not contain a fixed point and $\pi(x)=x$ ($x$ is the
first fixed point). We obtain two $132$-avoiding $(n+1)$-involutions
from $\pi$. The first one is given by inserting a fixed point
between $\pi'$ and $\pi''$, and the second one (if and only if $\pi$ has at
least one fixed point) is given by modifying the first fixed point
$x$ by a cycle between $\pi'$ and $\pi''$. All
$132$-avoiding involutions can be obtained exactly once by
applying this rule, starting from $\epsilon$.

Let $w\in P_{x,\overline{x}}$ have length $n$ and satisfy
$|w|_x-|w|_{\ax}=p$. Then $w = w_0 x w_1 x \ldots x w_p$ where $w_i$
are Dyck words for all $0 \leq i \leq p$. We obtain two Dyck word
prefixes of length $n+1$ from $w$: $x w$ and $x w_0 \ax w_1 x
\cdots x w_p$ (if and only if $p>0$). All Dyck word prefixes can be obtained
exactly once by applying this rule, starting from $\epsilon$.
\end{proof}

Clearly, these two generating trees for the $132$-avoiding
involutions and the Dyck word prefixes can be characterized by the
following succession system:
\begin{equation}
\left\{\begin{array}{lcll}
    \multicolumn{4}{l}{(0)} \\
    (0) & \leadsto & (1) & \\
    (p) & \leadsto & (p+1) , (p-1) & \mbox{if } p \geq 1
    \end{array}\right.
\end{equation}

Figure~\ref{figag} shows the bijection $\Phi$ between
$132$-avoiding involutions and Dyck word prefixes (and the labels
of the succession system which characterizes them) for the first
values.

\begin{figure}
\vspace*{-7.00truecm} \hspace*{-2.75truecm}
\epsfxsize=590.0pt %\epsfxsize=330.0pt + 25%
\epsffile{figag.eps} %[xscale=4/5,yscale=4/5]
\vspace*{-7.75truecm} {\caption{The generating trees of the
$132$-avoiding involutions and the Dyck word prefixes, with the
labels of the succession system which characterizes them.}
\label{figag}}
\end{figure}

\begin{corollary}
\label{nb132ptfix} The number of $132$-avoiding $n$-involutions is given by
            $$\binom{n}{[n/2]}.$$
Moreover, the number of $132$-avoiding $n$-involutions
having exactly $p$ fixed points with $0 \leq p \leq n$ (and $p$ is odd if and only if
$n$ is odd) is given by the ballot number
$$\binom{n}{\frac{n+p}{2}}-\binom{n}{\frac{n+p}{2}+1}.$$
\end{corollary}
\begin{proof}
Indeed, the number of Dyck word prefixes $w$
of length $n$ with $|w|_x-|w|_{\overline{x}}=p$ is given by
the ballot number (or Delannoy number \cite{Errera}, or
distribution $\alpha$ of the Catalan number \cite{Kre}).
\end{proof}

In particular, the number of $132$-avoiding $2n$-involutions
without fixed points is given by $C_n$, the $n$th Catalan number.
%---------------------------------------------------------------------------
% In(132,\tau)
%---------------------------------------------------------------------------

The following theorem is the basis for all of the other results in this
section.

\begin{theorem}\label{thg}
Let $T$ be a set of patterns, $T' = \{(\tau_1,\dots,\tau_k,k+1) :
(\tau_1,\dots,\tau_k)\in T\}$, and let $\SS_T(x)$ be the
generating function for $|\SS_n(132,T)|$. Then
\begin{equation}
\II_{T'}(x)=\frac{1}{1-x^2\SS_T(x^2)}+\frac{x}{1-x^2\SS_T(x^2)}\II_T(x).
\label{eq11}
\end{equation}
\end{theorem}
\begin{proof}
Proposition \ref{prom}, together with the definition of $T'$, yields for
$n\geq1$
    $$\II_{T'}(n)=\II_T(n-1)+\sum_{j=1}^{[n/2]} \SS_T(j-1)\II_{T'}(n-2j),$$
where $\SS_T(j-1)=|\SS_{j-1}(132,T)|$.
Hence, in terms of generating functions,
Remark~\ref{genll} yields
    $$\II_{T'}(x)-1=x\II_T(x)+x^2
\SS_T(x^2)\frac{\II_{T'}(x)+\II_{T'}(-x)}{2}+x^2\SS_T(x^2)\frac{\II_{T'}(x)-
\II_{T'}(-x)}{2},$$ which is equivalent to Equation~\ref{eq11}.
\end{proof}

%---------------------------------------------------------------------------
% In(132,12..k)
%---------------------------------------------------------------------------

\subsection{Avoiding $132$ and $12\ldots k$}\label{subsec21}

In this subsection we consider involutions which avoid both $132$ and $12\ldots k$.
We start with an example.

\begin{example}\label{ex1} {\rm (see \cite{SS})}
Let $T'=\{123\}$ and $T=\{12\}$. Equation~\ref{eq11} gives
$$\II_{123}(x)=\frac{1}{1-x^2\SS_{12}(x^2)}+\frac{x}{1-x^2\SS_{12}(x^2)}\II_{12}(x),$$
and by definition we have $\SS_{12}(x)=\II_{12}(x)=\frac{1}{1-x}$;
hence
    $$\II_{123}(x)=\frac{1+x}{1-2x^2}.$$
It follows that $|\II_{123}(n)|=2^{[n/2]}$ for all $n\geq 0$.
Similarly, $\II_{1234}(x)=\frac{1}{1-x-x^2}$, which means that
$|\II_{1234}(n)|=F_n$, the $n$th Fibonacci number.
\end{example}

As an extension of Example~\ref{ex1},
we consider the case $T=\{12\ldots k\}$.

\begin{theorem}\label{th12k}
For all $ k\geq 1$,
    $$\II_{12\ldots k}(x)=\frac{1}{x U_k\left( \frac{1}{2x} \right)}
          \sum_{j=0}^{k-1} U_j\left( \frac{1}{2x} \right).$$
\end{theorem}
\begin{proof}
The theorem is immediate for $k=1$. Let $k\geq 2$; Theorem
\ref{thg} gives
    $$\II_{12\ldots k}(x)=\frac{1}{1-x^2\SS_{12\ldots
(k-1)}(x^2)}+\frac{x}{1-x^2\SS_{12\ldots (k-1)}(x^2)}\II_{12\ldots
(k-1)}(x).$$ On the other hand, the generating function for
$|\SS_n(132,12\ldots(k-1))|$ is
$R_{k-1}(x)$ (see \cite[Theorem~1]{CW}); combining this with
Identity~\ref{eqrk}, we have
    $$\II_{12\ldots k}(x)=R_k(x^2)+xR_k(x^2)\II_{12\ldots (k-1)}(x).$$
Clearly $\II_1(x)=R_0(x)=1$, so by induction
on $k$ and Identity~\ref{rk}, we get the desired result.
\end{proof}

We now give a combinatorial explanation for this result.
%---------------------------------------------------------------------------
% Phi : 132,12..k == Dyck prefix bounded height
%---------------------------------------------------------------------------
Let $\pi$ be a $132$-avoiding involution. Observe that if $\pi$ avoids $12\ldots k$ then
$\pi$ has less than $k$ fixed points. Moreover, if $\pi$ (of length $n$) has
less than $k$ fixed points and is obtained from a $132$-avoiding
involution $\sigma$ of length less than $n$ having $k$ fixed
points (taking $\sigma$ as large as possible) by applying the
rules described for the bijection $\Phi$ given in Theorem~\ref{Phi},
then $\pi$ contains a subsequence $1 2 \ldots k$.  This is because the first
fixed points of $\sigma$ become cycles in $\pi$ such that the
beginning of these cycles and the last remaining fixed points of
$\sigma$ in $\pi$ constitute a subsequence of type $1 2 \ldots
k$. It follows that the succession system
\begin{equation}
\left\{\begin{array}{lcll}
    (0) \\
    (0) & \leadsto & (1) \\
    (p) & \leadsto & (p+1) , (p-1) & 1 \leq p \leq k-2 \\
    (k-1) & \leadsto & (k-2)
    \end{array}\right.
\label{eq22}
\end{equation}
characterizes the generating tree for the involutions which avoid both
$132$ and $1 2 \ldots k$.

It is easy to see that
$|\II_{2n}(132,12\ldots k)|=2|\II_{2n-1}(132, 12\ldots k)|$
for any odd $k$.
Moreover, observe that the set of labels of succession
system~\ref{eq22} is finite, so the corresponding generating
function is rational. More precisely, we immediately deduce from the
succession system~\ref{eq22} that the number of $n$-involutions
avoiding both $132$ and $12\ldots k$ having $p$ fixed points is given by the
$(p+1)$th component of the vector given by $V_k . M_k^n$, where
$V_k = ( \ 1 \ 0 \ 0 \ \dots \ 0 \ )$ is a vector of $k$ elements
and

$$M_k = \left(
\begin{array}{ccccccccc}
    0 & 1 & 0 & 0 & 0 & \cdots & 0 & 0 & 0 \\
    1 & 0 & 1 & 0 & 0 & \cdots & 0 & 0 & 0 \\
    0 & 1 & 0 & 1 & 0 & \cdots & 0 & 0 & 0 \\
    0 & 0 & 1 & 0 & 1 & \cdots & 0 & 0 & 0 \\
      &   &   &   &   & \ddots &   &   &   \\
    0 & 0 & 0 & 0 & 0 & \cdots & 1 & 0 & 1 \\
    0 & 0 & 0 & 0 & 0 & \cdots & 0 & 1 & 0 \\
\end{array} \right)$$
is a $k \times k$ matrix. This is equivalent to an
automaton in which the states are $0, 1, \dots, k-1$ and the
transitions are arrows from $i$ to $i+1$ for $0 \leq i < k-1$ and
from $i$ to $i-1$ for $0<i\leq k-1$.

The bijection $\Phi$ establishes a one-to-one correspondence
between $n$-involutions avoiding both $132$ and $12\ldots k$
having $p$ fixed
points and Dyck word prefixes $w = w_0 x w_1 x \ldots x w_p$
of length $n$ such that $w_i$ is a Dyck word
of height less than $k-p+i$ (that is, $w_i \in P_{x,\overline{x}}$,
$|w_i|_x = |w_i|_{\ax}$, and for all $w_i = w' w''$,
$|w'|_x-|w'|_{\ax}<k-p+i$) for all $0 \leq i \leq p$.
In particular, $2n$-involutions avoiding both $132$ and $12\ldots k$
without fixed points are in bijection by $\Phi$ with Dyck words of length
$2n$ of height less than $k$.

These Dyck words of bounded height were considered by Kreweras
\cite{Kre} and Viennot \cite{V}. In particular, Dyck words of
length $2n$ with height less than $1$, $2$, $3$, $4$, $5$ are
enumerated by $0$, $1$, $2^{n-1}$, $F_{n-2}$,
$\frac{3^{n-1}+1}{2}$ respectively.
We provide some simple bijections for special cases $k=3,4,5$
(related to Example~\ref{ex1}) by generating some well known words
in the same way as involutions which avoid both $132$ and $1 2 \ldots
k$.

First we consider the case $k=3$.
The words of the form
$\{a,b\}^*$ or $a\{a,b\}^*$, which are enumerated by the powers of $2$, can be
generated from the empty word (labeled $(0)$) by the rules:
\begin{equation}
\left\{\begin{array}{lcl}
    w (0) & \leadsto & a w (1) \\
    a w (1) & \leadsto & a w (2) , b w (0) \\
    w (2) & \leadsto & a w (1)
    \end{array}\right.
\end{equation}
Here the words labeled $(0)$ start with $b$ and the words
labeled $(1)$ or $(2)$ start with $a$.
It follows that $\{a,b\}^n$ (respectively $a\{a,b\}^n$) is in
bijection with $\II_{2n}(132,123)$ (respectively
$\II_{2n+1}(132,123)$), which is therefore enumerated by $2^n$ (respectively $2^n$).

Next we consider the case $k=4$ and the words of the form $\{a,b^2\}^\ast$
enumerated by the Fibonacci numbers.
We can generate these from the empty
word (labeled $(0)$) by the rules:
\begin{equation}
\left\{\begin{array}{lcl}
    w (0) & \leadsto & a w (1) \\
    a w (1) & \leadsto & a a w (2) , b^2 w (0) \\
    a w (2) & \leadsto & b^2 w (3) , a a w (1) \\
    w (3) & \leadsto & a w (2)
    \end{array}\right.
\end{equation}
Here the words labeled $(0)$ or $(3)$ start with $b^2$ and
the words labeled $(1)$ or $(2)$ start with $a$.
It follows that $\{a,b^2\}^n$ is in bijection with
$\II_n(132,1234)$, which is therefore enumerated by $F_n$, the $n$th
Fibonacci number.

Finally, let us consider the case $k=5$ and the words of the form
$\{a,b,c\}^\ast a$ or $\{a,b,c\}^\ast a \cup b \{a,b,c\}^\ast a$, which are
enumerated by the powers of $3$.
We can generate these words from the empty
word (labeled $(0)$) by the rules:
\begin{equation}
\left\{\begin{array}{lcl}
    w (0) & \leadsto & a w (1) \\
    w (1) & \leadsto & b w (2) , w (0) \\
    w = b w' = b b^* c w (2) & \leadsto & w (3) , a w' (1) \\
    w = b w' = b b^* a w (2) & \leadsto & c w' (3) , w (1) \\
    w (3) & \leadsto & w (4) , b w (2) \\
    w (4) & \leadsto & c w (3)
    \end{array}\right.
\end{equation}
Here the words labeled $(0)$ or $(1)$ start with $b^\ast a$,
the words labeled $(3)$ or $(4)$ start with $b^\ast c$, and the
words labeled $(2)$ start with $b$ (and have one letter more than
words labeled $(0)$ or $(4)$ at the same level).
It follows that $\{a,b,c\}^n a$ (respectively $\{a,b,c\}^n a \cup b
\{a,b,c\}^n a$) is in bijection with
$\II_{2n+1}(132,12345)$ (respectively $\II_{2n+2}(132,12345)$),\break 
which is therefore enumerated by $3^n$ (respectively $2\cdot 3^n$).

Figure~\ref{fig-forbid} (which is output of the software \verb/forbid/
\cite{GuibertThese}) shows the first values of
$|\II_n(132,12\ldots k)|$ for $3 \leq k \leq 5$
according to the number $p$ of fixed points.

%\vspace*{-3.5truecm}
\begin{figure}[ht]
\begin{center}
Involutions $\pi \in\II_n(132,123)$ according to
$|\{\pi(x)=x\}|=p$ for $1 \leq n \leq 13$
$$\begin{array}{l||*{13}{r}}
  % after \\: \hline or \cline{col1-col2} \cline{col3-col4} ...
p \ \backslash \ n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8  & 9  & 10 & 11
& 12 & 13
\\\hline\hline
2 &    &  1 &    &  2 &    &  4 &    &  8  &     &  16 &     & 32  &    \\
1 & 1  &    &  2 &    &  4 &    &  8 &     &  16 &     & 32  &     & 64 \\
0 &    &  1 &    &  2 &    &  4 &    &  8  &     &  16 &     & 32
&
\\\hline
  &  1 &  2 &  2 &  4 &  4 &  8 &  8 &  16 &  16 &  32 &  32 &  64 & 64
\end{array}$$
Involutions $\pi \in\II_n(132,1234)$ according to
$|\{\pi(x)=x\}|=p$ for $1 \leq n \leq 13$
$$\begin{array}{l||*{13}{r}}
p \ \backslash \ n & 1 & 2 & 3 & 4 & 5 &  6 &  7 &  8 &  9 & 10 &
11 &  12 &  13 \\\hline\hline
3 &   &   & 1 &   & 3 &    &  8 &    & 21 &    &  55 &     & 144 \\
2 &   &  1&   &  3&   &   8&    &  21&    &  55&     &  144&     \\
1 & 1 &   & 2 &   & 5 &    & 13 &    & 34 &    &  89 &     & 233 \\
0 &   & 1 &   & 2 &   &  5 &    & 13 &    & 34 &     &  89 &
\\\hline
  & 1 & 2 & 3 & 5 & 8 & 13 & 21 & 34 & 55 & 89 & 144 & 233 & 377
\end{array}$$
Involutions $\pi \in\II_n(132,12345)$ according to
$|\{\pi(x)=x\}|=p$ for $1 \leq n \leq 15$
$$\begin{array}{l||*{13}{r}}
p \ \backslash \ n & 1 & 2 & 3 & 4 & 5 &  6 &  7 &  8 &  9 &  10 &
11 &  12 &  13 \\\hline\hline
4 &   &   &   &  1&   &   4&    &  13&    &   40&     &  121&     \\
3 &   &   &  1&   &  4&    &  13&    &  40&     &  121&     & 364 \\
2 &   &  1&   &  3&   &   9&    &  27&    &   81&     &  243&     \\
1 &  1&   &  2&   &  5&    &  14&    &  41&     &  122&     & 365 \\
0 &   &  1&   &  2&   &   5&    &  14&    &   41&     &  122&
\\\hline
  &  1& 2 &  3&  6&  9&  18&  27&  54&  81&  162&  243&  486& 729
\end{array}$$
%\vspace*{-3.5truecm}
{\caption{$|\II_n(132, 12\ldots k)|$
for $3 \leq k \leq 5$ according to the number $p$ of fixed
points.} \label{fig-forbid}}
\end{center}
\end{figure}
%\vspace*{-0.5truecm}

Some of the integer sequences we have considered also appear in
\cite{SloanePlouffe}. In particular, the entry M1458 corresponds
to involutions avoiding both $132$ and $12345$ having exactly one
fixed point whereas the entry M2847 corresponds to involutions
avoiding both $132$ and $1234567$ of odd length. Moreover, these
two entries refer to \cite[Tables I and III]{HM};  it will be
interesting to relate $132$-involutions to order-consecutive
partitions.

%---------------------------------------------------------------------------
% In(132,2134..k)
%---------------------------------------------------------------------------

\subsection{Avoiding $132$ and $2134\ldots k$}
\label{subsec23}
In this subsection we consider involutions which avoid both $132$ and $2134\ldots k$.
We begin with an example.

\begin{example}\label{ex2}
Let $T'=\{213\}$ and $T=\{21\}$. Equation~\ref{eq11} gives
$$\II_{213}(x)=\frac{1}{1-x^2\SS_{21}(x^2)}+\frac{x}{1-x^2\SS_{21}(x^2)}\II_{21}(x).$$
Clearly $\SS_{21}(x)=\II_{21}(x)=\frac{1}{1-x}$;
hence
    $$\II_{213}(x)=\frac{1+x}{1-2x^2}.$$
Therefore $|\II_{213}(n)|=2^{[n/2]}$ for all $n\geq 0$.
Similarly, $\II_{2134}(x)=\frac{1}{1-x-x^2}$, so
$|\II_{2134}(n)|=F_n$, the $n$th Fibonacci number.
\end{example}

We can easily give a bijective proof of the fact that
$|\II_{213}(n)|=2^{[n/2]}$.
Any $\pi\in\II_n(132,213)$ is either $12\ldots n$ or
$(n+1-i)(n+2-i)\dots n \pi' 12\dots i$ ($i\geq1$), where $\pi'$ is (upon subtracting $i$ from each element) also an involution avoiding both $132$ and
$213$. We map this recursive decomposition of an involution
$\pi$ avoiding both $132$ and $213$ to a word of nonnegative
integers formed by the successive positive numbers $i$ (first we
treat $\pi$ which gives $i$, next we consider the same
decomposition for $\pi'-i$, and so on) and whose last nonnegative
integer is $[p/2]$, where $p$ is the number of the fixed points in
$\pi$. We also add a symbol $\send$ to the word when $n$ is odd.
This mapping is clearly bijective.

For example, the involutions $\epsilon$, $1$, $12$, $21$, $123$,
$321$, $1234$, $4231$, $3412$ and $4321$ are mapped
to $0$, $0\send$, $1$, $10$, $1\send$, $10\send$, $2$, $11$, $20$
and $110$ respectively. Moreover, the involution $21 \linebreak[0] \ 19
\linebreak[0] \ 20 \linebreak[0] \ 16 \linebreak[0] \ 17
\linebreak[0] \ 18 \linebreak[0] \ 15 \linebreak[0] \ 14
\linebreak[0] \ 9 \linebreak[0] \ 10 \linebreak[0] \ 11
\linebreak[0] \ 12 \linebreak[0] \ 13 \linebreak[0] \ 8
\linebreak[0] \ 7 \linebreak[0] \ 4 \linebreak[0] \ 5
\linebreak[0] \ 6 \linebreak[0] \ 2 \linebreak[0] \ 3
\linebreak[0] \ 1$ in $\II_{21}(132,213)$ is mapped to
$123112\send$, because we first successively consider the element $1$
(with $21$), the elements $2$ and $3$ (with $19$ and $20$), the elements
$4$, $5$ and $6$ (with $16$, $17$ and $18$), the element $7$ (with
$15$), the element $8$ (with $14$) which give us the letters
$1$, $2$, $3$, $1$, $1$, respectively. The five remaining fixed points
(the elements $9$, $10$, $11$, $12$ and $13$) give us the last letter
$2$. Since the length of $\pi$ is odd, we add the symbol
$\send$ to the end.

Thus, involutions in $\II_n(132, 213)$ are mapped onto words $w =
w_1 w_2 \ldots w_{l-1} w_l$ (with an extra symbol $\send$ if $n$
is odd), where $l \geq 1$, $w_j \geq 1$ for all $1 \leq j < l$, $w_l
\geq 0$ and $\sum_{j=1}^{l} w_j =[n/2]$. Trivially, these words are
in bijection with words of the form $w_1 w_2 \ldots w_{l-1} (w_l+1)$, which are
compositions of $[n/2] + 1$ into $l$ positive parts, which are enumerated by
$2^{[n/2]}$.

The case of varying $k$ is more interesting. As an extension of
Example~\ref{ex2}, we consider the case $T=\{2134\ldots k\}$.
As with Theorem~\ref{th12k}, we have

\begin{theorem}\label{th21k}
For all $k\geq 1$,
    $$\II_{2134\ldots k}(x)=\frac{1}{x\cdot U_k\left( \frac{1}{2x} \right)}
          \sum_{j=0}^{k-1} U_j\left( \frac{1}{2x} \right).$$
\end{theorem}

Therefore, Theorems~\ref{th12k} and \ref{th21k} yield
$\II_{12\ldots k}(n)=\II_{2134\ldots k}(n)$. We give a
bijective proof of this result.

\begin{theorem}
\label{12k=2134k} There is a bijection between $n$-involutions
avoiding both $132$ and $12\ldots k$ and $n$-involutions
avoiding both $132$ and $2134\ldots k$, for any $k
\geq 3$.
Moreover, two involutions in bijection have the same number of
fixed points $p$ for all $0 \leq p \leq k-3$.
Involutions which avoid both $132$ and $12\ldots k$ and have $k-2$ or
$k-1$ fixed points correspond to involutions which avoid both
$132$ and $2134\ldots k$ and have $k-2$ or more fixed points.
\end{theorem}
\begin{proof}
To prove this result, we characterize the generating tree
for the involutions avoiding both $132$ and $2134\ldots k$ by
the same succession system \ref{eq22}
established for a generating tree for the involutions avoiding
both $132$ and $12\ldots k$.

If $\pi\in\II_n(132,2134\ldots
k)$ and
%$q=|\{\pi(x)=x\}|$
$q$ is the number of fixed points of $\pi$, then the label $(p)$
of $\pi$ is given by
\begin{equation}
p = \left\{\begin{array}{ll}
q & \mbox{if } q \leq k-3 \\
k-2 & \mbox{if } q \geq k-2 \mbox{ and } (n+k) \bmod 2 = 0 \\
k-1 & \mbox{if } q \geq k-2 \mbox{ and } (n+k) \bmod 2 = 1 \\
\end{array}\right..
\end{equation}
The empty involution has label $(0)$.
We obtain $\sigma\in\II_{n+1}(132,2134\ldots k)$ by
applying the following rules:
\begin{itemize}
\item[(i)]
If $0\leq p \leq k-3$, we have $\pi=\pi'\pi''$ with
$|\pi'|=\frac{n-p}{2}$, and then $\sigma$ is obtained by inserting
a fixed point between $\pi'$ and $\pi''$;  observe $\sigma$ has label $(p+1)$.

\item[(ii)]
If $p=k-2$, we have $\pi=\pi'x\pi''$ with
$\pi(x)=x=\frac{n+4-k}{2}$, and then $\sigma$ is obtained by
inserting a fixed point between $\pi'$ and $x$;  observe $\sigma$ has label $(k-1)$.

\item[(iii)]
If $1\leq p \leq k-3$, we have $\pi=\pi'\pi''x\pi'''$ with
$|\pi'|=\frac{n-p}{2}$, $\pi(x)=x$ and $\pi(y) \neq y$ for all $1
\leq y < x$. Then $\sigma$ is obtained by modifying the first
fixed point $x$ by a cycle starting between $\pi'$ and $\pi''$
(and ending in $x$);  observe $\sigma$ has label $(p-1)$.

\item[(iv)]
If $p=k-1$, we have $\pi=\pi'x(x+1)\pi''$ with
$\pi(x)=x=\frac{n+3-k}{2}$, and then $\sigma$ is obtained by
inserting a fixed point between $\pi'$ and $x$;  observe $\sigma$ has label $(k-2)$.

\item[(v)]
If $p=k-2$, we have $\pi=\pi'(x-j)(x-j+1)\dots(x+j)\pi''$ with $j
\geq 0$, $\pi(x)=x=\frac{n+4-k}{2}$, $|\pi'|=\frac{n-k}{2}+1-j$
and $e>x$ for all $e \in \pi'$. Then $\sigma$ is obtained by
modifying the $2j+1$ fixed points between $\pi'$ and $\pi''$ by
$j+1$ consecutive cycles each of difference (between the index and
the value) $j+1$ that is
$(\pi_1'+1)(\pi_2'+1)\dots(\pi_{\frac{n-k}{2}+1-j}'+1)
(\frac{n-k}{2}+3)(\frac{n-k}{2}+4)\dots(\frac{n-k}{2}+3+j)
(\frac{n-k}{2}-j+2)(\frac{n-k}{2}-j+3)\dots(\frac{n-k}{2}+2)
\pi''$;  observe $\sigma$ has label $(k-3)$.
\end{itemize}
Thus we obtain the following succession system:
\begin{equation}
\left\{\begin{array}{lcll}
    (0) \\
    (0) & \leadsto & (1) \mbox{ by (i) } \\
    (p) & \leadsto & (p+1) \mbox{ by (i) } , (p-1) \mbox{ by (iii) } & 1 \leq p \leq k-3 \\
    (k-2) & \leadsto & (k-1) \mbox{ by (ii) } , (k-3) \mbox{ by (v) } \\
    (k-1) & \leadsto & (k-2) \mbox{ by (iv) }
    \end{array}\right.
\end{equation}
This is equivalent to succession system \ref{eq22}.
\end{proof}

\begin{corollary}
There is a bijection between $\SS_n(132, 12\ldots k)$ and
$\SS_n(132,2134\ldots k)$ for any $k\geq3$.
\end{corollary}
\begin{proof}
By Proposition~\ref{prom}, we deduce that $n$-permutations $\pi$
avoiding both $132$ and $12\ldots k$ (respectively $2134\ldots k$)
are in bijection with $2n$-involutions without fixed points
$(\pi^{-1}+n)\pi=(\pi^{-1}_1+n,\pi^{-1}_2+n,\dots,\pi^{-1}_n+n,\pi_1,\pi_2,\dots,\pi_n)$
avoiding both $132$ and $12\ldots k$ (respectively $2134\ldots k$).
Moreover, a particular case of
Theorem~\ref{12k=2134k} establishes a one-to-one correspondence
between involutions avoiding both $132$ and $12\ldots k$ without
fixed points and involutions avoiding both $132$ and $2134\ldots
k$ without fixed points.
\end{proof}
%---------------------------------------------------------------------------
% In(132,extended double-wedge pattern)
%---------------------------------------------------------------------------

\subsection{Avoiding $132$ and an extended double-wedge pattern}\label{dwp}

In this subsection we construct a wide class of patterns which are equinumerous with involutions which avoid $132$ and either $12\ldots k$ or $2134\ldots k$, which we
studied in Subsections~\ref{subsec21} and \ref{subsec23} respectively.
Following \cite{MV2}, we say that $\tau\in\SS_k$ is a wedge pattern
whenever it can be represented as
$\tau=(\tau^1,\rho^1,\dots,\tau^r,\rho^r)$, where each of
$\tau^i$ is nonempty, $\rho^j$ is an increasing subsequence such
every element of $\rho^j$ is greater than every element of
$\rho^{j+1}$ for all $j$, and
$(\tau^1,\tau^2,\dots,\tau^r)=(s+1,s+2,\dots,k)$. For example,
$645783912$ and $456378129$ are wedge patterns.

For a further generalization of Theorem~\ref{th12k},
Theorem~\ref{th21k}, and \cite[Theorem~2.6]{MV2}, we consider
the following definition. We say that $\tau\in\II_{2l}$ is a {\em
double-wedge\/} pattern whenever there exists a wedge pattern $\sigma\in
\SS_{l-1}$ such that
  $$\tau=(\sigma^{-1}+l,2l,\sigma,l)\ \mbox{or}\ \tau=(\sigma+l,2l,\sigma^{-1},l).$$
For example, the double-wedge patterns in $\SS_{10}$ are
$6789(10)12345$, $7689(10)21345$, $7869(10)31245$,
$7896(10)41235$, $8679(10)23145$, $8796(10)42135$,
$8967(10)34125$,\break $9678(10)23415$, and $9768(10)32415$.

\begin{theorem}\label{dwedge}
For any double-wedge pattern $\tau\in\II_{2l}(132)$,
  $$\II_\tau(x)=\II_{12\ldots(2l)}(x)=\frac{R_l(x^2)}{1-xR_l(x^2)}.$$
\end{theorem}
\begin{proof}
By Proposition~\ref{prom} we have two possibilities for the block
decomposition of an arbitrary $\pi\in\II_n(132)$. Let us write an
equation for $\II_\rho(x)$ where $\rho=(\sigma^{-1},2l,\sigma,l)$.
The contribution of the first decomposition above (using Remark~\ref{genll}) is given by $x\II_\rho(x)$. The contribution of
the second decomposition above (using Remark~\ref{genll})
is given by $x^2\SS_\sigma(x^2)\II_\rho(x)$ where
$\SS_\sigma(x^2)$ is the generating function for
$|\SS_n(132,\sigma)|$. Therefore (with a $1$ for the empty
permutation),
$$\II_\rho(x)=1+x\II_\rho(x)+x^2\SS_\sigma(x^2)\II_\rho(x).$$
On the other hand, Mansour and Vainshtein \cite[Theorem~2.6]{MV2}
have shown that $\SS_\sigma(x)=R_{l-1}(x)$ for any wedge pattern $\sigma$,
so
$$\II_\rho(x)=\frac{1}{1-x-x^2R_{l-1}(x^2)},$$
and using Identity~\ref{eqrk} we have
     $$\II_\rho(x)=\frac{R_l(x)}{1-xR_l(x^2)}.$$
Using the identity
$$\sum_{j=0}^{2l}U_j(t)=\frac{U_{2l}(t)U_{l-1}(t)}{U_l(t)-U_{l-1}(t)}$$
together with Theorem~\ref{th12k}, we now obtain
$\II_\rho(x)=\II_{12\ldots (2l)}(x)$.
\end{proof}

We say that $\tau\in\II_k$ is
an {\em extended double-wedge pattern} whenever $\tau=\tau'\tau''$ ,where
$\tau'$ is a double-wedge pattern and
$\tau''=(|\tau'|+1,|\tau'|+2,\ldots,k)$.
%that is a double-wedge pattern extended by fixed points.

\begin{theorem}\label{extwedge}
For any extended double-wedge pattern $\tau$ of length $k$, where $k \ge 2l$,
the generating function for
$|\SS_n(132,\tau)|$ is given
by $R_{k}(x)$.
\end{theorem}
\begin{proof}
By definition we have
either $\tau=(\sigma^{-1}+l,2l,\sigma,l,2l+1,2l+2,\ldots,k)$
or $\tau=(\sigma+l,2l,\sigma^{-1},l,2l+1,2l+2,\ldots,k)$
where $\sigma$ is a wedge pattern in $\SS_{l-1}(132)$.
Suppose $\tau=(\sigma^{-1}+l,2l,\sigma,l)$ and let $\SS_\tau(x)$ be
the generating function for
$|\SS_n(132,\tau)|$. By \cite[Theorem~1]{MV2} we have
$$\SS_\tau(x)=1+x(\SS_\tau(x)-\SS_{\sigma^{-1}}(x))\SS_\sigma(x)+x\SS_{\sigma^{-1}}(x)
\SS_\tau(x).$$ On the other hand, by \cite[Theorem~2.6]{MV2}, and since
$\sigma$ is a wedge pattern in $\SS_{l-1}(132)$, we have
$\SS_{\sigma^{-1}}(x)=\SS_\sigma(x)=R_{l-1}(x)$. Therefore, by use
of Identity~\ref{eqrk} we get
$$\SS_\tau(x)=\frac{R_l(x)(1-xR_{l-1}(x)R_l(x))}{1-xR_l^2(x)},$$
and use of the identity
    $$\frac{R_l(x)(1-xR_{l-1}(x)R_l(x))}{1-xR_l^2(x)}=R_{2l}(x)$$
together with \cite[Theorem~1]{MV2}, we have
$\SS_{(\tau,2l+1,\ldots,k)}(x)=R_k(x)$.
The proof in the other case is similar.
\end{proof}

As a corollary of Theorem~\ref{dwedge} we have the following result.

\begin{theorem}\label{idwedge}
For any extended double-wedge pattern $\tau\in\II_k(132)$,
    $$\II_{\tau}(x)=\II_{12\ldots k}(x).$$
\end{theorem}
\begin{proof}
Observe that if $\SS_\beta(x)=\SS_\gamma(x)$ and
$\II_\beta(x)=\II_\gamma(x)$ then Theorem~\ref{thg} yields
$\II_{\tau'}(x)=\II_{\beta'}(x)$ and \cite[Theorem~1]{MV2} yields
$\SS_{\tau'}(x)=\SS_{\rho'}(x)$, where
$\tau'=(\tau_1,\dots,\tau_p,\break p+1)$ and
$\rho'=(\rho_1,\dots,\rho_p,p+1)$ are two patterns in $\SS_{p+1}$.
Arguing by induction on $p$ and using Theorems~\ref{dwedge} and \ref{extwedge}, we obtain the desired result.
\end{proof}

It would be interesting to find bijective proofs of Theorems~\ref{dwedge} and \ref{idwedge}.
%---------------------------------------------------------------------------
% In(132,(d+1)(d+2)..k12..d)
%---------------------------------------------------------------------------

\subsection{Avoiding $132$ and $(d+1)(d+2)\ldots k12\ldots
d$}\label{sub2lay}

In this subsection we consider involutions which avoid $132$ and $(d+1)(d+2)\ldots k12\ldots d$.

\begin{example}\label{ex22}
By Proposition~\ref{prom} we find that for $n\geq1$,
    $$\II_{231}(n)=n;\quad  \II_{321}(n)=[n/2]+1.$$
\end{example}

We remark that the $n$-involutions which avoid both $132$ and
$231$ are the permutations of the form $i (i-1) \ldots 1 (i+1) (i+2) \ldots n$, $1 \leq
i \leq n$, and that the $n$-involutions which avoid both $132$ and $321$
are the permutations of the form $(i+1) (i+2) \ldots (2i) 1 2 \ldots i (2i+1) (2i+2) \ldots n$, $0 \leq i \leq [n/2]$.

As an extension of Example~\ref{ex22}, we consider the case
$T=\{<k,d>\}$, where $<k,d>=(d+1,d+2,\ldots,k,1,2,\ldots,d)$.

\begin{theorem}\label{thkd}
For any $k\geq 2$, $k/2\geq d\geq 1$,
    $$\II_{<k,d>}(x)=\frac{1}{x(U_d(t)-U_{d-1}(t))}\left[
U_{d-1}(t)+\frac{U_{k-2d-1}(t)}{U_{k-d}(t)U_{k-d-1}(t)}\sum_{j=0}^{k-d-1}
U_j(t)\right],\quad t=\frac{1}{2x}.$$
\end{theorem}
\begin{proof}
By Proposition~\ref{prom}, we have two possibilities for the block
decomposition of an arbitrary $\pi\in\II_n(132)$. Let us use
Remark~\ref{genll} to write an equation for $\II_{<k,d>}(x)$. The
contribution of the second decomposition above is
$x\II_{<k,d>}(x)$. The contribution of the first decomposition
above is given in two cases. First, if $\gamma$ avoids $12\ldots
(k-d)$, then $\beta$ and $\delta$ avoid $12\ldots(k-d-1)$, so we
have $x^2R_{k-d-1}(x^2)\II_{12\ldots(k-d)}(x)$, as in
Theorem~\ref{th12k}. Second, if $\gamma$ contains $12\ldots
(k-d)$ at least once then $\beta$ and $\delta$ avoid $12\ldots
(d-1)$, so we have
$x^2R_{d-1}(x^2)(\II_{<k,d>}(x)-\II_{12\ldots(k-d)}(x))$.
Here we have used the fact that the
generating function for those permutations in
$\II_n(132,<k,d>)$ which contain $12\ldots(k-d)$ at least once is
given by $\II_{<k,d>}(x)-\II_{12\ldots(k-d)}(x)$. We now have
\begin{multline*}
\II_{<k,d>}(x)=1+x\II_{<k,d>}(x)+x^2R_{k-d-1}(x^2)\II_{12\ldots(k-d)}(x)\\
+
x^2R_{d-1}(x^2)(\II_{<k,d>}(x)-\II_{12\ldots(k-d)}(x)),
\end{multline*} 
which means that
$$\II_{<k,d>}(x)=\frac{1}{1-x-x^2R_{k-d-1}(x^2)}\cdot(1+x^2\II_{12\ldots
(k-d)}(x)(R_{k-d-1}(x^2)-R_{d-1}(x^2))).$$ Hence, by
Identity~\ref{eqrk} together with the identity
$R_a(x)-R_b(x)=\frac{U_{a-b-1}(t)}{\sqrt{x}U_a(t)U_b(t)}$, we get
the desired result.
\end{proof}

\begin{example}
\label{ex3412} For all $n \ge 1$,
$|\II_{3412}(n)|=F_n$, the $n$th Fibonacci number.
\end{example}

We now give a bijective proof of Example~\ref{ex3412}. Any
$\pi\in\SS_n(132,3412)$ can be written $i\pi'
1(i+1)(i+2)\cdots n$, where $1\leq i\leq n$ and $\pi'$ is (upon subtracting 1 from each element) also
an involution avoiding both $132$ and $3412$. We map $\pi$ to a word in
$\{a, b^2\}^\ast$ of length $n$ in the following way: $a$ if $\pi_i=i$,
$b^2$ if $\pi_i<i$ and nothing if $\pi_i>i$ for all $1\leq i\leq
n$. This mapping is clearly bijective.

%---------------------------------------------------------------------------
% In(132,\tau1,\tau2)
%---------------------------------------------------------------------------

\subsection{Avoiding $132$ and two other patterns}

In this subsection we consider involutions which avoid 132 and two other patterns.
We begin with an example.

\begin{example}\label{ex3}
Let $T'=\{123,213\}$ and $T=\{12,21\}$. Equation~\ref{eq11}
gives
$$\II_{123,213}(x)=\frac{1}{1-x^2\SS_{12,21}(x^2)}+\frac{x}{1-x^2\SS_{12,21}(x^2)}
\II_{12,21}(x),$$
and $\SS_{12,21}(x)=\II_{12,21}(x)=1+x$; hence
    $$\II_{123,213}(x)=\frac{1+x+x^2}{1-x^2-x^4}$$
which means that $\II_{123,213}(2n)=F_{n+1}$ and
$\II_{123,213}(2n+1)=F_{n}$ for all $n\geq 0$, where $F_m$ is the
$m$th Fibonacci number.
\end{example}

We prove Example~\ref{ex3} by a bijective argument, in which we distinguish the cases of odd length from those of even length.

Any $\pi\in\II_{2n+1}(132,123,213)$ can be written
either $(2n+1) \pi' 1$ or $(2n) (2n+1) \pi'' 2 1$ or $1$ (if
$n=0$), where $\pi'$ (upon subtracting 1 from each element) and $\pi''$ (upon subtracting 2 from each element) are also involutions avoiding
$132$, $123$ and $213$ . We map $\pi$ to a word of $\{a,b^2\}^*$ of
length $n$ in the following way: $a$ if $\pi_i=2n+2-i$, $b^2$ if
$\pi_i=2n+1-i$, and nothing if $\pi_i=2n+3-i$ for all $1\leq i\leq
n$. This mapping is clearly bijective.

Any $\pi\in\II_{2n}(132,123,213)$ can be written either $(2n) \pi'
1$ (this case includes $2 1$, when $n=1$) or $(2n-1) (2n) \pi'' 2 1$ or $1
2$ (if $n=1$) or the empty involution (if $n=0$), where $\pi'$ (upon subtracting 1 from each element)
and $\pi''$ (upon subtracting 2 from each element) are also involutions avoiding $132$, $123$ and $213$. We
map $\pi$ to a word of $\{a,b^2\}^*$ of length $n+1$ in the following way:
$a$ if $\pi_i=2n+1-i$ for all $1\leq i\leq n-1$, $b^2$ if
$\pi_n=n+1$, $b^2$ if $\pi_i=2n-i$ for all $1\leq i\leq n-2$,
$b^2a$ if $\pi_{n-1}=n+1$, and $aa$ if $\pi_n=n$. Moreover, the
empty involution is mapped to $a$. This mapping is clearly
bijective.

Using Proposition~\ref{prom} and Theorem~\ref{thg} it is easy to
see the following.

\begin{corollary}\label{th12k213}
For all $k\geq 1$,
    $$\II_{12\ldots k, 213}(x)=\II_{(k-1)\ldots 21k,123}(x)=\frac{1+x+x^2+\cdots+x^{k-1}}{1-x^2-x^4-\cdots-x^{2(k-1)}}.$$
\end{corollary}

\begin{example}
\label{ex312decr} Using Proposition~\ref{prom} it is easy to see,
for all $n\geq 1$,
$$\II_{213,321}(n)=\frac{1}{2}(3+(-1)^n)\qquad\mbox{and}\qquad
\II_{213,4321}(n)=[n/2]+1.$$
\end{example}

Observe that the $n$-involutions
avoiding $132$, $213$, and $321$ which are not equal to $1 2 \ldots n$ are the permutations of the form
$(m+1) (m+2) \ldots n 1 2 \ldots m$, where $n=2m$ and $m \geq 1$. Similarly, the $n$-involutions avoiding $132$, $213$, and $4321$
are the permutations of the form $(n+1-i) (n+2-i) \dots n (i+1) (i+2) \dots (n-i) 1 2 \dots i$, where $0 \leq i \leq [n/2]$.
%=======================================================================================
\section{Avoiding $132$ and containing another pattern}
\label{sec3} Let $\II_\tau^r(n) = |\{ \pi\in\II_n(132) :
\pi \mbox{ contains } \tau \mbox{ exactly } r \mbox{ times} \}|$ and let
$$\II_\tau^r(x)=\sum_{n\geq0}\II_\tau^r(n)x^n$$ 
be the corresponding
generating function. We begin with an example.

\begin{example}\label{exbb0}
By Proposition~\ref{prom} it is easy to see
$$\II_{12}^1(x)=x\II_{1}^1(x)+x^2\II_{12}^1(x),$$
which means that $\II_{12}^1(x)=\frac{x^2}{1-x^2}$.
\end{example}

As extension of Example~\ref{exbb0}, we consider the case
$\tau=12\ldots k$.

\begin{theorem}\label{th1_12}
For all $k\geq 1$,
    $$\II_{12\ldots k}^{1}=\frac{1}{U_k\left( \frac{1}{2x} \right)}.$$
\end{theorem}
\begin{proof}
By Proposition~\ref{prom}, for all $n\geq k$ we have
    $$\II_{12\ldots k}^{1}(n)=\II_{12\ldots (k-1)}^{1}(n-1)+\sum_{j=1}^{[n/2]}
\SS_{12\ldots (k-1)}(j-1)\II_{12\ldots k}^{1}(n-2j),$$
where $\SS_{12\ldots k}(j-1)=|\SS_{j-1}(132,12\ldots k)|$.
Moreover, $\II_{12\ldots k}^{1}(n)=0$
for all $n\leq k-1$, and $\II_{12\ldots k}^{1}(k)=1$. As in the
proof of Theorem~\ref{th12k}, we have
    $$\II_{12\ldots k}^{1}(x)=xR_{k}(x^2)\II_{12\ldots (k-1)}^{1}(x).$$
Now the result follows by induction on $k$, with the initial condition $\II_1^{1}(x)=x$.
\end{proof}

We also have explicit formulas for
the cases $\tau=2134\dots k$ and $\tau=23\dots k1$.

\begin{theorem}
For all $k\geq 2$,
    $$\II_{2134\ldots k}^{1}=\frac{1-x^2}{U_k\txx},
    \quad
    \II_{23\ldots k1}^1(x)=\frac{x^3}{(1-x)U_{k-2}\txx}.$$
\end{theorem}

More generally, using Proposition~\ref{prom} and an argument similar to that given in the
proof of Theorem~\ref{th12k}, we obtain the following result.

\begin{theorem}\label{th12kr}
For any $k,r\geq 1$,
    $$\II_{12\ldots k}^{r}(x)=x\II_{12\ldots (k-1)}^{r}(x)+x^2\sum_{2a+b=r}
\SS_{12\ldots (k-1)}^{a}(x^2)\II_{12\ldots k}^{b}(x),$$ where
$\SS_{12\ldots (k-1)}^{a}(x)$ is the generating function for the
number of $n$-permutations containing $12\ldots (k-1)$
exactly $a$ times.
\end{theorem}

Krattenthaler~\cite{Kr} has found an explicit formula for the
generating function $\SS_{12\ldots k}^{r}(x)$ for the number of
$132$-avoiding $n$-permutations containing $12\ldots k$ exactly $r$
times, so Theorem~\ref{th12kr} yields a recurrence for
$\II_{12\ldots k}^{r}(x)$. Using Krattenthaler's result \cite{Kr} (see
also \cite[Theorem~3.1]{MV1}), we obtain the following recurrence for
$\II_{12\ldots k}^{r}(x)$ where $r=1,2,\dots,2k$.

\begin{theorem}
Let $k\geq 1$; for all $r=1,2,\dots,2k$,
$$\II_{12\ldots k}^{r}(x)=x\II_{12\ldots (k-1)}^r(x)+x^2R_{k-1}(x^2)\II_{12\ldots
k}^{r}(x)+\sum_{2a+b=r,\ a>0} x^{a+1}\II_{12\ldots
k}^{b}(x)\frac{U_{k-1}^{a-1}\txx}{U_k^{a+1}\txx}.$$
\end{theorem}

When $r = 2$, the above Theorem yields an explicit formula for
$\II_{12\ldots k}^{2}(x)$.

\begin{corollary}
For all $k\geq 1$,
$$\II_{12\ldots k}^{2}(x)=\frac{1}{U_k\txx}\sum_{i=1}^k
\frac{\sum_{j=0}^{k-i} U_j\txx}{U_{k+1-i}\txx U_{k-i}\txx}.$$
\end{corollary}
%=================================================================
\section{Containing $132$ once and avoiding another pattern}
\label{sec4}

In this section we consider involutions which contain 132 exactly once and avoid another pattern.
We first relate involutions containing $132$ exactly once to
$132$-avoiding involutions.

\begin{theorem}
\label{bij132once-132} There is a bijection $\Psi$ between
$n$-involutions containing $132$ exactly once having $p$
fixed points ($1\leq p\leq n$) and
$132$-avoiding $(n-2)$-involutions having $p$ fixed points.
\end{theorem}

\begin{proof}
Let $\pi=\pi'xz\pi''y\pi'''$ with $\pi(x)=x$, $\pi(y)=z$ and
$1+x=y<z$ be an $n$-involution containing $132$ exactly once,
where the subsequence $xzy$ is of type 132 and $\pi$ has $p$
fixed points.  We replace the subsequence $xzy$ with a fixed
point between $\pi''$ and $\pi'''$ in order to obtain a
$132$-avoiding $(n-2)$-involution
having $p$ fixed points. Note that the only way to have
exactly one $132$ subsequence in $\pi$ is to have a cycle with
a fixed point just
to its left. Moreover, we must have $y=x+1$ in order to
forbid another $132$
subsequence, cycles are only allowed from $\pi'$ to $\pi''$ and
from $\pi'$ to $\pi'''$ (and not from $\pi''$, $\pi'$, $\pi''$,
$\pi'''$ respectively to $\pi'''$, $\pi'$, $\pi''$, $\pi'''$)
and fixed points can only be into $\pi'''$. Clearly the
involution we obtain avoids $132$ and in particular, the fixed
point $z-2$ cannot be a part of a $132$-subsequence because it
cannot be the $3$ or $2$ (all the elements on its left are greater
than it) and it cannot be the $1$ (there is no cycle starting on
its right).

Let $\sigma = \sigma' \sigma'' \sigma''' t \sigma''''$ be an involution with $p$ fixed points, where
$\sigma(t)=t$ and $\sigma(i)\neq i$ for all $1\leq i< t$ (that is,
$t$ is the first fixed point), $\sigma'(i)>t$ for all $1\leq i
\leq |\sigma'|$ (all the elements of $\sigma'$ are cycles ending
within $\sigma''''$), $\sigma''(i) \in [|\sigma'\sigma''|+1,t-1]$
for all $1 \leq i \leq |\sigma''|$ and $\sigma'''(i) \in
[|\sigma'|+1,|\sigma'\sigma''|]$ for all $1 \leq i \leq
|\sigma'''|$ ($\sigma''\sigma'''$ consists entirely of
cycles from $\sigma''$ to $\sigma'''$).
We modify the fixed
point $t$ by inserting a cycle starting between $\sigma''$ and $\sigma'''$
(and ending between $\sigma'''$ and $\sigma''''$) and by adding a
fixed point just to the right of $\sigma''$ in order to obtain an
involution of length $n$ containing $132$ once and having $p$ fixed
points. Proposition~\ref{prom} leads immediately to the
decomposition of $\sigma$. The involution we obtain contains $132$
exactly once, in the form of the subsequence we modify and insert. There
is no other $132$-subsequence and in particular, the fixed point
inserted and the start of the new cycle cannot be the $3$ or $2$
of another $132$-subsequence (all the elements on their left are
greater than them), the fixed point inserted and the start of the
new cycle and the end of the new cycle cannot be the $1$ of
another $132$-subsequence (there is no cycle starting on their
right), the end of the new cycle cannot be the $3$ of another
$132$-subsequence (because in that case the $2$ must be connected
to $\sigma'$ and the $1$ must be the fixed point inserted or an
element of $\sigma'''$ that forms a $231$-subsequence), and the
end of the new cycle cannot be the $2$ of another
$132$-subsequence (because in that case the $1$ must be an element
of $\sigma'\sigma''$ or the start of the new cycle and the $3$
must be the fixed point inserted or an element of $\sigma'''$ that
forms a $312$-subsequence).

So we have established a bijection between an involution $\pi$
containing $132$ once and a $132$-avoiding involution $\sigma$ of the forms given above,
where $t=z-2$, $\pi'$ corresponds to $\sigma'\sigma''$,
$\pi''=\sigma'''$ and $\pi'''$ corresponds to $\sigma''''$.
\end{proof}

For example, the involution $22 \linebreak[0] \ 19 \linebreak[0] \
17 \linebreak[0] \ 18 \linebreak[0] \ 16 \linebreak[0] \ 12
\linebreak[0] \ 11 \linebreak[0] \ 13 \linebreak[0] \ {\bf 9}
\linebreak[0] \ {\bf 14} \linebreak[0] \ 7 \linebreak[0] \ 6
\linebreak[0] \ 8 \linebreak[0] \ {\bf 10} \linebreak[0] \ 15
\linebreak[0] \ 5 \linebreak[0] \ 3 \linebreak[0] \ 4
\linebreak[0] \ 2 \linebreak[0] \ 20 \linebreak[0] \ 21
\linebreak[0] \ 1 \linebreak[0] \ 23$, which contains $132$ exactly
once (the subsequence $9$~$14$~$10$), corresponds to the
$132$-avoiding involution $20 \linebreak[0] \ 17 \linebreak[0] \
15 \linebreak[0] \ 16 \linebreak[0] \ 14 \linebreak[0] \ 10
\linebreak[0] \ 9 \linebreak[0] \ 11 \linebreak[0] \ 7
\linebreak[0] \ 6 \linebreak[0] \ 8 \linebreak[0] \ {\bf 12}
\linebreak[0] \ 13 \linebreak[0] \ 5 \linebreak[0] \ 3
\linebreak[0] \ 4 \linebreak[0] \ 2 \linebreak[0] \ 18
\linebreak[0] \ 19 \linebreak[0] \ 1 \linebreak[0] \ 21$.

\begin{corollary}
The number of $n$-involutions containing $132$ exactly once
which have $p$ fixed points, $1 \leq p \leq n$, is the ballot
number
$$\binom{n-2}{\frac{n+p}{2}-1}-\binom{n-2}{\frac{n+p}{2}}.$$
Moreover, the number of $n$-involutions containing $132$ exactly once
is given by
            $$\binom{n-2}{\left[\frac{n-3}{2} \right]}.$$
\end{corollary}
\begin{proof}
This result is immediate from the bijection $\Psi$ of
Theorem~\ref{bij132once-132} and Corollary~\ref{nb132ptfix}. In
fact, the number of $n$-involutions containing $132$ exactly once
is $|\II_{n-2}(132)|$
if $n$ is odd and \\
$|\{ \pi \in \II_{n-2}(132) \mbox{ having more than one fixed point } \}|$ if $n$ is even.
\end{proof}

Of course, some of the following results can immediately be
obtained from the bijection $\Psi$ of Theorem~\ref{bij132once-132} and
the results of Section~\ref{sec2}.

Let $\JJ_\tau(n)$ be the number of $\tau$-avoiding $n$-involutions
containing $132$ exactly once, and let
$\JJ_\tau(x)=\sum_{n\geq 0}\JJ_\tau(n)x^n$ be the corresponding
generating function. The following proposition, which is immediate from our definitions,  is the basis for all of
the other results in this section.

\begin{proposition}\label{prom2}
Suppose $\pi\in\II_n$ contains $132$ exactly once and has $\pi_j=n$.
Then exactly one of the following holds.
\begin{enumerate}
\item   $\pi=(\alpha,n)$ where $\alpha\in\II_{n-1}$
contains $132$ exactly once;

\item   $\pi=(\alpha,n,\beta,\gamma,j)$ where $1\leq j\leq n/2$,
        $\gamma={\alpha}^{-1}$, $\alpha$ is an $132$-avoiding permutation
        of the numbers $n-1,n-2,\dots,n-j+1$,
        and $\beta$ is an involution of the numbers
        $j+1,j+2,\dots,n-j$ which contains $132$ exactly once;

\item   $\pi=(\alpha,m,2m+1,\gamma,m+1)$ where $n=2m+1$, $\gamma={\alpha}^{-1}+m+1$,
        and $\gamma\in\SS_{m-1}(132)$.
\end{enumerate}
\end{proposition}

For example, for $n=5$, the only three involutions containing
$132$ exactly once are $13245$, $52431$ and $42513$.
These illustrate the cases $(1)$, $(2)$ and $(3)$ of Proposition~\ref{prom2}, respectively.

We can use Proposition~\ref{prom2} to find the generating function for the number of
$n$-involutions containing $132$ exactly once.

\begin{theorem}\label{thcc1} The generating function for the
number of $n$-involutions containing $132$ exactly once is
given by
    $$\JJ_\varnothing(x)=\frac{x^3C(x^2)}{1-x-x^2C(x^2)}.$$
\end{theorem}
\begin{proof}
By Proposition~\ref{prom2}, we have three possibilities for the
block decomposition of an arbitrary $\pi\in\II_n$ containing $132$
exactly once. Let us use Remark~\ref{genll} to write an equation
for $\JJ_\varnothing(x)$. The contribution of the first
decomposition above is $x\JJ_\varnothing(x)$, the contribution of
the second decomposition above is $x^2C(x^2)\JJ_\varnothing(x)$,
and the contribution of the third decomposition above is
$x^3C(x^2)$. Hence
$\JJ_\varnothing(x)=x\JJ_\varnothing(x)+x^2C(x^2)\JJ_\varnothing(x)+x^3C(x^2)$.
\end{proof}

\begin{example}\label{excc1}
By Proposition \ref{prom2}, $|\JJ_{123}(n)|=2^{(n-3)/2}$ when $n$ is odd and $|\JJ_{123}(n)|=0$ otherwise.
In addition, $|\JJ_{1234}(n)|=F_{n-3}$, the $(n-3)$th Fibonacci
number, and $\JJ_{12345}(n)=3^{[(n-3)/2]}$.
\end{example}

Again, the case of varying $k$ is more interesting. As an
extension of Example \ref{excc1}, we consider the case
$\tau=12\ldots k$.

\begin{theorem}\label{thcc2}
For all $k\geq 1$,
    $$\JJ_{12\ldots k}(x)=\frac{x}{U_k\txx}\sum_{j=1}^{k-2} U_{j}\txx.$$
\end{theorem}
\begin{proof}
By Proposition~\ref{prom2} and Remark~\ref{genll} (as in the proof of Theorem~\ref{thcc1}), together with the fact that the generating
function for $|\SS_n(132,12\ldots k)|$
is given by $R_k(x)$ (see \cite{CW}), we have
    $$\JJ_{12\ldots k}(x)=x\JJ_{12\ldots(k-1)}+x^2R_{k-1}(x^2)\JJ_{12\ldots
k}(x)+x^3R_{k-1}(x^2).$$
By Identity~\ref{eqrk}, we get
$$\JJ_{12\ldots k}(x)=xR_k(x^2)\JJ_{12\ldots(k-1)}(x)+x^3R_{k-1}(x^2)R_k(x^2).$$
Hence, by induction on $k$ together with
Example~\ref{excc1}, we get the desired result.
\end{proof}

The case $\tau=2134\ldots k$ is similar to the case $\tau=12\ldots k$.

\begin{theorem}\label{thcc22}
For all $k\geq 3$,
    $$\JJ_{2134\ldots k}(x)=\frac{x}{U_k\txx}
            \left[ xU_2\txx +\sum_{j=2}^{k-2} U_{j}\txx \right].$$
\end{theorem}
\begin{proof}
Arguing as in the proof of Theorem~\ref{thcc2}, we use the fact
that the generating function for
$|\SS_n(132,2134\ldots k)|$ is given by $R_k(x)$ (see \cite{MV2}) to obtain
    $$\JJ_{2134\ldots k}(x)=xR_k(x^2)\JJ_{2134\ldots(k-1)}(x)+x^3R_{k-1}(x^2)R_k(x^2).$$
Hence, by induction on $k$ with the initial
value $\JJ_{213}(x)=x^4R_3(x^2)$, we easily have the desired
result.
\end{proof}

\begin{example}
Theorem~\ref{thcc22} yields
$\JJ_{2134}(2n+3)=\JJ_{2134}(2n+4)=F_{2n}$, the $(2n)$th Fibonacci
number, for all $n \geq 0$.
\end{example}

\begin{example}\label{excc2}
Proposition~\ref{prom2} yields $\JJ_{231}(n)=1$ and $\JJ_{2341}(n)=2^{[(n-1)/2]}-1$ for all $n\geq 1$.
\end{example}

As an extension of Example~\ref{excc2}, we consider the case
$\tau=23\ldots k1$.

\begin{theorem}\label{thcc3}
For all $k\geq 3$,
    $$\JJ_{23\ldots k1}(x)=\frac{x^2U_{k-3}\txx}{(1-x)U_{k-2}\txx}
       \left[ 1+\frac{1}{U_{k-1}\txx}\sum_{j=1}^{k-3} U_j\txx \right].$$
\end{theorem}
\begin{proof}
As in the proof of Theorem~\ref{thcc2}, we have
    $$\JJ_{23\ldots k1}(x)=x\JJ_{23\ldots
k1}(x)+x^2R_{k-2}(x^2)\JJ_{12\ldots(k-1)}(x)+x^3R_{k-2}(x^2).$$
By using Theorem~\ref{thcc2} we get the desired result.
\end{proof}

More generally, we present the following explicit expression when
$\tau=<k,d>$.

\begin{theorem}\label{thcc4}
For $k\geq 4$ and $2\leq d\leq k/2$ we have
\begin{multline*}
\JJ_{<k,d>}(x)\\
=\frac{R_d(x^2)}{1-xR_d(x^2)}\left[x^2R_{k-d-1}(x^2)
+\frac{x^2(R_{k-d-1}(x^2)-R_{d-1}(x^2))}{U_{k-d}\txx}\sum_{j=1}^{k-d-2}U_j\txx\right].
\end{multline*}
\end{theorem}
\begin{proof}
By Proposition~\ref{prom2}, we have three possibilities for the
block decomposition of an arbitrary $\pi\in\II_n$ containing $132$
exactly once. Let us use Remark~\ref{genll} to write an equation for $\JJ_{<k,d>}(x)$. The contribution of the first
decomposition above is $x\JJ_{<k,d>}(x)$. The contribution of the
second decomposition above is as follows: if $\pi'$ contains
$12\ldots(k-d-1)$ then $\pi$ contains $<k,d>$ which is a
contradiction, so $\pi'$ avoids $12\ldots(k-d-1)$.
Therefore the contribution of the second decomposition is
$x^3R_{k-d-1}(x^2)$. Finally, the contribution of the third
decomposition above involves two cases:
$\pi''$ contains $12\ldots (k-d)$ or avoids $12\ldots (k-d)$.
In the first case we have
$x^2R_{d-1}(x^2)(\JJ_{<k,d>}(x)-\JJ_{12\ldots(k-d)}(x))$, and in
the second case we have $x^2R_{k-d-1}(x)\JJ_{12\ldots(k-d)}(x)$.
Therefore, if we use Theorem~\ref{thcc2} to write an equation for $\JJ_{<k,d>}(x)$ we obtain the desired result.
\end{proof}
%=================================================================
\section{Containing $132$ once and containing another pattern}
\label{sec5} Let $\JJ_\tau^r(n)$ denote the number of $n$-involutions
containing $132$ exactly once and containing $\tau$ exactly
$r$ times. Let $\JJ_\tau^r(x)=\sum_{n\geq 0}\JJ_\tau^r(n)x^n$ be
the corresponding generating function. We begin with the
following result.

\begin{theorem}\label{thd1}
For all $k\geq1$,
$$\JJ_{12\ldots k}^1(x)=0.$$
\end{theorem}
\begin{proof}
By Proposition~\ref{prom2} and by Remark~\ref{genll}, it is easy to
see
    $$\JJ_{12\ldots k}^1(x)=x\JJ_{12\ldots (k-1)}^1(x)+x^2R_{k-1}(x^2)\JJ_{12\ldots
k}^1(x).$$ Moreover, $\JJ_{12}^1(x)=0$ by definition, hence the theorem holds by
induction on $k$.
\end{proof}

Next we consider the case
$\tau=23\ldots k1$.

\begin{theorem}\label{thd2}
For all $k\geq1$,
$$\JJ_{23\ldots k1}^1(x)=0.$$
\end{theorem}

\begin{example}\label{exdd1}
Proposition~\ref{prom2} yields that $\JJ_{21}^1(n)=1$ for $n\geq
3$.
\end{example}

As an extension of Example~\ref{exdd1}, we consider the case
$\tau=2134\ldots k$.

\begin{theorem}\label{thd3}
For all $k\geq3$,
$$\JJ_{2134\ldots k}^1(x)=\frac{x(1-x^2)}{U_k\txx}.$$
\end{theorem}
\begin{proof}
Using Proposition~\ref{prom2} and Remark~\ref{genll}, it is
easy to see that
    $$\JJ_{2134\ldots k}^1(x)=x\JJ_{2134\ldots
(k-1)}^1(x)+x^2R_{k-1}(x^2)\JJ_{2134\ldots k}(x)$$ and
$\JJ_{21}^1(x)=x^3/(1-x)$.
The result follows by induction on $k$.
\end{proof}

{\bf Acknowledgments}: The authors are grateful to Eric S. Egge
for his careful reading of the manuscript.
%=================================================================
\begin{thebibliography}{WWW}
\bibitem[B1]{B1}
M.~B\'ona, The permutation classes equinumerous to the smooth
class, {\em Electron. J. Combin.} {\bf 5} (1998), Article~\#R31.

\bibitem[B2]{B2}
M.~B\'ona, The solution of a conjecture of Stanley and Wilf for
all layered patterns, {\em J. Combin. Theory Ser. A}, {\bf 85}
(1999), 96--104.

\bibitem[CC]{CC}
L.~Chottin, R.~Cori, Une preuve combinatoire de la rationalit\'e
d'une s\'erie g\'en\'eratrice associ\'ee aux arbres, {\em
R.A.I.R.O. Informatique th\'eorique} {\bf 16} n$^{\rm o}$ 2
(1982), 113--128.

\bibitem[CW]{CW}
T.~Chow and J.~West, Forbidden subsequences and Chebyshev
polynomials, {\em Discr. Math.} {\bf 204} (1999), 119--128.

\bibitem[CGHK]{Chung}
F.R.K.~Chung, R.L.~Graham, V.E.~Hoggat and M.~Kleiman, The number
of Baxter permutations, {\em J. Comb. Th. A} {\bf 24} (1978),
382--394.

\bibitem[E]{Errera}
A.~Errera, Un probl\`eme d'\'enum\'eration, {\em M\'emoires
publi\'ees par l'Acad\'emie royale de Belgique}, Bruxelles, {\bf
11} (1931).

\bibitem[Ge]{Gessel}
I.M.~Gessel, Symmetric functions and P-recursiveness, {\em J.
Comb. Th. A} {\bf 53} (1990), 257--285.

\bibitem[Gi]{GireThese}
S.~Gire, Arbres, permutations \`a motifs exclus et cartes
planaires~: quelques probl\`emes algorithmiques et combinatoires,
{\em Ph.D.-thesis, Universit\'e Bordeaux~1, France} (1993).

\bibitem[G-B]{GouyouBYoung}
D.~Gouyou--Beauchamps, Standard Young tableaux of height $4$ and
$5$, {\em European J. Combin.} {\bf 10} (1989), 69--82.

\bibitem[Gu]{GuibertThese}
O.~Guibert, Combinatoire des permutations \`a motifs exclus en
liaison avec mots, cartes planaires et tableaux de Young, {\em
Ph.D.-thesis, Universit\'e Bordeaux~1, France} (1995).

\bibitem[GPP]{GPP}
O.~Guibert, E.~Pergola and R.~Pinzani, Vexillary involutions are
enumerated by Motzkin numbers, {\em Annals of Comb.} {\bf 5}
(2001), 153--174.

\bibitem[HM]{HM}
F.~K.~Hwang, C.~L.~Mallows, Enumerating nested and consecutive
partitions, {\em J. Combin. Theory Ser. A}, {\bf 70} (1995),
323--333.

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

\bibitem[Kt]{Kr}
C.~Krattenthaler, Permutations with restricted patterns and Dyck
paths, {\em Adv. in Applied Math.} {\bf 27} (2001), 510--530.

\bibitem[Km]{Km}
D.~Kremer, Permutations with forbidden subsequences and a
generalized Schr\"oder number, {\em Discr. Math.} {\bf 218}
(2000), 121--130.

\bibitem[Kw]{Kre}
G.~Kreweras, Sur les \'eventails de segments, {\em Cahiers du
BURO} {\bf 15} (1970), 3--41.

\bibitem[MV1]{MV1}
T.~Mansour and A.~Vainshtein, Restricted permutations, continued
fractions, and Chebyshev polynomials {\em Electron. J. Combin.}
\textbf{7} (2000) \#R17.

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

\bibitem[MV3]{MV3}
T.~Mansour and A.~Vainshtein, Layered restrictions and Chebyshev
polynomials, {\em Annals of Combinatorics} {\bf 5} (2001),
451--458.

\bibitem[MV4]{MV4}
T.~Mansour and A.~Vainshtein, Restricted permutations and
Chebyshev polynomials, {\em S\'eminaire Lotharingien de
Combinatoire} {\bf 47} (2002), Article~B47c.

\bibitem[P]{PergolaThese}
E.~Pergola, ECO: a Methodology for Enumerating Combinatorial
Objects, Ph.D.-thesis, University of Firenze, Italy (1998).

\bibitem[Re]{Regev}
A.~Regev, Asymptotic values for degrees associated with strips of
Young diagrams, {\em Adv. Math.} {\bf 41} (1981), 115--136.

\bibitem[Ri]{Ri}
Th.~Rivlin, Chebyshev polynomials. From approximation theory to
algebra and number theory, John Wiley, New York (1990).

\bibitem[Ro]{R}
A.~Robertson, Permutations containing and avoiding 123 and 132
patterns, {\em Discrete Mathematics and Theoretical Computer
Science}, {\bf 3} (1999), 151--154.

\bibitem[RWZ]{RWZ}
A.~Robertson, H.~Wilf, and D.~Zeilberger, Permutation patterns and
continuous fractions, {\em Electron. J. Combin.} {\bf 6} (1999),
Article~\#R38.

\bibitem[SS]{SS}
R.~Simion, F.W.~Schmidt, Restricted Permutations, {\em Europ. J.
of Combinatorics} {\bf 6} (1985), 383--406.

\bibitem[SP]{SloanePlouffe}
N.J.A.~Sloane, S.~Plouffe, The encyclopedia of integer sequences,
Academic Press (1995).

\bibitem[S]{St}
R.~Stanley, Enumerative Combinatorics, vol. {\bf 1}, Wadsworth and
Brooks/Cole, Pacific Grove, CA, 1986, xi + 306 pages; second
printing, Cambridge University Press, Cambridge, 1996.

\bibitem[V]{V}
G.~X.~Viennot, Heaps of pieces 1: basic definitions and
combinatorial lemmas, G.~Labelle and P.~Leroux editors, {\em
Combinatoire \'enum\'erative, Lecture Notes in Math.} {\bf 1234}
(1986), pp.~321--350.

\bibitem[W1]{WestPHD}
J.~West, Permutations with forbidden subsequences and
stack-sortable permutations, Ph.D.-thesis, Massachusetts Institute
of Technology, Cambridge (1990).

\bibitem[W2]{W}
J.~West, Generating trees and forbidden subsequences, {\em Discr.
Math.} {\bf 157} (1996), 363--372.
\end{thebibliography}
\end{document}
