\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 $ii$, 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 $ki$ 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 ja_{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}