Mahonian pairs

JOURNAL OF COMBINATORIAL THEORY SERIES A

卷:119

Article

Sagan, Bruce E.¹  Savage, Carla D.² 

[1] Michigan State Univ, Dept Math, E Lansing, MI 48824 USA

[2] N Carolina State Univ, Dept Comp Sci, Raleigh, NC 27695 USA

关键词: Ballot sequence;    Greene-Kleitman symmetric chain decomposition;    Foata's fundamental bijection;    Integer partition;    Inversion number;    Mahonian statistic;    Major index;    Rank of a partition;    q-Catalan number;    q-Fibonacci number;   

DOI  :  10.1016/j.jcta.2011.11.003

来源: Elsevier

【 摘 要 】

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 subset 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, G(n), can be expressed by saying that (G(n), G(n)) is a Mahonian pair. We investigate various Mahonian pairs (S, T) with S not equal T. Our principal tool is Foata's fundamental bijection phi:P* -> P* since it has the property that maj w = inv phi(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}*, phi 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. (C) 2011 Elsevier Inc. All rights reserved.

【 授权许可】

Free