Superpattern
From Wikipedia, the free encyclopedia
A k-superpattern is a smallest combinatorial pattern that contains all k-subpatterns.
Contents |
[edit] 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.
[edit] Examples
Lets look at the combinatorial pattern 25314. This has length 5. Now lets look at the 3-subpatterns. Here are some 3-subpatterns: We take 253, 251, 245, 531, 534, 314 and renumber them to get 132, 231, 123, 321, 312, 213 (these are the 3-subpatterns listed respectively to the ones I picked). There are more: we could have also picked 514 for example, but that is just renumbered to 312 and is a repetition of one of the subpatterns I already picked. In fact, we found all the 3-subpatterns i.e. all 6 (3!) permutations of length 3. So 25314 contains all 3-subpatterns, now is it the smallest pattern with this property. 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 the only one number can be in both the largest increasing sequence and the largest decreasing sequence). Hence, 25314 is a 3-superpattern of length 5.
[edit] Theorems
An upper bound on the length of a superpattern is length(k-superpattern)< 2k2/3 shown by Michael Skobel.
A closed formula for the length of superpatterns is not presently known.
[edit] References
- Bóna, Miklós (2002). A walk through combinatorics: an introduction to enumeration and graph theory. London: World Scientific. ISBN 9810249012.
