- Superpattern
A k-

**superpattern**is a smallestcombinatorial pattern that contains all k-subpatterns.**Definitions**A combinatorial pattern is a

permutation of numbers from 1 to n, where n is somenatural number . n is the length of the combinatorial pattern.A k-subpattern is asubset of size k of the original pattern with the order preserved but the pattern renumbered with respect to the sizes of its members.**Examples**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 principle we need a minimium of : 3 + 3 - 1 = 5 numbers (since only one number can be in both the largest increasingsequence and 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.**Theorems**k

^{2}/e2/4.

The only lower bound proven for length(k-superpattern) is k^{2}/e , which is proven by assuming that $\{\; n\; choose\; k\; \}\; ge\; k!$ and applying Stirling's approximation to the binomial coefficient.

An upper bound on the length of a superpattern is length(k-superpattern)< 3k^{2}/4, which is proven by showing the probability of finding a length(k-superpattern) in a 3k^{2}/4-pattern is greater than 0.

It is believed that the length of k-superpatterns is approaching k^{2}/2.**References***cite book

last = Bóna

first = Miklós

title = A walk through combinatorics: an introduction to enumeration and graph theory

publisher = London: World Scientific

date = 2002

pages =

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.*