Anzahl wesentlich verschiedener Paarungen von n Elementen in n-1 Runden

09/05/2014 - 10:50 von Ralf Goertz | Report spam
Hi,

nachdem gerade Dodekaeder abgezàhlt wurden, passt meine Frage vielleicht
ganz gut. Ich muss ein bisschen ausholen:

Ich hatte mir die Frage gestellt, ob es möglich ist, dass n Elemente in
n-1 Runden in Paare aufgeteilt werden können, so dass sich keine Paarung
wiederholt. Relativ schnell machte ich mir klar, dass es leicht geht,
wenn n einer Potenz von 2 ist. Halbieren, alle aus der einen Gruppen
nacheinander mit allen aus der anderen Gruppe paaren, dann die
Subgruppen wieder teilen etc. Dann versuchte ich zu zeigen, dass es
immer geht (bei ungeradem n füge man ein Dummy-Element ein). Mir fiel
erstmal nichts Konstruktives ein, bis mir jemand sagte, dass es mit 18
zumindest geht, weil es schließlich in der Fußball-Bundesliga so gemacht
würde. Damit war natürlich das Stichwort Rundentournier mehr oder
weniger gefallen und mit dem Rutschsystem auch ein konstruktiver Beweis
gefunden.

Mich interessiert nun aber, wie viele wesentlich verschiedene solcher
Paarungen es bei n Elemente gibt. Wesentlich verschieden soll dabei
heißen, dass zwei Lösungen dann *nicht* als wesentlich verschieden
gelten, wenn es eine Permutation der Elemente gibt, so dass die n-1
Runden der ersten Lösung eine Permutation der Runden der zweiten Lösung
ist. Beispiel n=4:

erste Lösung

erste Runde (1,3) (2,4)
zweite Runde (1,4) (2,3)
dritte Runde (1,2) (3,4)

zweite Lösung

erste Runde (1,3) (2,4)
zweite Runde (1,2) (3,4)
dritte Runde (1,4) (2,3)

Wenn man die Elemente identisch permutiert, dann sind in der zweiten
Lösung Runden 2 und 3 vertauscht. Oder man vertauscht die Elemente 2 und
4 und hat dann die identische Permutation der Runden. In jedem Fall ist
Lösung 2 nicht wesentlich verschieden von Lösung 1. Ich schàtze mal,
dass es für n=4 nur eine Lösung gibt, aber wie sieht es bei größeren n
aus?

Ralf
 

Lesen sie die antworten

#1 Ralf Goertz
11/05/2014 - 15:42 | Warnen spam
Ralf Goertz wrote:

Ich schàtze mal, dass es für n=4 nur eine Lösung gibt, aber wie sieht
es bei größeren n aus?



Ich glaube fast, es gibt für jedes n nur eine Lösung. Ordnet man die
Runden so, dass das erste Element nacheinander mit 2,3,…,n gepaart wird,
so kann man jede beliebige Lösung eindeutig auf diese Permutation der
Runden abbilden. Findet man nun zwei Lösungen, die sich auf verschiedene
kleinste Elemente abbilden, kann man leicht überprüfen, ob diese beiden
Lösungen durch Permutation der Elemente ineinander übergehen. Beipiel
n=6

erste Lösung | zweite Lösung
(1,2) (3,4) (5,6) (3,4) (5,6)
(1,3) (2,5) (4,6) (2,6) (4,5)
(1,4) (2,6) (3,5) (2,5) (3,6)
(1,5) (2,4) (3,6) (2,3) (4,6)
(1,6) (2,3) (4,5) (2,4) (3,5)

Beide Lösungen sind àquivalent sind, da man von der ersten zur zweiten
Lösung kommt, indem man 5 und 6 vertauscht. Da es n! Permutationen der
Elemente und (n-1)! Permutationen der Runden gibt, vermute ich, dass
jeweils n Permutationen der Elemente zu derselben Permutation der Runden
führen. Da wir insgesamt n*(n-1)/2 verschiedene Paare haben, die wie
oben angedeutet, angeordnet werden müssen und davon aber n-1 bereits
festliegen (die mit der 1), gibt es ((n-2)*(n-1)/2)! verschiedene
Anordnungsmöglichkeiten der übrigen Paare. Könnte man, was ich vermute,
auch die erste Zeile festmachen, blieben noch (((n-2)^2)/2)!. Da die
Reihenfolge innerhalb der Zeilen keine Rolle spielt, reduziert sich
diese Zahl weiter auf (((n-2)^2)/2)!/((n/2-1)*(n-2)!). Davon sind aber
natürlich bei weitem nicht alle erlaubt, sondern nur die, wo jede der
Zahlen 1…n in jeder der n Zeilen genau einmal vorkommt. Wie ich die
identifizieren soll, das heißt, wieviele das sind, weiß ich allerdings
nicht.

Hat jemand eine Idee?

Ähnliche fragen