Asymptotic enumeration of permutations avoiding generalized patterns

Details Asymptotic enumeration of permutations avoiding generalized patterns Asymptotic enumeration of permutations avoiding generalized patterns

2005-05-12

arxiv.org/abs/math/0505254v1

Mathematics

Combinatorics

14 pages, 3 figures, to be published in Adv. in Appl. Math

Scientific paper

Motivated by the recent proof of the Stanley-Wilf conjecture, we study the asymptotic behavior of the number of permutations avoiding a generalized pattern. Generalized patterns allow the requirement that some pairs of letters must be adjacent in an occurrence of the pattern in the permutation, and consecutive patterns are a particular case of them. We determine the asymptotic behavior of the number of permutations avoiding a consecutive pattern, showing that they are an exponentially small proportion of the total number of permutations. For some other generalized patterns we give partial results, showing that the number of permutations avoiding them grows faster than for classical patterns but more slowly than for consecutive patterns.

Affiliated with

Also associated with

No associations

Rating

Asymptotic enumeration of permutations avoiding generalized patterns 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 Asymptotic enumeration of permutations avoiding generalized patterns, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Asymptotic enumeration of permutations avoiding generalized patterns will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-163220