Generalized Permutation Patterns and a Classification of the Mahonian Statistics

Eric Babson   ; Einar Steingrímsson

Séminaire lotharingien de combinatoire, Tome 44 (2000-2001)

Résumé

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.