Asymptotic bounds for permutations containing many different patterns

We say that a permutation σ∈Sn contains a permutation π∈Sk as a pattern if some subsequence of σ has the same order relations among its entries as π. We improve on results of Wilf, Coleman, and Eriksson et al. that bound the asymptotic behavior of pat(n), the maximum number of distinct patterns of any length contained in a single permutation of length n. We prove that by estimating the amount of redundancy due to patterns that are contained multiple times in a given permutation. We also consider the question of k-superpatterns, which are permutations that contain all patterns of a given length k. We give a simple construction that shows that Lk, the length of the shortest k-superpattern, is at most . This may lend evidence to a conjecture of Eriksson et al. that .