A Bijective Proof of a Major Index Theorem of Garsia and Gessel

Details A Bijective Proof of a Major Index Theorem of Garsia and Gessel A Bijective Proof of a Major Index Theorem of Garsia and Gessel

2009-06-01

arxiv.org/abs/0906.0377v1

Mathematics

Combinatorics

Scientific paper

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 whose union is [n]. Two special cases are singled out: If the single element j is inserted into any permutation P of the remaining elements of [n], then the theorem states that inserting j into P increases the major index of P by some element of {0,1,...,n-1}, the increase determined uniquely by the index of insertion. We provide a direct proof of this fact using an algorithm which calculates the increase at each index; this in turn leads to a bijective proof of MacMahon's 1916 result on the equidistribution of major index and inversion number over S_n. Using this special case we prove the general case of the theorem by establishing a bijection between shuffles of ordered sequences and a certain set of partitions. In the second special case of interest, 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.

Affiliated with

Also associated with

No associations

Rating

A Bijective Proof of a Major Index Theorem of Garsia and Gessel does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A Bijective Proof of a Major Index Theorem of Garsia and Gessel, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Bijective Proof of a Major Index Theorem of Garsia and Gessel will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-234236