{
  "id": "math/0512650",
  "version": "v1",
  "published": "2005-12-30T03:05:31.000Z",
  "updated": "2005-12-30T03:05:31.000Z",
  "title": "Counting permutations by congruence class of major index",
  "authors": [
    "Helene Barcelo",
    "Bruce Sagan",
    "Sheila Sundaram"
  ],
  "comment": "15 pages",
  "categories": [
    "math.CO",
    "math.NT"
  ],
  "abstract": "Consider S_n, the symmetric group on n letters, and let maj pi denote the major index of a permutation pi in S_n. Given positive integers k,l and nonnegative integers i,j, define m_n^{k,l}(i,j) := number of pi in S_n such that maj pi = i (mod k) and maj pi^{-1} = j (mod l). We prove bijectively that if k,l are relatively prime and at most n then m_n^{k,l}(i,j) = n!/(kl) which, surprisingly, does not depend on i and j. Equivalently, if m_n^{k,l}(i,j) is interpreted as the (i,j)-entry of a matrix m_n^{k,l}, then this is a constant matrix under the stated conditions. This bijection is extended to show the more general result that for d at least 1 and k,l relatively prime, the matrix m_n^{kd,ld} admits a block decompostion where each block is the matrix m_n^{d,d}/(kl). We also give an explicit formula for m_n^{n,n} and show that if p is prime then m_{np}^{p,p} has a simple block decomposition. To prove these results, we use the representation theory of the symmetric group and certain restricted shuffles.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2005-12-30T03:05:31.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05A10",
      "05A19",
      "11B50"
    ],
    "keywords": [
      "major index",
      "congruence class",
      "counting permutations",
      "symmetric group",
      "maj pi denote"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 15,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2005math.....12650B"
    }
  }
}