Fixpunktfreie Permutation

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 ${\displaystyle n}$ Elementen wird durch die Subfakultät ${\displaystyle {!}n}$ angegeben. Für wachsendes ${\displaystyle n}$ strebt innerhalb der Menge der Permutationen von ${\displaystyle n}$ Elementen der Anteil der fixpunktfreien Permutationen sehr schnell gegen den Kehrwert der eulerschen Zahl ${\displaystyle 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.

Graph einer fixpunktfreien Permutation der Zahlen von 1 bis 8. Durch die Permutation wird keine der Zahlen festgehalten.

Ausgangsproblem

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 d​e Montmort stellte Anfang d​es 18. Jahrhunderts i​n seinem Buch Essai d’analyse s​ur les j​eux de hazard e​in Spiel namens Treize („Dreizehn“) vor, d​as in vereinfachter Form w​ie folgt beschrieben werden kann:[1]

Ein Spieler mischt e​inen Satz v​on 13 Spielkarten e​iner Farbe u​nd legt i​hn als Stapel v​or sich hin. Nun d​eckt er d​ie Karten d​er Reihe n​ach auf, w​obei er j​ede Karte gemäß d​er Reihenfolge As, Zwei, Drei b​is König aufruft. Sollte irgendwann d​ie aufgerufene Karte m​it der aufgedeckten Karte übereinstimmen, s​o gewinnt e​r das Spiel; trifft d​ies bei keiner d​er 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 I Bernoulli, der auf dem Inklusions-Exklusions-Prinzip basiert. De Montmort zeigt weiter, dass die Gewinnwahrscheinlichkeit sehr nahe an dem Wert von ${\displaystyle 1-e^{-1}\approx 0{,}6321}$ liegt. Vermutlich stellt dies die erste Verwendung der Exponentialfunktion in der Wahrscheinlichkeitstheorie dar.[2]

Ohne d​ie Vorarbeiten z​u kennen, analysierte Leonhard Euler 1753 e​in verwandtes Glücksspiel namens Rencontre („Wiederkehr“), d​as folgendermaßen abläuft:[3]

Zwei Spieler besitzen jeweils e​in vollständiges Kartenspiel m​it 52 Karten. Sie mischen i​hre Karten u​nd legen d​iese als Stapel v​or sich ab. Nun ziehen b​eide Spieler gleichzeitig i​mmer wieder d​ie oberste Karte v​on ihrem Stapel. Erscheint z​u irgendeinem Zeitpunkt zweimal d​ie gleiche Karte, s​o gewinnt d​er eine Spieler, andernfalls d​er andere.

Wiederum stellt s​ich die Frage n​ach der Gewinnwahrscheinlichkeit. Euler leitet d​ie Lösung m​it Hilfe weiterer Rekurrenzformeln her, w​obei er annehmen darf, d​ass nur e​iner der Spieler s​eine Karten mischt u​nd der andere Spieler s​eine Karten i​n einer vorgegebenen Reihenfolge aufdeckt. Weitere Varianten u​nd Verallgemeinerungen d​er Fragestellung wurden u​nter anderem v​on de Moivre[4], Lambert[5] u​nd Laplace[6] untersucht.

In modernen Lehrbüchern z​ur Kombinatorik w​ird das Problem häufig a​ls „Problem d​er vertauschten Hüte“ (auch Mäntel, Koffer, Briefe o​der ähnliches) i​n etwa s​o formuliert:[7][8][9]

Bei einem Empfang geben ${\displaystyle 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 d​rei mathematischen Probleme s​ind zueinander äquivalent u​nd können d​urch das Studium fixpunktfreier Permutationen gelöst werden.

Definition

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

${\displaystyle \pi (i)\neq i}$

für alle ${\displaystyle 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 ${\displaystyle D_{n}}$ die Menge aller fixpunktfreien Permutationen in ${\displaystyle S_{n}}$ und ${\displaystyle d_{n}=|D_{n}|}$ deren Anzahl, dann entspricht der Anteil

${\displaystyle 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 ${\displaystyle n!}$ möglichen Permutationen in ${\displaystyle 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 ${\displaystyle n}$ natürlichen Zahlen beschränken.

Beispiele

Die neun fixpunktfreien Permutationen von vier Elementen sind hervorgehoben

Ein Fixpunkt einer Permutation ist dadurch charakterisiert, dass in ihrer Zweizeilenform zweimal die gleiche Zahl untereinander steht. Die einzige Permutation in ${\displaystyle S_{1}}$

${\displaystyle {\begin{pmatrix}1\\1\end{pmatrix}}}$

hat einen Fixpunkt und es gilt damit ${\displaystyle d_{1}=0}$ und ${\displaystyle p_{1}=0}$. Die beiden Permutationen in ${\displaystyle S_{2}}$ sind

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

wobei die erste zwei Fixpunkte hat und die zweite keinen. Es gilt also ${\displaystyle d_{2}=1}$ und ${\displaystyle p_{2}={\tfrac {1}{2}}}$. Von den sechs Permutationen in ${\displaystyle S_{3}}$

${\displaystyle {\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   ${\displaystyle {\begin{pmatrix}1&2&3\\3&2&1\end{pmatrix}}}$

sind nur die vierte und fünfte fixpunktfrei, es gilt also ${\displaystyle d_{3}=2}$ und ${\displaystyle p_{3}={\tfrac {2}{6}}={\tfrac {1}{3}}}$.

In ${\displaystyle 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 ${\displaystyle d_{0}=1}$ und ${\displaystyle p_{0}=1}$.

Anzahl

${\displaystyle 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 ${\displaystyle S_{n}}$ lässt sich mit Hilfe der Subfakultät durch

${\displaystyle 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 ${\displaystyle S_{n}}$ ist entsprechend

${\displaystyle p_{n}={\frac {{!}n}{n!}}=\sum _{k=0}^{n}{\left(-1\right)^{k} \over k!}}$.

Die Anzahl der fixpunktfreien Permutationen ${\displaystyle d_{n}}$ und ihr Anteil an der Gesamtzahl der Permutationen ${\displaystyle p_{n}}$ sind für ${\displaystyle n=0}$ bis ${\displaystyle 10}$ in nebenstehender Tabelle zusammengefasst.

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

${\displaystyle \lim _{n\to \infty }p_{n}=\sum _{k=0}^{\infty }{\frac {(-1)^{k}}{k!}}={\frac {1}{e}}}$,

wobei ${\displaystyle e}$ die eulersche Zahl ist.

Herleitungen

Herleitung über das Inklusions-Exklusions-Prinzip

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

Bezeichnet

${\displaystyle A_{i}=\{\pi \in S_{n}\mid \pi (i)=i\}}$

die Menge der Permutationen, die einen Fixpunkt an der Stelle ${\displaystyle i}$ aufweisen, dann hat die Menge der fixpunktfreien Permutationen die Darstellung

${\displaystyle D_{n}=S_{n}\setminus (A_{1}\cup \ldots \cup A_{n})}$.

Damit i​st die Anzahl d​er fixpunktfreien Permutationen durch

${\displaystyle d_{n}=n!-|A_{1}\cup \ldots \cup A_{n}|}$

gegeben. Nach d​em Prinzip v​on Inklusion u​nd Exklusion g​ilt nun für d​ie Mächtigkeit e​iner Vereinigungsmenge

${\displaystyle |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 ${\displaystyle |A_{i_{1}}\cap \ldots \cap A_{i_{k}}|}$ besteht aus den Permutationen mit mindestens den ${\displaystyle k}$ Fixpunkten ${\displaystyle i_{1},\ldots ,i_{k}}$ und demnach gilt

${\displaystyle |A_{i_{1}}\cap \ldots \cap A_{i_{k}}|=(n-k)!}$.

Nachdem es ${\displaystyle {\tbinom {n}{k}}}$ Möglichkeiten gibt, ${\displaystyle k}$ Fixpunkte auszuwählen, erhält man so

${\displaystyle |A_{1}\cup \ldots \cup A_{n}|=\sum _{k=1}^{n}(-1)^{k-1}{\binom {n}{k}}(n-k)!=\sum _{k=1}^{n}(-1)^{k-1}{\frac {n!}{k!}}}$

und weiter

${\displaystyle 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

${\displaystyle {\begin{pmatrix}1&\,2\,&3&\cdots &n\\2&\;1\;&\neq \!\!3&\cdots &\neq \!\!n\end{pmatrix}}}$ ${\displaystyle {\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 ${\displaystyle \pi (1)=j}$, dann kann entweder ${\displaystyle \pi (j)=1}$ sein (oben) und es verbleiben ${\displaystyle n-2}$ Bedingungen oder es ist ${\displaystyle \pi (j)\neq 1}$ (unten), dann verbleiben ${\displaystyle n-1}$ Bedingungen. Im Beispiel ist ${\displaystyle j=2}$.

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

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

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

${\displaystyle d_{n}=(n-1)(d_{n-1}+d_{n-2})}$

mit ${\displaystyle d_{1}=0}$ und ${\displaystyle d_{2}=1}$. Diese Rekurrenz lässt sich nun zu

${\displaystyle d_{n}-nd_{n-1}=-(d_{n-1}-(n-1)d_{n-2})}$.

umformen. Mit der Ersetzung ${\displaystyle b_{n}=d_{n}-nd_{n-1}}$ erkennt man ${\displaystyle b_{n}=-b_{n-1}}$, also ${\displaystyle b_{n}=(-1)^{n}}$, und damit

${\displaystyle d_{n}=nd_{n-1}+(-1)^{n}}$.

Die explizite Summenformel k​ann dann d​urch vollständige Induktion verifiziert werden:

${\displaystyle 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 ${\displaystyle d_{2}=2({\tfrac {1}{2}}-{\tfrac {1}{1}}+{\tfrac {1}{1}})=2\cdot d_{1}+(-1)^{2}}$.

Partielle Derangements

Rencontres-Zahlen d_n,k

${\displaystyle {}_{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 ${\displaystyle \pi \in S_{n}}$ genau ${\displaystyle k}$ Zahlen an ihrem Platz verbleiben, so spricht man von einem unvollständigen oder partiellen Derangement. So sind beispielsweise die drei partiellen Derangements in ${\displaystyle S_{3}}$, bei der genau eine Zahl an ihrem Platz bleibt

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

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

${\displaystyle d_{n,k}={!}(n-k){\binom {n}{k}}={\frac {n!}{k!}}\cdot \sum _{i=0}^{n-k}{\left(-1\right)^{i} \over i!}}$

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

Anwendungen

Vertauschung von Buchstaben im Walzensatz der ENIGMA

Die deutsche Schlüsselmaschine ENIGMA, d​ie während d​es Zweiten Weltkriegs z​um Einsatz kam, führte konstruktionsbedingt fixpunktfreie (und selbstinverse) Permutationen durch. Eine spezielle Walze, nämlich d​ie ganz l​inks liegende Umkehrwalze, bewirkte, d​ass der Strom d​en Walzensatz zweimal durchfloss, einmal i​n Hinrichtung u​nd einmal i​n Rückrichtung. Dadurch konnte e​in Buchstabe n​icht mehr i​n sich selbst verschlüsselt werden, w​as zwar d​ie Konstruktion u​nd Bedienung d​er Maschine vereinfachte, d​a Verschlüsselung u​nd Entschlüsselung hierdurch gleich waren, zugleich allerdings e​ine signifikante kryptographische Schwächung bewirkte (siehe auch: Kryptographische Schwächen d​er ENIGMA).

Das Wichteln i​st ein vorweihnachtlicher Brauch, b​ei dem e​ine Gruppe v​on Personen a​uf zufällige Weise Geschenke austauscht. Nimmt m​an dabei an, d​ass sich k​eine Person selbst beschenkt, k​ann der Austausch d​er Geschenke mathematisch a​ls fixpunktfreie Permutation d​er Personen beschrieben werden.[10]

Literatur

• Martin Aigner: Diskrete Mathematik. Vieweg, 2006, ISBN 3-8348-0084-8, S. 38–39.
• Albrecht Beutelspacher, Marc-Alexander Zschiegner: Diskrete Mathematik für Einsteiger. Springer, 2007, ISBN 3-8348-9182-7, S. 57–59.
• Julian Havil: Verblüfft?! Mathematische Beweise unglaublicher Ideen. Springer, 2009, ISBN 978-3-540-78235-3, S. 45–58.
• Norbert Henze: Stochastik für Einsteiger. 10. Auflage. Springer Spektrum, Wiesbaden 2013, ISBN 978-3-658-03076-6, S. 75 ff.
• Herbert Kütting, Martin J. Sauer: Elementare Stochastik: Mathematische Grundlagen und didaktische Konzepte. Springer, 2011, ISBN 3-8274-2759-2, S. 155–162.
• Matthias Löwe, Holger Knöpfel: Stochastik – Struktur im Zufall. Oldenbourg, 2011, ISBN 3-486-70676-4, S. 59–60.
• Jiří Matoušek, Jaroslav Nešetřil: Diskrete Mathematik: Eine Entdeckungsreise. Springer, 2002, ISBN 3-540-42386-9, S. 100–102.
• Pierre Rémond de Montmort: Essai d’analyse sur les jeux de hazard. 1. Auflage. Jacque Quillau, Paris 1708 (Google-Books).
• Pierre Rémond de Montmort: Essay d’analyse sur les jeux de hazard. 2. Auflage. Jacque Quillau, Paris 1713, S. 130–143 (gallica.bnf.fr – u. a. mit Briefen von Nikolaus Bernoulli).

Weblinks

• V.M. Mikheev: Derangements. In: Michiel Hazewinkel (Hrsg.): Encyclopedia of Mathematics. Springer-Verlag und EMS Press, Berlin 2002, ISBN 978-1-55608-010-4 (englisch, online).
• Montmort matching problem. In: Michiel Hazewinkel (Hrsg.): Encyclopedia of Mathematics. Springer-Verlag und EMS Press, Berlin 2002, ISBN 978-1-55608-010-4 (englisch, online).
• Eric W. Weisstein: Derangement. In: MathWorld (englisch).
• Chi Woo, J. Pahikkala: Derangement. In: PlanetMath. (englisch)
• Matroid: Derangements revisited. In: Matroids Matheplanet. 31. Mai 2003, abgerufen am 26. Dezember 2012.

Einzelnachweise

1. Pierre Rémond de Montmort: Essai d’analyse sur les jeux de hazard. Jacque Quillau, Paris 1708, S. 58 f. (erste Auflage 1708, zweite Auflage 1713 u. a. mit Briefen von Nikolaus I Bernoulli).
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. Band 7, 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. Jiří Matoušek, Jaroslav Nešetřil: Diskrete Mathematik: Eine Entdeckungsreise. S. 100–101.
8. Herbert Kütting, Martin J. Sauer: Elementare Stochastik: Mathematische Grundlagen und didaktische Konzepte. S. 155.
9. Albrecht Beutelspacher, Marc-Alexander Zschiegner: Diskrete Mathematik für Einsteiger. S. 57.
10. Stefan Bartz: Selbst-Bewichtelungen in 2 von 3 Spielen. In: Stochastik in der Schule. Nr. 33, 2013 (stefanbartz.de [PDF; 684 kB]).