On the length of the longest subsequence avoiding an arbitrary pattern in a random permutation

Details On the length of the longest subsequence avoiding an arbitrary pattern in a random permutation On the length of the longest subsequence avoiding an arbitrary pattern in a random permutation

2005-05-23

arxiv.org/abs/math/0505485v2

Mathematics

Combinatorics

14 pages (Reference list corrected)

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

On the length of the longest subsequence avoiding an arbitrary pattern in a random permutation does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the length of the longest subsequence avoiding an arbitrary pattern in a random permutation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the length of the longest subsequence avoiding an arbitrary pattern in a random permutation will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-72788