{
  "id": "1005.5419",
  "version": "v1",
  "published": "2010-05-29T00:20:15.000Z",
  "updated": "2010-05-29T00:20:15.000Z",
  "title": "Equivalence classes of permutations avoiding a pattern",
  "authors": [
    "Henning Ulfarsson"
  ],
  "comment": "27 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "Given a permutation pattern p and an equivalence relation on permutations, we study the corresponding equivalence classes all of whose members avoid p. Four relations are studied: Conjugacy, order isomorphism, Knuth-equivalence and toric equivalence. Each of these produces a known class of permutations or a known counting sequence. For example, involutions correspond to conjugacy, and permutations whose insertion tableau is hook-shaped with 2 in the first row correspond to Knuth-equivalence. These permutations are equinumerous with certain congruence classes of graph endomorphisms. In the case of toric equivalence we find a class of permutations that are counted by the Euler totient function, with a subclass counted by the number-of-divisors function. We also provide a new symmetry for bivincular patterns that produces some new non-trivial Wilf-equivalences",
  "revisions": [
    {
      "version": "v1",
      "updated": "2010-05-29T00:20:15.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05A15",
      "05A19"
    ],
    "keywords": [
      "equivalence classes",
      "permutations avoiding",
      "toric equivalence",
      "euler totient function",
      "first row correspond"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 27,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2010arXiv1005.5419U"
    }
  }
}