Labeled Partitions and the q-Derangement Numbers
William Y.C. Chen and Deheng Xu
Abstract: Inspired by MacMahon's original proof of his celebrated theorem on the distribution of the major index over permutations, we give a reformulation of his argument in terms of labeled partitions. In this framework, we establish a decomposition theorem for labeled partitions which is analogous to the decomposition of a permutation into derangement points and fixed points. This decomposition implies a reformulation of Wachs' formula concerning the derangement parts and major index on permutations which was derived in order to present a bijective treatment of Gessel's formula on the q-derangement numbers.
AMS Classification: 05A30; 05A19, 05A15
Keywords: q-derangement number, major index, bijection, partitions, labeled partitions