Séminaire Lotharingien de Combinatoire, B44b (2000), 18 pp.
Eric Babson and Einar Steingrímsson
Generalized Permutation Patterns and a
Classification of the Mahonian Statistics
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.
Received: May 9, 2000; Revised May 12, 2000, Accepted: May 19, 2000.
The following versions are available: