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

MaRDI QIDQ976714zbMATH OpenFDO

Authors Mordechai Novick

Publication date 16 June 2010

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

Full work available at URL https://arxiv.org/abs/0906.0377, https://eudml.org/doc/225678, http://www.emis.de/journals/EJC/Volume_17/Abstracts/v17i1r64.html

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

Mathematics Subject Classification ID

Permutations, words, matrices (05A05)

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.

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

Cited in

(9)

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

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)