Fixpunktfreie Permutationen

Aus MINT.lentner.net
Zur Navigation springen Zur Suche springen

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

Kombi3c.png

Es gibt nur zwei fixpunktfreie Vertauschungen von 3 Farben

Kombi3a.png
Kombi3b.png

Wir brauchen (fixpunktfreie) Permutationen von 6 Farben

Kombi1.png
...

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 ...
Kombi1.png
... die Reihe der Ringfarben 346521 (zum weißen Mittelpunkt kommt der grüne Ring, zum gelben Mittelpunkt der blaue, ...).

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

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

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

Permutationen per Hand aufzählen

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?