{
  "id": "1109.4976",
  "version": "v2",
  "published": "2011-09-23T00:25:00.000Z",
  "updated": "2012-05-09T14:14:54.000Z",
  "title": "Permutation patterns and statistics",
  "authors": [
    "Theodore Dokos",
    "Tim Dwyer",
    "Bryan P. Johnson",
    "Bruce E. Sagan",
    "Kimberly Selsor"
  ],
  "comment": "28 pages, 5 figures, tightened up the exposition, noted that some of the conjectures have been proved",
  "categories": [
    "math.CO"
  ],
  "abstract": "Let S_n denote the symmetric group of all permutations of the set {1, 2, ...,n} and let S = \\cup_{n\\ge0} S_n. If Pi is a set of permutations, then we let Av_n(Pi) be the set of permutations in S_n which avoid every permutation of Pi in the sense of pattern avoidance. One of the celebrated notions in pattern theory is that of Wilf-equivalence, where Pi and Pi' are Wilf equivalent if #Av_n(Pi)=#Av_n(Pi') for all n\\ge0. In a recent paper, Sagan and Savage proposed studying a q-analogue of this concept defined as follows. Suppose st:S->N is a permutation statistic where N represents the nonnegative integers. Consider the corresponding generating function, F_n^{st}(Pi;q) = sum_{sigma in Av_n(Pi)} q^{st sigma}, and call Pi,Pi' st-Wilf equivalent if F_n^{st}(Pi;q)=F_n^{st}(Pi';q) for all n\\ge0. We present the first in-depth study of this concept for the inv and maj statistics. In particular, we determine all inv- and maj-Wilf equivalences for any Pi containd in S_3. This leads us to consider various q-analogues of the Catalan numbers, Fibonacci numbers, triangular numbers, and powers of two. Our proof techniques use lattice paths, integer partitions, and Foata's fundamental bijection. We also answer a question about Mahonian pairs raised in the Sagan-Savage article.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2012-05-09T14:14:54.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05A05"
    ],
    "keywords": [
      "permutation patterns",
      "foatas fundamental bijection",
      "first in-depth study",
      "symmetric group",
      "integer partitions"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 28,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2011arXiv1109.4976D"
    }
  }
}