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 zwei fixpunktfreie Vertauschungen von 3 Farben

Kombi3a.png
Kombi3b.png

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?