Mahonian pairs

AbstractWe introduce the notion of a Mahonian pair. Consider the set, P⁎, of all words having the positive integers as alphabet. Given finite subsets S,T⊂P⁎, we say that (S,T) is a Mahonian pair if the distribution of the major index, maj, over S is the same as the distribution of the inversion number, inv, over T. So the well-known fact that maj and inv are equidistributed over the symmetric group, Sn, can be expressed by saying that (Sn,Sn) is a Mahonian pair. We investigate various Mahonian pairs (S,T) with S≠T. Our principal tool is Foataʼs fundamental bijection ϕ:P⁎→P⁎ since it has the property that majw=invϕ(w) for any word w. We consider various families of words associated with Catalan and Fibonacci numbers. We show that, when restricted to words in {1,2}⁎, ϕ transforms familiar statistics on words into natural statistics on integer partitions such as the size of the Durfee square. The Rogers–Ramanujan identities, the Catalan triangle, and various q-analogues also make an appearance. We generalize the definition of Mahonian pairs to infinite sets and use this as a tool to connect a partition bijection of Corteel–Savage–Venkatraman with the Greene–Kleitman decomposition of a Boolean algebra into symmetric chains. We close with comments about future work and open problems