Superpattern

Superpattern

A k-superpattern is a smallest combinatorial pattern that contains all k-subpatterns.

Definitions

A combinatorial pattern is a permutation of numbers from 1 to n, where n is some natural number. n is the length of the combinatorial pattern.A k-subpattern is a subset 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 increasing sequence 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

k2/e2/4.
The only lower bound proven for length(k-superpattern) is k2/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)< 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.

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.

Look at other dictionaries:

  • Permutation — For other uses, see Permutation (disambiguation). The 6 permutations of 3 balls In mathematics, the notion of permutation is used with several slightly different meanings, all related to the act of permuting (rearranging) objects or values.… …   Wikipedia

  • Combinatorial enumeration — is a subfield of enumeration that deals with the counting of objects whose symmetries do not exist or, if they exist, are combinatorial in nature. See also * combinatorics * superpattern …   Wikipedia

  • List of mathematics articles (S) — NOTOC S S duality S matrix S plane S transform S unit S.O.S. Mathematics SA subgroup Saccheri quadrilateral Sacks spiral Sacred geometry Saddle node bifurcation Saddle point Saddle surface Sadleirian Professor of Pure Mathematics Safe prime Safe… …   Wikipedia

  • List of permutation topics — This is a list of topics on mathematical permutations.*Alternating group *Alternating permutation *Bijection *Circular shift *Combination *Cycle index *Cycle notation *Cyclic order *Cyclic permutation *Derangement *Even and odd permutations… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”