Superpermutation
Eine Superpermutation von <math>n</math> Zeichen ist in der Kombinatorik eine Zeichenkette, die jede mögliche Permutation, also Kombination, dieser <math>n</math> Zeichen als Zeichenkette beinhaltet.
Es wurde gezeigt, dass für <math>1 \le n \le 5</math> die kleinste Superpermutation die Länge <math>\textstyle \,1! + 2! + \dots + n! \,=\, \sum_{k=1}^n k!\,</math> hat.
So gibt es für die drei Elemente <math>\{1, 2, 3\}</math> mit <math>123</math>, <math>132</math>, <math>213</math>, <math>231</math>, <math>312</math> und <math>321</math> insgesamt 6 Permutationen. Die kleinste Superpermutation, die all diese Permutationen beinhaltet, ist mit <math>321323123</math> genau 9 Zeichen lang.
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 <math>n=6</math> wurde 2014 eine kürzere Superpermutation als <math>\textstyle\sum_{k=1}^n k!</math> gefunden:
- Anstelle einer Länge von 873 Zeichen wurden für <math>n = 6</math> nur 872 Zeichen benötigt.
Es wird daher erwartet, dass für <math>n\ge6</math> gilt, dass maximal eine Länge von <math>2! + 3! + \dots + n!</math> für die kürzeste Superpermutation benötigt wird: “{{Modul:Vorlage:lang}} Modul:Multilingual:153: attempt to index field 'data' (a nil value)”.<ref>Vorlage:Cite book/NameVorlage:Cite book/Name: [Internetquelle: archiv-url ungültig Tackling the Minimal Superpermutation Problem.] (PDF) , archiviert vom Vorlage:IconExternal (nicht mehr online verfügbar) am Vorlage:Cite book/URL (Lua-Fehler in Modul:Multilingual, Zeile 153: attempt to index field 'data' (a nil value)).Vorlage:Cite book/URLVorlage:Cite book/MeldungVorlage:Cite book/Meldung2Vorlage:Cite book/MeldungVorlage:Cite book/MeldungVorlage:Cite book/MeldungVorlage:Cite book/MeldungVorlage:Cite book/Meldung</ref>
Auf dem Imageboard 4chan wurde am 27. September 2011 von einem anonymen Nutzer nachgewiesen, dass die kürzeste Superpermutation für <math>n\ge2</math> eine Länge von mindestens <math>n! + (n - 1)! + (n - 2)! + n - 3</math> hat.<ref>/sci/ - Science & Math. Abgerufen am 2. Januar 2019.</ref> Robin Houston, Jay Pantone und Vince Vatter haben am 25. Oktober 2018 einen vollständigen Beweis dessen in der Datenbank OEIS veröffentlicht.<ref>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 Vorlage:IconExternal (nicht mehr online verfügbar) am 2. Januar 2018; abgerufen am 2. Januar 2019 (Lua-Fehler in Modul:Multilingual, Zeile 153: attempt to index field 'data' (a nil value)).</ref>
Die Ausgangsfrage behandelte die Anime-Fernsehserie Die Melancholie der Haruhi Suzumiya, deren 14 Episoden eine non-lineare Geschichte erzählen, die in verschiedenen Reihenfolgen Sinn ergeben kann. Ein User wollte wissen, in welcher Reihenfolge man denn nun die Serie schauen müsse, um in kürzester Zeit alle möglichen Reihenfolgen gesehen zu haben.<ref>Konrad Krug: Von Animes und Supermutationen. In: Deutsche Mathematiker-Vereinigung. 15. Januar 2019, abgerufen am 3. Februar 2026.</ref>
Literatur[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]
- The Minimal Superpermutation Problem – Nathaniel Johnston’s blog
- Vorlage:Cite book/NameVorlage:Cite book/Name: [Internetquelle: archiv-url ungültig Superpermutations – Numberphile.] (video) Brady Haran, , archiviert vom Vorlage:IconExternal (nicht mehr online verfügbar) am Vorlage:Cite book/URL; abgerufen am 1. Februar 2018 (Lua-Fehler in Modul:Multilingual, Zeile 153: attempt to index field 'data' (a nil value)).Vorlage:Cite book/URLVorlage:Cite book/MeldungVorlage:Cite book/Meldung2Vorlage:Cite book/MeldungVorlage:Cite book/MeldungVorlage:Cite book/MeldungVorlage:Cite book/MeldungVorlage:Cite book/Meldung
Einzelnachweise[Bearbeiten]
<references />