A bijective proof of a major index theorem of Garsia and Gessel

zbMATH Open1189.05010arXiv0906.0377MaRDI QIDQ976714FDOQ976714

Authors: Mordechai Novick 

Publication date: 16 June 2010

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/0906.0377

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• Inversions and Major Index for Permutations
• A Bijective Proof of Stanley's Shuffling Theorem
• A new derivation of the generating function for the major index
• Bijective proofs of shuffle compatibility results
• The major index polynomial for conjugacy classes of permutations

Mathematics Subject Classification ID

Permutations, words, matrices (05A05)

Cited In (9)

• A bijective proof of Macdonald's reduced word formula
• On a theorem of Baxter and Zeilberger via a result of Roselle
• Bijective proofs of shuffle compatibility results
• On a conjecture concerning shuffle-compatible permutation statistics
• Some refinements of Stanley's shuffle theorem
• The major index specialization of the \(q,t\)-Catalan.
• The major index polynomial for conjugacy classes of permutations
• A combinatorial proof of a result of Gessel and Greene
• A cyclic analogue of Stanley's shuffling theorem

This page was built for publication: A bijective proof of a major index theorem of Garsia and Gessel

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q976714)