Mahonian pairs

Article, Preprint English OPEN
Sagan, Bruce E. ; Savage, Carla D. (2012)
  • Publisher: Elsevier BV
  • Journal: Journal of Combinatorial Theory, Series A, volume 119, issue 3, pages 526-545 (issn: 0097-3165)
  • Related identifiers: doi: 10.1016/j.jcta.2011.11.003
  • Subject: Mathematics - Combinatorics | Theoretical Computer Science | Computational Theory and Mathematics | 05A05 (Primary), 05A10 (Secondary), 05A15, 05A19, 05A30, 11P81 | Discrete Mathematics and Combinatorics
    arxiv: Mathematics::Combinatorics

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.
Share - Bookmark