A MAJ STATISTIC FOR SET PARTITIONS

We propose a weighting of set partitions which is analogous to the major index for permutations. The corresponding weight generating function yields the q-Stirling numbers of the second kind of Carlitz and Gould. Other interpretations of maj are given in terms of restricted growth functions, rook placements and reduced matrices. The Foata bijection interchanging inv and maj for permutations also has a version for partitions. Finally, we generalize these constructions to an analog of Rawling's rmaj and to two new kinds of p, q-Stirling numbers. © 1991, Academic Press Limited. All rights reserved.