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.

  Download:   PDF