Superpermutation
![](http://upload.wikimedia.org/wikipedia/commons/thumb/1/19/Superpermutation_distribution.png/220px-Superpermutation_distribution.png)
Eine Superpermutation von Zeichen ist in der Kombinatorik eine Zeichenkette, die jede mögliche Permutation, also Kombination, dieser Zeichen als Zeichenkette beinhaltet.
Es wurde gezeigt, dass für 1≤ die kleinste Superpermutation die Länge , also , hat. So gibt es beispielsweise 6 Permutationen für die drei Elemente , nämlich , , , , und ; und eine kleinste Superpermutation, welche alle diese Permutationen beinhaltet, hat eine Länge von 9 Zeichen: .
Die ersten fünf Superpermutationen haben die Längen 1, 3, 9, 33 und 153. Die Zeichenketten dieser Permutationen sehen beispielsweise so aus:
- 1
- 121
- 123121321
- 123
4123142312 4312134213 2413214321 - 123
4512341523 4125341235 4123145231 4253142351 4231542312 4531243512 4315243125 4312134521 3425134215 3421354213 2451324153 2413524132 5413214532 1435214325 1432154321.
Für eine Zeichenmenge von wurde 2014 eine kürzere Superpermutation als gefunden. Anstelle einer Länge von 873 Zeichen wurden für nur 872 Zeichen benötigt. Es wird daher erwartet, dass für gilt, dass maximal eine Länge von für die kürzeste Superpermutation benötigt wird: “The minimal length is still unknown for , but we can show that for all it is strictly less than the conjectured length […]”.[1]
Auf dem Imageboard 4chan wurde am 27. September 2011 von einem anonymen Nutzer nachgewiesen, dass die kürzeste Superpermutation für eine Länge von mindestens hat.[2] Robin Houston, Jay Pantone und Vince Vatter haben am 25. Oktober 2018 einen vollständigen Beweis dessen in der Datenbank OEIS veröffentlicht.[3]
Literatur
[Bearbeiten | Quelltext bearbeiten]- Daniel A. Ashlock, Jenett Tillotson: Construction of small superpermutations and minimal injective superstrings. In: Congressus Numerantium. 1993, S. 91–98, Zbl 0801.05004.
- Nathaniel Johnston: Non-uniqueness of minimal superpermutations. In: Discrete Mathematics. Band 313, Nr. 14, 28. Juli 2013, S. 1553–1557, doi:10.1016/j.disc.2013.03.024, arxiv:1303.4150 (Zbl 1368.05004).
- Robin Houston: Tackling the Minimal Superpermutation Problem. 21. August 2014, arxiv:1408.5108.
Weblinks
[Bearbeiten | Quelltext bearbeiten]- The Minimal Superpermutation Problem – Nathaniel Johnston’s blog
- James Grime: Superpermutations – Numberphile. (video) Brady Haran, abgerufen am 1. Februar 2018 (englisch).
Einzelnachweise
[Bearbeiten | Quelltext bearbeiten]- ↑ Robin Houston: Tackling the Minimal Superpermutation Problem. (PDF; englisch).
- ↑ /sci/ - Science & Math. Abgerufen am 2. Januar 2019.
- ↑ Anonymous 4chan Poster, Robin Houston, Jay Pantone, Vince Vatter: A lower bound on the length of the shortest superpattern. (PDF; 91,5 kB) In: OEIS. 25. Oktober 2018, S. 3, archiviert vom (nicht mehr online verfügbar) am 2. Januar 2018; abgerufen am 2. Januar 2019 (englisch).