We say that a permutation sigma is an element of S-n contains a permutation pi is an element of S-k as a pattern if some subsequence of sigma has the same order relations among its entries as pi. 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 2(n) - O(n(2)2(n-root 2n)) <= pat(n) <= 2(n) - Theta(n2(n-root 2n)) 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 L-k, the length of the shortest k-superpattern, is at most k(k+1)/2. This may lend evidence to a conjecture of Eriksson et al. that L-k similar to K-2/2. (C) 2008 Elsevier Inc. All rights reserved.
展开▼
