{
  "id": "0806.0666",
  "version": "v4",
  "published": "2008-06-04T00:27:40.000Z",
  "updated": "2009-11-26T14:08:14.000Z",
  "title": "(2+2)-free posets, ascent sequences and pattern avoiding permutations",
  "authors": [
    "Mireille Bousquet-Mélou",
    "Anders Claesson",
    "Mark Dukes",
    "Sergey Kitaev"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "We present bijections between four classes of combinatorial objects. Two of them, the class of unlabeled (2+2)-free posets and a certain class of involutions (or chord diagrams), already appeared in the literature, but were apparently not known to be equinumerous. We present a direct bijection between them. The third class is a family of permutations defined in terms of a new type of pattern. An attractive property of these patterns is that, like classical patterns, they are closed under the action of $D_8$, the symmetry group of the square. The fourth class is formed by certain integer sequences, called ascent sequences, which have a simple recursive structure and are shown to encode (2+2)-free posets and permutations. Our bijections preserve numerous statistics. We determine the generating function of these classes of objects, thus recovering a non-D-finite series obtained by Zagier for the class of chord diagrams. Finally, we characterize the ascent sequences that correspond to permutations avoiding the barred pattern $3{\\bar 1}52{\\bar 4}$ and use this to enumerate those permutations, thereby settling a conjecture of Pudwell.",
  "revisions": [
    {
      "version": "v4",
      "updated": "2009-11-26T14:08:14.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "ascent sequences",
      "pattern avoiding permutations",
      "chord diagrams",
      "bijections preserve numerous statistics",
      "symmetry group"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2008arXiv0806.0666B"
    }
  }
}