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.

Review text

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.

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

(10)

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