A bijective proof of a major index theorem of Garsia and Gessel
The electronic journal of combinatorics, Tome 17 (2010)
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,...,n\}$ which are shuffles of given disjoint ordered sequences $\pi_1,...,\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.
@article{10_37236_336,
author = {Mordechai Novick},
title = {A bijective proof of a major index theorem of {Garsia} and {Gessel}},
journal = {The electronic journal of combinatorics},
year = {2010},
volume = {17},
doi = {10.37236/336},
zbl = {1189.05010},
url = {http://geodesic.mathdoc.fr/articles/10.37236/336/}
}
Mordechai Novick. A bijective proof of a major index theorem of Garsia and Gessel. The electronic journal of combinatorics, Tome 17 (2010). doi: 10.37236/336
Cité par Sources :