\documentclass[12pt]{article}

\usepackage[latin1]{inputenc}
\usepackage[OT1]{fontenc} 

\usepackage{amssymb}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\pref}[1]{{(\protect\ref{#1})}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%Defines #1 to be a math operator (?)
\def\newop#1{\expandafter\def\csname #1\endcsname{\mathop{\rm #1}\nolimits}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand\lb{\linebreak}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand\cls{{\mathcal S}}
\def\disp{\displaystyle}
\newcommand{\pf}{{\bf Proof: \/}}

\def\emm#1,{{\em#1}\/}
\newcommand\cd{\cdot}
\def\ch#1,#2,{{#1\choose #2}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newtheorem{thm}{Theorem}
\newtheorem{theorem}[thm]{Theorem}
\newtheorem{defn}[thm]{Definition}\newtheorem{definition}[thm]{Definition}
\newtheorem{lem}[thm]{Lemma}\newtheorem{lemma}[thm]{Lemma}
\newtheorem{prop}[thm]{Proposition}\newtheorem{proposition}[thm]{Proposition}
\newtheorem{cor}[thm]{Corollary}\newtheorem{corollary}[thm]{Corollary}
\newtheorem{conj}[thm]{Conjecture}\newtheorem{conjecture}[thm]{Conjecture}
\newtheorem{eg}[thm]{Example}\newtheorem{example}[thm]{Example}
\newtheorem{remark}[thm]{Remark}
\newtheorem{fact}[thm]{Fact}
\newtheorem{blank}[thm]{$\!\!$}
\newtheorem{porism}[thm]{Porism}
\newtheorem{question}[thm]{Question}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand\st{\; | \;}
\newcommand\NN{\mathbb N}

\newcommand\qed{\hfill{\nobreak\quad\raise -.18ex\hbox{\vrule\vbox to
      8pt{\hrule width 8pt \vfill\hrule}\vrule}\par\vspace{2ex}}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\dd{\kern.4ex\mbox{\raise.4ex\hbox{{\rule{.35em}{.12ex}}}}\kern.4ex}

\def\ybay{[ba]}
\def\ybxa{[b{\dd}a)}
\def\ycxbxay{[c{\dd}b{\dd}a]}
\def\ybacy{[bac]}

\def\ybaxcy{[ba{\dd}c]}
\def\ybaxdcy{[ba{\dd}dc]}
\def\ybaxcdy{[ba{\dd}cd]}
\def\ycaxbdy{[ca{\dd}bd]}
\def\ycbxady{[cb{\dd}ad]}
\def\ybacy{[bac]}

\def\ybxcay{[b{\dd}ca]}

\def\axb{\ensuremath{(a{\dd}b)}}
\def\bxa{\ensuremath{(b{\dd}a)}}
\def\bxax{\ensuremath{(b{\dd}a{\dd})}}
\def\ab{\ensuremath{(ab)}}
\def\ba{\ensuremath{(ba)}}

\def\abc{\ensuremath{(abc)}}
\def\acb{\ensuremath{(acb)}}
\def\bac{\ensuremath{(bac)}}
\def\bca{\ensuremath{(bca)}}
\def\cab{\ensuremath{(cab)}}
\def\cba{\ensuremath{(cba)}}

\def\axbc{\ensuremath{(a{\dd}bc)}}
\def\axcb{\ensuremath{(a{\dd}cb)}}
\def\bxac{\ensuremath{(b{\dd}ac)}}
\def\bxca{\ensuremath{(b{\dd}ca)}}
\def\cxab{\ensuremath{(c{\dd}ab)}}
\def\cxba{\ensuremath{(c{\dd}ba)}}

\def\abxc{\ensuremath{(ab{\dd}c)}}
\def\acxb{\ensuremath{(ac{\dd}b)}}
\def\baxc{\ensuremath{(ba{\dd}c)}}
\def\bcxa{\ensuremath{(bc{\dd}a)}}
\def\caxb{\ensuremath{(ca{\dd}b)}}
\def\cbxa{\ensuremath{(cb{\dd}a)}}

\def\axbxc{\ensuremath{(a{\dd}b{\dd}c)}}
\def\axcxb{\ensuremath{(a{\dd}c{\dd}b)}}
\def\bxaxc{\ensuremath{(b{\dd}a{\dd}c)}}
\def\bxcxa{\ensuremath{(b{\dd}c{\dd}a)}}
\def\cxaxb{\ensuremath{(c{\dd}a{\dd}b)}}
\def\cxbxa{\ensuremath{(c{\dd}b{\dd}a)}}

\def\cba{\ensuremath{(cba)}}

\def\bxcaxd{\ensuremath{(b{\dd}ca{\dd}d)}}
\def\caxdb{\ensuremath{(ca{\dd}db)}}
\def\cbxda{\ensuremath{(cb{\dd}da)}}
\def\abxdc{\ensuremath{(ab{\dd}dc)}}
\def\baxdc{\ensuremath{(ba{\dd}dc)}}
\def\dcxab{\ensuremath{(dc{\dd}ab)}}
\def\dcxba{\ensuremath{(dc{\dd}ba)}}
\def\baxcd{\ensuremath{(ba{\dd}cd)}}
\def\caxbd{\ensuremath{(ca{\dd}bd)}}
\def\cbxad{\ensuremath{(cb{\dd}ad)}}
\def\bxcad{\ensuremath{(b{\dd}cad)}}

\def\yaxcb{\ensuremath{[a{\dd}cb)}}

\def\daxcb{\ensuremath{(da{\dd}cb)}}

\def\daxbc{\ensuremath{(da{\dd}bc)}}
\def\dbxac{\ensuremath{(db{\dd}ac)}}

\def\adxcb{\ensuremath{(ad{\dd}cb)}}
\def\acxdb{\ensuremath{(ac{\dd}db)}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Eulerian stats %%%%%%%%%%%%%%%%%%%%%%
\newcommand\des{\mathop{\mathrm{des}}}
\newcommand\exc{\mathop{\mathrm{exc}}}
%%%%%%%%
\def\newMAH#1{%
\expandafter\def\csname #1\endcsname{\mathop{\mbox{{\sc#1}}}\nolimits}%
}

\newMAH{maj}
\newMAH{mil}
\newMAH{inv}
\newMAH{env}
\newMAH{den}
\newMAH{mah}
\newMAH{lag}
\newMAH{mad}
\newMAH{mak}
\newMAH{madl}
\newMAH{makl}
\newMAH{sist}
\newMAH{imaj}
\newMAH{hag}
\newMAH{dag}
\newMAH{stat}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Partial stats %%%%%%%%%%%%%%%%%%%%%%
\def\newexpMAH#1{%
\expandafter\def\csname exp#1\endcsname{\mathop{\mbox{{\footnotesize\sc{#1}}}}\nolimits}%
}

\newexpMAH{inv}
\newexpMAH{maj}
\newexpMAH{mad}
\newexpMAH{mil}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Partial stats %%%%%%%%%%%%%%%%%%%%%%
\newcommand\res{\mathop{\mathrm{Res}}}
\newcommand\les{\mathop{\mathrm{Les}}}
\newcommand\dtop{\mathop{\mathrm{Dtop}}}
\newcommand\etop{\mathop{\mathrm{Etop}}}
\newcommand\dbot{\mathop{\mathrm{Dbot}}\nolimits}
\newcommand\ebot{\mathop{\mathrm{Ebot}}}
\newcommand\ddiff{\mathop{\mathrm{Ddif}}\nolimits}
\newcommand\ddif{\mathop{\mathrm{Ddif}}}
\newcommand\ediff{\mathop{\mathrm{Edif}}}
\newcommand\edif{\mathop{\mathrm{Edif}}}
\newop{exc}
\newop{nex}

\newcommand\desbots{\mathrm{Desbots}}
\newcommand\destops{\mathrm{Destops}}
\newcommand\nondestops{\mathrm{NonDestops}}

\def\EXC#1{#1_{\mbox{$\mathrm\scriptscriptstyle E$}}}
\def\NEX#1{#1_{\mbox{$\mathrm\scriptscriptstyle N$}}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Partial stats %%%%%%%%%%%%%%%%%%%%%%
\textheight 200mm
\textwidth 140mm
\topmargin -0mm
\oddsidemargin 7mm
\evensidemargin 7mm
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{document}
\thispagestyle{empty}




\begin{center} {\large \bf Generalized permutation patterns and\\[1ex] a
    classification of the Mahonian statistics}\\

\vspace{12pt} 
{\large Eric Babson and Einar Steingr\'{\i}msson}\\
%  {Matematiska Institutionen CTH \& GU}\\ {412 96 G\"oteborg}}\\ 
%  {SWEDEN}\\
%{\normalsize\tt einar@math.chalmers.se}
\end{center}

\bigskip

\begin{abstract}
  We introduce generalized permutation patterns, where we allow the
  requirement that two adjacent letters in a pattern must be adjacent
  in the permutation.  We show that essentially all Mahonian
  permutation statistics in the literature can be written as linear
  combinations of such patterns.  Almost all known Mahonian
  permutation statistics can be written as linear combinations of
  patterns of length at most 3.  There are only fourteen possible such
  Mahonian statistics, which we list.  Of these, eight are known and
  we give proofs for another three.  The remaining three we conjecture
  to be Mahonian.  We also give an explicit numerical description of
  the combinations of patterns a Mahonian statistic must have,
  depending on the maximal length of its patterns.
\end{abstract}


\section{\large Introduction and preliminaries}

The simplest, and best known, Mahonian permutation statistic is the
number of inversions.  Its distribution, which is the defining
criterion of a Mahonian statistic, was given already in 1839, by
Rodriguez \cite{rodriguez}.  However, it was with MacMahon
\cite{macmahon}, almost a century ago, that the systematic study of
permutation statistics saw the light of day and it is his name that
the Mahonian ones bear.  Among other things, MacMahon defined the
major index of a permutation, and showed that it is equidistributed
with the number of inversions.

Since then, and in particular in the last decade, many new Mahonian
statistics have been described in the literature.  Apart from ``pure''
permutation statistics, they have arisen in different contexts, such
as the study of Motzkin paths, orthogonal polynomials and algebra, and
they also have strong connections to rook theory.

Seemingly, these statistics have very different character, which is
underscored by their disparate definitions.  However, we shall show in
this paper that almost all Mahonian permutation statistics in the
literature essentially belong to a class of statistics containing only
fourteen different such.  

This class of statistics can be seen as the next step in complexity
after the simply defined number of inversions.  For each integer
$n\ge2$ there is a corresponding class of Mahonian statistics, whose
complexity in definition grows with $n$.  For each such class we give
strong numerical conditions that the definitions must satisfy in order
to give Mahonian statistics.


We define a permutation in the symmetric group $\cls_n$ to be a word
(or sequence) $a_1 a_2\cdots a_n$ of length $n$ consisting of all the
elements of $\{1,2,\ldots,n\}$.  It is convenient to define
$\cls_\infty$ as the disjoint union of the $\cls_n$ for
$n=1,2,3,\ldots$.

A \emm $k$-pattern, is a function from $\cls_\infty$ to $\NN$ that
counts the number of occurrences of certain subsequences (not
necessarily contiguous) of length $k$ in a permutation in
$\cls_\infty$.  We write our patterns as words in the alphabet
$a,b,c,\ldots$, where two adjacent letters may or may not be separated
by a dash.  The absence of a dash between two adjacent letters in a
pattern indicates that the corresponding letters in the permutation
must be adjacent, and in the order given by the pattern.  Also, the
ordering (by size) of the letters in a subword matching a certain
pattern (and thus counted by that pattern) must be the same as the
ordering of the letters in the pattern, which is based on the usual
ordering of the alphabet $a,b,c,\ldots$.  Here are some examples:

\begin{itemize}
\item %
  The pattern $\axbxc$ counts increasing subsequences of length 3 in a
  permutation.  This is a ``classical'' permutation pattern (see
  below).
\item %
The pattern $\bxa$ is the well known number of
inversions in a permutation (denoted $\inv$ here).  
\item %
  The pattern $\ba$ counts the \emm descents, in a permutation
  $\pi=a_1 a_2\cdots a_n$, that is, the number of $i$'s such that
  $a_i>a_{i+1}$.  (We frequently also refer to the descent $i$ as
  consisting of the two letter subword $a_ia_{i+1}$.)
\item %
  The pattern $\bxcaxd$ counts the number of occurrences of letters\lb
  $a_i,a_k,a_{k+1},a_j$ with $i<k<j$ and $a_{k+1}<a_i<a_k<a_j$.  Thus,
  the\lb permutation $\pi=314265$ has two occurrences of $\bxcaxd$,
  namely\linebreak $3\dd42\dd6$ and $3\dd42\dd5$, so we write
  $\bxcaxd\pi=2$.
\end{itemize}

The pattern $\axbxc$, and any pattern that in our notation has dashes
between every pair of adjacent letters, is of a type that might be
called classical.  These patterns, usually written with the positive
integers and without the (implicit) dashes, have mostly been studied
with respect to \emm avoidance,, that is, how many permutations in
$\cls_n$ have \emm no, occurrence of the pattern in question.  For
example, the number of 132-avoiding permutations $\pi$ in $\cls_n$ is
known to be the $n$-th Catalan number $\ch 2n,n,/(n+1)$.  In our
notation, this is the cardinality of the set
$\{\pi\in\cls_n\st\axcxb\pi=0\}$.

Although the study of pattern avoidance is scarcely more than a decade
old, there is already a sizable, and rapidly growing, literature on
the subject.  In recent years, this has also been extended to counting
the permutations with a given number of occurrences of a pattern.  For
some background on this, and for more references, see
\cite{bona,noonan-zeil,simion-schmidt,west-chow}.  Pattern avoidance
for our generalized patterns has been studied by Claesson
\cite{claesson}.

Another type of patterns implicitly present in the literature is the
set of patterns of length 3 with no dashes in our notation.  These are
the \emm valleys, ($\bac$ and $\cab$), the \emm peaks, ($\acb$ and
$\bca$), the \emm double ascents, $\abc$ and the \emm double descents,
$\cba$ in a permutation, the study of which was pioneered by
Fran\c{c}on and Viennot \cite{fravie}, and which is intimately related
to Flajolet's \cite{flajolet} generation of Motzkin paths by means of
certain continued fractions.

A \emm pattern function, is a linear combination of patterns and a
\emm $d$-function, is a linear combination of patterns that have
length at most $d$.  The length of a pattern is its number of letters,
disregarding dashes.

In this paper we show that most known Mahonian permutation statistics
can be written as linear combinations of patterns and that there is a
finite number of Mahonian $d$-functions for each $d$.  In particular,
we show that, up to some simple equivalences, there are (at most)
fourteen different Mahonian 3-functions.  Eight of these are known to
be Mahonian (and these include almost all Mahonian statistics in the
literature) and we provide proofs for three more.  For the remaining
three, which we conjecture to be Mahonian, there is overwhelming
evidence that they are.


\section{\large Mahonian statistics and  pattern functions}\label{sec-mah} 

A permutation statistic is \emm Mahonian, if it has the same
distribution as $\inv$, the number of inversions.  It is easy to see,
and was proved by Rodriguez \cite{rodriguez}, that the distribution of
$\inv$ is given by the generating function
\begin{equation}\label{inv-dist}%
\sum_{\pi\in\cls_n}{q^{\expinv\pi}} = [n]! := [n][n-1]\cdots[1],
\end{equation}
where $[k]=1+q+q^2+\cdots+q^{k-1}$.  

Clearly, $\inv$ is identical with the pattern $\bxa$.  MacMahon
\cite{macmahon} showed that the \emm major index, of a permutation,
$\maj$, is Mahonian.  The usual definition of $\maj$ is the sum of the
descents in a permutation.  For example, $\maj41523=1+3=4$, since
$\pi$ has descents in positions 1 and 3.

A naive way of computing $\maj$ is to count, for each descent in
$\pi$, the letters in $\pi$ preceding the latter of the two letters
constituting the descent.  If a letter thus preceding a descent is
smaller than both letters in the descent it will be counted by the
pattern $\axcb$.  If the size of the letter lies between that of the
descent letters it will be counted by $\bxca$, and if it is larger
than both, then it is counted by $\cxba$.  Finally, we need to count
the first letter in the descent, which is done by the pattern $\ba$,
which of course counts the descents in a permutation.

Thus, we can write $\maj$ as a combination of patterns:
$$
\maj = \axcb + \bxca + \cxba +\ba.
$$

Another Mahonian statistic is $\mak$, introduced by Foata and
Zeilberger \cite{FZ}.  It was essentially defined as the pattern
$\bxca$ plus the sum of the \emm descent bottoms, in $\pi$.  A descent
bottom is simply the smaller (rightmost) letter in a descent.  It is
easy to see that the sum of descent bottoms in $\pi$ equals the sum of
patterns $\axcb + \cbxa + \ba$.  Thus, we can write $\mak$ as follows:
$$
\mak = \bxca + \cbxa + \axcb + \ba.
$$

The Mahonian statistic $\mad$ introduced in \cite{mad} is obtained
from $\mak$ by replacing descent bottoms with \emm descent
differences,, that is, the sum of the differences in size between the
two letters of a descent.  Thus,
$$
\mad = \bxca + \bxca + \caxb + \ba.
$$

In \cite{simstan2}, Simion and Stanton defined 16 different Mahonian
statistics, each of which is a combination of the patterns $\bxca$,
$\caxb$, $\ab$ and $\ba$.  (One of these statistics equals $\mad$ on
permutations, but not on words (permutations of multisets), where
$\mad$ is still Mahonian.)  As it turns out, these are 4 genuinely
different statistics, the others being images under the ``trivial''
bijections from the symmetric group to itself.  These trivial
bijections will be treated later on in this paper.

All the Mahonian statistics mentioned above, except for $\inv$, are
\emm descent-based,, that is, they are defined in terms of the
descents (or ascents) in a permutation and the number of descents
appears ``transparently'' in the definition.  There are some Mahonian
statistics in the literature that are based instead on \emm
excedances,.  An excedance in a permutation $\pi=a_1 a_2\cdots a_n$ is
an $i$ such that $a_i>i$, and the number of excedances in a
permutation is denoted $\exc$.  The first of these statistics was \emm
Denert's statistic,, $\den$, introduced by Denert \cite{denert}.  It
was shown by Foata and Zeilberger \cite{FZ} that the pair
$(\exc,\den)$ has the same distribution as $(\des,\maj)$.  In
particular, $\den$ is Mahonian.

Several authors, namely Biane \cite{biane}, de M\'edicis and Viennot
\cite{medvie}, and Foata and Zeilberger \cite{FZ}, have defined
bijections from $\cls_n$ to the set of \pagebreak \emm labeled Motzkin
paths, in order to prove, among other things, equidistribution results
for Mahonian statistics.  It was shown by Clarke, Steingr\'{\i}msson
and Zeng \cite{mad} that these bijections are all essentially
equivalent and based on that a bijection from $\cls_n$ to itself was
given.  This bijection was shown to prove not only the
equidistribution of $(\exc,\den)$ and $(\des,\mak)$ but also the
equidistribution of $(\exc,\inv)$ and $(\des,\mad)$.

In fact, this bijection can even be used to translate an
excedance-based statistic of Haglund \cite[Theorem 5]{haglund}, which
we call $\hag$, into a descent-based statistic $\dag$, which then can
be written as a combination of patterns.  The statistic $\dag$ has
patterns of length up to 4, and this is the only Mahonian statistic we
are aware of in the literature that has patterns of length greater
than 3.  In Section \ref{sec-hag} we show how to rewrite Haglund's
original statistic into an excedance-based form and then translate it,
using the bijection in \cite{mad}, into a descent-based statistic,
which then is written as a pattern-function.

We know of no excedance-based Mahonian statistic in the literature
that can not be translated into a descent-based Mahonian statistic via
the bijection in \cite{mad}.  Moreover, \emm all, descent-based
Mahonian statistics defined directly on permutations that we are aware
of can be written as combinations of patterns.

However, there are two families of statistics, due to Dworkin
\cite{dworkin} and Haglund \cite{haglund}, respectively, that are
Mahonian, but these statistics are
defined relative to arbitrary \emm boards, considered in rook theory.
Thus, the definitions must vary as the length of the permutations
varies.  Some families of boards, nevertheless, give coherent
definitions of the statistics for all $n$.  One of Dworkin's
statistics, based on the triangular board for each $n$, turns out to
be equivalent to $\den$, as shown by Haglund \cite{haglund}.
Haglund's statistic for the same boards is the statistic $\hag$
mentioned above.  There may well be other families of statistics among
these that can be defined directly on the permutations, but we have
not made a systematic study of this.

There are also many Mahonian statistics that interpolate betwen known
Mahonian statistics, or otherwise are defined on subwords of a
permutation (or word) \cite{bressoud-zeil, galo-white, han, kadell,
  rawlings}.  We will not treat these here.


Apart from these execptions, it seems that all Mahonian permutation
statistics in the literature can be written as pattern functions or
else are equivalent, via the bijection in \cite{mad}, to such
functions.

This leads to an obvious question: How many Mahonian $d$-functions are
there, in particular, is there a finite number for each $d$?
Moreover, \emm which, pattern functions are Mahonian?  We answer these
questions (almost) completely for 3-functions and we give an explicit
numerical description of the combinations of patterns a Mahonian
$d$-function must have for all $d$.


\section{\large The main results}\label{sec-main}

So far, our patterns have had an implicit dash at the beginning and
the end, in the sense that they have been allowed to begin, and end,
anywhere in a permutation.  Strictly speaking, we should write
$({\dd}ba{\dd})$ instead of $\ba$.  The generalization that consists
of allowing patterns to have or not to have a dash at the
beginning/end is worth studying, and causes slight changes in the
results presented in Section \ref{sec-class}, as will be mentioned
later.  However, we relegate this generalization to the sidelines and
treat (a limited part of) it separately in Section \ref{sec-gen}.

Nevertheless, in this section we will consider patterns that are
required to begin at the first letter in a permutation and/or end at
the last letter.  We write such patterns with square brackets to
indicate this.  For example, the pattern $\ybxa$ counts the number of
letters in a permutation that are smaller than the first letter, and
$\ycxbxay$ counts decreasing subsequences of length three that contain
both the first and last letter in a permutation.  Most importantly
here, a pattern that has no dashes (not even implicit ones at the
beginning or end) is identically zero on $\cls_n$ except when $n$ is
the length of the pattern.  For example, $\ybacy$ is zero except on
the single permutation 213.

In this section, a \emm $k$-pattern with $i$ dashes,, or
{\em$(k,i)$-pattern}, is a pattern of length $k$ with $i$ dashes,
where we count implicit dashes at the beginning or end.  Thus,
$\ybacy$ is a $(3,0)$-pattern and $\ybxa$ is a $(3,2)$-pattern.


Using this, we can show that any $d$-function, when restricted to
$\cls_n$ for $n\ge d$, can be written as a linear combination of
$d$-patterns.  As an example, if a $4$-function contains the
(3,1)-pattern $\ybaxcy$, that pattern can be rewritten as a combination
of four $(4,1)$-patterns and a $(3,0)$-pattern:
\begin{eqnarray}\label{rewrite}
\ybaxcy =  \ybaxdcy + \ybaxcdy + \ycaxbdy + \ycbxady + \ybacy.
\end{eqnarray}    
Namely, any occurrence of the pattern $\ybaxcy$ in a permutation $\pi$
will be detected by exactly one of the patterns in the RHS of
\pref{rewrite}.  Which of the patterns in the RHS will detect this
depends on the size of the letter in $\pi$ preceding the letter
corresponding to the $c$, relative to the size of other letters in the
pattern $\ybaxcy$. If there is no letter in $\pi$ between those
corresponding to the $a$ and the $c$ this will be detected by the
pattern $\ybacy$.  Conversely, any pattern in $\pi$ detected by the RHS
of \pref{rewrite} must correspond to a unique occurrence of the
pattern $\ybaxcy$.

Now, $\ybacy$ is 0 except on $\cls_3$, so we have written $\ybaxcy$ as
a linear combination of 4-patterns, when considered as a function on
$\cls_n$ for $n\ge4$.  In general, any $k$-pattern with $i$ dashes can
be written in terms of $(k+1)$-patterns with $i$ dashes, and one
$k$-pattern with $i-1$ dashes.  Given a $d$-function, we can thus
successively strip each of its $k$-patterns, for $k<d$, of its dashes,
and end up with a function whose $k$-patterns for $k<d$ have no dashes
and thus vanish on $\cls_d$ and higher.  We record this as follows.

\begin{proposition}\label{d-prop}
  Any $d$-function, when restricted to $\cls_n$ for $n\ge d$, can be
  written as a linear combination of $d$-patterns.
\qed{} 
\end{proposition}

We call the rewriting of which \pref{rewrite} is an example \emm
upgrading,.  Observe that the number of dashes never increases in an
upgrading of a pattern.  Thus, for any $d\ge2$, the above procedure
can be used to write the Mahonian pattern $\bxa$, that is, the number
of inversions, as a combination of $d$-patterns with one, two or three
dashes plus some shorter patterns with no dashes.  A simple inductive
argument then yields the following lemma.

\begin{lemma}\label{inv-d}%
  The statistic $\inv$, when restricted to $\cls_n$ for $n\ge d$, can
  be written as a combination of $d$-patterns, of which $d!/2$ have
  three dashes, $(d-2)d!/2$ have two dashes, and $\ch d-1,2,d!/2$
  have one dash.  
\end{lemma}

We now wish to determine which linear combinations of $d$-patterns can
be Mahonian (on $\cls_n$ for $n\ge d$).  First a definition and a
proposition.

\begin{definition}%
  The \emm weight on $\cls_n$, of a function $f$ is the sum
  $\disp\sum_{\pi\in\cls_n}{f(\pi)}$.
\end{definition} 

%\pf{%
%  Pick $k$ of the numbers $1,2,\ldots,n+k-d$, call them
%  $a_1,a_2\ldots,a_k$
%%
%\mps{Needs to be filled in}
%% 
%  and assume $a_1<a_2<\cdots<a_k$.  Let $b_i$ be the size of the
%  $i$-th block in the pattern and let $c_i = a_i-b_{i-1}$ (where
%  $b_0=0$).  Then $c_i$ is the place in the permutation where the
%  $i$-th block of the pattern starts.
% \qed{}

To compute the weight of $\bxa$, the number of inversions, on
$\cls_n$, we proceed as follows.  We wish to count the total number of
inversions in all permutations in $\cls_n$.  Each inversion consists
of two letters $x$ and $y$ in a permutation, where $x<y$ and $y$
precedes $x$ in $\pi$.  There are $\ch n,2,$ such pairs and it
suffices to count how many inversions one such pair is involved in,
over all permutations in $\cls_n$.  There are $\ch n,2,$ ways to
choose the two places in a permutation where we put the $x$ and the
$y$.  The remaining $(n-2)$ letters in the permutation can be arranged
arbitrarily, in $(n-2)!$ ways, as we are only counting the inversions
involving $x$ and $y$.  Thus, the total number of inversions, that is
the weight of $\bxa$, is 
$$
\ch n,2,\cd\ch n,2,(n-2)!=\frac{n!}{2}\ch n,2,.
$$

A simple generalization of the above argument yields the following
proposition.  Note that a pattern with $k+1$ dashes has $k$ blocks of
letters separated by the dashes and recall that we are counting dashes
at the beginning/end of a pattern.  Also, we define $\ch m,-1,$ to be
1 if $m=-1$ and 0 otherwise.



\begin{proposition}\label{w-prop}%
  The weight on $\cls_n$ of a $d$-pattern with $k+1$ dashes is given
  by
$$
W_n(d,k) = \frac{n!}{ d!}\ch n-d+k,k,.
$$
In particular, the weight of a $d$-pattern with no dashes $(k=-1)$ is
1 if $n=d$  and 0 otherwise.
\end{proposition}

Now, two functions with the same distribution must have the same
weight so, by definition, a Mahonian function must have the same
weight as $\bxa$, the number of inversions.  We record this for later
use.
\begin{corollary}\label{mah-coro}%
  The weight of a Mahonian function on $\cls_n$ is $\frac{n!}{2}\ch
  n,2,$.
\end{corollary}


  Clearly, the weight of a sum of patterns is the the sum of the
  respective weights.  As it turns out, this gives significant
  restrictions on the possible combinations of patterns in order for a
  function to be Mahonian.
  

\begin{theorem}\label{d-thm}%
  Let $f$ be an arbitrary Mahonian $d$-function, written so that all
  of its $k$-patterns, for $k<d$, have no dashes.  Then $f$ has $d!/2$
  $(d,3)$-patterns, $(d-2)d!/2$ $(d,2)$-patterns, and $\ch d-1,2,d!/2$
  $(d,1)$-patterns.
\end{theorem}
\pf{%
  Observe first that each $d$-pattern has value 1 on precisely one
  permutation in $\cls_d$ and 0 on the others.  Thus, we can only have
  positive integral combinations of patterns.  Therefore a Mahonian
  linear combination of patterns cannot contain any patterns with more
  than three dashes.  Namely, the weight of such a pattern is $P(n)\cd
  n!/d!$ where $P$ is a polynomial in $n$ of degree greater than two,
  whereas the weight of $\inv=\bxa$ is $n!/2$ times a polynomial in
  $n$ of degree two.
  
  It therefore suffices to consider the possible combinations of
  $d$-patterns with 0, 1, 2 or 3 dashes.  If the respective numbers of
  these patterns are $x$, $y$, $z$ and $w$ then, by Proposition
  \ref{w-prop} and Corollary \ref{mah-coro}, they must satisfy the
  equation
$$
\ch n-d-1,-1,x + \ch n-d,0,y + \ch n-d+1,1,z + \ch n-d+2,2,w =
\frac{n!}{2}\ch n,2,
$$
for all $n\ge d$, where, as in Proposition \ref{w-prop}, $\ch
k,-1,$ is 1 if $k=-1$ and 0 otherwise.  Solving this equation for
$n=d,\ldots, d+3$ is equivalent to solving a system of linear
equations corresponding to the following matrix.
$$
\pmatrix{%
1 & 1 & 1 & 1\cr
0 & 1 & 2 & 3\cr
0 & 1 & 3 & 6\cr
0 & 1 & 4 & 10}
$$
This matrix is easily seen to be invertible, so there is a unique
possible solution to the above equation.  By Lemma \ref{inv-d} this
solution is as claimed, and holds for all $n\ge d$.
}\qed{}

Let $f$ be a Mahonian $d$-function. If we allow $k$-patterns with any
number of dashes for $k<d$ then such a function can be written in more
than one way as a $d$-function, possibly including combinations of
patterns with arbitrary real coefficients.  However, any such
combination can be put into the standard form of Theorem \ref{d-thm}
(while remaining the same function) so the theorem essentially rules
out anything but positive integral combinations.

Even if we consider the more natural situation with $k$-patterns, for
$k<d$, that don't vanish above $\cls_k$, we can give a unique standard
way of writing any Mahonian $d$-function, if we add a modest
requirement.

Namely, if we demand that all patterns in $f$ contain at least two
dashes (in particular if a pattern is required to have dashes at the
beginning and end), then we can again write $f$ in a certain standard
form and say exactly how many patterns of each type there must be in
$f$.

\begin{corollary}\label{k-coro}%
  Let $f$ be a Mahonian $d$-function whose patterns all have at least
  two dashes.  Then $f$ can be written as a sum of $k!/2$ patterns of
  length $k$ with two dashes, for $2\le k< d$, and $d!/2$ patterns of
  length $d$ with three dashes.
\end{corollary}
\pf{%
  If we repeatedly upgrade all the $(k,3)$-patterns for $k<d$, we are
  left with a combination of $(d,3)$-patterns and $(k,2)$-patterns for
  $k=2,3,\ldots,d$.  It follows from Theorem \ref{d-thm} that there
  must be exactly $d!/2$ $(d,3)$-patterns.  Now, $f$ must contain
  exactly one 2-pattern (in order to be Mahonian on $\cls_2$), and
  this 2-pattern has two dashes, by hypothesis.  That is not enough
  weight to make a function Mahonian on $\cls_3$, so $f$ must contain
  some 3-patterns.  In fact, $f$ must contain exactly three 3-patterns
  in order to have the weight of a Mahonian function on $\cls_3$.  An
  easy induction argument shows that, under the assumption that all
  the $k$-patterns have two dashes, there must be exactly $k!/2$ such
  patterns for each $k<d$.  That, in turn, leaves no room for
  $d$-patterns, other than the $d!/2$ $(d,3)$-patterns already shown
  to be present.
}\qed{}%


\section{\large A classification of the Mahonian 3-functions}\label{sec-class}

According to Corollary \ref{k-coro}, a Mahonian pattern function all
of whose patterns have dashes at the beginning and end must contain
one of the patterns $\ba$ and $\ab$.  In order to find all such
Mahonian functions, however, we can restrict to the pattern $\ba$.  In
fact, for each pattern function $f$ with a given distribution, there
are three others that obviously have the same distribution.  These are
functions obtained from $f$ by one of the three \emm trivial,
bijections of $\cls_n$ to itself, namely \emm reversion,, $R$, \emm
complementation,, $C$, and the composition $R\circ C$.

The reverse of a permutation $\pi=a_1 a_2\cdots a_n$ is the
permutation $\pi^r= a_na_{n-1}\cdots a_1$ and the complement of $\pi$
is the permutation $\pi^c=b_1b_2\cdots b_n$ where $b_i=n+1-a_i$.  As
an example, since
$$
\maj=\axcb+\bxca+\cxba+\ba,
$$
reversing each of the patterns in $\maj$ yields the function
$$
\maj^r=\bcxa+\acxb+\abxc+\ab
$$
and clearly $\maj^r\pi^r=\maj\pi$ for any permutation $\pi$.

In what follows, we will make use of this, and we will in particular
only consider pattern functions whose 2-pattern is $\ba$.  A Mahonian
3-function all of whose patterns have dashes at the beginning and the
end must thus consist of the pattern $\ba$ and three 3-patterns with
one ``internal'' dash each.  Allowing the pattern $\ybxa$ instead of
$\ba$ yields a few more Mahonian statistics different from those with
2-pattern $\ba$ but we will treat this separately in Section
\ref{sec-gen}.

The number of ways of combining one of the 2-patterns $\ba$ and $\ab$
and three 3-patterns with one internal dash each is $2\cd\ch14,3,=728$
and only $728/4=182$ if we take into account the trivial bijections
mentioned above.  Computer-aided calculations show that of these 182
3-functions, all but 14 fail to have the Mahonian distribution already
on $\cls_5$.  Among these fourteen statistics, eight are known, but
six seem to be new.  For three of those six we prove in
Proposition \ref{new-mah} that they are Mahonian.

This leaves three possible Mahonian statistics for which proofs are
missing.  However, we have verified by computer that they have the
Mahonian distribution for $n\le11$ so the following conjecture is a
safe bet.

\begin{conjecture}%
  The following statistics (number 6,11,13 in Table \ref{mah-tab})
  are Mahonian:
\begin{eqnarray*}
  \acxb  +  \baxc  +  \cxba +\ba,   \\[4pt]   %23   
  \axcb  +  \bxca  +  \bxca +\ba,    \\[4pt]   %10   
  \bcxa  +  \caxb  +  \caxb +\ba.    
\end{eqnarray*}
\end{conjecture} 

\medskip

In Table \ref{mah-tab} we give a list of all fourteen (possible)
Mahonian 3-functions.  We group them into the seven equivalence
classes induced by the relation $\sim$, where two statistics $S$ and
$T$ satisfy $S\sim T$ if the distribution of the bistatistics
$(\des,S)$ and $(\des,T)$ is the same.  Here $\des$ is the number of
descents, and thus equals $\ba$.

The equidistributions of such bistatistics have been much studied (see
e.g.  \cite{mad,dworkin,foa1,FZ,haglund,medvie}) and the fact that all
Mahonian 3-functions must contain the pattern $\ba=\des$ ``explains''
why this is a natural classification.  Note that if $S= S'+\ba$ and
$T=T'+\ba$ are two equidistributed functions and $(\des,S)$ and
$(\des,T)$ are also equidistributed then so are $S'$ and $T'$.  The
converse of this is not true, of course, so stripping two statistics
with different distributions of the pattern $\ba$ may result in
statistics with the same distribution.  It is easily checked, however,
that this does not happen with any two different classes in Table
\ref{mah-tab}.  Because of this, and for simplicity, we omit writing
the pattern $\ba$ in the statistics in Table \ref{mah-tab}.  In Table
\ref{bi-tab} we give the distribution of the bistatistic $(\des,S)$
for the statistics $S$ in each of the seven equivalence classes in
Table \ref{mah-tab}.  Observe that in Table \ref{bi-tab} the
statistics $S$ \emm do contain, the pattern $\ba$.


\newMAH{stat}

\begin{table}[htbp]
  \begin{center}
    \leavevmode
$$
\begin{array}{rcccccl}
 1 & \acxb & + & \acxb & + & \bxac  & \\   %1
 2 & \acxb & + & \acxb & + & \bxca  & \\   %2   
 3 & \acxb & + & \bxca & + & \bxca  & \\   %6   
 4 & \bxca & + & \bxca & + & \caxb  &  \mad \\[12pt]   %25 


 5 & \acxb & + & \baxc & + & \cbxa  & \stat\\   %3   
 6 & \acxb & + & \baxc & + & \cxba  & \\   %4   
 7 & \axcb & + & \bxca & + & \cbxa &  \mak \\   %11 
 8 & \axcb & + & \bxca & + & \cxba  &  \maj \\   %12 
 9 & \axcb & + & \caxb & + & \cbxa   & \makl\\[12pt]   %13   


 10 & \acxb & + & \caxb & + & \cbxa  & \stat'\\[12pt]   %7   

 11 & \axcb & + & \bxca & + & \bxca   & \\[12pt]   %10   

 12 & \axcb & + & \cxab & + & \cxba & \stat''\\[12pt]   %14   

 13 & \bcxa & + & \caxb & + & \caxb   & \\[12pt]   %23   

 14 & \bcxa & + & \caxb & + & \cbxa  &  \inv \\   %24 
\end{array}
$$
    \caption{\label{mah-tab} All Mahonian 3-functions (omitting the
      pattern $\ba$), up to trivial bijections.  The first four belong
      to those defined by Simion and Stanton \cite{simstan2}.  The
      statistic $\makl$ appears in \cite[Prop. 13]{mad}.}
  \end{center}
\end{table}


\begin{table}[htbp]
  \begin{center}
    \leavevmode
\footnotesize
$$
\begin{array}{rrrrrrrrrrr}
1&0&0&0&0&0&0&0&0&0&0\\
0&4&3&5&5&5&3&1&0&0&0\\
0&0&6&6&11&12&12&9&6&3&1\\
0&0&0&4&3&5&5&5&3&1&0\\
0&0&0&0&1&0&0&0&0&0&0\\[14pt]


1&0&0&0&0&0&0&0&0&0&0\\
0&4&9&9&4&0&0&0&0&0&0\\
0&0&0&6&14&22&14&6&0&0&0\\
0&0&0&0&0&0&4&9&9&4&0\\
0&0&0&0&0&0&0&0&0&0&1\\[14pt]


1&0&0&0&0&0&0&0&0&0&0\\
0&4&9&5&6&1&1&0&0&0&0\\
0&0&0&10&14&20&12&7&3&0&0\\
0&0&0&0&0&1&7&8&6&4&0\\
0&0&0&0&0&0&0&0&0&0&1\\[14pt]


1&0&0&0&0&0&0&0&0&0&0\\
0&4&3&8&4&5&1&1&0&0&0\\
0&0&6&3&14&12&14&8&6&2&1\\
0&0&0&4&1&5&5&6&3&2&0\\
0&0&0&0&1&0&0&0&0&0&0\\[14pt]


1&0&0&0&0&0&0&0&0&0&0\\
0&4&6&8&7&1&0&0&0&0&0\\
0&0&3&7&12&20&14&10&0&0&0\\
0&0&0&0&1&1&6&5&9&4&0\\
0&0&0&0&0&0&0&0&0&0&1\\[14pt]


1&0&0&0&0&0&0&0&0&0&0\\
0&4&3&5&3&5&2&3&1&0&0\\
0&0&6&6&13&9&14&7&7&3&1\\
0&0&0&4&3&8&4&5&1&1&0\\
0&0&0&0&1&0&0&0&0&0&0\\[14pt]


1&0&0&0&0&0&0&0&0&0&0\\
0&4&6&6&6&2&2&0&0&0&0\\
0&0&3&9&12&18&12&9&3&0&0\\
0&0&0&0&2&2&6&6&6&4&0\\
0&0&0&0&0&0&0&0&0&0&1\\
\end{array}
$$
    \caption{\label{bi-tab} 
      Distribution of $(\des,S)$ on $\cls_5$ for the seven different
      equivalence classes of statistics $S$ (together with $\ba$) in
      Table~\ref{mah-tab}, in the same order.  Rows are indexed by
      number of descents, columns by value of $S$; both start at 0.}
  \end{center}
\end{table}


We now prove that the statistics number 5, 10 and 12 in Table
\ref{mah-tab} are Mahonian.

\begin{proposition}\label{new-mah}%
The following statistics are Mahonian:
\begin{eqnarray*}
\stat&=&\acxb + \baxc + \cbxa + \ba,\\[.4ex]  %3
\stat'&=&\acxb + \caxb + \cbxa + \ba,\\[.4ex]  %7
\stat''&=& \axcb + \cxab + \cxba + \ba.  %15
\end{eqnarray*} 

\end{proposition}
\pf{%
  We prove, by induction on the length of a permutation, that $\stat$
  is Mahonian.  The proofs for the other two statistics are similar
  and are omitted.  We analyze how the value of $\stat$ changes as we
  prepend $k=1,2,\ldots,n$ to a permutation $\pi\in\cls_{n-1}$ and add
  one to those letters in $\pi$ that are greater than or equal to $k$.
  For example, prepending 3 to the permutation 4132 we get 35142.  (In
  the case of $\stat''$, the letter should be appended to the end of
  $\pi$.)
  
  Let the first letter of $\pi$ be $m$ and suppose we are prepending
  $k$ to $\pi$.  There are two cases, depending on whether $k$ is
  greater than $m$ or not.  
  
  If $k$ is smaller than or equal to $m$, then the only pattern in
  $\stat$ that is affected is $\acxb$.  If $k=m$ then there is no
  effect.  If $k =m-1$ then the value of $\acxb$ will increase by one,
  since the one letter between $k$ and $m'=m+1$ (the ``new value'' of
  $m$) in size will appear after $m'$ in the resulting permutation.
  In general, if $k=m-i$, where $0\le i<m$, then the value of
  $\acxb$ will increase by $i$.
  
  If $k$ is greater than $m$ then we are creating a descent at the
  beginning of the permutation, thus increasing $\ba$ by one.  Also,
  each letter in $\pi$ that is smaller than $m$ (and thus to the right
  of $m$) will contribute an increase of one to $\cbxa$.  Therefore,
  the total increase to $\cbxa$ and $\ba$ will be precisely $m$.  In
  addition, if $k=m+i$, where $i\ge1$, then $\baxc$ will increase by
  $n-m-i$.  The pattern $\acxb$ is not affected in this case.
  
  Thus, prepending the letters $1,2,\ldots,n$ to $\pi$ will increase
  the value of $\stat$ by $0,1,\ldots,n-1$, respectively (but not
  necessarily in this order).  Given that the distribution of $\stat$
  on $\cls_1$ is 1, this implies, by induction, that its distribution
  on $\cls_n$ is the same as that of $\inv$, given in \pref{inv-dist}.
%
\qed{}

We conjecture that $\stat$ belongs to the same equivalence class as
$\maj$ and $\mak$. As is the case for all conjectures in this paper,
this has been verified by computer for $n\le11$.
\begin{conjecture}%
  The distribution of the bistatistic $(\des,\stat)$ is equal to that
  of $(\des,\maj)$.
\end{conjecture}


\section{\large A generalization}\label{sec-gen}

If we allow patterns with no (implicit) dash at the beginning, as in
Section \ref{sec-main}, we find several candidates for Mahonian
statistics among the 3-functions (where we only consider the 2-pattern
$\ybxa$ and we have restricted the 3-patterns to have dashes at the
beginning and end).  All but four of these can be shown to equal some
of the ones in Table \ref{mah-tab}, as functions, and so are not new.
We conjecture that the remaining four are Mahonian and that they
belong to the equivalence class of $(\des,\maj)$.


\begin{conjecture}\label{conj1}%
  The following statistics are Mahonian, where, as in
  Section~\ref{sec-main}, a square bracket $[$ at the beginning of a
  pattern means that the pattern must begin at the first letter of the
  permutation.  Furthermore, the bistatistics $(\des,S_i)$, for
  $i=1,2,3,4$, are equidistributed with $(\des,\maj)$.
\begin{eqnarray*}
S_1 &=&\axcb \; +\; \bxac \; +\; \cbxa \; +\; \ybxa,\\[4pt]
S_2 &=& \axcb \; +\; \bxac \; +\; \cxba \; +\; \ybxa,\\[4pt]
S_3 &=& \axcb \; +\; \bxca \; +\; \cbxa \; +\; \ybxa,\\[4pt]
S_4 &=& \axcb \; +\; \bxca \; +\; \cxba \; +\; \ybxa.
\end{eqnarray*}
\end{conjecture}

\section{\large A Mahonian 4-function}\label{sec-hag}

We now show, without giving all details, how the statistic $\hag$ of
Haglund \cite[Thm.  5]{haglund} can be rewritten to make it suitable
for ``translation'' by the bijection in \cite{mad} into a statistic
$\dag$, which in turn can be written in terms of patterns of lengths
up to four.

We use here terminology from \cite{mad}, where $\ddif\pi$ is the sum
of descent differences $(a_i-a_{i+1})$ over all descents $i$ in $\pi$,
and $\edif$ is the coresponding sum of excedance differences ($a_i-i$)
over all excedances $i$.  Moreover, $\exc(\pi)$ is the subword of
$\pi$ consisting of those letters $a_i$ for which $a_i>i$ and
$\nex(\pi)$ is the complementary subword of $\exc(\pi)$ in $\pi$.

Haglund calls his statistic simply \emm stat, and defines it as
follows, where $\pi=a_1a_2\cdots{}a_n$ and we take $i$ to be less than
$j$ in all sets:
$$
\edif\pi + \sum_{a_i\le i}{(1-a_i)} + \inv(\exc(\pi))+
\#\{a_i\le j<a_j\} + \#\{a_i<a_j\le j\}.
$$
This can be rearranged and then rewritten as follows:
\begin{eqnarray*}%
&& \edif\pi +  \inv(\exc(\pi)) +\sum_{a_i\le i}{(1-a_i)} +
 \#\{a_i<a_j\le j\}+\#\{a_i\le j<a_j\}\\[4pt]
&&=\edif\pi + \inv(\exc(\pi)) -\#\{a_j<a_i\le i\} + \#\{a_i\le
j<a_j\}\\[6pt]
%
&&=\edif\pi +  \inv(\exc(\pi)) - \inv(\nex(\pi)) + E,
\end{eqnarray*} 
where $E$ is the sum of numbers defined for each excedance bottom
$k$ as the number of letters $a_i$ with $i<k$ and $a_i\le k$. 

We define a descent-based version of this statistic, $\dag$ by
\begin{equation}
  \label{dag-eq}
\dag\pi=\ddif\pi + \res(\destops) - \res(\nondestops) + D,
\end{equation}
where $D$ is the sum of numbers defined for each descent bottom $a_i$
as the number of descent tops smaller than or equal to $a_i$ and
non-descent bottoms smaller than or equal to $a_i$.  Moreover, $\res$
is a function equal to the pattern $\bxca$, and $\res(\destops)$ is
the number of occurrences of that pattern where the letter
corresponding to the $b$ is a descent top, that is, the first letter
$a_i$ in a descent $a_i>a_{i+1}$.  The term $\res(\nondestops)$ is the
corresponding number for the non-descent tops.

Applying the bijection $\Phi$ in \cite[Section 3]{mad} to a
permutation $\pi$ we have that $\dag\pi=\hag\Phi(\pi)$.  Thus $\dag$
is Mahonian since $\hag$ is.

With some work, it is possible to write \pref{dag-eq} as follows:
\begin{eqnarray}\label{new-dag}
&&\ba + \yaxcb +  \cba + \caxb\\[4pt]
&& + 2\cd\caxdb + 2\cd\cbxda + \abxdc + \baxdc + \dcxab + \dcxba.\nonumber
\end{eqnarray}
Using the identity
$$
  \yaxcb = \axcb - \left[\daxcb + \caxdb + \baxdc + \abxdc\right]
  $$
  (obtained by upgrading $\axcb$) we can then rewrite
  \pref{new-dag} as follows:
\begin{eqnarray*}
&&\ba +\cab +\cba+\axcb\\[4pt]
&&+ 2\cd\caxdb + 2\cd\cbxda + \dcxab + \dcxba +\daxbc +\dbxac.
\end{eqnarray*}
Finally, to get this into the standard form of Corollary \ref{k-coro},
we upgrade $\axcb$ and obtain
\begin{eqnarray*}
\dag = &&\ba +\cab +\cba+\acb\\[4pt]
&&+ 2\cd\caxdb + 2\cd\cbxda + \dcxab + \dcxba +\daxbc\\[4pt]
&& +\dbxac+\adxcb +\acxdb +\abxdc +\baxdc.
\end{eqnarray*}

We have compared, with the aid of a computer, the statistic $\dag$ to
all the statistics in Table \ref{mah-tab} (and the statistics obtained
from these by the bijection $R\circ C$) and found that it is not
equal, as a function, to any of them.  Thus, $\dag$ is genuinely a
4-function.  It was shown by Haglund \cite[Thm. 5]{haglund} that
$(\exc,\hag)$ is equidistributed with $(\des,\maj)$.  Appealing to the
properties of the bijection $\Phi$ in \cite[Prop. 3]{mad}, it follows
that $(\des,\dag)$ also has the same distribution.


\pagebreak

\begin{thebibliography}{22}
\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{bona} M. B\'ona: The number of permutations with exactly $r$
  $132$-subsequences is $P$-recursive in the size! Adv. in Appl. Math.
  {\bf 18} (1997), no. 4, 510--522.
  
\bibitem{bressoud-zeil} D. Bressoud and D. Zeilberger: A proof of
  Andrews' $q$-Dyson conjecture, Discrete Math.  {\bf 54} (1985),
  201--224.

\bibitem{claesson} A. Claesson: Generalized pattern avoidance, in
  preparation.
  
\bibitem{mad} R. J. Clarke, E. Steingr\'{\i}msson and J. Zeng: New
  Euler-Mahonian statistics on permutations and words, Adv. in Appl.
  Math. {\bf 18} (1997), 237--270.
  
\bibitem{denert} M. Denert: The genus zeta function of hereditary
  orders in central simple algebras over global fields, Math. Comp.
  {\bf54} (1990), 449-465.


\bibitem{dworkin} M. Dworkin: An interpretation for Garsia and
  Remmel's $q$-hit numbers, J. Combin. Theory Ser. A {\bf 81} no. 2,
  (1998), 149--175.
  
\bibitem{flajolet} P. Flajolet: Combinatorial aspects of continued
  fractions, Disc. Math. {\bf 41} (1982), 125--161.

\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{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{galo-white} J. Galovich, D. White: Recursive statistics on
  words, Proceedings of the 6th Conference on Formal Power Series and
  Algebraic Combinatorics (New Brunswick, NJ, 1994). Discrete Math.
  {\bf 157} (1996), no. 1-3, 169--191.

\bibitem{haglund} J. Haglund: $q$-rook polynomials and matrices over
  finite fields, Adv. in Appl. Math. {\bf 20} (1998), no.~4, 450--487.
  
\bibitem{han} G.-N. Han: Calcul Denertien, doctoral thesis, Publ.
  I.R.M.A. Strasbourg, 1991.

\bibitem{kadell} K. Kadell:  Weighted inversion numbers, restricted
  growth functions, and standard Young tableaux, J. Combin. Theory, Ser. A
{\bf 40} (1985), 22--44.

\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. in Appl. Math. {\bf 15} (1994), 262--304.
  
\bibitem{noonan-zeil} J. Noonan, D. Zeilberger: The enumeration of
  permutations with a prescribed number of "forbidden" patterns, Adv.
  in Appl. Math. {\bf 17} (1996), no. 4, 381--407.

\bibitem{rawlings} D. Rawlings:  The $r$-major index, J. Combin. Theory, Ser. A
{\bf 31} (1981), 175--183.

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

\bibitem{simion-schmidt} R. Simion, F. Schmidt: Restricted permutations,
  European J. Combin. {\bf 6} (1985), no. 4, 383--406.

\bibitem{simstan2} R. Simion and D. Stanton: Octabasic Laguerre
  polynomials and permutation statistics, J.  Comput. Appl. Math. {\bf
    68} (1996), 297--329.
  
\bibitem{west-chow} J. West, T. Chow: Forbidden subsequences and Chebyshev
  polynomials, Discrete Math.  {\bf 204} (1999), no. 1-3, 119--128.

\end{thebibliography} 

\bigskip
\bigskip

\def\mb#1,#2,{\makebox[90mm][l]{#1}#2\\}%

\noindent
\mb   Eric Babson, Einar Steingr\'{\i}msson,
\mb   Department of Mathematics,   Matematik,
\mb   University of Washington,   CTH \& GU,
\mb   {Seattle, WA 98195-4350},   S-412 96 G\"oteborg,
\mb   USA,   SWEDEN,
\mb  {\tt babson@math.washington.edu}, {\tt einar@math.chalmers.se},


\end{document}