Hallo,
kennt jemand eine Formel fuer folgendes Problem:
Zunaechst einmal: man kann ja alle Permutationen einer Folge durch paarweise Vertauschungen von Nachbarn erzeugen.
Jetzt gibt es aber die Einschraenkung, dass einmal vertauschte Nachbarn zusammenbleiben muessen. Sie duerfen nur noch als Block weitervertauscht werden. Dann kann man nicht mehr alle Permutationen erzeugen, sondern nur einen Teil davon. Die Frage ist nun wie viele Permutationen kann man noch erzeugen?
Bsp:
ABCD -> A(CB)D -> CABD waere jetzt nicht mehr erlaubt, weil dadurch CB wieder getrennt wuerden
moeglich waeren ((CB)A)D und A(D(CB))
folgende 2 Permutationen kann man fuer n=4 nicht erzeugen:
CADB und BDAC
Ich kenne bereits folgende Werte (suche aber noch den funktionalen Zusammenhang):
n n! x
1 1 1
2 2 2
3 6 6
4 24 22
5 120 90
6 720 394
7 5040 1806
8 40320 8558
9 362880 41586
Ich kenne auch noch weitere Werte (bis n=16), falls das jemandem helfen sollte. Das Verhaeltnis x/n! geht recht schnell gegen 0.
Fuer eine Loesung oder Ideen zur Loesung waere ich sehr dankbar!
MfG,
Richard