{
  "id": "math/0505485",
  "version": "v2",
  "published": "2005-05-23T21:05:16.000Z",
  "updated": "2005-05-31T21:33:21.000Z",
  "title": "On the length of the longest subsequence avoiding an arbitrary pattern in a random permutation",
  "authors": [
    "Michael H. Albert"
  ],
  "comment": "14 pages (Reference list corrected)",
  "categories": [
    "math.CO"
  ],
  "abstract": "We consider the distribution of the length of the longest subsequence avoiding a given pattern in a random permutation of length n. The well-studied case of a longest increasing subsequence corresponds to avoiding the pattern 21. We show that there is some constant c such that the mean value of this length is asymptotic to twice the square root of c times n and that the distribution of the length is tightly concentrated around its mean. We observe some apparent connections between c and the Stanley-Wilf limit of the class of permutations avoiding the given pattern.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2005-05-31T21:33:21.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05A16",
      "05A05"
    ],
    "keywords": [
      "longest subsequence avoiding",
      "random permutation",
      "arbitrary pattern",
      "longest increasing subsequence corresponds",
      "stanley-wilf limit"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 14,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2005math......5485A"
    }
  }
}