A bijective proof of a major index theorem of Garsia and Gessel. (English) Zbl 1189.05010

Novick, Mordechai

Electron. J. Comb. 17, No. 1, Research Paper R64, 12 p. (2010).

Summary: In this paper we provide a bijective proof of a theorem of Garsia and Gessel describing the generating function of the major index over the set of all permutations of \([n]=\{1,\dots,n\}\) which are shuffles of given disjoint ordered sequences \(\pi_1,\dots,\pi_k\) whose union is \([n]\). The proof is based on a result (an “insertion lemma”) of Haglund, Loehr, and Remmel which describes the change in major index resulting from the insertion of a given new element in any place in a given permutation. Using this lemma we prove the theorem by establishing a bijection between shuffles of ordered sequences and a certain set of partitions. A special case of Garsia and Gessel’s theorem provides a proof of the equidistribution of major index and inversion number over inverse descent classes, a result first proved bijectively by Foata and Schutzenberger in 1978. We provide, based on the method of our first proof, another bijective proof of this result.

MSC:

05A05

Permutations, words, matrices