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

\topmargin 0 pt \textheight 46\baselineskip \advance\textheight by
\topskip \setlength{\parindent}{10pt} \setlength{\parskip}{5pt plus
2pt minus 1pt} \setlength{\textwidth}{155mm}
\setlength{\oddsidemargin}{5.0mm}
\setlength{\evensidemargin}{5.0mm}
%\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\PP{\mathcal P}
\def\qq{{\bold q}}
\def\txx{{\frac1{2\sqrt{x}}}}
\def\sign{\operatorname{sign}}
\def\find{\operatorname{find}}
\def\val{\operatorname{val}}
\def\fris{\operatorname{fris}}
\def\lris{\operatorname{lris}}
\def\fdes{{\operatorname{fdes}}}
\def\ldes{\operatorname{ldes}}
\def\mld{\operatorname{lpeak}}
\def\sl{\sum}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Input-Datei zum Erzeugen von Gitterpunktwegen.%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%LaTeX-Version%
%%%%%%%%%%%%%%%
%entering a path: 
%  \Pfad(x-coordinate of starting point,y-coordinate of starting point),path
%  as 1-2-3-4-5-6-7-8-word\endPfad
%(1=step in x-direction, 2=step in y-direction, 3=upward diagonal step, 4=downward diagonal step)
%(5=step in negative x-direction, 6=step in negative y-direction, 7=downward left diagonal step, 8=upward left diagonal step)
%
%entering a dotted path: 
%  \SPfad(x-coordinate of starting point,y-coordinate of starting point),path
%  as 1-2-3-4-5-6-7-8-word\endSPfad
%(1=step in x-direction, 2=step in y-direction, 3=upward diagonal step, 4=downward diagonal step)
%(5=step in negative x-direction, 6=step in negative y-direction, 7=downward left diagonal step, 8=upward left diagonal step)
%
%coordinate-axes:
%  \Koordinatenachsen(length of positive x-axes, length of positive y-axes)(length of negative x-axes, length of negative y-axes)
%The length of negative axes are entered as negative numbers.
%
%lattice:
%  \Gitter(number of points in positive x-direction, number of points in positive y-direction)(number of points in negative x-direction, number of points in negative y-direction)
%
%diagonal lines:
%  \Diagonale(x-coordinate of SW-most point,y-coordinate of SW-most point)length of the projection on the x-axes
%
%antidiagonal lines:
%  \AntiDiagonale(x-coordinate of NW-most point,y-coordinate of NW-most point)length of the projection on the x-axes
%
%labelling of points:
%  \Label[location?]{[label]}(x-coordinate,y-coordinate)
%where:
%  [location?]=\l,\lo,\lu,\r,\ro,\ru,\o,\u
%and l=left, r=right, u=bottom, o=top.
%In addition, if by \Einheit?cm the basic unit is changed, there exist
%\llo,\loo,\llu,\luu,\rro,\roo,\rru,\ruu.
%
%The basic unit can be changed by entering
%  \Einheit=?cm
%The default is \Einheit=0.5cm.
%
%The thickness of the paths can be changed by entering
%     \PfadDicke{?cm}
%The default is \PfadDicke=1pt.
%
%The following point sizes are available:
%\DuennPunkt, \NormalPunkt, \DickPunkt. Syntax:
%  \DickPunkt(x-coordinate,y-coordinate), etc.
%
%Besides, a circle is available by \Kreis. Syntax:
%  \Kreis(x-coordinate,y-coordinate)
%
\catcode`\@=11
\font\tenln    = line10
\font\tenlnw   = linew10

\thinlines
\newskip\Einheit \Einheit=0.6cm
\newcount\xcoord \newcount\ycoord
\newdimen\xdim \newdimen\ydim \newdimen\PfadD@cke \newdimen\Pfadd@cke
\PfadD@cke1pt \Pfadd@cke0.5pt
\def\PfadDicke#1{\PfadD@cke#1 \divide\PfadD@cke by2 \Pfadd@cke\PfadD@cke \multiply\PfadD@cke by2}
\long\def\LOOP#1\REPEAT{\def\BODY{#1}\ITERATE}
\def\ITERATE{\BODY \let\next\ITERATE \else\let\next\relax\fi \next}
\let\REPEAT=\fi
\def\Punkt{\hbox{\raise-2pt\hbox to0pt{\hss\scriptsize$\bullet$\hss}}}
\def\DuennPunkt(#1,#2){\unskip
  \raise#2 \Einheit\hbox to0pt{\hskip#1 \Einheit
          \raise-2.5pt\hbox to0pt{\hss\normalsize$\bullet$\hss}\hss}}
\def\NormalPunkt(#1,#2){\unskip
  \raise#2 \Einheit\hbox to0pt{\hskip#1 \Einheit
          \raise-3pt\hbox to0pt{\hss\large$\bullet$\hss}\hss}}
\def\DickPunkt(#1,#2){\unskip
  \raise#2 \Einheit\hbox to0pt{\hskip#1 \Einheit
          \raise-4pt\hbox to0pt{\hss\Large$\bullet$\hss}\hss}}
\def\Kreis(#1,#2){\unskip
  \raise#2 \Einheit\hbox to0pt{\hskip#1 \Einheit
          \raise-4pt\hbox to0pt{\hss\Large$\circ$\hss}\hss}}
\def\Diagonale(#1,#2)#3{\unskip\leavevmode
  \xcoord#1\relax \ycoord#2\relax
      \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit
         \unitlength\Einheit
         \line(1,1){#3}\hss}}
\def\AntiDiagonale(#1,#2)#3{\unskip\leavevmode
  \xcoord#1\relax \ycoord#2\relax \advance\xcoord by -0.05\relax
      \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit
         \unitlength\Einheit
         \line(1,-1){#3}\hss}}
\def\Pfad(#1,#2),#3\endPfad{\unskip\leavevmode
  \xcoord#1 \ycoord#2 \thicklines\ZeichnePfad#3\endPfad\thinlines}
\def\ZeichnePfad#1{\ifx#1\endPfad\let\next\relax
  \else\let\next\ZeichnePfad
    \ifnum#1=1
      \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit
         \vrule height\Pfadd@cke width1 \Einheit depth\Pfadd@cke\hss}%
      \advance\xcoord by 1
    \else\ifnum#1=2
      \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit
        \hbox{\hskip-\PfadD@cke\vrule height1 \Einheit width\PfadD@cke depth0pt}\hss}%
      \advance\ycoord by 1
    \else\ifnum#1=3
      \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit
         \unitlength\Einheit
         \line(1,1){1}\hss}
      \advance\xcoord by 1
      \advance\ycoord by 1
    \else\ifnum#1=4
      \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit
         \unitlength\Einheit
         \line(1,-1){1}\hss}
      \advance\xcoord by 1
      \advance\ycoord by -1
    \else\ifnum#1=5
      \advance\xcoord by -1
      \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit
         \vrule height\Pfadd@cke width1 \Einheit depth\Pfadd@cke\hss}%
    \else\ifnum#1=6
      \advance\ycoord by -1
      \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit
        \hbox{\hskip-\PfadD@cke\vrule height1 \Einheit width\PfadD@cke depth0pt}\hss}%
    \else\ifnum#1=7
      \advance\xcoord by -1
      \advance\ycoord by -1
      \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit
         \unitlength\Einheit
         \line(1,1){1}\hss}
    \else\ifnum#1=8
      \advance\xcoord by -1
      \advance\ycoord by +1
      \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit
         \unitlength\Einheit
         \line(1,-1){1}\hss}
    \fi\fi\fi\fi
    \fi\fi\fi\fi
  \fi\next}
\def\hSSchritt{\leavevmode\raise-.4pt\hbox to0pt{\hss.\hss}\hskip.2\Einheit
  \raise-.4pt\hbox to0pt{\hss.\hss}\hskip.2\Einheit
  \raise-.4pt\hbox to0pt{\hss.\hss}\hskip.2\Einheit
  \raise-.4pt\hbox to0pt{\hss.\hss}\hskip.2\Einheit
  \raise-.4pt\hbox to0pt{\hss.\hss}\hskip.2\Einheit}
\def\vSSchritt{\vbox{\baselineskip.2\Einheit\lineskiplimit0pt
\hbox{.}\hbox{.}\hbox{.}\hbox{.}\hbox{.}}}
\def\DSSchritt{\leavevmode\raise-.4pt\hbox to0pt{%
  \hbox to0pt{\hss.\hss}\hskip.2\Einheit
  \raise.2\Einheit\hbox to0pt{\hss.\hss}\hskip.2\Einheit
  \raise.4\Einheit\hbox to0pt{\hss.\hss}\hskip.2\Einheit
  \raise.6\Einheit\hbox to0pt{\hss.\hss}\hskip.2\Einheit
  \raise.8\Einheit\hbox to0pt{\hss.\hss}\hss}}
\def\dSSchritt{\leavevmode\raise-.4pt\hbox to0pt{%
  \hbox to0pt{\hss.\hss}\hskip.2\Einheit
  \raise-.2\Einheit\hbox to0pt{\hss.\hss}\hskip.2\Einheit
  \raise-.4\Einheit\hbox to0pt{\hss.\hss}\hskip.2\Einheit
  \raise-.6\Einheit\hbox to0pt{\hss.\hss}\hskip.2\Einheit
  \raise-.8\Einheit\hbox to0pt{\hss.\hss}\hss}}
\def\SPfad(#1,#2),#3\endSPfad{\unskip\leavevmode
  \xcoord#1 \ycoord#2 \ZeichneSPfad#3\endSPfad}
\def\ZeichneSPfad#1{\ifx#1\endSPfad\let\next\relax
  \else\let\next\ZeichneSPfad
    \ifnum#1=1
      \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit
         \hSSchritt\hss}%
      \advance\xcoord by 1
    \else\ifnum#1=2
      \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit
        \hbox{\hskip-2pt \vSSchritt}\hss}%
      \advance\ycoord by 1
    \else\ifnum#1=3
      \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit
         \DSSchritt\hss}
      \advance\xcoord by 1
      \advance\ycoord by 1
    \else\ifnum#1=4
      \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit
         \dSSchritt\hss}
      \advance\xcoord by 1
      \advance\ycoord by -1
    \else\ifnum#1=5
      \advance\xcoord by -1
      \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit
         \hSSchritt\hss}%
    \else\ifnum#1=6
      \advance\ycoord by -1
      \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit
        \hbox{\hskip-2pt \vSSchritt}\hss}%
    \else\ifnum#1=7
      \advance\xcoord by -1
      \advance\ycoord by -1
      \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit
         \DSSchritt\hss}
    \else\ifnum#1=8
      \advance\xcoord by -1
      \advance\ycoord by 1
      \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit
         \dSSchritt\hss}
    \fi\fi\fi\fi
    \fi\fi\fi\fi
  \fi\next}
\def\Koordinatenachsen(#1,#2){\unskip
 \hbox to0pt{\hskip-.5pt\vrule height#2 \Einheit width.5pt depth1 \Einheit}%
 \hbox to0pt{\hskip-1 \Einheit \xcoord#1 \advance\xcoord by1
    \vrule height0.25pt width\xcoord \Einheit depth0.25pt\hss}}
\def\Koordinatenachsen(#1,#2)(#3,#4){\unskip
 \hbox to0pt{\hskip-.5pt \ycoord-#4 \advance\ycoord by1
    \vrule height#2 \Einheit width.5pt depth\ycoord \Einheit}%
 \hbox to0pt{\hskip-1 \Einheit \hskip#3\Einheit 
    \xcoord#1 \advance\xcoord by1 \advance\xcoord by-#3 
    \vrule height0.25pt width\xcoord \Einheit depth0.25pt\hss}}
\def\Gitter(#1,#2){\unskip \xcoord0 \ycoord0 \leavevmode
  \LOOP\ifnum\ycoord<#2
    \loop\ifnum\xcoord<#1
      \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit\Punkt\hss}%
      \advance\xcoord by1
    \repeat
    \xcoord0
    \advance\ycoord by1
  \REPEAT}
\def\Gitter(#1,#2)(#3,#4){\unskip \xcoord#3 \ycoord#4 \leavevmode
  \LOOP\ifnum\ycoord<#2
    \loop\ifnum\xcoord<#1
      \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit\Punkt\hss}%
      \advance\xcoord by1
    \repeat
    \xcoord#3
    \advance\ycoord by1
  \REPEAT}
\def\Label#1#2(#3,#4){\unskip \xdim#3 \Einheit \ydim#4 \Einheit
  \def\lo{\advance\xdim by-.5 \Einheit \advance\ydim by.5 \Einheit}%
  \def\llo{\advance\xdim by-.25cm \advance\ydim by.5 \Einheit}%
  \def\loo{\advance\xdim by-.5 \Einheit \advance\ydim by.25cm}%
  \def\o{\advance\ydim by.25cm}%
  \def\ro{\advance\xdim by.5 \Einheit \advance\ydim by.5 \Einheit}%
  \def\rro{\advance\xdim by.25cm \advance\ydim by.5 \Einheit}%
  \def\roo{\advance\xdim by.5 \Einheit \advance\ydim by.25cm}%
  \def\l{\advance\xdim by-.30cm}%
  \def\r{\advance\xdim by.30cm}%
  \def\lu{\advance\xdim by-.5 \Einheit \advance\ydim by-.6 \Einheit}%
  \def\llu{\advance\xdim by-.25cm \advance\ydim by-.6 \Einheit}%
  \def\luu{\advance\xdim by-.5 \Einheit \advance\ydim by-.30cm}%
  \def\u{\advance\ydim by-.30cm}%
  \def\ru{\advance\xdim by.5 \Einheit \advance\ydim by-.6 \Einheit}%
  \def\rru{\advance\xdim by.25cm \advance\ydim by-.6 \Einheit}%
  \def\ruu{\advance\xdim by.5 \Einheit \advance\ydim by-.30cm}%
  #1\raise\ydim\hbox to0pt{\hskip\xdim
     \vbox to0pt{\vss\hbox to0pt{\hss$#2$\hss}\vss}\hss}%
}
\catcode`\@=12



\newbox\Adr
\setbox\Adr\vbox{
\centerline{\sc Toufik Mansour$^{1,2}$}
\vskip18pt
\centerline{Department of Mathematics, Chalmers University of Technology}
\centerline{S-412~96 G\"oteborg, Sweden}
\centerline{E-mail: \tt toufik@math.chalmers.se}
}

\title{Equidistribution and Sign-Balance on $132$-Avoiding permutations}

\author[Toufik Mansour]{\box\Adr}

\thanks{$^1$Research financed by EC's
IHRP Programme, within the Research Training Network ``Algebraic
Combinatorics in Europe", grant HPRN-CT-2001-00272}

\thanks{$^2$Current address: Department of Mathematics,
University of Haifa, 31905 Haifa, Israel. E-mail:
{\tt  toufik@math.haifa.ac.il}}

%===========================================================================
\begin{abstract}
Let $R_n$ be the set of all permutations of length $n$ which avoid
$132$. In this paper we study the statistics \emph{last descent}
(``ldes"), \emph{first descent} (``fdes"), \emph{last rise}
(``lris"), and \emph{first rise} (``fris") on the set $R_n$. In
particular, we prove that the bistatistic (``fris",``lris") on the
set of all permutations $R_n\backslash\{n\ldots21\}$ and the
bistatistic (``$n-{}$ldes",``$n-{}$fdes") on the set of all permutations
of $R_n\backslash\{12\ldots n\}$ are equidistributed. Furthermore, we
consider the case of sign balance for these statistics on the
set of all permutations $R_n$, and we give a combinatorial
interpretation for some of these statistics.
\end{abstract}

\keywords{$132$-avoiding permutations, Dyck paths,
equidistribution of statistics, sign-balance}

\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 51 \rms (2004), Article~B51e\hfill}
\def\thepage{}
%
%

%===========================================================================
\section{Introduction}
Let $S_n$ denote the set of permutations of $\{1, \ldots, n\}$,
written in one-line notation, and suppose that $\pi \in S_n$ and
$\sigma \in S_k$. We say that a subsequence of $\pi$ has {\it
type} $\sigma$ whenever it has the same pairwise comparisons
as $\sigma$. For example, the subsequence 24869 of the permutation
214538769 has type 12435. We say that $\pi$ {\it avoids} $\sigma$
(or {\em $\pi$ is $\sigma$-avoiding}) whenever $\pi$ contains no
subsequence of type $\sigma$. For example, the permutation
214538769 avoids 4321 and 2413, but it has 2589 as a subsequence,
so it does not avoid 1234. We denote the set of $\sigma$-avoiding
permutations in $S_n$ by $S_n(\sigma)$. We define $R_n=S_n(132)$.
For $\pi\in R_n$, we define the following statistics:

\begin{enumerate}
\item $\ldes(\pi)={}$last descent of
$\pi=\max\{1\leq i\leq n-1|\pi_i>\pi_{i+1}\}$ where\linebreak 
$\ldes(12\ldots n)=0$,

\item $\mbox{fdes}(\pi)=\mbox{first descent of }\pi=\min\{1\leq i\leq
n-1|\pi_i>\pi_{i+1}\}$ where\linebreak $\fdes(12\ldots n)=0$,

\item $\lris(\pi)={}$last rise of $\pi=\max\{1\leq i\leq
n-1|\pi_i<\pi_{i+1}\}$ where $\lris(n\ldots21)=0$,

\item $\fris(\pi)={}$first rise of $\pi=\min\{1\leq i\leq
n-1|\pi_i<\pi_{i+1}\}$ where $\fris(n\ldots21)=0$,

\item $\mbox{lind}(\pi)=\pi^{-1}(n)={}$the index of the letter
``$n$" in $\pi$,

\item $\find(\pi)=\pi^{-1}(1)={}$the index of the letter ``$1$"
in $\pi$.
\end{enumerate}

Foata and Sch\"utzenberger \cite[Theorem~1]{FS} proved that the
major index and the inversion number are equidistributed on
$S_n$ whose inverse has a prescribed descent set. Recently, Adin
and Roichman~\cite[Theorem 1.1]{AR} gave an analogue for this
result for $S_n(321)$. They proved that the statistics ``ldes" and ``lind${}-1$" 
are
equidistributed on the set $S_n(321)$. Note that these
statistics are identical on the set $R_n$. (To prove that, let
$s=\pi_1^{-1}$. We may assume that $s>1$, otherwise $\pi$ equals
the identity of $S_n$, which has no descents. Clearly,
$\pi_{s-1}>\pi_s$. Furthermore, we have
$1=\pi_s<\pi_{s+1}<\cdots<\pi_n$ since $\pi$ avoids $132$.
Therefore, $s-1$ is exactly the last descent of $\pi$.)

The {\em Catalan sequence} is the sequence
$(C_n)_{n\geq0}=(1,1,2,5,14,42,132,429,1430,\dots)$, 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
denoted by $C(t)=\frac{1-\sqrt{1-4t}}{2t}$. The Catalan numbers
provide a complete answer to the problem of counting certain
properties of more than $100$ different combinatorial structures
(see \cite[page~219 and Exercise~6.19]{St}). The
structures that are useful for us in the present paper are Dyck
paths (see~\cite{St}) and $132$-avoiding permutations
(see~\cite{Kn}).

A {\em Dyck path\/} is a path in the plane integer lattice ${\mathbb
Z}^2$ consisting of up-steps $U=(1,1)$ and down-steps $D=(1,-1)$
which never passes below the $x$-axis. We denote the set of Dyck
paths of length $2n$ by $\PP_n$. A point on the Dyck path is
called a {\em peak} if it is immediately preceded by an up-step
and immediately followed by a down-step. For $p\in\PP_n$, we define
   $$\mld(p)=\mbox{the height (the $y$-coordinate) of the last peak of }p.$$
Recently, Adin and Roichman~\cite[Theorem~1.2]{AR} proved that the
statistics ``ldes" on the set $S_n(321)$, ``ldes" on the set
$\PP_n$, and ``lind${}-1$" are equidistributed on the set $\PP_n$. In
this paper we prove the following analogue of this result.

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

\begin{theorem}\label{thbb}
For all $n\geq1$, we have
$$\sum_{p\in\PP_n}q^{n-\mld(p)}%=\sum_{p\in\PP_n}q^{n-1-\val(p)}
=\sum_{\pi\in R_n}q^{\ldes(\pi)}.$$
\end{theorem}

In addition, we study the sign-and-``find" and sign-and-``lind"
enumerators for $R_n$ (see~\cite[Theorem 1.3]{AR} for $S_n(321)$),
and we prove the following result.
\begin{theorem}
For all $n\geq1$,
$$\sum_{\pi\in R_{2n}}\sign(\pi)q^{\ldes(\pi)}=(1-q)\sum_{\pi\in
R_{2n+1}}\sign(\pi)q^{\find(\pi)-1},$$
and
$$\sum_{\pi\in R_{2n-1}}\sign(\pi)q^{\ldes(\pi)}=\sum_{\pi\in
R_{n-1}}q^{2(\find(\pi)-1)}.$$
\end{theorem}

The paper is organized as follows. In Section~2, we study the
statistics ``ldes", ``fdes", ``lris", and ``fris" on the set $R_n$.
In particular, we prove that the bistatistic (``fris",``lris") on
the set $R_n\backslash\{n\ldots21\}$ and the bistatistic
(``$n-{}$ldes",``$n-{}$fdes") on the set $R_n\backslash\{12\ldots n\}$ are
equidistributed. In Section~3, we consider the case of sign balance
of some statistics on the set $R_n$. Finally, in Section~4, we
give a combinatorial interpretation (using Dyck paths) for some of
these statistics.
%------------------------------------------------------------------
\section{Equidistribution of statistics}
In this section, we study the statistics ``ldes", ``fdes", ``lris",
and ``fris" on the set $R_n$ by using the block decomposition
approach of $132$-avoiding permutations in $S_n$ (see~\cite{MV4}).

First of all, let us describe the block decomposition of a
permutation $\pi\in R_n$. Let $n\geq1$ and $\pi=(\pi',n,\pi'')\in
R_n$ such that $\pi_j=n$. $\pi$ avoids $132$ if and only if $\pi'$
is a permutation of the numbers $n-j+1, n-j+2,\dots,n-1$, $\pi''$
is a permutation of the numbers $1,2,\dots,n-j$, and both $\pi'$
and $\pi''$ avoid $132$. This representation is called the {\em
block decomposition} of $\pi$.

\begin{theorem}\label{thb2}
The statistic ``$\fris$" on  the set $R_n\backslash\{n\ldots21\}$
and the statistic ``$n-\ldes$" on the set $R_n\backslash\{12\ldots
n\}$ are equidistributed, that is, for $n\geq1$, we have
$$\sum_{\pi\in R_n\backslash\{n\ldots21\}}q^{\fris(\pi)}= \sum_{\pi\in
R_n\backslash\{12\ldots n\}}q^{n-\ldes(\pi)}.$$ Moreover,
$$\sum_{n\geq0}\sum_{\pi\in
R_n}q^{\fris(\pi)}x^n=\frac{1}{1-x}-\frac{1}{1-qx}+\frac{1}{1-qxC(x)}$$
and
$$\sum_{n\geq0}\sum_{\pi\in
R_n}q^{\ldes(\pi)}=\frac{1}{1-xC(qx)}.$$
\end{theorem}
\begin{proof}
%Let $n\geq1$ and $\pi=(\pi',n,\pi'')\in R_n$ such that $\pi_j=n$.
Let $F_n(q)=\sum_{\pi\in R_n}q^{\ldes(\pi)}$ for $n\geq0$.
Using the block
decomposition of $\pi\in R_n$,
we may derive a recurrence for $F_n(q)$. Namely, by making use of the fact that
$|S_m(132)|=C_m=\frac{1}{m+1}\binom{2m}{m}$ (see~\cite{Kn}), we get
for $n\geq1$,
\begin{equation}\label{eqf}
F_{n}(q)=F_{n-1}(q)+q\sum_{j=0}^{n-2}q^jC_jF_{n-1-j}(q).
\end{equation}
Multiplying both sides by $x^n$, summing over all $n\geq1$,
and finally using $F_0(q)=1$, we obtain that
$$F(x;q)=1+\sum_{n\geq1}\sum_{\pi\in R_n}q^{\ldes(\pi)}x^n=\frac{1}{1-xC(xq)}.$$

Let now $H_n(q)=\sum_{\pi\in R_n}q^{\fris(\pi)}$ for $n\geq0$.
Again, using the block
decomposition of $\pi$, we may derive 
a recurrence for $H_n(q)$. First of all, the contribution of the permutations 
$\pi$ with $\pi_1=n$
gives $1+q(H_{n-1}(q)-1)$. Secondly, the contribution of the permutations 
$\pi$ with $\pi_2=n$ gives
$C_{n-2}q$. Finally, for $\pi_j=n$ with $j\geq3$, we get as contribution
$(H_{j-1}(q)-1)C_{n-j}$ whenever $\pi'\neq(n-1)\ldots(n+1-j)$ in the
decomposition $\pi=(\pi',n,\pi'')$, and
$q^{j-1}C_{n-j}$ for $\pi'=(n-1)\ldots(n+1-j)$. Hence, for
$n\geq1$, we have
$$H_n(q)=1+q(H_{n-1}(q)-1)+C_{n-2}q+
\sum_{j=2}^{n-1}C_{n-1-j}(H_j(q)-1)+\sum_{j=2}^{n-1}q^jC_{n-1-j},$$
or, equivalently,
\begin{equation}\label{eqh}
H_n(q)=1+q(H_{n-1}(q)-1)+\sum_{j=2}^{n-1}C_{n-1-j}(H_j(q)-1)+\sum_{j=1}^{n-1}q^jC_{n-1-j}.
\end{equation}
If we write $K_n(q)$ for $q^n(H_n(q^{-1})-1)+1$, then it is easy to see that
$$K_n(q)=K_{n-1}(q)+q\sum_{j=0}^{n-2}q^jC_jK_{n-1-j}(q).$$
Since $K_0(q)=K_1(q)=1$, an induction on $n$ together with
Equation~\eqref{eqf} gives for $n\geq0$,
    $$q^n(H_n(1/q)-1)+1=F_n(q).$$
The rest follows now easily.
\end{proof}

\begin{theorem}\label{thb3}
The statistic ``$\lris$" on  the set $R_n\backslash\{n\ldots21\}$
and the statistic ``$n-\fdes$" on the set $R_n\backslash\{12\ldots
n\}$ are equidistributed, that is, for $n\geq1$, we have
$$\sum_{\pi\in R_n\backslash\{n\ldots21\}}q^{\lris(\pi)}= \sum_{\pi\in
R_n\backslash\{12\ldots n\}}q^{n-\fdes(\pi)}.$$ Moreover, 
$$\sum_{n\geq0}\sum_{\pi\in
R_n}q^{\fdes(\pi)}x^n=\frac{1-q+q(1-x)^2C(x)}{(1-x)(1-xq)}$$
and 
$$ \sum_{n\geq0}\sum_{\pi\in
R_n}q^{\lris(\pi)}x^n=\frac{1+x(C(xq)-1)C(xq)}{1-x}.$$
\end{theorem}
\begin{proof}
Let $L_n(q)=\sum_{\pi\in R_n}q^{\fdes(\pi)}$ for $n\geq0$. Let
$\pi=(\pi',n,\pi'')\in R_n$ such that $\pi_j=n$. 
Using this block decomposition of $\pi$, we may derive
a recurrence for $L_n(q)$. 
Namely, the contribution of the permutations with $j=1$ gives $C_{n-1}q$, the
contribution for $j=2$ gives $C_{n-2}q^2$, the contribution for
$n\geq j\geq3$ and $\pi'\neq(n+1-j)\ldots(n-1)$ gives
$C_{n-j}(L_{j-1}(q)-1)$, the contribution for $n-1\geq j\geq3$ and
$\pi'=(n+1-j)\ldots(n-1)$ gives $q^jC_{n-j}$, and the contribution
for $j=n$ and $\pi'=(n+1-j)\ldots(n-1)n$ gives $1$. Hence, for
$n\geq1$, we have
$$L_n(q)=C_{n-1}q+C_{n-2}q^2+\sum_{j=3}^{n}C_{n-j}(L_{j-1}(q)-1)+\sum_{j=3}^{n-1}q^jC_{n-j}+1,$$
or, equivalently,
\begin{equation}\label{eql}
L_n(q)=1+q\sum_{j=0}^{n-2}q^{j}C_{n-1-j}+\sum_{j=0}^{n-1}C_{n-1-j}(L_j(q)-1).
\end{equation}
Multiplying by $x^n$, summing over $n\geq1$, and finally using
$L_0(q)=L_1(q)=1$, we obtain that
$$\sum_{n\geq0}L_n(q)x^n=\frac{1-q+q(1-x)^2C(x)}{(1-x)(1-xq)}.$$

Now, let $P_n(q)=\sum_{\pi\in R_n}q^{\lris(\pi)}$ for 
$n\geq0$. Again, we may derive a recurrence for $P_n(q)$ 
by using the above block
decomposition of $\pi$. Namely, the contribution for $j=n$
gives $C_{n-1}q^{n-1}$, the contribution for $j=n-1$ gives
$C_{n-2}q^{n-2}$, the contribution for $1\leq j\leq n-2$ and
$\pi''\neq(n-j)\ldots21$ gives $C_{j-1}q^j(P_{n-j}(q)-1)$, and the
contribution for $n-2\geq j\geq1$ and $\pi''=(n-j)\ldots21$ gives
$q^{j-1}C_{j-1}$. Hence, for $n\geq1$, we have
$$P_n(q)=C_{n-1}q^{n-1}+C_{n-2}q^{n-2}+\sum_{j=1}^{n-2}C_{j-1}q^j(P_{n-j}(q)-1)+\sum_{j=1}^{n-2}q^{j-1}C_{j-1},$$
or, equivalently,
\begin{equation}\label{eqp}
P_n(q)=\sum_{j=0}^{n-1}q^jC_{j}+q\sum_{j=0}^{n-1}C_{j}q^j(P_{n-1-j}(q)-1).
\end{equation}
Multiplying by $x^n$, summing over $n\geq1$, and using finally
$P_0(q)=P_1(q)=1$, we obtain that
$$\sum_{n\geq0}P_n(q)x^n=\frac{1+x(C(xq)-1)C(xq)}{1-x}.$$

Using Equations~\eqref{eql} and \eqref{eqp} together with an induction on
$n$, we conclude that $q^n(P_n(q^{-1})-1)+1=L_n(q)$, and this completes
the proof.
\end{proof}

More generally, we prove that the bistatistics (``fris",``lris")
on the set $R_n\backslash\{n\ldots21\}$ and
(``$n-\ldes$",``$n-\fdes$") on the set $R_n\backslash\{12\ldots n\}$
are equidistributed.

\begin{theorem}\label{thz}
The bistatistic (``$\fris$",``$\lris$") on the set
$R_n\backslash\{n\ldots21\}$ and the bistatistic
(``$n-\ldes$",``$n-\fdes$") on the set $R_n\backslash\{12\ldots n\}$ are
equidistributed, that is, for $n\geq1$, we have
$$\sum_{\pi\in R_n\backslash\{12\ldots
n\}}p^{n-\ldes(\pi)}q^{n-\fdes(\pi)}=\sum_{\pi\in
R_n\backslash\{n\ldots21\}}p^{\fris(\pi)}q^{\lris(\pi)}.$$
Moreover,
$$\sum_{n\geq0}\sum_{\pi\in
R_n}p^{\fris(\pi)}q^{\lris(\pi)}x^n=1+\frac{x(1-p+p(1-2qx+pq^2x^2)C(qx))}{(1-x)(1-pqx)(1-pqxC(qx))}.$$
\end{theorem}
\begin{proof}
Let $A_n(p,q)=\sum_{\pi\in R_n}p^{\fris(\pi)}q^{\lris(\pi)}$ for
$n\geq1$ and $A_0(p,q)=1$. 
Using the block decomposition 
$\pi=(\pi',n,\pi'')\in R_n$ where $\pi_j=n$ once more, we derive a
recurrence for $A_n(p,q)$ if $n\ge1$. Namely, the
contribution of the permutations with $\pi'=(n-1)\ldots(n+1-j)$ and
$\pi''=(n-j)\ldots1$ gives $\sum_{j=0}^{n-1} (pq)^j$. The
contribution of the permutations where $\pi'=(n-1)\ldots(n+1-j)$ and
$\pi''\neq(n-j)\ldots1$ gives 
$$pq(A_{n-1}(p,q)-1)+\sum_{j=2}^n
q^jp^{j-1}(P_{n-j}(q)-1).$$ 
($P_n(q)$ is the polynomial appearing in the proof of
Theorem~\ref{thb3}.) The contribution of the permutations where
$\pi'\neq(n-1)\ldots(n+1-j)$ and $\pi''=(n-j)\ldots1$ gives
$\sum_{j=1}^nq^{j-1}(H_{j-1}(p)-1)$. ($H_n(p)$ is the polynomial appearing 
in the
proof of Theorem~\ref{thb2}). Finally, the contribution of the permutations
where
$\pi'\neq(n-1)\ldots(n+1-j)$ and $\pi''\neq(n-j)\ldots1$ equals
$\sum_{j=1}^n q^j(H_{j-1}(p)-1)(P_{n-j}(q)-1)$. Hence, for
$n\geq1$, we have
\begin{align*}
A_n(p,q)={}&pq(A_{n-1}(p,q)-1)+\sum_{j=0}^{n-1}(pq)^j
+q\sum_{j=1}^{n-1}(pq)^j(P_{n-1-j}(q)-1)\\
&+\sum_{j=0}^{n-1}q^j(H_{j}(p)-1)
+q\sum_{j=0}^{n-1}q^j(H_j(p)-1)(P_{n-1-j}(q)-1).
\end{align*}
Let $A(x;p,q)$, $P(x;q)$, and $H(x;p)$ be the generating functions
for the sequences\break $A_n(p,q)$, $P_n(q)$, and $H_n(p)$, respectively, 
that is,
$$A(x;p,q)=\sum_{n\geq0}A_n(p,q)x^n,\quad P(x;q)=\sum_{n\geq0}P_n(q)x^n,
\quad \text{and}\quad 
H(x;p)=\sum_{n\geq0}H_n(p)x^n.$$ 
Multiplying
the above recurrence by $x^n$, summing over $n\geq1$, and finally using
$A_0(p,q)=H_0(p)=P_0(q)=1$, we obtain that
\begin{align*}
(1-pqx)A(x;p,q)={}&1+\frac{x}{(1-x)(1-pqx)}+\frac{x}{1-x}\left(H(qx;p)-\frac{1}{1-qx}\right)\\
&+\frac{qx}{1-pqx}\left(P(x;q)-\frac{1}{1-x}\right)-qx\left(P(x;q)-\frac{1}{1-x}\right)\\
&-\frac{pqx}{1-x}+xq\left(H(qx;p)-\frac{1}{1-qx}\right)\left(P(x;q)-\frac{1}{1-x}\right).
\end{align*}
From Theorem~\ref{thb2} we have
$$H(x;q)=\frac{1}{1-qxC(x)}+\frac{1}{1-x}-\frac{1}{1-qx},$$
while Theorem~\ref{thb3} yields
$$P(x;q)=\frac{1}{1-x}(1+x(C(qx)-1)C(qx)).$$ 
Hence,
$$A(x;p,q)=1+\frac{x(1-p+p(1-2qx+pq^2x^2)C(qx))}{(1-x)(1-pqx)(1-pqxC(qx))}.$$

We now turn to the computation of the generating function
$$B(x;p,q)=\sum_{n\geq0}\sum_{\pi\in
R_n}p^{n-\ldes(\pi)}q^{n-\fdes(\pi)}x^n.$$ 
Using the arguments in
the proof of the formula for $A(x;p,q)$, we get that
$$B(x;p,q)=A(x;p,q)-\frac{1}{1-x}+\frac{1}{1-pqx}.$$
Hence,
\begin{align*}
\sum_{n\geq0}\sum_{\pi\in R_n\backslash\{12\ldots
n\}}p^{n-\ldes(\pi)}q^{n-\fdes(\pi)}x^n&=B(x;p,q)-\dfrac{1}{1-pqx}\\
&=A(x;p,q)-\dfrac{1}{1-x}\\
&=\sum_{n\geq0}\sum_{\pi\in
R_n\backslash\{n\ldots21\}}p^{\fris(\pi)}q^{\lris(\pi)}x^n,
\end{align*} 
as requested.
\end{proof}

\section{Sign Balance on $R_n$}
We denote the set of all {\em even} (respectively {\em odd\/}) permutations
$\pi\in R_n$ by $R_n^{+}$ (respectively $R_n^{-}$). We define
$e_n=|R_n^{+}|$, $o_n=|R_n^{-}|$, and $m_n=e_n-o_n$ for all
$n\geq0$. (Simion and Schmidt ~\cite{SS} proved that
$m_n=C_{(n-1)/2}$ if $n$ is odd and $m_n=0$ otherwise.) In this
section we study the sign-balance of $R_n$ with respect to certain
statistics.

\begin{theorem}\label{thc1}
We have
  $$\sum_{n\geq0}M_n(q)x^n
  =\sum_{n\geq0}\sum_{\pi\in R_n}\sign(\pi)q^{\ldes{(\pi)}}
  =\frac{1+x-x^2qC(x^2q^2)}{1-x^2C(x^2q^2)}.$$
\end{theorem}
\begin{proof}
Let $F_n^{\pm}(q)=\sum_{\pi\in R_n^{\pm}} q^{\ldes(\pi)}$, and let
$\pi=(\pi',n,\pi'')\in R_n$ such that $\pi_{j+1}=n$, $0\leq j\leq
n-1$. Then, for this block decomposition of $\pi$, we have
$$\sign(\pi)=(-1)^{(j+1)(n-j-1)}\sign(\pi')\sign(\pi'')=(-1)^{(j+1)(n-1)}\sign(\pi')\sign(\pi''),$$
or, equivalently,
$$\sign(\pi)=\left\{\begin{array}{ll}
                       \sign(\pi')\cdot\sign(\pi''),&\mbox{if}\, n\,\mbox{is odd,}\\
                        (-1)^{j+1}\cdot\sign(\pi')\cdot\sign(\pi''),\quad&\mbox{if}\,
                        n\,\mbox{is even}.
                        \end{array}\right.$$
Therefore, for $n\geq1$, we obtain
\begin{align*}
F_{2n+1}^{\pm}(q)&=F_{2n}^{\pm}(q)+\sl_{j=0}^{2n-1}q^{j+1}(e_jF^{\pm}_{2n-j}(q)+o_jF^{\mp}_{2n-j}(q))\\
F_{2n}^{\pm}(q)&=F_{2n-1}^{\pm}(q)+\sl_{j=0,2,4,\ldots,2n-2}q^{j+1}(e_jF_{2n-1-j}^{\mp}(q)+o_jF_{2n-1-j}^{\pm}(q))\\
&\kern3cm+
\sl_{j=1,3,\ldots,2n-3}q^{j+1}(e_jF_{2n-1-j}^{\pm}(q)+o_jF_{2n-1-j}^{\mp}(q).
\end{align*}
Hence, for all $n\geq1$, we have
\begin{align*}
M_{2n+1}(q)&=M_{2n}(q)+\sl_{j=0}^{2n-1}q^{j+1}m_jM_{2n-j}(q),\\
M_{2n}(q)&=M_{2n-1}(q)-\sl_{j=0,2,4,\ldots,2n-2}q^{j+1}m_jM_{2n-1-j}(q)\\
&\kern4cm+
\sl_{j=1,3,\ldots,2n-3}q^{j+1}m_jM_{2n-1-j}(q).
\end{align*}
Let $M(x;q)=\sum_{n\geq0}M_n(q)x^n$ and
$m(x)=\sum_{n\geq0}m_nx^n$. Using \cite[Lemma~2.3]{M2}, we get that
\begin{multline*}
(1-x-xqm(xq))M(x;q)-{}(1+x+xqm(-xq))M(-x;q)\\
=-xq(m(xq)+m(-xq)),
\end{multline*}
and
\begin{multline*}
(1-x+xqm(-xq))M(x;q)+{}(1+x-xqm(xq))M(-x;q)\\
=2-xq(m(xq)-m(-xq)).
\end{multline*}
Hence, solving the above two equations for the variables $M(x;q)$
and $M(-x;q)$, and using the fact that $m(x)=1+xC(x^2)$
(see~\cite{SS}), we obtain the desired result.
\end{proof}

As a corollary of the above theorem, we have the following result
concerning the sign-and-``ldes" statistic on $R_n$.

\begin{corollary}
For all $n\geq1$, we have
$$\sum_{\pi\in R_{2n}}\sign(\pi)(-1)^{\ldes(\pi)}=2C_n\mbox{ and
}\sum_{\pi\in R_{2n-1}}\sign(\pi)(-1)^{\ldes(\pi)}=C_{n-1}.$$
Moreover,
$$1+\sum_{n\geq1}\sum_{\pi\in
R_n}\sign(\pi)(-1)^{\ldes(\pi)}x^n=(1+x+x^2C(x^2))C(x^2).$$
\end{corollary}

More generally, Theorem~\ref{thc1} yields the following result.

\begin{corollary}\label{thcc}
For all $n\geq1$, we have
$$\sum_{\pi\in R_{2n}}\sign(\pi)q^{\ldes(\pi)}=(1-q)\sum_{\pi\in
R_{2n+1}}\sign(\pi)q^{\ldes(\pi)},$$ and
$$\sum_{\pi\in R_{2n-1}}\sign(\pi)q^{\ldes(\pi)}=\sum_{\pi\in
R_{n-1}}q^{2(\ldes(\pi))}.$$
\end{corollary}

\begin{theorem}\label{thcf}
We have
\begin{align*}
\sum_{n\geq0}N_n(q)x^n
&=\sum_{n\geq0}\sum_{\pi\in
R_n}\sign(\pi)q^{\fdes{(\pi)}}\\
&=1+x\dfrac{(1-q)(1-xq+2q)-q(1-x^2)(1+xq-2q)C(x^2)}{(1-x)(1-x^2q^2)}.\end{align*}
\end{theorem}
\begin{proof}
Let $L_n^{\pm}(q)=\sum_{\pi\in R_n^{\pm}} q^{\fdes(\pi)}$, and let
$\pi=(\pi',n,\pi'')\in R_n$ such that $\pi_{j+1}=n$, $0\leq j\leq
n-1$. Then, for this block decomposition of $\pi$, we have
$$\sign(\pi)=(-1)^{(j+1)(n-j-1)}\sign(\pi')\sign(\pi'')=(-1)^{(j+1)(n-1)}\sign(\pi')\sign(\pi''),$$
or, equivalently,
$$\sign(\pi)=\left\{\begin{array}{ll}
                       \sign(\pi')\cdot\sign(\pi''),&\mbox{if}\, n\,\mbox{is odd,}\\
                        (-1)^{j+1}\cdot\sign(\pi')\cdot\sign(\pi''),\quad&\mbox{if}\,
                        n\,\mbox{is even}.
                        \end{array}\right.$$
Therefore, for $n\geq1$, we obtain
\begin{align*}
L_{2n+1}^{\pm}(q)&=\sl_{j=0}^{2n-1}q^{j+1}L_{2n-j}^{\pm}+(L_j^{\pm}(q)-\epsilon^{\pm})e_{2n-j}+(L_j^{\mp}(q)-\epsilon^{\mp})o_{2n-j}\\
L_{2n}^{\pm}(q)&=\sl_{j=0,2,4,\ldots,2n-2}q^{j+1}L_{2n-1-j}^{\mp}(q)+(L_j^{\mp}(q)-\epsilon^{\mp})e_{2n-1-j}+(L_j^{pm}(q)-\epsilon^{\pm})o_{2n-1-j}\\
&\qquad +\sl_{j=1,3,\ldots,2n-3}q^{j+1}L_{2n-1-j}^{\pm}\\
&\qquad +
\sl_{j=1,3,\ldots,2n-3}(L_j^{\pm}-\epsilon^{\pm})e_{2n-1-j}+(L_j^{\mp}-\epsilon^{\mp})o_{2n-1-j},
\end{align*}
where $\epsilon^+=1$ and $\epsilon^-=0$. Hence, for all $n\geq1$, we have
\begin{align*}
N_{2n+1}(q)&=1+\sl_{j=0}^{2n-1}q^{j+1}m_{2n-j}+\sl_{j=0}^{2n}(N_j(q)-1)m_{2n-j},\\
M_{2n}(q)&=1-\sl_{j=0,2,\ldots,2n-2}q^{j+1}m_{2n-1-j}+
\sl_{j=1,3,\ldots,2n-3}q^{j+1}m_{2n-1-j}\\
&\kern1cm
-\sl_{j=0,2,\ldots,2n-2}(N_j(q)-1)m_{2n-1-j}+
\sl_{j=1,3,\ldots,2n-1}(N_j(q)-1)m_{2n-1-j}.
\end{align*}
Let $N(x;q)=\sum_{n\geq0}N_n(q)x^n$ and
$m(x)=\sum_{n\geq0}m_nx^n$. Using \cite[Lemma~2.3]{M2}, we get that
\begin{multline*}
\frac{1}{2}(N(x;q)-N(-x;q))=\frac{x}{1-x^2}+\frac{xq}{2}\left(\frac{m(x)}{1-xq}+\frac{m(-x)}{1+xq}-\frac{2}{1-x^2q^2}\right)\\
+\frac{x}{2}\left[\left(N(x;q)-\frac{1}{1-x}\right)m(x)+\left(N(-x,q)-\frac{1}{1+x}\right)m(-x)\right],
\end{multline*}
and
\begin{align*}
\frac{1}{2}(N(x;q)+N(-x,q))={}&\frac{1}{1-x^2}-\frac{xq}{2(1-x^2q^2)}(m(x)-m(-x))\\
&+\frac{x^2q^2}{2(1-x^2q^2)}(m(x)+m(-x)-2)\\
&-\frac{x}{4}\left(N(x;q)+N(-x;q)-\frac{2}{1-x^2}\right)(m(x)-m(-x))\\
&+\frac{x}{4}\left(N(x;q)-N(-x;q)-\frac{2x}{1-x^2}\right)(m(x)+m(-x)).
\end{align*}
Hence, solving the above two equations for the variables $N(x;q)$
and $N(-x;q)$, and using the fact that $m(x)=1+xC(x^2)$
(see~\cite{SS}), we get the desired result.
\end{proof}
%----------------------------------------
\section{Dyck paths}
Following \cite{Kr}, we define a bijection $\Phi$ between
permutations in $S_n(132)$ and Dyck paths from the origin to the
point $(2n,0)$. Let $\pi=\pi_1\dots\pi_n$ be a $132$-avoiding
permutation. We read the permutation $\pi$ from left to right and
successively generate a Dyck path. When $\pi_j$ is read, then in
the path we adjoin as many up-steps as necessary, followed by a
down-step from height $h_j+1$ to height $h_j$ (measured from the
$x$-axis), where $h_j$ is the number of elements in
$\pi_{j+1},\pi_{j+2},\dots,\pi_n$ which are larger than $\pi_j$.
For example, if $\pi=534261\in S_6$, then the corresponding Dyck path
is the one shown in Figure~\ref{fig1}.
\begin{center}
\begin{figure}[ht]
$$
\Gitter(13,5)(0,0)
\Koordinatenachsen(13,5)(0,0)
\Pfad(0,0),334334434434\endPfad
\Label\lu{0}(0,0)
\Label\u{\scriptstyle 1}(1,0)
\Label\u{\scriptstyle 2}(2,0)
\Label\u{\scriptstyle 3}(3,0)
\Label\u{\scriptstyle 4}(4,0)
\Label\u{\scriptstyle 5}(5,0)
\Label\u{\scriptstyle 6}(6,0)
\Label\u{\scriptstyle 7}(7,0)
\Label\u{\scriptstyle 8}(8,0)
\Label\u{\scriptstyle 9}(9,0)
\Label\u{\scriptstyle 10}(10,0)
\Label\u{\scriptstyle 11}(11,0)
\Label\u{\scriptstyle 12}(12,0)
\Label\l{\scriptstyle 1}(0,1)
\Label\l{\scriptstyle 2}(0,2)
\Label\l{\scriptstyle 3}(0,3)
\Label\l{\scriptstyle 4}(0,4)
\Label\r{\scriptstyle x}(13,0)
\Label\o{\scriptstyle y}(0,5)
\hskip6.5cm
$$
\caption{The Dyck path
$\Phi(534261)$.} \label{fig1}
\end{figure}
\end{center}
Namely, the first element to be read is $5$. There is one element in
$34261$ which is larger than $5$, therefore the path starts with
two up-steps followed by a down-step, thus reaching height $1$.
Next $3$ is read. There are $2$ elements in $4261$ which are
larger than $3$, therefore the path continues with two up-steps
followed by a down-step, thus reaching height $2$. Etc.
Conversely, given a Dyck path starting at the
origin and returning to the $x$-axis, the obvious inverse of the
bijection $\Phi$ produces a $132$-avoiding permutation.

\begin{theorem}\label{thd1}
For all $n\geq0$, we have
$$\sum_{p\in\PP_n}q^{n-\mld(p)}=\sum_{\pi\in R_n}q^{\ldes(\pi)}.$$
\end{theorem}
\begin{proof}
We prove that $n+1-\mld(\Phi(\pi))=fdes(\pi)$ for any $\pi\in
R_n$. Let $\pi=(\pi',1,\pi'')\in R_n$ such that $\pi_1=j$. Since
$\pi$ avoids $132$, the letters of $\pi''$ are
increasing (i.e., $\pi''_a<\pi''_b$ for all $a<b$). Therefore, by
definition of $\Phi$, the Dyck path $p=\Phi(\pi)$
satisfies the equation $\mld(p)=|\pi''|+1=n+1-j$, where $|\pi''|$ is the
number of letters in $\pi''$.
\end{proof}

\begin{remark}
The relation $n+1-\mbox{\em peak}(\Phi(\pi))=\fdes(\pi)$ for $\pi\in
R_n$ can be read off immediately from the permutation diagram,
see~\cite{R}.
\end{remark}

{\bf Acknowledgment}. The author thanks the anonymous referee,
whose suggestions improved both the content and exposition of this
paper. The final version of this paper was written during the
author's stay at the University of Haifa, Israel, and he would
like to express his gratitude to the University of Haifa for the
support.
%=========================================================================
\begin{thebibliography}{99}
\bibitem[AR]{AR}
{\sc Ron M. Adin and Yuval Roichman}, Equidistribution and
sign-balance on $321$-avoiding permutations, preprint, 2003,
{\tt $<$http://arXiv.org/abs/math.CO/0304429$>$}.

\bibitem[FS]{FS}
{\sc D. Foata and M.-P. Sch\"utzenberger}, Major index and
inversion number of permutations, {\em Math. Nachr.} {\bf 83}
(1978), 143--159.

\bibitem[Kn]{Kn}
{\sc D.~Knuth}, {\em The Art of Computer Programming}, vol. 1,
Addison Wesley, Reading, MA, 1968.

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

\bibitem[M1]{M}
{\sc T. Mansour}, Counting peaks at height $k$ in a Dyck path,
{\em Journal Integer of Sequences} {\bf 5} (2002), Article 02.1.1.

\bibitem[M2]{M2}
{\sc T. Mansour}, Restricted $132$-alternating permutations and
Chebyshev polynomials, {\em Annals of Combinatorics} {\bf 7:2} (2003),
201--227.

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

\bibitem[SimSch]{SS}
{\sc R.~Simion and F.~Schmidt}, Restricted permutations, {\em
European J. Combin.} {\bf 6} (1985), 383--406.

\bibitem[R]{R}
{\sc A.~Reifegerste}, On the diagram of $132$-avoiding permutations,
{\em European J. Combin.} {\bf 24} (2003), 759--776.

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