Superpermutation

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 […]”. 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. Robin Houston, Jay Pantone und Vince Vatter haben am 25. Oktober 2018 einen vollständigen Beweis dessen in der Datenbank OEIS veröffentlicht.