{
  "id": "0906.0377",
  "version": "v1",
  "published": "2009-06-01T20:40:30.000Z",
  "updated": "2009-06-01T20:40:30.000Z",
  "title": "A Bijective Proof of a Major Index Theorem of Garsia and Gessel",
  "authors": [
    "Moti Novick"
  ],
  "categories": [
    "math.CO"
  ],
  "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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2009-06-01T20:40:30.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "bijective proof",
      "major index theorem",
      "inversion number",
      "second special case",
      "ordered sequences"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2009arXiv0906.0377N"
    }
  }
}