{
  "id": "math/0002200",
  "version": "v1",
  "published": "2000-02-24T10:45:57.000Z",
  "updated": "2000-02-24T10:45:57.000Z",
  "title": "Permutations with restricted patterns and Dyck paths",
  "authors": [
    "Christian Krattenthaler"
  ],
  "comment": "17 pages, AmS-TeX",
  "journal": "Adv. Appl. Math. 27 (2001), 510-530",
  "categories": [
    "math.CO"
  ],
  "abstract": "We exhibit a bijection between 132-avoiding permutations and Dyck paths. Using this bijection, it is shown that all the recently discovered results on generating functions for 132-avoiding permutations with a given number of occurrences of the pattern $12... k$ follow directly from old results on the enumeration of Motzkin paths, among which is a continued fraction result due to Flajolet. As a bonus, we use these observations to derive further results and a precise asymptotic estimate for the number of 132-avoiding permutations of $\\{1,2,...,n\\}$ with exactly $r$ occurrences of the pattern $12... k$. Second, we exhibit a bijection between 123-avoiding permutations and Dyck paths. When combined with a result of Roblet and Viennot, this bijection allows us to express the generating function for 123-avoiding permutations with a given number of occurrences of the pattern $(k-1)(k-2)... 1k$ in form of a continued fraction and to derive further results for these permutations.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2000-02-24T10:45:57.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05A05",
      "05A15",
      "05A16"
    ],
    "keywords": [
      "dyck paths",
      "permutations",
      "restricted patterns",
      "precise asymptotic estimate",
      "generating function"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "AMS-TeX",
      "pages": 17,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2000math......2200K"
    }
  }
}