Đang chuẩn bị liên kết để tải về tài liệu:
Báo cáo toán học: "A Bijective Proof of a Major Index Theorem of Garsia and Gessel"

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 mordecha.novick@mail.huj i.ac.il 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 Ơ ơ-1-.ơn of a multiset of integers of size n as the sum of the descents of Ơ i.e. 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 M.Sc. 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 i.e. the set of ai copies of