Mahonian pairs

We 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, S n , can be expressed by saying that ( S n , S n ) 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 maj w = 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.