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 1≤ ${\displaystyle n\leq 5}$ die kleinste Superpermutation die Länge ${\displaystyle 1!+2!+\dots +n!}$, also $\sum _{i=1}^{n}i!$, hat. So gibt es beispielsweise 6 Permutationen für die drei Elemente ${\displaystyle \{1,2,3\}}$, nämlich ${\displaystyle 123}$, ${\displaystyle 132}$, ${\displaystyle 213}$, ${\displaystyle 231}$, ${\displaystyle 312}$ und ${\displaystyle 321}$; und eine kleinste Superpermutation, welche alle diese Permutationen beinhaltet, hat eine Länge von 9 Zeichen: ${\displaystyle 321323123}$.

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 $\sum _{i=1}^{n}i!$ 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 (1!+2!+\dots +n!)-1}$ 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 […]”.^[1]

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.^[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]

• 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. 

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

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).