| Babson-Steingrímsson statistics are indeed Mahonian (and sometimes even Euler-Mahonian (2008) | |||||||||||||||
Abstract | |||||||||||||||
| Abstract: 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. 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 = x1x2... xn 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 xi < xj < xj+1. Similarly, the pattern (b ca)(w) is that number of occurrences of xj+1 < xi < xj, and in general, for any permutation α, β, γ of a, b, c, the expression (α βγ)(w) is the number of pairs (i, j), 1 ≤ i < j < n, such that the orderings of the two triples (xi, xj, xj+1) and (α, β, γ) are identical. The statistic (ab c)(w) is defined in the same way by looking at the occurrences (xi, xi+1, xj) such that i + 1 < j and xi < xi+1 < xj. Of course, (ba)(w) denotes the number of descents, des w (i.e. the number of places 1 ≤ i < n such that xi> xi+1), | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||