zbMATH — the first resource for mathematics

A bijective proof of a major index theorem of Garsia and Gessel. (English) Zbl 1189.05010
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.

05A05 Permutations, words, matrices
Full Text: EMIS EuDML