Superpermutation
# Superpermutation

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

Es wurde gezeigt, dass für 1≤ $n\leq 5$ die kleinste Superpermutation die Länge $1!+2!+\dots +n!$, also $∑_{i=1}^ni!\sum$ _{i=1}^{n}i!, hat. So gibt es beispielsweise 6 Permutationen für die drei Elemente $\{1,2,3\}$, nämlich $123$, $132$, $213$, $231$, $312$ und $321$; und eine kleinste Superpermutation, welche alle diese Permutationen beinhaltet, hat eine Länge von 9 Zeichen: $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 $n=6$ wurde 2014 eine kürzere Superpermutation als $∑_{i=1}^ni!\sum$ _{i=1}^{n}i! gefunden. Anstelle einer Länge von 873 Zeichen wurden für $n=6$ nur 872 Zeichen benötigt. Es wird daher erwartet, dass für $n\geq 6$ gilt, dass maximal eine Länge von $(1!+2!+\dots +n!)-1$ für die kürzeste Superpermutation benötigt wird: “The minimal length is still unknown for $n\geq 6$, but we can show that for all $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 $n\geq 2$ eine Länge von mindestens $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.

