{
  "id": "1211.3442",
  "version": "v1",
  "published": "2012-11-14T22:00:33.000Z",
  "updated": "2012-11-14T22:00:33.000Z",
  "title": "Pattern avoidance in matchings and partitions",
  "authors": [
    "Jonathan Bloom",
    "Sergi Elizalde"
  ],
  "comment": "34 pages, 12 Figures, 5 Tables",
  "categories": [
    "math.CO"
  ],
  "abstract": "Extending the notion of pattern avoidance in permutations, we study matchings and set partitions whose arc diagram representation avoids a given configuration of three arcs. These configurations, which generalize 3-crossings and 3-nestings, have an interpretation, in the case of matchings, in terms of patterns in full rook placements on Ferrers boards. We enumerate 312-avoiding matchings and partitions, obtaining algebraic generating functions, in contrast with the known D-finite generating functions for the 321-avoiding (i.e., 3-noncrossing) case. Our approach also provides a more direct proof of a formula of B\\'ona for the number of 1342-avoiding permutations. Additionally, we give a bijection proving the shape-Wilf-equivalence of the patterns 321 and 213 which greatly simplifies existing proofs by Backelin--West--Xin and Jel\\'{\\i}nek, and provides an extension of work of Gouyou-Beauchamps for matchings with fixed points. Finally, we classify pairs of patterns of length 3 according to shape-Wilf-equivalence, and enumerate matchings and partitions avoiding a pair in most of the resulting equivalence classes.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2012-11-14T22:00:33.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05A15",
      "05A05",
      "05A18",
      "05A19"
    ],
    "keywords": [
      "pattern avoidance",
      "arc diagram representation avoids",
      "full rook placements",
      "set partitions",
      "obtaining algebraic generating functions"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 34,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2012arXiv1211.3442B"
    }
  }
}