Superpermutation

Eine Superpermutation von ${\displaystyle n}$ Zeichen ist in der Kombinatorik eine Zeichenkette, die jede mögliche Permutation, also Kombination, dieser ${\displaystyle n}$ Zeichen als Zeichenkette beinhaltet.

Es wurde gezeigt, dass für ${\displaystyle 1\leq n\leq 5}$ die kleinste Superpermutation die Länge ${\displaystyle \textstyle \,1!+2!+\dots +n!\,=\,\sum _{k=1}^{n}k!\,}$ hat.

So gibt es für die drei Elemente ${\displaystyle \{1,2,3\}}$ mit ${\displaystyle 123}$, ${\displaystyle 132}$, ${\displaystyle 213}$, ${\displaystyle 231}$, ${\displaystyle 312}$ und ${\displaystyle 321}$ insgesamt 6 Permutationen. Die kleinste Superpermutation, die all diese Permutationen beinhaltet, ist mit ${\displaystyle 321323123}$ 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
• 123412314231243121342132413214321
• 123451234152341253412354123145231425314235142315423124531243512431524312543121345213425134215342135421324513241532413524132541321453214352143251432154321.

Für eine Zeichenmenge von ${\displaystyle n=6}$ wurde 2014 eine kürzere Superpermutation als ${\displaystyle \textstyle \sum _{k=1}^{n}k!}$ gefunden:

Anstelle einer Länge von 873 Zeichen wurden für ${\displaystyle n=6}$ nur 872 Zeichen benötigt.

Es wird daher erwartet, dass für ${\displaystyle n\geq 6}$ gilt, dass maximal eine Länge von ${\displaystyle 2!+3!+\dots +n!}$ für die kürzeste Superpermutation benötigt wird: “The minimal length is still unknown for ${\displaystyle n\geq 6}$, but we can show that for all ${\displaystyle n\geq 6}$ it is strictly less than the conjectured length […]”.

Auf dem Imageboard 4chan wurde am 27. September 2011 von einem anonymen Nutzer nachgewiesen, dass die kürzeste Superpermutation für ${\displaystyle n\geq 2}$ eine Länge von mindestens ${\displaystyle n!+(n-1)!+(n-2)!+n-3}$ hat. Robin Houston, Jay Pantone und Vince Vatter haben am 25. Oktober 2018 einen vollständigen Beweis dessen in der Datenbank OEIS veröffentlicht.

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.

Literatur

• 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

• The Minimal Superpermutation Problem – Nathaniel Johnston’s blog
• James Grime: Superpermutations – Numberphile. (video) Brady Haran, abgerufen am 1. Februar 2018 (englisch). 

Einzelnachweise

1. ↑ Robin Houston: Tackling the Minimal Superpermutation Problem. (PDF; Abgerufen im 1. Januar 1englisch). 
2. ↑ /sci/ - Science & Math. Abgerufen am 2. Januar 2019. 
3. ↑ 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 Original (nicht mehr online verfügbar) am 2. Januar 2018; abgerufen am 2. Januar 2019 (englisch). 
4. ↑ Konrad Krug: Von Animes und Supermutationen. In: Deutsche Mathematiker-Vereinigung. 15. Januar 2019, abgerufen am 3. Februar 2026.