  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 of
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 different
from T. Our principal tool is Foata's fundamental bijection f: P^* -> P^* since
it has the property that maj w = inv f(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}^*, f 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.
