Babson–Steingrı́msson Statistics are Indeed Mahonian (and Sometimes Even Euler–Mahonian)
✍ Scribed by Dominique Foata; Doron Zeilberger
- Publisher
- Elsevier Science
- Year
- 2001
- Tongue
- English
- Weight
- 159 KB
- Volume
- 27
- Category
- Article
- ISSN
- 0196-8858
No coin nor oath required. For personal study only.
✦ Synopsis
Babson and Steingrímsson have recently introduced seven new permutation statistics, that they conjectured were all Mahonian (i.e., equi-distributed with the number of inversions). We prove their conjecture for the first four and also prove that the first and the fourth are even Euler-Mahonian. We use two different, in fact, opposite, techniques. For three of them we give a computer-generated proof, using the Maple package ROTA, that implements the second author's "Umbral Transfer Matrix Method." For the fourth one a geometric permutation transformation is used that leads to a further refinement of this Euler-Mahonian distribution study. 2001 Elsevier Science
1. BABSON AND STEINGR ÍMSSON'S NOTATION
In [BaSt00] Babson and Steingrímsson introduced a convenient notation for "atomic" permutation statistics. Given a permutation w = x 1 x 2
x n of 1 2 n they define, for example, a -bc w to be the number of occurrences of the "pattern" a -bc, i.e., the number of pairs of places 1 ≤ i < j < n such that x i < x j < x j+1 . Similarly, the pattern b -ca w