Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: A Bijective Proof of a Major Index Theorem of Garsia and Gessel. | A Bijective Proof of a Major Index Theorem of Garsia and Gessel Mordechai Novick Department of Mathematics Hebrew University Jerusalem Israel Submitted Jun 3 2009 Accepted Apr 7 2010 Published Apr 19 2010 Mathematics Subject Classification 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 ni . nk 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. 1 Introduction In 1913 Percy MacMahon introduced the major index statistic defined for any permutation Ơ of a multiset of integers of size n as the sum of the descents of Ơ . maj ơ 1 ix ơi ơi i 1- Let n 1 . n and n 0 0 1 . n . Let n q 1 qn-i n q Ị Ịn 1 i q and if a1 . ak are positive integers which sum to n then let n ai . ak This paper is a condensed version of an . thesis written under the direction of Gil Kalai of the Hebrew University and Yuval Roichman of Bar-Ilan University. I extend my thanks to both of them for their time and assistance. 1We adopt the convention that for any statement A x A 1 if A is true and x A 0 if A is false. n q ai q ak q 1 THE ELECTRONIC JOURNAL OF COMBINATORICS 17 2010 R64 1 If T denotes the multiset 1ai .kak . the set of ai copies of
