Superpermutationen

Ich stand letztens in der Dusche (#showerthoughts) und dachte über zwei Videos nach, die kurz zuvor gesehen habe. Das eine ist dies:
Superpermutations - Numberphile
Und das andere dieses:
Superpermutations: the maths problem solved by 4chan

Als Komponist ist ja man immer öfter damit beschäftigt, wie man sinnfreie Wiederholung vermeidet ohne aber nur neue, zusammenhanglose Ideen aneinanderzuhäufen. Wie bei Beethoven: das Motiv kommt einmal, ein zweites Mal (bisschen anders vielleicht) aber beim dritten Mal muss es ausbrechen und sich entwickeln (#motivischthematischeArbeit). Einfachstes Beispiel: seine 5. Sinfonie. Da-da-da-daaa (eins), du-du-du-duuu (zwei), da-da-da-dah-du-du-du-duh-da-da-da-daaaaaa (drei: weiterentwickelt).

Jetzt zurück zur Mathematik. Permutation beschreibt die…

Umstellung in der Reihenfolge bei einer Zusammenstellung einer bestimmten Anzahl geordneter Größen
(siehe Duden)

Superpermutation hingegen ist die kürzestmögliche Zeichenkette, die alle Ordnungsmöglichkeiten beinhaltet. Für 2 Elemente (1, 2) also entweder 121 (12, 21) oder 212 (21, 12).

Wenn ich das zweite Video richtig verstanden habe, kommt man mit einem Algorithmus (den man auch im Video sieht) auf eine Lösung für mehr Elemente. Das dumme ist nur: das ist scheinbar nicht die einzige Lösung und ebenso leider auch nicht die kürzeste! Ist das nicht spannend? Wir wissen nach tausenden von Jahren immer noch nicht genau, nach welchem Gesetz sich so etwas einfaches wie "möglichst vermischte Elemente in kürzester Schreibweise" verhält.

Nichtsdestotrotz habe ich mich mal herangewagt und eine visuelle Lösung versucht. Vielleicht kommt ja ein klügerer als ich auf die weiterführende Idee, oder so.

Was mir auf den ersten Blick aufgefallen ist:

  • die größte Kombination an inkorrekten Permutationen ist immer genau in der Mitte
  • die Abstände zur nächsten inkorrekten Permutation ist immer so groß wie die Elementanzahl
  • überhaupt sind die Abstände und Kombinationen symmetrisch zur Mitte (siehe n=5: 1,1,1,2… und am Ende …2,1,1,1)

Aber gibt es vielleicht noch mehr Regelmäßigkeiten, die bei der Suche für größere Superpermutationen helfen können?