Fixpunktfreie Permutation

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
Graph einer fixpunktfreien Permutation der Zahlen von 1 bis 8. Durch die Permutation wird keine der Zahlen festgehalten.

Eine fixpunktfreie Permutation oder Derangement (von französisch déranger „durcheinanderbringen“) ist in der Kombinatorik eine Permutation der Elemente einer Menge, sodass kein Element seine Ausgangsposition beibehält. Die Anzahl möglicher fixpunktfreier Permutationen einer Menge mit n Elementen wird durch die Subfakultät {!}n angegeben. Für wachsendes n strebt innerhalb der Menge der Permutationen von n Elementen der Anteil der fixpunktfreien Permutationen sehr schnell gegen den Kehrwert der eulerschen Zahl e. Sollen in einer Permutation manche der Elemente an ihrem alten Platz verbleiben, spricht man von einem partiellen Derangement, deren Anzahl durch die Rencontres-Zahlen ermittelt werden kann.

Ausgangsproblem[Bearbeiten]

Playing card spade A - vertical cut.pngPlaying card spade 2 - vertical cut.pngPlaying card spade 3 - vertical cut.pngPlaying card spade 4 - vertical cut.pngPlaying card spade 5 - vertical cut.pngPlaying card spade 6 - vertical cut.pngPlaying card spade 7 - vertical cut.pngPlaying card spade 8 - vertical cut.pngPlaying card spade 9 - vertical cut.pngPlaying card spade 10 - vertical cut.pngPlaying card spade J - vertical cut.pngPlaying card spade Q - vertical cut.pngPlaying card spade K.svg

Playing card spade 7 - vertical cut.pngPlaying card spade 3 - vertical cut.pngPlaying card spade J - vertical cut.pngPlaying card spade 5 - vertical cut.pngPlaying card spade 9 - vertical cut.pngPlaying card spade A - vertical cut.pngPlaying card spade Q - vertical cut.pngPlaying card spade 2 - vertical cut.pngPlaying card spade 6 - vertical cut.pngPlaying card spade 10 - vertical cut.pngPlaying card spade K - vertical cut.pngPlaying card spade 8 - vertical cut.pngPlaying card spade 4.svg

Beim Treize-Spiel gewinnt der Spieler, wenn bei 13 durchmischten Spielkarten einer Farbe (untere Reihe) mindestens eine Karte in der richtigen Reihenfolge (obere Reihe) auftritt, hier die Zehn.

Der französische Mathematiker Pierre Rémond de Montmort stellte Anfang des 18. Jahrhunderts in seinem Buch Essai d'analyse sur les jeux de hazard ein Spiel namens Treize („Dreizehn“) vor, das in vereinfachter Form wie folgt beschrieben werden kann:[1]

Ein Spieler mischt einen Satz von 13 Spielkarten einer Farbe und legt ihn als Stapel vor sich hin. Nun deckt er die Karten der Reihe nach auf, wobei er jede Karte gemäß der Reihenfolge As, Zwei, Drei bis König aufruft. Sollte irgendwann die aufgerufene Karte mit der aufgedeckten Karte übereinstimmen, so gewinnt er das Spiel; trifft dies bei keiner der 13 Karten zu, verliert er.

Nun stellt de Montmort sich die Frage nach der Wahrscheinlichkeit, mit der der Spieler das Spiel gewinnt. In der ersten Auflage seines Buchs von 1708 gibt de Montmort zwar das korrekte Ergebnis an, allerdings ohne genauere Herleitung. In der zweiten Auflage von 1713 stellt er dann zwei Beweise vor, einen eigenen, der auf einer rekursiven Darstellung beruht, und einen weiteren aus einem Briefwechsel mit Nikolaus Bernoulli, der auf dem Inklusions-Exklusions-Prinzip basiert. De Montmort zeigt weiter, dass die Gewinnwahrscheinlichkeit sehr nahe an dem Wert von 1-e^{-1} \approx 0{,}6321 liegt. Vermutlich stellt dies die erste Verwendung der Exponentialfunktion in der Wahrscheinlichkeitstheorie dar.[2]

Ohne die Vorarbeiten zu kennen analysierte Leonhard Euler 1753 ein verwandtes Glücksspiel namens Rencontre („Wiederkehr“), das folgendermaßen abläuft:[3]

Zwei Spieler besitzen jeweils ein vollständiges Kartenspiel mit 52 Karten. Sie mischen ihre Karten und legen diese als Stapel vor sich ab. Nun ziehen beide Spieler gleichzeitig immer wieder die oberste Karte von ihrem Stapel. Erscheint zu irgendeinem Zeitpunkt zweimal die gleiche Karte, so gewinnt der eine Spieler, andernfalls der andere.

Wiederum stellt sich die Frage nach der Gewinnwahrscheinlichkeit. Euler leitet die Lösung mit Hilfe weiterer Rekurrenzformeln her, wobei er annehmen darf, dass nur einer der Spieler seine Karten mischt und der andere Spieler seine Karten in einer vorgegebenen Reihenfolge aufdeckt. Weitere Varianten und Verallgemeinerungen der Fragestellung wurden unter anderem von de Moivre[4], Lambert[5] und Laplace[6] untersucht.

In modernen Lehrbüchern zur Kombinatorik wird das Problem häufig als „Problem der vertauschten Hüte“ (auch Mäntel, Koffer, Briefe oder ähnliches) in etwa so formuliert:[7][8][9]

Bei einem Empfang geben n Gäste ihre Hüte an der Garderobe ab. Die Garderobenfrau ist an diesem Abend jedoch sehr zerstreut und gibt beim Verlassen jedem Gast einen zufällig gewählten Hut zurück. Wie groß ist die Wahrscheinlichkeit, dass mindestens ein Gast den richtigen Hut erhält?

Die drei mathematischen Probleme sind auf gewisse Weise zueinander äquivalent und können durch das Studium fixpunktfreier Permutationen gelöst werden.

Definition[Bearbeiten]

Ist S_n die symmetrische Gruppe aller Permutationen der Menge \{ 1, \ldots , n \}, dann heißt eine Permutation \pi = ( \pi(1), \pi(2), \ldots , \pi(n) ) \in S_n fixpunktfrei, wenn

\pi(i) \neq i

für alle i = 1, \ldots , n gilt. Eine fixpunktfreie Permutation ist damit eine Permutation, bei der kein Element seine Ausgangsposition beibehält, das heißt es tritt kein Zyklus der Länge eins auf. Bezeichnet D_n die Menge aller fixpunktfreien Permutationen in S_n und d_n = | D_n | deren Anzahl, dann entspricht der Anteil

p_n = \frac{|D_n|}{|S_n|} = \frac{d_n}{n!}.

nach der Laplace-Formel gerade der Wahrscheinlichkeit für das Auftreten einer fixpunktfreien Permutation, wenn man annimmt, dass alle n! möglichen Permutationen in S_n gleich wahrscheinlich sind. Allgemeiner können auch Permutationen beliebiger endlicher Mengen, beispielsweise Alphabete, betrachtet werden, zur Analyse der mathematischen Eigenschaften kann man sich jedoch auf die ersten n natürlichen Zahlen beschränken.

Beispiele[Bearbeiten]

Ein Fixpunkt einer Permutation ist dadurch charakterisiert, dass in ihrer Zweizeilenform zweimal die gleiche Zahl untereinander steht. Die einzige Permutation in S_1

\begin{pmatrix} 1 \\ 1 \end{pmatrix}

hat einen Fixpunkt und es gilt damit d_1 = 0 und p_1 = 0. Die beiden Permutationen in S_2 sind

\begin{pmatrix} 1 & 2 \\ 1 & 2 \end{pmatrix}   und   \begin{pmatrix} 1 & 2 \\ 2 & 1 \end{pmatrix},

wobei die erste zwei Fixpunkte hat und die zweite keinen. Es gilt also d_2 = 1 und p_2 = \tfrac12. Von den sechs Permutationen in S_3

\begin{pmatrix} 1 & 2 & 3 \\ 1 & 2 & 3 \end{pmatrix}, \begin{pmatrix} 1 & 2 & 3 \\ 1 & 3 & 2 \end{pmatrix}, \begin{pmatrix} 1 & 2 & 3 \\ 2 & 1 & 3 \end{pmatrix}, \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix}, \begin{pmatrix} 1 & 2 & 3 \\ 3 & 1 & 2 \end{pmatrix}   und   \begin{pmatrix} 1 & 2 & 3 \\ 3 & 2 & 1 \end{pmatrix}

sind nur die vierte und fünfte fixpunktfrei, es gilt also d_3 = 2 und p_3 = \tfrac26 = \tfrac13.

In S_0 besteht die Trägermenge aus der leeren Menge mit der einzigen Permutation darin, die leere Menge auf die leere Menge abzubilden. Da aus der leeren Menge kein Element ausgewählt werden kann, ist diese Permutation fixpunktfrei und es gilt d_0 = 1 und p_0 = 1.

Anzahl[Bearbeiten]

n fixpunktfreie
Permutationen
alle
Permutationen
Anteil
0 1 1 1
1 0 1 0
2 1 2 0,5
3 2 6 0,33333333...
4 9 24 0,375
5 44 120 0,36666666...
6 265 720 0,36805555...
7 1.854 5.040 0,36785714...
8 14.833 40.320 0,36788194...
9 133.496 362.880 0,36787918...
10 1.334.961 3.628.800 0,36787946...

Die Anzahl der fixpunktfreien Permutationen in S_n lässt sich mit Hilfe der Subfakultät durch

d_n = {!}n = n! \cdot\sum_{k=0}^n \frac{(-1)^k}{k!}   (Folge A000166 in OEIS)

ausdrücken. Der Anteil der fixpunktfreien Permutationen in S_n ist entsprechend

p_n = \frac{{!}n}{n!} = \sum_{k=0}^n {\left(-1\right)^k \over k!}.

Die Anzahl der fixpunktfreien Permutationen d_n und ihr Anteil an der Gesamtzahl der Permutationen p_n sind für n=0 bis 10 in nebenstehender Tabelle zusammengefasst.

Für n \geq 4 liegt damit der Anteil der fixpunktfreien Permutationen bei etwa 37 % (siehe auch 37%-Regel). Asymptotisch gilt für diesen Anteil

\lim_{n \to \infty} p_n = \sum_{k=0}^\infty \frac{(-1)^k}{k!} = \frac{1}{e},

wobei e die eulersche Zahl ist.

Herleitungen[Bearbeiten]

Herleitung über das Inklusions-Exklusions-Prinzip[Bearbeiten]

Nach dem Prinzip von Inklusion und Exklusion ergibt sich die Mächtigkeit der Vereinigung dreier Mengen \scriptstyle | A \cup B \cup C | aus der Summe der Mächtigkeiten der einzelnen Mengen \scriptstyle | A | + | B | + | C | minus der Summe der Mächtigkeiten der Schnittmengen von je zwei Mengen \scriptstyle | A \cap B | + | A \cap C | + | B \cap C | plus der Mächtigkeit der Schnittmenge der drei Mengen \scriptstyle | A \cap B \cap C|.

Bezeichnet

A_i = \{ \pi \in S_n \mid \pi(i) = i \}

die Menge der Permutationen, die einen Fixpunkt an der Stelle i aufweisen, dann hat die Menge der fixpunktfreien Permutationen die Darstellung

D_n = S_n \setminus ( A_1 \cup \ldots \cup A_n ).

Damit ist die Anzahl der fixpunktfreien Permutationen durch

d_n = n! - | A_1 \cup \ldots \cup A_n |

gegeben. Nach dem Prinzip von Inklusion und Exklusion gilt nun für die Mächtigkeit einer Vereinigungsmenge

| A_1 \cup \ldots \cup A_n | = \sum_{k=1}^n (-1)^{k-1} \sum_{1 \leq i_1 < \ldots < i_k \leq n} \left| A_{i_{1}} \cap \cdots \cap A_{i_k} \right|.

Jede der Schnittmengen | A_{i_1} \cap \ldots \cap A_{i_k} | besteht aus den Permutationen mit mindestens k Fixpunkten und demnach gilt

| A_{i_1} \cap \ldots \cap A_{i_k} | = (n-k)!.

Nachdem es \tbinom nk Möglichkeiten gibt, k Fixpunkte auszuwählen, erhält man so

| A_1 \cup \ldots \cup A_n | = \sum_{k=1}^n (-1)^{k-1} \binom nk (n-k)! = \sum_{k=1}^n (-1)^{k-1} \frac{n!}{k!}

und weiter

d_n = n! - \sum_{k=1}^n (-1)^{k-1} \frac{n!}{k!} = n! \cdot \sum_{k=0}^n \frac{(-1)^k}{k!}.

Herleitung über Rekurrenzen[Bearbeiten]

\begin{pmatrix} 1 & \,2\, & 3 & \cdots & n \\ 2 & \;1\; & \neq\!\!3 & \cdots & \neq\!\!n \end{pmatrix}
\begin{pmatrix} 1 & 2 & 3 & \cdots & n \\ 2 & \neq\!\!1 & \neq\!\!3 & \cdots & \neq\!\!n \end{pmatrix}
Bei der Herleitung sind zwei Fälle zu unterscheiden: ist \scriptstyle \pi(1) = j, dann kann entweder \scriptstyle \pi(j) = 1 sein (oben) und es verbleiben \scriptstyle n-2 Bedingungen oder es ist \scriptstyle \pi(j) \neq 1 (unten), dann verbleiben \scriptstyle n-1 Bedingungen. Im Beispiel ist \scriptstyle j=2.

Ist \pi \in D_n mit n \geq 3 eine fixpunktfreie Permutation, dann gilt per Definition \pi(1) \neq 1. Nun werden die folgenden zwei Fälle unterschieden:

  • Befindet sich die Zahl 1 an der Stelle j = \pi(1), dann können die übrigen n-2 Zahlen auf d_{n-2} Möglichkeiten fixpunktfrei auf die verbleibenden Plätze verteilt werden.
  • Ansonsten betrachtet man die Menge \{ 1, \ldots , n \} \setminus \{ j \}. Diese Zahlen müssen nun die Positionen 2, 3, \ldots , n einnehmen, sodass keine der Zahlen festbleibt und zudem die 1 nicht an der Stelle j steht. Die Anzahl der Möglichkeiten dies zu erreichen ist gerade d_{n-1}.

Nachdem es n-1 mögliche Werte für j gibt, folgt daraus die lineare Rekurrenz

d_n = (n-1) ( d_{n-1} + d_{n-2} )

mit d_1 = 0 und d_2 = 1. Diese Rekurrenz lässt sich nun zu

d_n - n d_{n-1} = - ( d_{n-1} - (n-1) d_{n-2}).

umformen. Mit der Ersetzung b_n = d_n - n d_{n-1} erkennt man b_n = - b_{n-1}, also b_n = (-1)^n, und damit

d_n = n d_{n-1} + (-1)^n.

Die explizite Summenformel kann dann durch vollständige Induktion verifiziert werden:

d_n = n! \cdot \sum_{k=0}^n \frac{(-1)^k}{k!} = n! \cdot \sum_{k=0}^{n-1} {\left(-1\right)^k \over k!} + n! \cdot \frac{(-1)^n}{n!} = nd_{n-1} + (-1)^n

wobei d_2 = 2 ( \tfrac12 - \tfrac11 + \tfrac11 ) = 2 \cdot d_1 + (-1)^2.

Partielle Derangements[Bearbeiten]

Rencontres-Zahlen dn,k
{}_{n} \! \diagdown \!\! {}^{k} 0 1 2 3 4 5 Summe
0 1 1
1 0 1 1
2 1 0 1 2
3 2 3 0 1 6
4 9 8 6 0 1 24
5 44 45 20 10 0 1 120

Sollen in einer Permutation \pi \in S_n genau k Zahlen an ihrem Platz verbleiben, so spricht man von einem unvollständigen oder partiellen Derangement. So sind beispielsweise die drei partiellen Derangements in S_3, bei der genau eine Zahl an ihrem Platz bleibt

\begin{pmatrix} 1 & 2 & 3 \\ 1 & 3 & 2 \end{pmatrix}, \begin{pmatrix} 1 & 2 & 3 \\ 3 & 2 & 1 \end{pmatrix}   und   \begin{pmatrix} 1 & 2 & 3 \\ 2 & 1 & 3 \end{pmatrix}.

Bezeichnet nun D_{n,k} die Menge der partiellen Derangements in S_n bei denen genau k Zahlen an ihrem Platz verbleiben, dann wird die Anzahl d_{n,k} = | D_{n,k} | durch die Rencontres-Zahlen

d_{n,k} = {!}(n-k) \binom nk = \frac {n!}{k!} \cdot \sum_{i=0}^{n-k} {\left( -1 \right)^i \over i!}

angegeben (Folge A008290 in OEIS). Als Spezialfall für k=0 erhält man mit D_n = D_{n,0} die Menge der fixpunktfreien Permutationen und mit d_n = d_{n,0} die Subfakultät.

Anwendungen[Bearbeiten]

Vertauschung von Buchstaben durch die Verschlüsselungsmaschine Enigma

Die deutsche Verschlüsselungsmaschine Enigma, die während des Zweiten Weltkriegs zum Einsatz kam, führte konstruktionsbedingt fixpunktfreie (und selbstinverse) Permutationen durch. Eine spezielle Walze, die Umkehrwalze, bewirkte, dass der Strom den Walzensatz zweimal durchfloss, einmal in Hinrichtung und einmal in Rückrichtung. Dadurch konnte ein Buchstabe nicht mehr in sich selbst verschlüsselt werden, was allerdings eine signifikante kryptographische Schwächung der Maschine darstellte.

Das Wichteln ist ein vorweihnachtlicher Brauch, bei dem eine Gruppe von Personen auf zufällige Weise Geschenke austauscht. Nimmt man dabei an, dass sich keine Person selbst beschenkt, kann der Austausch der Geschenke mathematisch als fixpunktfreie Permutation der Personen beschrieben werden.[10]

Siehe auch[Bearbeiten]

Literatur[Bearbeiten]

Einzelnachweise[Bearbeiten]

  1.  Pierre Rémond de Montmort: Essai d'analyse sur les jeux de hazard. Jacque Quillau, Paris 1708, S. 58 f.
  2.  Florence Nightingale David: Games, Gods and Gambling. Griffin, London 1962, S. 162.
  3.  Leonhard Euler: Calcul de la probabilité dans le jeu de rencontre. In: Memoirs de l'academie des sciences de Berlin. 1753.
  4.  Abraham de Moivre: Doctrine of Chances. W. Pearson, London 1718, S. 109–117.
  5.  Johann Heinrich Lambert: Examen d’une espèce de Superstition ramenée au calcul des probabilités. In: Nouveaux Mémoires de l’Académie Royale des Sciences et des Belles-Lettres. 1771, S. 411–420.
  6.  Pierre-Simon Laplace: Théorie Analytic des Probabilities. Courcier, Paris 1812.
  7.  Matoušek, Nešetřil: Diskrete Mathematik: Eine Entdeckungsreise. S. 100–101.
  8.  Kütting, Sauer: Elementare Stochastik: Mathematische Grundlagen und didaktische Konzepte. S. 155.
  9.  Beutelspacher, Zschiegner: Diskrete Mathematik für Einsteiger. S. 57.
  10.  Stefan Bartz: Selbst-Bewichtelungen in 2 von 3 Spielen (PDF; 684 kB). In: Stochastik in der Schule. Nr. 33, 2013.

Weblinks[Bearbeiten]