Fixpunktfreie Permutationen

In der Mathematik sind Permutationen Vertauschungen irgendwelcher Objekte. Dies kommen im Leben an allen Ecken und Enden vor, hier im MINT-Wiki zum Beispiel bei der Diskussion der Zauberwürfelmuster. Durch Vertauschungen von Würfelchen entstehen am Zauberwürfel schöne Muster. Manche Muster sind möglich, manche nicht. Wollen wir dem auf den Grund gehen, sind wir schon mitten drin in der Mathematik der Vertauschungen, der sog. Gruppentheorie.

Bei den Zauberwürfelmustern müssen wir sogar über sog. fixpunktfreie Permutationen nachdenken, denn wir wollen ja, dass sich auch wirklich alle Farben bewegen.

Beispiel einer Farbpermutation mit Fixpunkt

Es gibt nur zwei fixpunktfreie Vertauschungen von 3 Farben

Wir brauchen (fixpunktfreie) Permutationen von 6 Farben

...

welche gibt es denn da noch???

Schneller aufgeschrieben sind die Permutationen, wenn wir nur einfach Zahlen vertauschen: Aus 123456 wird durch vertauschen z.B. 426513. Die 2 wurde da nicht vertauscht, sie ist also ein Fixpunkt.

Unsere Farbkombinationen oben sind auch nur Vertauschungen von Zahlen, wenn wir die Farben einfach durchnummerieren (z.B. 1=weiß, 2=gelb, 3=grün, 4=blau, 5=rot, 6=orange). Aus der ursprünglichen Mittelpunktsreihenfolge 123456 wird dann bei der Farbpermutation ...

... die Reihe der Ringfarben 346521 (zum weißen Mittelpunkt kommt der grüne Ring, zum gelben Mittelpunkt der blaue, ...).

... wird 132 (weiß=1 ist ein Fixpunkt).

... wird 312 (weiß=1 ist ein Fixpunkt).

... wird 231 (weiß=1 ist ein Fixpunkt).

Welche Farbkombis (fixpunktfreie Permutationen) gibt es nun für 6 Farben?

Ash aus der 9. Klasse hat im Netz die Info gefunden, dass es da 265 Farbvarianten gibt! Der WIKIPEDIA-Artikel hierzu ist leider nix für Schülerinnen. Der Autor will das Problem für alle Farben lösen. Entsprechend schwierig ist das zu verstehen. Wir brauchen das nur bis 6 Farben. Das geht auch mit Schulmathematik: ...

Permutationen und fixpunktfreie Permutationen bei 2 Farben

In Kurzschreibweise: 12 und 21

Ergibt 2 Permutationen, davon ist eine einzige fixpunktfrei - Bingo

Permutationen und fixpunktfreie Permutationen bei 3 Farben

123, davon 3 Fixpunkte
132, 1 ist Fixpunkt
213, 3 ist Fixpunkt
231 fixpunktfrei
312 fixpunktfrei
321 2 ist Fixpunkt

Ergibt 6 Permutationen, davon ist zwei fixpunktfrei - Bingo

Permutationen und fixpunktfreie Permutationen bei 6 Farben

Alle Permutationen der Zahlen 1 2 3 4:

• An erster Stelle ist die 1, ... dann kann an zweiter Stelle 2, 3 oder 4 sein
  • 1 2 3 4
  • 1 2 4 3
  • 1 3 2 4
  • 1 3 4 2
  • 1 4 2 3
  • 1 4 3 2
• An erster Stelle ist die 2, ... dann kann an zweiter Stelle 1, 3 oder 4 sein
  • 2 1 3 4
  • 2 1 4 3
  • 2 3 1 4
  • 2 3 4 1
  • 2 4 1 3
  • 2 4 3 1
• An erster Stelle ist die 3, ... dann kann an zweiter Stelle 1, 2 oder 4 sein
  • 3 1 2 4
  • 3 1 4 2
  • 3 2 1 4
  • 3 2 4 1
  • 3 4 1 2
  • 3 4 2 1
• An erster Stelle ist die 4, ... dann kann an zweiter Stelle 1, 2 oder 3 sein
  • 4 1 2 3
  • 4 1 3 2
  • 4 2 1 3
  • 4 2 3 1
  • 4 3 1 2
  • 4 3 2 1

... sind also insgesamt 24 Permutationen. Wir checken sie darauf, ob sie Fixpunkte enthalten:

• 1 2 3 4 , 1,2,3,4 sind Fixpunkte
• 1 2 4 3 , 1,2 sind Fixpunkte
• 1 3 2 4 , 1,4 sind Fixpunkte
• 1 3 4 2 , 1 ist ein Fixpunkt
• 1 4 2 3 , 1 ist ein Fixpunkt
• 1 4 3 2 , 1,3 sind Fixpunkte
• 2 1 3 4 , 3,4 sind Fixpunkte
• 2 1 4 3 fixpunktfrei
• 2 3 1 4 , 4 ist ein Fixpunkt
• 2 3 4 1 fixpunktfrei
• 2 4 1 3 fixpunktfrei
• 2 4 3 1 , 3 ist ein Fixpunkt
• 3 1 2 4 , 4 ist ein Fixpunkt
• 3 1 4 2 fixpunktfrei
• 3 2 1 4 , 2,4 sind Fixpunkte
• 3 2 4 1 , 2 ist ein Fixpunkt
• 3 4 1 2 fixpunktfrei
• 3 4 2 1 fixpunktfrei
• 4 1 2 3 fixpunktfrei
• 4 1 3 2 , 3 ist ein Fixpunkt
• 4 2 1 3 , 2 ist ein Fixpunkt
• 4 2 3 1 , 2,3 sind Fixpunkte
• 4 3 1 2 fixpunktfrei
• 4 3 2 1 fixpunktfrei

... also sind 9 von 24 Permutationen fixpunktfrei:

Mit anderen Worten ...

• zieht man eine Permutation per Los, dann sind 9 von 24 = 9/24 = 0,375 = 37,5% fixpunktfrei
• Pierre Montmort gewann 62,5% aller Spiele, nur 37,5% verlor er
• mit ungefähr 1/3 Wahrscheinlichkeit tanzt mindestens ein Paar unter vier Paaren zusammen, wenn ihre Paarungen gelost werden
• sitzt in 62,5% aller Fälle mindestens eine von 4 Schülerinnen in der zweiten Prüfung am selben Platz

-)

Was passiert, wenn die zahlen immer mehr werden?

• direkt zu cube.codes