%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% R.CLARKE et al. Latex-file of "Euler-Mahonian permutation statistics" SLC 35
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\documentstyle[12pt]{article}

\newcommand\mb{\boldmath}
\newcommand\mn{\rm}
\newcommand\mc{\cal}

\def\disp{\displaystyle}
\def\+{\; + \;}
\def\-{\; - \;}
\def\ra{\rightarrow}
\def\vecn#1{(#1_1,\ldots,#1_n)}
\def\permn#1{#1_1\cdots #1_n}
\def\cl#1{{\mc #1}}

\newcommand\ch{\choose} %Binomial coefficients
\newcommand\st{\; | \;} %Bar in a set with extra space around
\newcommand\clS{{\mc S}}        %Symmetric group
\newcommand\sn{\mbox{${\mc S}_n$}}        %Symmetric group

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Eulerian stats %%%%%%%%%%%%%%%%%%%%%%
\newcommand\des{\mathop{\mn des}}
\newcommand\exc{\mathop{\mn exc}}
\newcommand\eul{\mathop{\mn eul}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Mahonian stats %%%%%%%%%%%%%%%%%%%%%%
\newcommand\inv{\mathop{\mbox{\sc inv}}\nolimits}

\newcommand\invmv{\mathop{\mbox{\sc
      inv}}_{\mbox{$\mn\scriptscriptstyle MV$}}\nolimits}
\newcommand\expinv{\mathop{\mbox{$\mn\scriptscriptstyle INV$}}}
\newcommand\env{\mathop{\mbox{\sc env}}\nolimits}
\newcommand\maj{\mathop{\mbox{\sc maj}}\nolimits}
\newcommand\expmaj{\mathop{\mbox{$\mn\scriptscriptstyle MAJ$}}}
\newcommand\imaj{\mathop{\mbox{\sc imaj}}\nolimits}
\newcommand\mad{\mathop{\mbox{\sc mad}}\nolimits}
\newcommand\expmad{\mathop{\mbox{$\mn\scriptscriptstyle MAD$}}}
\newcommand\mak{\mathop{\mbox{\sc mak}}\nolimits}
\newcommand\madl{\mathop{\mbox{\sc madl}}\nolimits}
\newcommand\makl{\mathop{\mbox{\sc makl}}\nolimits}
\newcommand\den{\mathop{\mbox{\sc den}}\nolimits}
\newcommand\mah{\mathop{\mbox{\sc mah}}\nolimits}
\newcommand\sist{\mathop{\mbox{\sc sist}}\nolimits}
\newcommand\lag{\mathop{\mbox{\sc lag}}\nolimits}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Partial stats %%%%%%%%%%%%%%%%%%%%%%
\def\emb#1{e_#1}
\newcommand\rsg{\mathop{\mn Res}}
\newcommand\res{\mathop{\mn Res}}
\newcommand\les{\mathop{\mn Les}}
\newcommand\dtop{\mathop{\mn Dtop}}
\newcommand\etop{\mathop{\mn Etop}}
\newcommand\dbot{\mathop{\mn Dbot}\nolimits}
\newcommand\ebot{\mathop{\mn Ebot}}
\newcommand\ddiff{\mathop{\mn Ddif}\nolimits}
\newcommand\ddif{\mathop{\mn Ddif}}
\newcommand\ediff{\mathop{\mn Edif}}
\newcommand\edif{\mathop{\mn Edif}}
\newcommand\imv{\mathop{\mn Imv}}
\newcommand\ine{\mathop{\mn Ine}}
\newcommand\run{\mathop{\mn Run}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Miscellaneous %%%%%%%%%%%%%%%%%%%%%%
\def\EXC#1{#1_{\mbox{$\mn\scriptscriptstyle E$}}}
\def\NEX#1{#1_{\mbox{$\mn\scriptscriptstyle N$}}}
\def\inve#1{\inv #1_{\mbox{\sc e}}}
\def\imve#1{\imv #1_{\mbox{\sc e}}}
\def\invn#1{\inv #1_{\mbox{\sc n}}}
\def\phiw{\mbox{$\Phi_{\mbox{$\mn\scriptscriptstyle W$}}$}}
\newcommand\op{\mbox{\sc o}}
\newcommand\clo{\mbox{\sc c}}
\newcommand\imversion{\mbox{i\kern -.15mm{\em m}\kern .15mm version}}
\newcommand\imversions{\mbox{i\kern -.15mm{\em m}\kern .15mm versions}}
\newcommand\iimversion{\mbox{i\kern .23mm{\em m}\kern -.23mm version}}
\newcommand\iimversions{\mbox{i\kern .23mm{\em m}\kern -.23mm versions}}
\def\NE{{\mn N}}
\def\SE{{\mn S}}
\def\sE{{\mn E}}
\def\dE{{\mn dE}}
\newcommand{\mpg}{\marginpar}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\lbiw#1#2#3{\pmatrix{
#1_1\; #1_2\;\cdots #1_#3\; \cr
#2_1\; #2_2\;\cdots #2_#3\; \cr
}}

\def\biw#1#2{\pmatrix{
#1\cr
#2\cr
}}

\def\bbiw#1#2{\pmatrix{
\mb #1\cr
\mb #2\cr
}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand\wt{\mbox{$\widetilde{w}$}}
\newcommand\piti{\mbox{$\widetilde{\pi}$}}
\newcommand\w{\mbox{$w$}}
\newcommand\p{\mbox{$\pi$}}
\newcommand\pp{\mbox{$\pi'$}}
\newcommand\ta{\mbox{$\tau$}}
\newcommand\wb{\mbox{$\overline{w}$}}
\newcommand\pib{\mbox{$\overline{\pi}$}}
\newcommand\ol{\overline}
\newcommand\e{\mbox{$\epsilon$}}
\newcommand\ep{\mbox{$\epsilon(\pi)$}}
\newcommand\eep{\mbox{$\epsilon^2(\pi)$}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  Structure of Thms. etc.  %%%%%%%%%%%%%%
\newtheorem{thm}{Theorem}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{defn}{Definition}
\newtheorem{defns}[defn]{Definitions}
\newtheorem{eg}{Example}
\newtheorem{egs}[eg]{Examples}
\newtheorem{remark}{Remark}
\newtheorem{fact}[remark]{Fact}
\newtheorem{blank}[remark]{$\!\!$}
\newtheorem{porism}[thm]{Porism}
\newtheorem{conj}{Conjecture}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%
\newcommand{\pf}{{\bf Proof: \/}}

\renewcommand{\thefootnote}{\fnsymbol{footnote}}

%%% \qed produces a square at the end of the line.
\def\qed{\nobreak\quad\raise -2pt\hbox{\vrule\vbox to 10pt{\hrule width 4pt
\vfill\hrule}\vrule}\par\vspace{2ex}}
%The following variation is useful if you don't want a \par or \vspace after.
\def\qel{\nobreak\quad\raise -2pt\hbox{\vrule\vbox to 10pt{\hrule width 4pt
\vfill\hrule}\vrule}}

\hyphenation{mac-mahon}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\begin{document}

%\pagestyle{empty}

\title{New Euler--Mahonian permutation statistics}
\author{Robert J. Clarke%
\thanks{This work was carried out while the author was Visiting
Professor at the Universit\'e Louis-Pasteur in Strasbourg during summer and
autumn of 1995.}
\\Pure Mathematics Department
\\University of Adelaide
\\Adelaide, South Australia 5005
\and
Einar Steingr{\'\i}msson%
\thanks{Partially supported by a grant from
      The Icelandic Council of Science and partially supported by the EU
      Network in Algebraic Combinatorics while visiting Universit\'e
      Louis-Pasteur in Strasbourg.}\\
Matematiska institutionen \\
CTH \& GU\\
412 96 G\"oteborg, Sweden
\and
Jiang Zeng\thanks{Partially supported by the EU
Network in Algebraic Combinatorics.}
\\ D\'epartement de math\'ematique
 \\Universit\'e Louis-Pasteur
\\ 67084 Strasbourg Cedex, France}
\date{March 5, 1996}
\maketitle
\newpage

\begin{abstract}
\noindent We define or redefine new Mahonian permutation statistics, called
$\mad$, $\mak$ and $\env$.  Of these, $\env$ is shown to equal the classical
$\inv$, that is the number of inversions, while $\mak$ has been defined in a
slightly different way by Foata and Zeilberger.  It is shown that the triple
statistics $(\des,\mak,\mad)$ and $(\exc,\den,\env)$ are equidistributed over
\sn. Here $\den$ is Denert's statistic.  In particular, this implies the
equidistribution of $(\exc,\inv)$ and $(\des,\mad)$. These bistatistics are not
equidistributed with the classical Euler-Mahonian statistic
($\des$,$\maj$).  The
proof of the main result is by means of a bijection which is essentially
equivalent to several bijections in the literature (or inverses of these).
These
include bijections defined by Foata and Zeilberger, by Fran\c con and
Viennot and
by Biane, between the symmetric group and sets of weighted Motzkin paths.  These
bijections are used to give a continued fraction expression for the generating
function of $(\exc,\inv)$ or $(\des,\mad)$ on the symmetric group.
\end{abstract}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\newpage
\section{Introduction}
The subject of permutation statistics, it is frequently claimed, dates back at
least to Euler \cite{euler}.  However, it was not until MacMahon's extensive
study \cite{macmahon} at the turn of the century that this became an established
discipline of mathematics, and it was to take a long time before it developed
into the vast field that it is today.

In the last three decades or so, much progress has been made in discovering and
analyzing new statistics.  See for example \cite{foa1, foa2, FS1, FS2, FZ, ra,
simstan1, stanley}.  Inroads have also been made in connecting permutation
statistics to various geometric structures and to the classical theory of
hypergeometric functions, as in \cite{fla, fravie, garges, medvie}.

MacMahon considered four different statistics for a permutation \p: The
number of
descents ($\des \p$), the number of excedances ($\exc \p$), the number of
inversions ($\inv \p$), and the major index ($\maj \p$).  These are defined as
follows:  A descent in a permutation $\pi = a_1 a_2\cdots a_n$ is an $i$ such
that $a_i>a_{i+1}$, an excedance is an $i$ such that $a_i>i$, an inversion is a
pair $(i,j)$ such that $i<j$ and $a_i>a_j$, and the major index of \p\ is
the sum
of the descents in \p. (In fact, MacMahon studied these statistics in greater
generality, namely over the rearrangement class of an arbitrary word \w\ with
possibly repeated letters. However, although all of our present results except
those of section \ref{motzkin} can be generalized to words, and this will
be done
in a subsequent publication, \cite{CSZ}, we restrict our attention here to
permutations.)

MacMahon showed, algebraically, that $\exc$ is {\em equidistributed}\/ with
$\des$, and that $\inv$ is equidistributed with $\maj$, over \sn. That is
to say,
$$\sum_{\pi\in\cl S_n}{t^{\exc\pi}} = \sum_{\pi\in\cl S_n}{t^{\des z}}
\mbox{\hskip 5mm and \hskip 5mm} \sum_{\pi\in\cl S_n}{q^{\expinv\pi}} =
\sum_{\pi\in\cl S_n}{q^{\expmaj\pi}}.$$
The first combinatorial proof of these equidistribution results were given by
Foata (see \cite{foa2}).

Any permutation statistic that is equidistributed with ``$\des$'' is said to be
{\em Eulerian} and a permutation statistic that is equidistributed with
$\inv$ is
said to be {\em Mahonian} (see \cite{foa1}). Most of the permutation statistics
found in the literature fall into one of these two categories; they are either
Eulerian or Mahonian.

\pagestyle{plain}
Curiously, new Eulerian statistics have not become prominent since Mac-Mahon's
definition of $\des$ and $\exc$, whereas new Mahonian statistics are constantly
entering the scene.  Proving directly that a statistic is Mahonian is by no
means
always trivial, and there are still many such statistics for which no direct
proof exists.  What is more interesting, however, is the study of {\em pairs} of
statistics, usually an Eulerian one and a Mahonian one, and equidistribution of
such {\em bistatistics}, first developed in \cite{foa1}.

The first pair of equidistributed Euler-Mahonian bistatistics to be discovered
was that of $(\des,\inv)$ and $(\des,\imaj)$, where $\imaj \p$ is the major
index
of the {\em inverse} of the permutation \p\ (see \cite{FS2}).  Although
instrumental in some of the analytic developments of the subject, this discovery
cannot be extended to words with repetition of letters.  In addition, the
purists
among us are reluctant to admit to the Euler-Mahonian club a pair of pairs that
really is only a triple.  Thus, they would recommend that $(\des,\inv)$ be
accompanied by $\exc$ and a suitable Mahonian partner.

The first discovery of a {\em proper} pair of equidistributed Euler-Mahonian
bistatistics is only a few years old, and it came from a rather unexpected
direction.  Denert \cite{denert}, in 1990, conjectured that the pair
$(\des,\maj)$ was equidistributed with the pair $(\exc,\den)$, where $\den$ is a
Mahonian statistic somewhat related to, but crucially different from, $\inv$.
Shortly afterwards, her conjecture was proved by Foata and Zeilberger \cite{FZ},
who named the new statistic ``Denert's statistic''.  In the process, Foata and
Zeilberger defined yet another Mahonian statistic on permutations, which they
called $\mak$, and which, when taken together with $\des$, they showed to be
equidistributed with $(\exc,\den)$.

It is fair to say that the discovery of Denert's statistic paved the way to the
more esoteric reaches of Mahonian statistics, because it was the first such
statistic to be composed of ``smaller'' partial statistics. Since then,
many such
composite Mahonian statistics have been discovered, and most of these are
treated
here.

The pairs of bistatistics $(\exc,\den)$, $(\des,\maj)$ vs. $(\exc,\den)$,
$(\des,\mak)$ were the first proper pairs of Euler-Mahonian statistics to be
shown equidistributed over the symmetric group, and they are, to the best of our
knowledge, the only ones preceding the present paper. It is possible to vary the
definition of $\mak$ slightly, as will be made clear later, to obtain a new
statistic. However, the bistatistics obtained are equidistributed with each
other, and this is easy to show.

\vskip 6pt
\centerline{---------------}
\vskip 6pt

In the present paper, we define some new Mahonian statistics and redefine
many of
the existing ones, with an eye to illuminating their common properties and thus
also their differences.  Doing this allows us to recover some of the known
instances of equidistribution among Euler-Mahonian pairs, and to prove the
equidistribution of two new pairs introduced, as well as that of some similiar,
but not equal, pairs of bistatistics.  We do this simultaneously for all the
statistics involved, by means of a single, simply described bijection.

All of our constructions, and some of our statistics, have appeared previously,
in the work of several authors and in many different guises.  They have involved
Motzkin paths, binary trees, and even more exotic structures. As we will show,
the bijections in the literature pertaining to these statistics, those of
Foata--Zeilberger, Fran\c con--Viennot \cite{fravie}, de M\'edicis--Viennot
\cite{medvie}, Simion--Stanton \cite{simstan1} and Biane \cite{biane},
defined in
different ways and for different purposes, are all essentially the same, or
inverses of each other. These bijections are equivalent to the bijection of this
paper, but their relationships with each other have not before been elucidated.

Perhaps the most interesting fact to emerge is the equidistribution of the two
bistatistics $(\des,\mad)$ and $(\exc,\inv)$, where $\mad$ is one of our new
statistics. The latter bistatistic, whose components are classical, is {\em not}
equidistributed with $(\des,\maj)$ and might therefore, together with its
equidistributed mates, be classified as an ``Euler-Mahonian pair of the second
kind.'' In fact there exist at least three different {\em families} of
Euler-Mahonian statistics.  The first one, containing $(\des,\maj)$,
$(\des,\mak)$, and $(\exc,\den)$, has been extensively studied, both
analytically
and bijectively.  For the family containing $(\des,\inv)$ and $(\des,\imaj)$,
only the analytic branch has seen substantial development (see
\cite{fohan}). The
bijective theory of the family with $(\des,\mad)$ and $(\exc,\inv)$ is
thoroughly
analyzed in the present paper, but its analytic properties remain to be further
elicited.

It is, of course, possible to define scores of different families of
Euler-Mahonian statistics by arbitrarily combining an Eulerian statistic and a
Mahonian one.  Although some needles are sure to be found in that haystack, most
of the possible such statistics seem rather unattractive, and unlikely to
possess
particularly interesting properties.

An essential feature of our bijection is that it simultaneously preserves
each of
several building blocks of the statistics involved. This allows us to derive the
equidistribution of the triples of statistics $(\des,\mak,\mad)$ and
$(\exc,\den,\inv)$, involving Mahonian statistics of both the first and second
kind.

\vskip 6pt
\centerline{---------------}
\vskip 6pt

In the rest of this section we will present the formal definitions of our
statistics and state the main results and indicate precisely the relationship
between our statistics and those previously defined. These results will be
proved
in sections \ref{bijperm} and \ref{motzkin}. In section \ref{variations} we
present some variations and generalizations on our statistics.


\subsection{Definitions and main results}\label{defns}

We consider the set $\cal S_A$ of all permutations $\pi = a_1 a_2\cdots
a_n$ on a
totally ordered alphabet $\cl A$. Although it is not necessary, we always take
$\cl A$ to be the interval $[n] = \{1,2,\ldots,n\}$.  Thus, we consider
permutations in \sn.

The {\em biword associated to} a permutation $\pi=a_1a_2\ldots a_n$ is
$$
\piti = \pmatrix{
1&\; 2\;&\cdots &n\; \cr
a_1&\; a_2\;&\cdots &a_n\;\cr
}$$

This notation will be adhered to throughout, that is, if $\pi$ is a permutation,
then \piti\ has the above meaning.

\begin{defn}
Let $\p\in\sn$. A {\em descent} in \p\ is an integer $i$ with $1\le i<n$ such
that $a_i>a_{i+1}$.  Here $a_i$ is called the {\em descent top\/} and $a_{i+1}$
is called the {\em descent bottom\/}.  An {\em excedance} in \p\ is an integer
$i$ with $1\le i\le n$ such that and $a_i>i$.  Here $a_i$ is called the {\em
excedance top\/}. The {\em number of descents in} \p\ is denoted by $\des\pi$,
and the {\em number of excedances} is denoted by $\exc\pi$.

The {\em descent set of \p \/}, $D(\pi)$, is the set of descents.  The {\em
excedance set of \p \/}, $E(\pi)$, is the set of excedances.
\end{defn}

Given a permutation $\pi = a_1a_2\cdots a_n$, we separate \p\ into its {\em
descent blocks} by putting in dashes between $a_i$ and $a_{i+1}$ whenever
$a_i\le
a_{i+1}$.  A maximal contiguous subword of \p\ which lies between two
dashes is a
descent block.  A descent block is an {\em outsider}\/ if it has only one
letter,
otherwise it is a {\em proper} descent block. The leftmost letter of a proper
descent block is its {\em closer} and the rightmost letter is its {\em
opener}. A
letter which lies strictly inside a descent block is an {\em insider}. For
example, the permutation $1\ 8\ 5\ 2\ 6\ 7\ 9\ 3\ 4$ has descent block
decomposition $1-8\ 5\ 2-6-7-9\ 3-4$, with closers 8, 9, corresponding
openers 2,
3, outsiders 1, 6, 7, 4 and insider 5.  We will frequently write a permutation
\p\ with its separating dashes to emphasize this structure.

Let $B$ be a proper descent block of the permutation \p\ and let $\clo(B)$ and
$\op(B)$ be the closer and opener, respectively, of $B$.  If $a$ is a letter of
\w, we say that $a$ {\em is embraced by} $B$ if $\clo(B)> a > \op(B)$.

\begin{defn}\label{e numbers}
Let $\pi=a_1a_2\cdots a_n$ be a permutation.  The {\em (right) embracing
numbers\/} of \p\ are the numbers $e_1,e_2, \ldots, e_n$, where $e_i$ is the
number of descent blocks in \p\ that are strictly to the right of $a_i$ and that
embrace $a_i$.  The {\em right embracing sum} of \p, denoted by $\res\pi$, is
defined by
$$\res\pi = e_1+e_2+\cdots+e_n.$$
\end{defn}
For instance, the embracing numbers of $\pi=4\ 1-7-8\ 2-5-6\ 3$ are $2\ 0-1-0\
0-1-0\ 0$, so $\res \pi = 4$.

One can obviously define $\les\pi$ in an analogous way, by simply replacing
``right'' by ``left'' in the above definition. (See section \ref{variations}.)

\medskip
\begin{defn}%
The {\em descent bottoms sum} of a permutation $\pi = a_1a_2\cdots a_n$, denoted
by $\dbot\pi$, is the sum of the descent bottoms of \p. The {\em descent tops
sum} of \p, denoted by $\dtop\p$, is the sum of the descent tops of \p. The {\em
descent difference} of \p\ is
$$ \ddiff\pi=\dtop\pi-\dbot\pi.$$
\end{defn}
Otherwise expressed, $\ddiff \pi$ is the sum of closers minus the sum of openers
of descent blocks. As an example, for $\pi =4\ 1-2-6\ 5\ 3-7$, $\dbot
\pi=1+5+3=9$, $\dtop \pi= 4+6+5=15$ and $\ddiff \pi = 15-9=(4+6)-(1+3)=6$.

\begin{defn}
The {\em excedance bottoms sum} of a permutation $\pi = a_1a_2\cdots a_n$,
denoted by $\ebot\pi$, is the sum of the excedances of \p. The {\em excedance
tops sum} of \p, denoted by $\etop \pi$, is the sum of the excedance tops of \p.
The {\em excedance difference} of \p\ is
$$ \ediff\pi= \etop\pi-\ebot\pi. $$
The {\em excedance subword of \p\/}, denoted by $\EXC\p$, is the permutation
consisting of all the excedance tops of \p, in the order induced by \p. The {\em
non-excedance subword of \p\/}, denoted by $\NEX\p$, consists of those
letters of
\p\ that are not excedance tops.
\end{defn}
For example, let $\pi = 6\ 5\ 4\ 3\ 7\ 1\ 2$, so
$$\piti=\pmatrix{1&2&3&4&5&6&7\cr 6&5&4&3&7&1&2 \cr }.$$
Then $\EXC\pi= 6\ 5\ 4\ 7$ and $\NEX\pi= 3\ 1\ 2$. Also, $\ebot\pi=1+2+3+5=11$,
$\etop\pi=6+5+4+7=22$ and $\ediff\pi=22-11=11$.
\begin{defn}
An {\em inversion} in a permutation $\pi = a_1 a_2\cdots a_n$ is a pair $(i,j)$
such that $i<j$ and $a_i>a_j$.  The {\em number of inversions in} \p\ is denoted
by $\inv\pi$.
\end{defn}
The reason we spell $\inv$ with all capital letters is that $\inv$ is a Mahonian
statistic. We do this consistently throughout the paper, that is, all Mahonian
statistics are spelled with uppercase letters. The two Eulerian statistics,
$\exc$ and $\des$, are spelled with lowercase letters, while ``partial
statistics'' (such as $\res$), used in the definitions of Mahonian statistics,
are merely capitalized.

\begin{defn}\label{invno}
Let $\pi = a_1 a_2\cdots a_n$ be a permutation and $i$ an excedance in \p.
We say
that {\em $a_i$ is the bottom of $d$ inversions\/} if there are exactly $d$
letters in \p\ to the left of $a_i$ that are greater than $a_i$, and we call $d$
the {\em inversion bottom number of $i$\/}. Similarly, if $i$ is a non-excedance
in \p\ and there are exactly $d$ letters smaller than $a_i$ and to the right of
$a_i$ in \p, then we say that $d$ is the {\em inversion top number of $i$.} The
{\em side number of $i$ in \p\/} is the inversion bottom number or the inversion
top number of $i$ in \p, according as $i$ is an excedance or not in \p. The {\em
sequence of side numbers of\/} \p\ is the sequence $s_1,s_2,\ldots, s_n$ where
$s_i$ is the side number of $i$.
\end{defn}
For example, let $\pi = 6\ 5\ 4\ 3\ 7\ 1\ 2$ as before, with $\EXC\pi= 6\ 5\ 4\
7$ and $\NEX\pi= 3\ 1\ 2$. Then the inversion bottom numbers of the
excedances in
\p\ are 0, 1, 2, 0 and the inversion top numbers of the non-excedances in
\p\ are
2, 0, 0.  Hence the sequence of side numbers of \p\ is 0, 1, 2, 2, 0, 0, 0.

Note that if $i$ is an excedance of the permutation \p, then any letter in \p\
that is to the left of $a_i$ and greater than $a_i$ must also be an excedance.
Hence, the sum of the inversion bottom numbers of the letters in $\EXC{\pi}$
equals the total number of inversions in $\EXC{\pi}$, that is, $\inv\EXC{\pi}$.
Similarly, the sum of the inversion top numbers of the letters in $\NEX{\pi}$
equals $\inv\NEX{\pi}$.

\begin{defn}\label{ine}
Let $\pi$ be a permutation. Then
$$\ine\pi=\inv\EXC\pi+\inv\NEX\pi.$$
\end{defn}
Hence, from the remark preceding definition \ref{ine}, we have
\begin{equation}
\ine \pi=s_1+\cdots+s_n.
\end{equation}

We now define the four Mahonian statistics central to this paper. All these
statistics have been more or less introduced in the litterature in
different ways
(see \cite{FZ, medvie, simstan1, ran} and section \ref{links}), but we redefine
them here in a way suitable to generalize to words).

\begin{defn} Let $\pi$ be a permutation. Then
\begin{eqnarray*}
\mak\pi&=&\dbot\pi \+ \res\pi.\\
\mad\pi&=&\ddiff\pi \+ \res\pi.\\
\den\pi&=&\ebot\pi \+ \ine\pi.\\
\env\pi&=&\ediff\pi \+ \ine\pi.
\end{eqnarray*}
\end{defn}

As it turns out, our statistic $\env$ equals the classical $\inv$. It may seem
superfluous to redefine $\inv$ in this way, but it turns out that $\env$'s
similarity in definition to $\mad$ is crucial in proving our main results.

We now describe the main results of this paper.

In section \ref{links} we will prove the result referred to above.
\begin{prop}\label{invenvinvmv}
For any permutation $\pi$ we have $\env \p =\inv \p=\invmv \p$.
\end{prop}
Here $\invmv$ is a statistic, first defined by de M\'edicis and Viennot, that
will be defined below.

In section \ref{bijperm} we will define a mapping $\Phi$ on \sn\ and prove the
following result.
\begin{prop}\label{phistat}
For any permutation \p, we have
\begin{eqnarray*}
(\des,\dbot,\ddiff,\res)\ \pi&=&(\exc,\ebot,\ediff,\ine)\ \Phi(\pi),\\
(\des,\mad,\mak)\ \pi&=&(\exc,\inv,\den)\ \Phi(\pi).
\end{eqnarray*}
\end{prop}
By showing that $\Phi$ is a bijection, we deduce the following theorem.
\begin{thm}\label{masterperm}
The quadristatistics
$$(\des, \dbot, \ddiff, \res)\quad\mbox{and}\quad
(\exc, \ebot,\ediff, \ine)$$
are equidistributed over the symmetric group \sn. That is,
$$\sum_{\pi\in\cl S_n}{t^{\des\p}x^{\dbot\p}y^{\ddiff\p}q^{\res\p}}
=\sum_{\pi\in\cl S_n}{t^{\exc\p}x^{\ebot\p}y^{\ediff\p}q^{\ine\p}}.$$
Hence the triple $(\des, \mad, \mak)$ is equidistributed with $(\exc, \inv,
\den)$ over $\cl S_n$.
\end{thm}

In section \ref{motzkin}, we shall make evident the relation between our
bijection $\Phi$ and some well-known bijections between the symmetric group \sn\
and weighted Motzkin paths. As a by-product, we will obtain a continued fraction
expansion, equation (\ref{dfrac}), for the ordinary generating function of
$$
D_n(x,q)=\sum_{\pi\in{\clS}_n}x^{\des\p}q^{\mad\p},
$$
and then derive a symmetric property of $D_n(x,q)$, see Corollary \ref{cor}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Links to the past}\label{links}

Some Mahonian statistics on \sn\ equivalent or similar to our $\env$ and $\mad$
have been given by Simion and Stanton \cite{simstan1} and by de M\'edicis and
Viennot \cite{medvie}, and more recently by Randrianarivony \cite{ran}.

More precisely, de M\'edicis and Viennot introduced a statistic which we denote
by $\invmv$ and which can be defined in our notation by
\begin{eqnarray}
\invmv \p =\ine \pi &+&\#\{(i,j)\mid i\leq j<\p(i),\,
\p(j)> j\}\label{invbis} \nonumber\\
&+&\#\{(i,j)\mid \p(i)<\p(j)\leq i, \, \p(j)\leq j\}.\label{demed}
\end{eqnarray}

However, their proof that $\inv$ equals $\invmv$ is fairly complicated, and can
be compared to that of the equivalence of the two definitions of $\den$ given in
\cite{FZ}. Another proof that $\inv$ equals $\invmv$ was given by
Randrianarivony
\cite{ran}, who used Motzkin paths and the bijection of Foata and Zeilberger. In
\cite{clarke}, Clarke gave a short proof of the equivalence of the two
definitions of $\den$, using equation (\ref{first}) below.  Here we will give a
short proof of the results of de M\'edicis and Viennot and of Clarke, as well as
of Proposition \ref{invenvinvmv}.

\begin{lem}\label{envinv}
For any permutation $\pi= a_1a_2\cdots a_n$ we have
\begin{equation}\label{bob}
\sum_{i\in E(\pi)}(a_i-i)=
\sum_{i\in E(\pi)}\#\{\,j\mid i<j, a_i>a_j, j\notin E(\pi)\,\}.
\end{equation}
\end{lem}
\pf The right-hand side equals
\begin{equation}\label{invbit}
\sum_{i\in E(\pi)}\left(\#\{\,j\mid i<j, a_i>a_j\,\} -\#\{\,j\mid i<j,
a_i>a_j,
j\in E(\pi)\,\}\right).
\end{equation}
Now,
\begin{eqnarray}
a_i-i &=&\#\{\,j\mid a_j<a_i\,\}-\#\{\,j\mid j<i\}\nonumber\\
&=&\#\{\,j\mid j>i,a_j<a_i\,\}-\#\{\,j\mid j<i,a_j>a_i\,\}.\label{envbit}
\end{eqnarray}
Hence, comparing (\ref{invbit}) and (\ref{envbit}), we must show that
\begin{equation}\label{bits}
\sum_{i\in E(\pi)}\#\{\,j\mid i<j, a_i>a_j, j\in E(\pi)\,\} =\sum_{i\in
E(\pi)}\#\{\,j\mid
j<i,a_j>a_i\,\}.
\end{equation}
Clearly, each of the sums in equation (\ref{bits}) is $\inv\EXC\pi$. \qed

\begin{lem}
For any permutation $\pi= a_1a_2\cdots a_n$ we have
\begin{eqnarray}%
\#\{(i,j)\mid i\leq j<a_i, \, a_j > j\}
=\#\{(i,j)\mid a_i<a_j\leq i, \, a_j >j\},&&\label{first}\\
\#\{(i,j)\mid i\leq j<a_i, \, a_j\le j\}
=\#\{(i,j)\mid a_i<a_j\leq i, \, a_j\le j\}.&&\label{second}
\end{eqnarray}
\end{lem}
\pf Notice that
\begin{eqnarray}
\sum_{i\in E(\pi)}(a_i-i)&=&\#\{(i,j)\mid i\leq j<a_i\} \nonumber \\
&=&\#\{(i,j)\mid i<j<a_i,\, a_j\leq j\}\label{invmvenv}\\
&&+\;\#\{(i,j)\mid i\leq j<a_i, \, a_j>j\},\nonumber
\end{eqnarray}
and the right-hand side of (\ref{bob}) equals
$$
 \#\{(i,j)\mid i<j<a_i,\, a_j\leq j\}+\;\#\{(i,j)\mid i<a_i,\,a_j<a_i\leq j\}.
$$
Identity (\ref{first}) follows then from Lemma \ref{envinv}.
On the other hand, it is not hard to see
that $\sum_{i\in E(\pi)}(a_i-i)$ can be written as
\begin{eqnarray*}
\#\{(i,j)\mid i\leq j<a_i\} =\#\{(i,j)\mid a_i<j\leq i\}=\#\{(i,j)\mid
a_i<a_j\leq i\}.
\end{eqnarray*}
Identity (\ref{second}) follows immediately from (\ref{first}).  \qed

Identity (\ref{first}) is that of Clarke \cite{clarke}.
\medskip

\noindent{\bf Proof of Proposition \ref{invenvinvmv}:}  The first equality
follows immediately from the first part of Lemma \ref{envinv}. Comparing
definition (\ref{demed}) with equation (\ref{invmvenv}), it follows from
(\ref{second}) that $\invmv \p =\env \p $. \qed

On the other hand, de M\'edecis and Viennot \cite[Proposition 6.2]{medvie}
gave a
Mahonian statistic they called ``lag'' (but which we call $\lag$, for the
sake of
consistency). It can be defined as follows: Given a permutation $\pi=a_1
a_2\cdots a_n$, let
$$\pi'=(n+1)a_1 a_2\cdots a_n0\in \cl S_{n+2}$$
and let $\run\pi$ be the number of descent blocks in \p. Then
$$\lag \pi = \ddif \pi' +\les \pi' - \run \pi-n.$$
It is not hard to see that $\lag \p =\mad\pi^r$, where $\p ^r=a_na_{n-1}\cdots
a_1$.

We define the {\em dual} of a permutation $\p=a_1 a_2\cdots a_n \in \sn$ as the
permutation $\pi^{\ast}= b_1 b_2\cdots b_n$, where $b_i= n+1-a_i$ for $1\leq
i\leq n$.  Simion and Stanton \cite{simstan1} use notions dual to ours, with
ascents instead of descents, and embracing by ascent blocks, which they call
``runs''.  They also use the notion of left embracing. Their statistic,
translated into our dual setting, is
$$\sist\; \pi = n-\run \pi +2\les\pi+\res\pi$$
(see Theorem 2 in \cite{simstan1}), so, since $n-\run \pi = \des \pi$, we
have
$$\sist\; \pi = \des \pi +2\les \pi +\res \pi.$$
A counterpart of this statistic, namely
$$\sist'\; \pi = \des \pi +2\res\pi +\les\pi,$$
whose dual was also defined by Simion and Stanton, is readily seen to equal
$\mad$, because of the identity:
$$ \ddiff\p = \des\p+\res\p+\les\p.$$

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage
\section{The bijection $\Phi$}\label{bijperm}

Before proving Proposition \ref{phistat} and Theorem \ref{masterperm}, we
describe the construction of a bijection $\Phi: \sn \ra \sn$ which takes a
permutation \p\ to a permutation \ta\ such that the set of descent tops in \p\
equals the set of excedance tops in \ta\ and the set of descent bottoms in \p\
equals the set of excedances in \ta. Moreover, the embracing numbers of \p\ are
preserved in a way that we now describe.

Observe that, since the letters of a permutation are distinct, we can refer to
the $i$-th embracing number $e_i$ of the permutation \p\ as the embracing number
of the {\em letter} $a_i$ in \p, and we will then denote $e_i$ by $e(a_i)$.
Similarly, we may if we wish denote the $i$-th side number of \p\ by $d(a_i)$.

We will construct $\ta = \Phi(\pi)$ in such a way that the embracing number of a
letter $a_i$ in \p\ is the side number of $a_i$ in \ta.

Given a permutation \p, we first construct two biwords, $\biw f {f'}$ and
$\biw g
{g'}$, and then form the biword $\tau'=\biw {f\; g} {f'\; g'}$ by concatenating
$f$ and $g$, and $f'$ and $g'$, respectively. The permutation $f$ is defined as
the subword of descent bottoms in \p, ordered increasingly, and $g$ is
defined as
the subword of non-descent bottoms in \p, also ordered increasingly. The
permutation $f'$ is the subword of descent tops in \p, ordered so that the
inversion bottom number of a letter $a$ in $f'$ is the embracing number of
$a$ in
\p, and $g'$ is the subword of non-descent tops in \p, ordered so that the
inversion top number of a letter $b$ in $g'$ is the embracing number of $b$ in
\p. Rearranging the columns of $\tau'$, so that the top row is in increasing
order, we obtain the permutation $\ta=\Phi(\pi)$ as the bottom row of the
rearranged biword.

\begin{eg}
{\rm Let $\pi = 4\ 1-2-7-9\ 6\ 5-8\ 3$, with embracing numbers 1, 0, 0,
2, 0, 1, 1, 0, 0.  Then
$$ \biw f {f'} = \biw {1\ 3\ 5\ 6}{8\ 4\ 6\ 9},\,\,\,\, \biw g {g'} = \biw
{2\ 4\ 7\ 8\ 9}{1\ 2\ 7\ 5\ 3},\,\,\,\, \tau'= \biw {1\ 3\ 5\ 6\ 2\ 4\ 7\
8\ 9}  {8\ 4\ 6\ 9\ 1\ 2\ 7\ 5\ 3} $$
and thus $\Phi(\p)=\tau=8\ 1\ 4\ 2\ 6\ 9\ 7\ 5\ 3$. It is easily checked
that the
descent tops and descent bottoms in \p\ are the excedance tops and excedances in
\ta, respectively, and that the embracing number of each letter in \p\ is the
side number of the same letter in \ta. }
\end{eg}

\bigskip
\noindent{\bf Proof of Proposition \ref{phistat}:\/}
Assuming that the construction of $f'$ and $g'$ can be carried out in the way
described, and such that $f'=\EXC{\tau}$ and $g'=\NEX{\tau}$, it is clear that
the excedance tops and excedances in \ta\ are the descent tops and descent
bottoms, respectively, in \p, and that
$$\res\pi= \inv\EXC{\tau} +\inv\NEX{\tau} = \ine\tau.$$
As a consequence, we have
$$(\des,\dbot,\ddiff,\res)\ \pi= (\exc,\ebot,\ediff,\ine)\ \Phi(\pi).$$
 

To complete the proof, we need to show two things. Firstly, that $f'$ and $g'$
can be constructed so that the inversion bottom numbers and the inversion top
numbers of $f'$ and $g'$ respectively are those claimed, and, secondly, that
$f'=\EXC{\tau}$ (and thus $g'=\NEX{\tau}$).

Let $a$ be the least descent top in \p. Then, if the embracing number of $a$ in
\p\ is $k$, there are $k$ descent blocks in \p\ to the right of $a$ that embrace
$a$. Thus, there are at least $k$ descent tops in \p\ that are larger than $a$,
namely the closers of the descent blocks embracing $a$. Also, there are at least
$k+1$ descent bottoms in \p\ that are smaller than $a$, namely the openers
of the
descent blocks embracing $a$, together with the opener of the descent block
containing $a$. If we put $a$ in the $(k+1)$--st place in $f'$ from the left,
then the inversion bottom number of $a$ in $f'$ is $k$ as desired, and the
$(k+1)$--st place {\em does exist} in $f'$, because, as pointed out, there
are at
least $(k+1)$ descent bottoms, and thus at least $(k+1)$ descent tops, in \p\ if
$a$ has embracing number $k$.

Moreover, the same argument shows that $a$ is larger than the $(k+1)$--st letter
in $f$, because the first $(k+1)$ letters in $f$ are descent bottoms in \p\ that
are smaller than $a$. Hence, $a$ is an excedance in \ta. If we now remove the
letter $a$ from $f'$ and its corresponding descent bottom, the $(k+1)$--st
letter
of $f$, from $f$, then we can repeat the argument, appealing to induction, to
show that $f'$ can be constructed in the way described. That is, so that each
letter $x$ in $f'$ is an excedance top in \ta\ whose inversion bottom number
equals the embracing number of $x$ in \p. An analogous argument shows that $g'$
can be constructed as claimed, and so that each letter in $g'$ is not an
excedance top in \ta.  \qed

In order to prove Theorem \ref{masterperm}, we must show that $\Phi$ is a
bijection. Since $\Phi$ is a map from a finite set to itself, it suffices
to show
$\Phi$ injective, but in the process we will, in fact, construct an inverse to
$\Phi$.

We introduce the idea of the {\em skeleton\/} of a permutation.  This is closely
related to the idea of ``gravid permutation'' introduced by Foata and Zeilberger
[7].  We first adjoin to the positive integers a symbol $\infty$ such that
$a<\infty$ for any positive integer $a$.

\begin{defn}\label{skeleton}
Let $n$ be a positive integer.  A {\em block\/} is a subset $B$ of
$[n]\cup\infty$ such that $B\cap[n]\ne\emptyset$.  The block $B$ is called {\em
open\/} if $\infty\in B$, {\em closed\/} if $\infty\notin B$ and {\em
improper\/}
if $|B|=1$. The {\em opener\/}, $\op(B)$, of $B$ is the smallest element of $B$,
the {\em closer\/}, \clo$(B)$, of $B$ is the largest element of $B$.

A {\em skeleton\/} is a sequence $S=B_1-B_2-\ldots-B_r$ of blocks such that any
pair of blocks intersect in at most $\{\infty\}$.  The skeleton $S$ is {\em
valid\/} if for each $i$ with $1\le i<n$ we have $\op(B_i)<\clo(B_{i+1})$.
\end{defn}

\begin{defn}
Let $\pi\in{\cal S}_n$ be a permutation with descent block decomposition
$B_1-B_2-\cdots-B_r$.  Let $1\le a\le n$.  The {\em $a$-skeleton\/} of $\pi$ is
the sequence of blocks obtained by
\begin{itemize}
\item deleting any descent block $B$ of $\pi$ for which $\op(B)>a$;
\item replacing any remaining letter of $\pi$ that is greater than $a$ by
$\infty$;
\item replacing each remaining descent block (which is a {\em sequence\/} of
elements) by its underlying set.
\end{itemize}
\end{defn}

For example, if $\pi=3\ 1-6-7\ 5-9\ 8\ 4\ 2$, the 4-skeleton of $\pi$ is the
sequence $\{1,3\}-\{2,4,\infty\}$, which we will write as $3\ 1-\infty\ 4\ 2$.

It is clear that one can recover $\pi$ from its $n$-skeleton.

\begin{lem}\label{validity}
Let $\pi\in{\cal S}_n$.  For any $a$ with $1\le a\le n$, the $a$-skeleton of
$\pi$ is valid.
\end{lem}
\pf
We use downwards induction on $a$, knowing that the result is true for the
$n$-skeleton.  Suppose it is true for $a$.  To obtain the $(a-1)$-skeleton from
the $a$-skeleton, we merely replace $a$ by $\infty$ in the block $B$ in which it
occurs and delete that block if it now contains only $\infty$.  But as the
$a$-skeleton is valid and $a$ is the largest finite element occuring in it, a
block $\{a,\infty\}$ or $\{a\}$ can only occur as the last block in the
$a$-skeleton, in which case its deletion will not cause invalidity.\qed

The following result is easy to see.

\begin{lem}\label{embracing}
The embracing number of the letter $a$ in $\pi$ equals the number of open blocks
to the right of the block containing $a$ in the $a$-skeleton of $\pi$.\qel
\end{lem}


\noindent{\bf Proof of Theorem \ref{masterperm}:\/}  We show that $\Phi$ is an
injection by showing that, given a permutation \ta\ in the image of $\Phi$,
there
is at most one permutation $\pi$ such that $\Phi(\pi)=\tau$. Given such a
\ta, it
is clear what the associated biword $\biw {f\;  g} {f'\; g'}$ must be. Namely,
$\biw f {f'}$ consists of those columns of $\widetilde{\tau}$ that represent
excedances in \ta, and $\biw g {g'}$ consists of the remaining columns of
$\widetilde{\tau}$. Now denote by $F$, $F'$, $G$ and $G'$ the sets whose
elements
are the letters of $f$, $f'$, $g$ and $g'$ respectively.  Then we can identify
the openers of $\pi$ as the letters in $F\cap G'$, the closers as the letters in
$F'\cap G$, the insiders as those in $F\cap F'$ and the outsiders as those in
$G\cap G'$.  As we can calculate the side numbers of \ta, we know the embracing
numbers of $\pi$.  We will show how to construct successively the 1-, 2-, \dots,
$n$-skeletons of $\pi$.

\smallskip
The 1-skeleton of $\pi$ is either $\{1\}$ or $\{1,\infty\}$, according as 1
is an
outsider or an opener.  Suppose that the $(a-1)$-skeleton $S=B_1-B_2-\ldots-B_r$
of $\pi$ has been constructed.  To construct the $a$-skeleton of $\pi$ we must
insert $a$ in the correct place in $S$.  Let the embracing number of $a$ in
$\pi$
be $e$.  Let $B_i$ be the $(e+1)$-st open block from the right in $S$. If $a$ is
an insider or a closer in $\pi$ then, by Lemma \ref{embracing}, $a$ must be
inserted into $B_i$, and if $a$ is a closer then $B_i$ must be closed by the
removal of its $\infty$.  Suppose that $a$ is an outsider.  Then the improper
block $B=\{a\}$ must be inserted immediately to the left of $B_i$.  For if
$B$ is
inserted to the left of $B_{i-1}$ then either the resulting skeleton will be
invalid or Lemma \ref{embracing} will be violated.  Similarly, if $a$ is an
opener, the open block $\{a,\infty\}$ must be inserted immediately before $B_i$.

After the $n$-skeleton of $\pi$ has been constructed, we can immediately
construct $\pi$.  Hence there is at most one permutation $\pi$  such that
$\Phi(\pi)=\tau$. Hence, $\Phi$ is injective, and so a bijection, and its
inverse
is defined by the construction just described.

The equidistribution of ($\des$, $\dbot$, $\ddiff$, $\res$) and ($\exc$,
$\ebot$,
$\ediff$, $\ine$) now follows from Proposition \ref{phistat} and the fact that
$\Phi$ is a bijection. As $\inv = \env$, the equidistribution of ($\des$,
$\mak$,
$\mad$) with ($\exc$, $\den$, $\inv$) follows from the definitions of the
Mahonian statistics involved, since each is the sum of two of the partial
statistics $\dbot$, $\ddiff$, $\res$ and $\ebot$, $\ediff$, $\ine$,
respectively.
\qed

\begin{eg}
{\rm Let $\tau= 8\ 1\ 4\ 2\ 6\ 9\ 7\ 5\ 3$, so
$$ \biw f {f'} = \biw {1\ 3\ 5\ 6}{8\ 4\ 6\ 9},\,\,\,\, \biw g {g'} = \biw
{2\ 4\
7\ 8\ 9}{1\ 2\ 7\ 5\ 3},\,\,\,\, \tau'= \biw {1\ 3\ 5\ 6\ 2\ 4\ 7\ 8\ 9} {8\ 4\
6\ 9\ 1\ 2\ 7\ 5\ 3}. $$
For clarity, we now rewrite $\tau'$ with a bar separating $f$ from $g$ and $f'$
from $g'$, and we write the inversion bottom and inversion top numbers in $f'$
and $g'$ respectively as subscripts of their corresponding letters, omitting
those that are zero.
$$ \tau'= \biw {f&|&g} {f'&|&g'} = \left(\begin{array}{cccccccccc} 1 & 3 & 5 & 6
& | & 2 & 4 & 7 & 8 & 9 \\ 8 & 4_1 & 6_1 & 9 & | & 1 & 2 & 7_2 & 5_1 & 3
\end{array}\right). $$

\vspace{6pt}
\noindent The sequence of $k$-skeletons, for $k=1,2,\ldots,9$, of our required
permutation $\pi$ is:
\begin{eqnarray*}
&&\infty\ 1;\\
&&\infty\ 1-2;\\
&&\infty\ 1-2-\infty\ 3;\\
&&4\ 1-2-\infty\ 3;\\
&&4\ 1-2-\infty\ 5-\infty\ 3;\\
&&4\ 1-2-\infty\ 6\ 5-\infty\ 3;\\
&&4\ 1-2-7-\infty\ 6\ 5-\infty\ 3;\\
&&4\ 1-2-7-\infty\ 6\ 5-8\ 3;\\
&&4\ 1-2-7-9\ 6\ 5-8\ 3.
\end{eqnarray*}
Hence
$$\pi=4\ 1-2-7-9\ 6\ 5-8\ 3.$$}
\end{eg}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Motzkin paths and a continued fraction expansion} \label{motzkin}
%BOB Paragraph below deleted, as it repeats earlier remarks.
%In this section we shall make evident the relation between our
%bijection $\Phi$ and some well-known bijections between the symmetric
%group \sn\  and weighted Motzkin paths. As a by-product we get the
%continued fraction expansion for the generating function of \sn\
%with respect to some of our statistics.
%
A {\em Motzkin path}, informally, is a connected sequence of $n$ line segments,
or ``steps,'' in the first quadrant of ${\mbox{\bf R}}^2$, starting out from the
origin in ${\mbox{\bf R}}^2$ and ending at $(0,n)$. The steps are of four
different types, northeast steps (N) going from $(a,b)$ to $(a+1,b+1)$,
southeast
(S) going from $(a,b)$ to $(a+1,b-1)$ and solid/dotted east steps (E,dE), from
$(a,b)$ to $(a+1,b)$ (see Figure 1). Formally, a Motzkin path is defined as
follows.

\begin{defn}
A {\em Motzkin path} is a word $w=c_1c_2\cdots c_n$ on the alphabet $\{\NE, \SE,
\sE, \dE \}$ such that for each $i$ the {\em level $h_i$ of the $i$-th step},
defined by
$$h_i=\#\{j|j<i, c_j=\NE\}-\#\{j|j<i, c_j=\SE\}, $$
is non-negative, and equal to zero if $i=n$.
\end{defn}

\begin{defn}
A {\em weighted Motzkin path of length $n$} is a pair $(c,d)$, where
$c=c_1\cdots
c_n$ is a Motzkin path of length $n$, and $d=(d_1,\ldots, d_n)$ is a sequence of
integers such that
$$ 0\leq d_i\leq \cases{h_i& if $c_i\in\{\NE,\sE\}$,\cr
h_i-1& if $ c_i\in\{\SE,\dE\}$.\cr }$$
The set of weighted Motzkin paths of length $n$ is denoted by $\Gamma_n$.
\end{defn}

Fran\c con and Viennot \cite{fravie} gave the first bijection $\Psi_{\mn FV}$
between \sn\  and $\Gamma_n$. Here we describe one {\sl variant} of this
bijection.

\begin{defn}%
Let $\p =a_1\cdots a_n\in \cl S_n$ and set $a_0=0$ and $a_{n+1}=n+1$. For $1\leq
i\leq n$ we say that $a_i$ is a
\begin{itemize}
\item {\em linear double ascent} (outsider) if $a_{i-1}<a_i<a_{i+1}$;
\item {\em linear double descent} (insider) if $a_{i-1}> a_i> a_{i+1}$;
\item {\em linear peak} (closer) if $a_{i-1}<a_i>a_{i+1}$;
\item {\em linear valley} (opener) if $a_{i-1}>a_i<a_{i+1}$.
\end{itemize}
\end{defn}

\bigskip
\centerline {\sc The bijection $\Psi_{\mn FV}$ of Fran\c con and Viennot}
\bigskip

\noindent
Given a permutation $\p \in \cl S_n$, determine the right embracing number $e_i$
for each $i\in [n]$. Form the weighted Motzkin path $(c,d)=\Psi_{\mn FV}(\p
)$ by
%BOB Should be "$d_{\pi(i)}=e_i$" below, as $e_i$ goes with the pair
%$(i,\pi(i))$.
setting $d_{\pi(i)}=e_i$ and by defining $c_i$ as follows:
\begin{itemize}
\item if $i$ is a linear double descent, then $c_i=\dE$;
\item if $i$ is a linear double ascent then $c_i=\sE$; \item
if $i$ is a linear peak then $c_i=\SE$;
\item if $i$ is a linear valley then $c_i=\NE$.
\end{itemize}
For example, if $\p =6\  1-8\  7\  4\  2-5-9\  3$, then the corresponding
weighted Motzkin path $\Psi_{\mn FV}(\p )=(c,d)$ is shown in Figure 1.

\begin{figure}
{ \setlength{\unitlength}{0.6pt}
\begin{picture}(420,202)
\put(150,5)
{\begin{picture}(400,197)
\thicklines
\put(241,106){\dashbox{5}(35,0){}}
\put(134,135){\dashbox{5}(35,0){}}
\put(29,58){\line(4,3){105}}
\thinlines
\put(346,55){\circle*{7}}
\put(312,81){\circle*{7}}
\put(276,106){\circle*{7}}
\put(240,106){\circle*{7}}
\put(133,136){\circle*{7}}
\put(168,136){\circle*{7}}
\put(203,136){\circle*{7}}
\put(98,109){\circle*{7}}
\put(63,82){\circle*{7}}
\put(27,55){\circle*{7}}
\thicklines
\put(27,4){\vector(0,1){188}}
\put(98,107){\line(0,-1){103}}
\put(133,136){\line(0,-1){132}}
\put(168,135){\line(0,-1){132}}
\put(204,136){\line(0,-1){133}}
\put(240,107){\line(0,-1){103}}
\put(276,107){\line(0,-1){103}}
\put(205,136){\line(6,-5){36}}
\put(276,107){\line(4,-3){71}}
\put(346,52){\line(0,-1){50}}
\put(311,82){\line(0,-1){78}}
\put(63,82){\line(0,-1){78}}
\put(1,2){\line(1,0){345}}
\put(0,25){\line(1,0){345}}
\put(1,54){\vector(1,0){399}}
\put(10,33){$i$}
\put(45,33){\scriptsize 1}
\put(78,33){\scriptsize 2}
\put(113,33){\scriptsize 3}
\put(149,33){\scriptsize 4}
\put(183,33){\scriptsize 5}
\put(219,33){\scriptsize 6}
\put(255,33){\scriptsize 7}
\put(290,33){\scriptsize 8}
\put(327,33){\scriptsize 9}
\put(45,8){\scriptsize 0}
\put(78,8){\scriptsize 0}
\put(112,8){\scriptsize 0}
\put(150,8){\scriptsize 1}
\put(183,8){\scriptsize 1}
\put(218,8){\scriptsize 2}
\put(255,8){\scriptsize 1}
\put(291,8){\scriptsize 1}
\put(328,8){\scriptsize 0}
\put(3,8){$d_i$}
\put(168,136){\line(1,0){35}}
\end{picture}}
\end{picture}}

\medskip
\centerline {Figure 1}
\end{figure}

\bigskip
\centerline {\sc The bijection $\Psi_{\mn FZ}$ of Foata and Zeilberger}
\bigskip

\noindent In \cite{FZ} Foata and Zeilberger gave another bijection from \sn\  to
$\Gamma_n$, which can be described by the following example.

Start with a permutation $\p$, say, $\pi= 9\ 4\ 7\ 6\ 1\ 2\ 8\ 5\ 3$, so
$$\piti=\biw {1\ 2\ 3\ 4\ 5\ 6\ 7\ 8\ 9} {9\ 4\ 7\ 6\ 1\ 2\ 8\ 5\ 3}. $$
As in section \ref{bijperm}, separate \piti\ into two biwords corresponding to
$\p_E$ and $\p_N$ to get
$$ \biw f {f'}=\left(\matrix{1&2&3&4&7\cr9&4&7&6&8\cr}\right),\quad \biw g {g'}
=\left(\matrix{5&6&8&9\cr 1&2&5&3\cr}\right).$$
Form the weighted Motzkin path $(c,d)=\Psi_{\mn FZ}(\pi)$ as follows: Let
$s_1,s_2,\ldots,s_n$ be the sequence of side numbers of \p\ (see Definition
\ref{invno}) and put
\begin{equation}\label{pnumbers}
d_{\pi(i)}=s_i \mbox{ for } i=1,2,\ldots,n.
\end{equation}
 Let
$$c_i=\cases{\dE, & if $i\in F\cap F'$,\cr
\sE, & if $i\in G\cap G'$,\cr
\SE, & if $i \in F'\cap G$, \cr
\NE, & if $i\in F\cap G'$.\cr}$$
Here we have $d=(0,\,0,\,0,\,1,\,1,\,2,\,1,\,1,\,0)$ and
$$F\cap F'=\{4,\, 7\},\quad G\cap G'=\{5\}, \quad F'\cap G=\{6,\, 8,\,9\},
\quad F\cap G'=\{1,\, 2,\, 3\}. $$
\begin{defn}
For $\p \in \cl S_n$ and $i\in [n]$, we say that $i$ is a
\begin{itemize}
\item {\em cyclic double ascent} if $\p ^{-1}(i)<i<\p(i)$;
\item {\em cyclic double descent} if $\p ^{-1}(i)\geq i\geq \p(i)$;
\item {\em cyclic peak} if $\p ^{-1}(i)<i>\p(i)$;
\item {\em cyclic valley} if $\p ^{-1}(i)>i<\p(i)$.
\end{itemize}
\end{defn}

Note that the four sets $F\cap F'$, $G\cap G'$, $F'\cap G$ and $F\cap G'$
correspond respectively to cyclic double ascents, cyclic double descents, cyclic
peaks and cyclic valleys of $\p $. The corresponding weighted Motzkin path
is the
same as in Figure 1. We note that $\Psi_{\mn FV}=\Psi_{\mn FZ}\circ \Phi$. In
other words, we have the commutative diagram in Figure 2.

 
\bigskip
\centerline {\sc Biane's bijection}
\bigskip

\noindent In \cite{biane}, Biane gave a bijection similar to $\Psi_{\mn FZ}$
which we now describe.

\begin{defn}
A {\em labeled path of length $n$} is a pair $(c, \xi)$, where $c=c_1\cdots c_n$
is a Motzkin path of length $n$, and $\xi=(\xi_1, \ldots,\xi_n)$ is a sequence
such that
$$\xi_i\in \cases{\{\Delta\},& if $c_i = \NE$,\cr
\{0, \ldots,h_i\},& if $c_i = \dE$ or $\sE$,\cr
\{0, \ldots, h_i-1\}^2,& if $c_i = \SE$.\cr }$$
\end{defn}

\begin{figure}
{\setlength{\unitlength}{0.62pt}
\begin{picture}(420,110)
\put(185,5)
{\begin{picture}(420,110)
\thinlines
\put(26,50){$\Psi_{\mn FV}$}
\put(172,50){$\Psi_{\mn FZ}$}
\put(114,7){$\Gamma_n$}
\put(199,98){$\clS_n$}
\put(8,98){$\clS_n$}
\put(114,113){$\Phi$}
\thicklines
\put(195,96){\vector(-1,-1){68}}
\put(40,95){\vector(1,-1){68}}
\put(41,105){\vector(1,0){150}}
\end{picture}}
\end{picture}}

\medskip
\centerline {Figure 2}
\end{figure}

\bigskip
Biane's bijection is from the labeled paths of length $n$ to \sn. Using the same
notation as in the description of $\Psi_{\mn FZ}$, the inverse of Biane's
bijection can be summarized as follows. Let $d_1,d_2,\ldots,d_n$ be the sequence
of numbers calculated using equation (\ref{pnumbers}) from the side numbers of
\p.  Note that Biane gave a recursive algorithm to compute these numbers but did
not point out that they are actually the side numbers of $\pi$, that is the
inversion bottom and inversion top numbers in $f'$ and $g'$ respectively.  Form
the labeled path $(c, \xi)$ thus:
\begin{itemize}
\item if $i\in F\cap G'$ (valley), let $c_i=\NE$ and $\xi_i=\Delta$;
\item if $i\in F\cap F'$ (double ascent), let $c_i=\dE$ and $\xi_i=d_{i}$;
\item if $i\in G\cap G'$ (double descent), let $c_i=\sE$ and
$\xi_i=d_{\p(i)}$;
\item if $i\in F'\cap G$ (peak), let $c_i=\SE$ and $\xi_i=(d_{\p(i)},
d_i)$.
\end{itemize}
The path is the same as for $\Psi_{\mn FZ}$, the only difference being the
distribution of the side numbers associated to each step of the path. If we
apply
Biane's bijection to the permutation $\p$ above, we get the labeled path in
Figure 3.

\begin{figure}
{ \setlength{\unitlength}{0.6pt}
\begin{picture}(410,202)
\put(150,5)
{\begin{picture}(400,192)
\thicklines
\put(241,106){\dashbox{5}(35,0){}}
\put(134,135){\dashbox{5}(35,0){}}
\put(29,58){\line(4,3){105}}
\thinlines
\put(346,55){\circle*{7}}
\put(312,80){\circle*{7}}
\put(276,106){\circle*{7}}
\put(240,106){\circle*{7}}
\put(133,136){\circle*{7}}
\put(168,135){\circle*{7}}
\put(203,136){\circle*{7}}
\put(97,108){\circle*{7}}
\put(63,83){\circle*{7}}
\put(27,55){\circle*{7}}
\thicklines
\put(27,4){\vector(0,1){188}}
\put(98,107){\line(0,-1){103}}
\put(133,136){\line(0,-1){132}}
\put(168,135){\line(0,-1){133}}
\put(204,136){\line(0,-1){133}}
\put(240,107){\line(0,-1){103}}
\put(276,107){\line(0,-1){103}}
\put(205,136){\line(6,-5){36}}
\put(276,107){\line(4,-3){71}}
\put(347,52){\line(0,-1){50}}
\put(311,82){\line(0,-1){78}}
\put(63,82){\line(0,-1){78}}
\put(1,2){\line(1,0){345}}
\put(0,25){\line(1,0){345}}
\put(1,54){\vector(1,0){399}}
\put(10,33){$i$}
\put(45,33){\scriptsize 1}
\put(78,33){\scriptsize 2}
\put(112,33){\scriptsize 3}
\put(149,33){\scriptsize 4}
\put(183,33){\scriptsize 5}
\put(218,33){\scriptsize 6}
\put(255,33){\scriptsize 7}
\put(290,33){\scriptsize 8}
\put(327,33){\scriptsize 9}
\put(42,7){\tiny $\Delta$}
\put(76,7){\tiny $\Delta$}
\put(111,7){\tiny $\Delta$}
\put(150,8){\scriptsize 1}
\put(183,8){\scriptsize 0}
\put(207,8){\scriptsize (0,2)}
\put(255,8){\scriptsize 1}
\put(278,8){\scriptsize (1,1)}
\put(315,8){\scriptsize (0,0)}
\put(3,8){$\xi_i$}
\put(168,136){\line(1,0){35}}
\end{picture}}
\end{picture}}

\medskip
\centerline {Figure 3}
\end{figure}

In \cite{FZ}, Foata and Zeilberger's purpose with the bijection $\Psi_{\mn FZ}$
was to code the $\den$ statistic by weighted Motzkin paths, in order to
show that
$(\exc,\den)$ was equidistributed with $(\des,\maj)$. That $\Psi_{\mn FZ}$ also
keeps track of the $\inv$ statistic was first remarked by de M\'edicis and
Viennot \cite[Proposition 5.2]{medvie}. They proved that
\begin{eqnarray}
\inv\pi=\sum_{i=1}^nh_i+\sum_{i=1}^nd_i. \label{inveq}
\end{eqnarray}
In Biane's bijection, on the other hand, the $\inv$ statistic is seen to equal
$$\inv\p=\sum_{i=1}^n(h_i+|\xi_i|), $$
where $|\xi|=x+y$ if $\xi=(x,y)$ and $|\xi|=0$ if $\xi=\Delta$. This
is obviously equivalent to (\ref{inveq}).

Using the connections between Motzkin paths and permutations we have described,
we now give a continued fraction expansion for the generating function $D_n(x,
q)=\sum_{\p \in \cl S_n}{x^{\des\p}q^{\expmad\p}}$.

For $n\geq 0$ let $[n]_q=1+q+\cdots +q^{n-1}$ and let
$$ f_n(x, p, q)=\sum_{\p\in \cl S_n}x^{\exc \p }q^{\edif \p }p^{\ine \p }.$$
Then, by Theorem \ref{masterperm}, we also have
$$ f_n(x, p, q)=\sum_{\p \in \cl S_n}x^{\des \p}q^{\ddif \p }p^{\res \p }.$$

\begin{thm}\label{c-fraction}
The ordinary generating function of $f_n(x, p, q)$ has the following Jacobi
continued fraction expansion:
$$ \sum_{n\geq 0}f_n(x,p, q)t^n={1\over\displaystyle 1-b_0t- {\strut
\lambda_1t^2\over\displaystyle 1-b_1t- {\strut
\lambda_2t^2\over\displaystyle {}
{\strut \ddots\over\displaystyle 1-b_nt- {\strut
\lambda_{n+1}t^2\over\displaystyle \ddots }}}}}, $$
where $b_n=q^n(x[n]_p+[n+1]_p)$ and $\lambda_{n+1}=xq^{2n+1}([n+1]_p)^2$
for $n\geq 0$.
\end{thm}
\pf  For $\p \in \cl S_n$, if $\Psi_{\mn FZ}(\p )=(c,d)$, then it is easy
to see that
\begin{eqnarray*}
\exc \p &=&\sum_{{c_i=\NE}}1+\sum_{{c_i=\dE}}1,\\
\edif \p &=&\sum_{c_i=\SE}i- \sum_{c_i=\NE}i=\sum_{i=1}^n h_i,\\
\ine \p &=&\sum_{i=1}^n d_i.
\end{eqnarray*}
It follows that
\begin{eqnarray*}
f_n(x,p,q)\!&=&\!\sum_{(c,d)\in \Gamma_n}\prod_{c_i=\NE}\!xq^{h_i}p^{d_i}
\prod_{c_i=\SE}\!q^{h_i}p^{d_i}\prod_{c_i=\dE}\!xq^{h_i}p^{d_i}
\prod_{c_i=\sE}\!q^{h_i}p^{d_i}\cr
\noalign{\vskip 10pt}
\!&=&\!\sum_{c\in M_n}\prod_{c_i=\NE}\!xq^{h_i}[h_i+1]_p
\prod_{c_i=\SE}\!q^{h_i}[h_i]_p
\prod_{c_i=\dE}\!xq^{h_i}[h_i]_p\prod_{c_i=\sE}\!q^{h_i}[h_i+1]_p ,
\end{eqnarray*}
where $M_n$ is the set of all Motzkin paths of length $n$. The theorem then
follows by applying a result of Flajolet \cite[Theorem 1]{fla}.  \qed

Using the {\em contraction} formula
\begin{eqnarray}
{c_0\over\displaystyle 1- {\strut c_1t\over\displaystyle 1- {\strut
c_2t\over\displaystyle \ddots }}} =c_0+{c_0c_1t\over\displaystyle
1-(c_1+c_2)t-
{\strut c_2c_3t^2\over\displaystyle 1-(c_3+c_4)t- {\strut
c_4c_5t^2\over\displaystyle \ddots }}},\label{contraction}
\end{eqnarray}
we immediately get the following Stieltjes continued fraction expansion for the
same generating function.
\begin{cor}\label{Stieltjes}  We have
\begin{eqnarray}
\sum_{n\geq 0}f_n(x,p,q)t^n={1\over\displaystyle 1- {\strut
t\over\displaystyle
1- {\strut xqt\over\displaystyle {} {\strut \ddots\over\displaystyle 1-
{\strut
q^{n-1}[n]_pt\over\displaystyle 1- {\strut xq^n[n]_pt\over\displaystyle
\ddots
}}}}}}.
\end{eqnarray}

In particular, if $\disp D_n(x, q)= \sum_{\p \in \cl S_n}
{x^{\des\p}q^{\expmad\p}}$, then it follows from Corollary~\ref{Stieltjes}, by
putting $p=q$ in the above equation, that
\begin{eqnarray}
\sum_{n\geq 0}D_n(x,q)t^n= {1\over\displaystyle 1- {\strut
t\over\displaystyle 1-
{\strut xqt\over\displaystyle {} {\strut \ddots\over\displaystyle 1-
{\strut
q^{n-1}[n]_qt\over\displaystyle 1- {\strut xq^n[n]_qt\over\displaystyle
\ddots
}}}}}}.\qel\label{dfrac}
\end{eqnarray}
\end{cor}

Note that the continued fraction expansion of the generating function of
%$\sum_{\p \in \cl S_n}x^{\exc \p}q^{\expinv \p}$ can also be derived from
%\cite[Theorem 6.5]{medvie}.
$$D_n(x,q)=\sum_{\p \in \cl S_n}x^{\des \p}q^{\expmad \p}=
\sum_{\p \in \cl S_n}x^{\exc \p}q^{\expinv \p}$$
can also be derived from \cite[Theorem 6.5]{medvie}.

\begin{table}
{\scriptsize
\begin{tabular}{c|c c c c c c c c c c c c c c c c }
$k\backslash m$& 0& 1& 2& 3&4& 5& 6& 7&8 &9&10&11&12&13&14&15\\
\hline
0& \phantom{0}1& & & & & & & & & & & & & & & \\
1& &5 &4 &7 &8 &10 &10 &8 &4 &1 & & & & & & \\
2& & & 10 &12 &24 &32 &41 &44 &43 &36 &27 &18 &10 &4 &1 &\\
 3& & & & 10& 12& 24& 32& 41& 44& 43& 36& 27&18 & 10& 4& 1\\
 4& & & & & 5& 4& 7& 8& 10& 10& 8& 4& 1& & & \\
 5&\phantom{00}&\phantom{00} & \phantom{00} &\phantom{00}& \phantom{00}
  &1 & & & & & & & & & &{} \\
  \end{tabular}
\caption{$[x^kq^m]D_n(x,q)$ for $n=6$.}}
\end{table}

\begin{cor}\label{cor}
For $0\leq k\leq n-1$ and $0\leq m\leq {n(n-1)\over 2}$ we have
\begin{eqnarray}
[x^kq^{k+m}]D_n(x,q)=[x^{n-1-k}q^{n-1-k+m}]D_n(x,q),\label{dualitycor}
\end{eqnarray}
where $[x^kq^m]D_n(x,q)$ is the coefficient of $x^kq^m$ in the polynomial
$D_n(x,q)$.
\end{cor}
\pf  Let $B_n(x,q)=D_n(xq^{-1},q)$. Then (\ref{dualitycor}) is equivalent to
\begin{eqnarray}
[x^kq^m]B_n(x,q)=[x^{n-1-k}q^m]B_n(x,q).\label{duality}
\end{eqnarray}

{}From (\ref{dfrac}) and (\ref{contraction}) we derive
\begin{eqnarray}\label{bequation}
\sum_{n\geq 1}B_n(x,q)t^n= {t\over\displaystyle 1-(c_1+c_2)t- {\strut
c_2c_3t^2\over\displaystyle 1-(c_3+c_4)t- {\strut
c_4c_5t^2\over\displaystyle
\ddots }}},
\end{eqnarray}
where $c_{2n-1}=q^{n-1}[n]_q$ and $c_{2n}=xq^{n-1}[n]_q$ for $n\geq 0$.
Replacing
$x$ by $1/x$ and $t$ by $xt$ in (\ref{bequation}) we get
\begin{eqnarray}\label{beqinverse}
\sum_{n\geq 1}x^{n-1}B_n(x^{-1},q)t^n= {t\over\displaystyle 1-(c_1+c_2)t-
{\strut
c_2c_3t^2\over\displaystyle 1-(c_3+c_4)t- {\strut c_4c_5t^2\over\displaystyle
\ddots }}}.
\end{eqnarray}
Comparing (\ref{bequation}) and (\ref{beqinverse}) then yields
$B_n(x,q)=x^{n-1}B_n(x^{-1},q)$, which is clearly equivalent to (\ref{duality}).
\qed

To illustrate the above corollary, we give in Table 1 the number of permutations
corresponding to the values of $(\des,\mad)$ when $n=6$ and for clarity we omit
writing zeros.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Generalizations on our statistics}\label{variations}
\subsection{Left and right variations}
Two new statistics $\madl$ and $\makl$ are defined for a permutation \p\ as
follows.
\begin{defn}
\begin{eqnarray*}
\madl\pi&=&\ddiff\pi+\les\pi.\\
\makl\pi&=&\dbot\pi+\les\pi.
\end{eqnarray*}
\end{defn}
Recall that $\les\pi$ is the sum of the left embracing numbers of \p, defined by
replacing ``right'' by ``left'' in the definition of $\res\pi$. (See Definition
\ref{e numbers}.)

The relationship between these statistics and $\mad$ and $\mak$ is based on the
following result, for the proof of which we refer the reader to \cite{CSZ}.
\begin{prop}\label{epsilon}
There is an involution \e\ on \sn\ such that, for each $\pi\in \sn$,
$$(\des, \dbot, \dtop, \res, \les)\ \pi=
(\des, \dbot, \dtop, \les, \res)\ \ep. $$
In particular,
\begin{eqnarray*}
\mad \pi&=&\madl\ep,\\
\mak \pi&=&\makl\ep.
\end{eqnarray*}
\end{prop}

The involution \e\ can be informally described as follows.  Let \p\ be a
permutation with descent block decompostion $B_1-B_2-\cdots-B_k$.  Write the
descent blocks of \p\ down in reverse order to give a permutation
$\pp=B_k-B_{k-1}-\cdots-B_1$.  Now this may not be the descent block
decomposition of \pp, as new descents may have been introduced between adjacent
descent blocks.  If $\op(B_2)>\clo(B_1)$, that is, if a new descent has been
introduced between $B_2$ and $B_1$, then move block $B_2$ to the right of $B_1$
to get $B_k-B_{k-1}-\cdots-B_1-B_2$, otherwise leave block $B_2$ where it
is. Now
consider block $B_3$.  If there is a descent between $B_3$ and the block to its
right, move $B_3$ past that block. Continue moving $B_3$ to the right until
there
is no descent between it and the block to its right.  Continuing in this way we
arrive at the permutation \ep.
\begin{eg}
{\rm If $\pi=3\ 1-5\ 4\ 2-7\ 6$ with descent blocks $B_1-B_2-B_3$ then
$\pp=B_3-B_2-B_1=7\ 6-5\ 4\ 2-3\ 1$ and, as there is a descent between $B_3$ and
$B_2$, we get successively $5\ 4\ 2-7\ 6-3\ 1$ and $\ep=5\ 4\ 2-3\ 1-7\ 6$.}
\end{eg}

It follows from Proposition \ref{epsilon} that the triple ($\des$, $\madl$,
$\makl$) is equidistributed with the triple ($\des$, $\mad$, $\mak$) on \sn.

\subsection{Extensions to words}
The two Mahonian statistics $\inv$ and $\den$ have already been generalized to
words \cite{macmahon, han}. Indeed, all of the results in this paper except
those
in section \ref{motzkin} can be nicely extended to the case of words with
repeated letters. (Although we can {\em code} words with repeated letters to
weighted Motzkin paths, we cannot (yet) use this coding to obtain results
analogous to Theorem~\ref{c-fraction}.)  The definitions of our partial
statistics $\res$, $\dbot$, etc., become more complicated, but no essential
difficulties ensue.  This theory will be presented in \cite{CSZ}.

\subsection{Large and small letters}
Various authors, for example \cite{clfo, han2, stein}, have considered
statistics
on words and permutations in the context of an alphabet $\cl A=[m]$ in which the
letters are divided into two classes, {\em large\/} and {\em small\/}. Namely,
for some $k$ with $0\le k\le m$ and for $\ell=m-k$, the letters
$1,2,\ldots,\ell$
are designated small and the letters $\ell+1,\ldots,m$ are designated large.
Then, for a word $w=a_1a_2\cdots a_m$, a \mbox{$k$-{\em descent\/}} is an
integer
$i$ such that one of the following conditions holds:
\begin{itemize}
\item $1\le i<m$ and $a_i>a_{i+1}$;
\item $1\le i<m$ and $a_i=a_{i+1}>\ell$;
\item $i=m$ and $a_i>\ell$.
\end{itemize}
Then $\des_k w$ equals the number of $k$-descents of $w$. One can similarly
define $k$-extensions of the other Eulerian and Mahonian statistics. The results
of the present paper can all be $k$-extended, as will be presented by the
present
authors in a subsequent note \cite{CSZ2}.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{thebibliography}{99}
\bibitem{biane}P. Biane: Permutations suivant le type d'exc\'edance et le nombre
d'inversions et interpr\'etation combinatoire d'une fraction continue de Heine,
Europ. J. Combinatorics {\bf 14} (1993), 277--284.

\bibitem{clarke} R. J. Clarke: A short proof of a result of Foata and
Zeilberger,
Adv. Appl. Math. {\bf 16} (1995), 129--131.

\bibitem{clfo} R. J. Clarke and D. Foata: Eulerian Calculus I: Univariate
statistics, Europ. J. Combinatorics {\bf 15} (1994), 345--362.

\bibitem{CSZ} R. J. Clarke,  E. Steingr\'{\i}msson and J. Zeng, New
Euler-Mahonian statistics on permutations and words, preprint, (1995).

\bibitem{CSZ2}  R. J. Clarke,  E. Steingr\'{\i}msson and J. Zeng, The
$k$-extension of some new Euler-Mahonian statistics, preprint, (1995).

\bibitem{denert} M. Denert: The genus zeta function of hereditary orders in
central simple algebras over global fields, Math. Comp. {\bf 54} (1990),
449--465.

\bibitem{euler} L. Euler: Institutiones calculi differentialis, in {\em Opera
Omnia, Series Prima}, vol. X, Verlag von B.G. Teubner, Leipzig, 1913.

\bibitem{fla} P. Flajolet: Combinatorial aspects of continued fractions, Disc.
Math. {\bf 41} (1982), 145--153.

\bibitem{foa1} D. Foata: Distribution Eul\'eriennes et Mahoniennes sur le groupe
des permutations, in M. Aigner (ed.), {\em Higher Combinatorics}, 27--49, D.
Reidel, Boston, Berlin Combinatorics Symposium, 1976.

\bibitem{foa2} D. Foata: Rearrangements of words, in M. Lothaire, {\em
Combinatorics on Words}, (ed.) G.-C. Rota, Vol. 17, Encyclopedia of Math.  and
its Appl., Addison-Wesley Publishing Company, 1983.


\bibitem{fohan} D. Foata and G.-N. Han: Calcul basique des distributions
statistiques sur les permutations sign\'ees, Preprint, 1995.

\bibitem{FS1} D. Foata and M.-P. Sch\"utzenberger: {\em Th\'eorie
g\'eom\'etriques des poly-n\^omes eul\'eriens}, Lecture Notes in Math.,
vol. 138,
Springer-Verlag, Berlin, 1970.

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

\bibitem{FZ} D. Foata and D. Zeilberger: Denert's permutation statistic is
indeed
Euler-Mahonian, Studies in Appl. Math. {\bf 83} (1990), 31--59.

\bibitem{fravie} J. Fran\c con and X. G. Viennot: { Permutations selon les pics,
creux, doubles mont\'ees, doubles descentes, nombres d'Euler, nombres de
Genocchi}, Disc. Math. {\bf 28} (1979), 21--35.

\bibitem{garges} A. M. Garsia and I. M. Gessel: Permutations statistics and
partitions, Adv. in Math. {\bf 31} (1979), 288--305.

\bibitem{han} G.-N. Han: Une transformation fondamentale sur les
r\'earrangements de mots, Adv. in Math., {\bf 105} (1994), 26--41.

\bibitem{han2} G.-N. Han: The $k$-extension of a Mahonian statistic, Adv. Appl.
Math., {\bf 16} (1995),297--305.

\bibitem{macmahon} P.A. MacMahon: {\em Combinatory Analysis}, vols. 1 and 2.
Cambridge Univ. Press, Cambridge, 1915 (reprinted by Chelsea, New York, 1955).

\bibitem{medvie} A. de M\'edicis and X. G. Viennot: Moments des $q$-Polyn\^omes
de Laguerre et la bijection de Foata-Zeilberger, Adv. Appl. Math. {\bf 15}
(1994), 262--304.

\bibitem{ran} A. Randrianarivony: $q,p$--analogue des nombres de Catalan,
preprint, 1995.

\bibitem{ra} D. Rawlings: Permutation and multipermutation statistics, Europ. J.
Combinatorics, {\bf 2} (1981), 67-78.

\bibitem{rodrig} O. Rodriguez: Note sur les inversions, ou d\'erangements
produits dans les permutations, J. de Math. {\bf 4} (1839), 236--240.

\bibitem{simstan1} S. Simion and D. Stanton: Specializations of generalized
Laguerre polynomials, SIAM J. Math. Anal. {\bf 25} (1994), 712--719.

\bibitem{simstan2} S. Simion and D. Stanton: Octabasic Laguerre polynomials and
permutation statistics, J. Comp. Appl. Math., to appear.

\bibitem{stanley} R. Stanley: Binomial posets, M\" {o}bius inversion and
permutation enumeration, J. Comb. Theory, {\bf A, 20} (1976),  712--719.

\bibitem{stein} E. Steingr\'{\i}msson: Permutation statistics of indexed
permutations, Europ. J. Combinatorics, {\bf 15} (1994), 187--205.
\end{thebibliography}
\end{document}