Abstract: | We consider the distribution of the length of the longest subsequence avoiding an arbitrary pattern, π, in a random permutation of length n. The well‐studied case of a longest increasing subsequence corresponds to π = 21. We show that there is some constant cπ such that as n →∞ the mean value of this length is asymptotic to 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 pattern π. © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2007 |