A k-superpattern is a smallest
combinatorialpattern that contains all k-subpatterns.
A combinatorial pattern is a
permutationof numbers from 1 to n, where n is some natural number. n is the length of the combinatorial pattern.A k-subpattern is a subsetof size k of the original pattern with the order preserved but the pattern renumbered with respect to the sizes of its members.
Consider the combinatorial pattern 25314, which has length 5.
Now, consider some 3-subpatterns, which we take from 25314: 253, 251, 254, 234, 531, 534, 314 (we take 3 digits at a time, keeping the order preserved). We then renumber the selected subpatterns using the digits from 1 to 3 (since this is a 3-subpattern). In each subpattern, the smallest digit is replaced with a 1, the next larger one with a 2, and the largest with a 3. Thus, 253 gets renumbered to 132, 251 to 231, and so on. We end up with 132, 231, 123, 321, 312, 213. We could have picked 514, for example, for our original list of 3-subpatterns, but that would have just got renumbered to 312, which is a repetition of one of the subpatterns already picked. In fact, in our original list, we have selected all the possible 3-subpatterns, i.e. all 6 (3!) permutations of length 3.
From this, we can see that 25314 contains all possible 3-subpatterns. But, for it to be a 3-superpattern, it must be the smallest such combinatorial pattern.
Then, consider also that in order to have 123 and 321 in the same permutation, by the
inclusion-exclusion principlewe need a minimium of : 3 + 3 - 1 = 5 numbers (since only one number can be in both the largest increasing sequenceand the largest decreasing sequence). This implies that any larger pattern which contains both 123 and 321 as substrings must be at least 5 digits long. 25314 is such a pattern and is therefore a 3-superpattern of length 5.
2/4.The only lower bound proven for length(k-superpattern) is k2/e , which is proven by assuming that and applying Stirling's approximation to the binomial coefficient. An upper bound on the length of a superpattern is length(k-superpattern)< 3k2/4, which is proven by showing the probability of finding a length(k-superpattern) in a 3k2/4-pattern is greater than 0. It is believed that the length of k-superpatterns is approaching k2/2.
last = Bóna
first = Miklós
title = A walk through combinatorics: an introduction to enumeration and graph theory
publisher = London: World Scientific
date = 2002
isbn = 9810249012
* [http://www.combinatorics.org/Volume_9/PDF/v9i2r20.pdf Packing patterns into words]
* [http://nerant.com/Community.aspx Solution to Superpattern solution ]
Wikimedia Foundation. 2010.