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: