Quelltext der Seite Fixpunktfreie Permutation

[[Datei:050712 perm 1.png|mini|Graph einer fixpunktfreien Permutation der Zahlen von 1 bis 8. Durch die Permutation wird keine der Zahlen festgehalten.]]
Eine '''fixpunktfreie Permutation''' oder '''Derangement''' (von {{frS|''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 <math>n</math> Elementen wird durch die [[Subfakultät]] <math>{!}n</math> angegeben. Für wachsendes <math>n</math> strebt innerhalb der Menge der Permutationen von <math>n</math> Elementen der Anteil der fixpunktfreien Permutationen sehr schnell gegen den [[Kehrwert]] der [[Eulersche Zahl|eulerschen Zahl]] <math>e</math>. Sollen in einer Permutation manche der Elemente an ihrem alten Platz verbleiben, spricht man von einem '''partiellen Derangement''', deren Anzahl durch die [[Rencontres-Zahl]]en ermittelt werden kann.

== Ausgangsproblem ==
{{Manueller Rahmen
| content = [[Datei:Playing card spade A - vertical cut.png|15px]][[Datei:Playing card spade 2 - vertical cut.png|15px]][[Datei:Playing card spade 3 - vertical cut.png|15px]][[Datei:Playing card spade 4 - vertical cut.png|15px]][[Datei:Playing card spade 5 - vertical cut.png|15px]][[Datei:Playing card spade 6 - vertical cut.png|15px]][[Datei:Playing card spade 7 - vertical cut.png|15px]][[Datei:Playing card spade 8 - vertical cut.png|15px]][[Datei:Playing card spade 9 - vertical cut.png|15px]][[Datei:Playing card spade 10 - vertical cut.png|15px]][[Datei:Playing card spade J - vertical cut.png|15px]][[Datei:Playing card spade Q - vertical cut.png|15px]][[Datei:Playing card spade K.svg|60px]]
[[Datei:Playing card spade 7 - vertical cut.png|15px]][[Datei:Playing card spade 3 - vertical cut.png|15px]][[Datei:Playing card spade J - vertical cut.png|15px]][[Datei:Playing card spade 5 - vertical cut.png|15px]][[Datei:Playing card spade 9 - vertical cut.png|15px]][[Datei:Playing card spade A - vertical cut.png|15px]][[Datei:Playing card spade Q - vertical cut.png|15px]][[Datei:Playing card spade 2 - vertical cut.png|15px]][[Datei:Playing card spade 6 - vertical cut.png|15px]][[Datei:Playing card spade 10 - vertical cut.png|15px]][[Datei:Playing card spade K - vertical cut.png|15px]][[Datei:Playing card spade 8 - vertical cut.png|15px]][[Datei:Playing card spade 4.svg|60px]]
| width   = 250
| caption = Beim ''Treize''-Spiel gewinnt der Spieler, falls bei 13 durchmischten Spielkarten einer Farbe (untere Reihe) mindestens eine Karte an der richtigen Position (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'' <!-- („Essay über die Analyse von Glücksspielen“) --> ein Spiel namens ''Treize'' („Dreizehn“) vor, das in vereinfachter Form wie folgt beschrieben werden kann:<ref>{{Literatur |Autor=[[Pierre Rémond de Montmort]] |Titel=Essai d’analyse sur les jeux de hazard |Verlag=Jacque Quillau |Ort=Paris |Datum=1708 |Seiten=58 f |Kommentar=erste Auflage 1708, zweite Auflage 1713 u.&nbsp;a. mit Briefen von [[Nikolaus I Bernoulli]]}}</ref>

<poem style="margin-left:2em;">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.</poem>

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 [[Rekursion|rekursiven Darstellung]] beruht, und einen weiteren aus einem Briefwechsel mit [[Nikolaus I Bernoulli]], der auf dem [[Prinzip von Inklusion und Exklusion|Inklusions-Exklusions-Prinzip]] basiert. De Montmort zeigt weiter, dass die Gewinnwahrscheinlichkeit sehr nahe an dem Wert von <math>1-e^{-1} \approx 0{,}6321</math> liegt. Vermutlich stellt dies die erste Verwendung der [[Exponentialfunktion]] in der [[Wahrscheinlichkeitstheorie]] dar.<ref>{{Literatur |Autor=Florence Nightingale David |Titel=Games, Gods and Gambling |Verlag=Griffin |Ort=London |Datum=1962 |Seiten=162}}</ref>

Ohne die Vorarbeiten zu kennen, analysierte [[Leonhard Euler]] 1753 ein verwandtes Glücksspiel namens ''Rencontre'' („Wiederkehr“), das folgendermaßen abläuft:<ref>{{Literatur |Autor=[[Leonhard Euler]] |Titel=Calcul de la probabilité dans le jeu de rencontre |Sammelwerk=Memoirs de l’academie des sciences de Berlin |Band=7 |Datum=1753}}</ref>

<poem style="margin-left:2em;">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.</poem>

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 [[Abraham de Moivre|de Moivre]]<ref>{{Literatur |Autor=[[Abraham de Moivre]] |Titel=Doctrine of Chances |Verlag=W. Pearson |Ort=London |Datum=1718 |Seiten=109–117}}</ref>, [[Johann Heinrich Lambert|Lambert]]<ref>{{Literatur |Autor=[[Johann Heinrich Lambert]] |Titel=Examen d’une espèce de Superstition ramenée au calcul des probabilités |Sammelwerk=Nouveaux Mémoires de l’Académie Royale des Sciences et des Belles-Lettres |Datum=1771 |Seiten=411–420}}</ref> und [[Pierre-Simon Laplace|Laplace]]<ref>{{Literatur |Autor=[[Pierre-Simon Laplace]] |Titel=Théorie Analytic des Probabilities |Verlag=Courcier |Ort=Paris |Datum=1812}}</ref> 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:<ref>{{Literatur |Autor=[[Jiří Matoušek]], [[Jaroslav Nešetřil]] |Titel=Diskrete Mathematik: Eine Entdeckungsreise |Datum= |Seiten=100–101}}</ref><ref>{{Literatur |Autor=Herbert Kütting, Martin J. Sauer |Titel=Elementare Stochastik: Mathematische Grundlagen und didaktische Konzepte |Datum= |Seiten=155}}</ref><ref>{{Literatur |Autor=[[Albrecht Beutelspacher]], Marc-Alexander Zschiegner |Titel=Diskrete Mathematik für Einsteiger |Datum= |Seiten=57}}</ref>

<poem style="margin-left:2em;">Bei einem Empfang geben <math>n</math> 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?</poem>

Die drei mathematischen Probleme sind zueinander äquivalent und können durch das Studium [[Fixpunkt (Mathematik)|fixpunktfreier]] Permutationen gelöst werden.

== Definition ==
Ist <math>S_n</math> die [[symmetrische Gruppe]] aller [[Permutation]]en der Menge <math>\{ 1, \ldots , n \}</math>, dann heißt eine Permutation <math>\pi = ( \pi(1), \pi(2), \ldots , \pi(n) ) \in S_n</math> ''fixpunktfrei'', wenn

: <math>\pi(i) \neq i</math>

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

: <math>p_n = \frac{|D_n|}{|S_n|} = \frac{d_n}{n!}</math>

nach der [[Laplace-Formel]] gerade der Wahrscheinlichkeit für das Auftreten einer fixpunktfreien Permutation, wenn man annimmt, dass alle <math>n!</math> möglichen Permutationen in <math>S_n</math> [[Diskrete Gleichverteilung|gleich wahrscheinlich]] sind. Allgemeiner können auch Permutationen beliebiger [[Endliche Menge|endlicher Mengen]], beispielsweise [[Alphabet (Informatik)|Alphabete]], betrachtet werden, zur Analyse der mathematischen Eigenschaften kann man sich jedoch auf die ersten <math>n</math> [[Natürliche Zahl|natürlichen Zahlen]] beschränken.

== Beispiele ==
[[Datei:Derangement4.png|mini|Die neun fixpunktfreien Permutationen von vier Elementen sind hervorgehoben]]

Ein Fixpunkt einer Permutation ist dadurch charakterisiert, dass in ihrer [[Permutation#Zweizeilenform|Zweizeilenform]] zweimal die gleiche Zahl untereinander steht. Die einzige Permutation in <math>S_1</math>

: <math>\begin{pmatrix} 1 \\ 1 \end{pmatrix}</math>

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

: <math>\begin{pmatrix} 1 & 2 \\ 1 & 2 \end{pmatrix}</math> &nbsp; und &nbsp; <math>\begin{pmatrix} 1 & 2 \\ 2 & 1 \end{pmatrix}</math>,

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

: <math>\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}</math> &nbsp; und &nbsp; <math>\begin{pmatrix} 1 & 2 & 3 \\ 3 & 2 & 1 \end{pmatrix}</math>

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

In <math>S_0</math> besteht die Trägermenge aus der [[Leere Menge|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 <math>d_0 = 1</math> und <math>p_0 = 1</math>.

== Anzahl ==
{| class="wikitable float-right" style="text-align:right"
|- class="hintergrundfarbe8"
!style='"width:2em'| <math>n</math>
!style="width:6em"| fixpunktfreie<br />Permutationen
!style="width:6em"| alle<br />Permutationen
!style="width:6em"| Anteil
|-
|class="hintergrundfarbe8"| 0 || 1 || 1 ||style="text-align:left"| 1
|-
|class="hintergrundfarbe8"| 1 || 0 || 1 ||style="text-align:left"| 0
|-
|class="hintergrundfarbe8"| 2 || 1 || 2 ||style="text-align:left"| 0,5
|-
|class="hintergrundfarbe8"| 3 || 2 || 6 ||style="text-align:left"| 0,33333333…
|-
|class="hintergrundfarbe8"| 4 || 9 || 24 ||style="text-align:left"| 0,375
|-
|class="hintergrundfarbe8"| 5 || 44 || 120 ||style="text-align:left"| 0,36666666…
|-
|class="hintergrundfarbe8"| 6 || 265 || 720 ||style="text-align:left"| 0,36805555…
|-
|class="hintergrundfarbe8"| 7 || 1.854 || 5.040 ||style="text-align:left"| 0,36785714…
|-
|class="hintergrundfarbe8"| 8 || 14.833 || 40.320 ||style="text-align:left"| 0,36788194…
|-
|class="hintergrundfarbe8"| 9 || 133.496 || 362.880 ||style="text-align:left"| 0,36787918…
|-
|class="hintergrundfarbe8"| 10 || 1.334.961 || 3.628.800 ||style="text-align:left"| 0,36787946…
|}

Die Anzahl der fixpunktfreien Permutationen in <math>S_n</math> lässt sich mit Hilfe der [[Subfakultät]] durch

: <math>d_n = {!}n = n! \cdot\sum_{k=0}^n \frac{(-1)^k}{k!}</math> &nbsp; ({{OEIS|A000166}})

ausdrücken. Der Anteil der fixpunktfreien Permutationen in <math>S_n</math> ist entsprechend

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

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

Für <math>n \geq 4</math> liegt damit der Anteil der fixpunktfreien Permutationen bei etwa 37 % (daher auch ''37%-Regel''). Asymptotisch gilt für diesen Anteil

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

wobei <math>e</math> die [[eulersche Zahl]] ist.

== Herleitungen ==

=== Herleitung über das Inklusions-Exklusions-Prinzip ===
[[Datei:Inclusion-exclusion.svg|mini|Nach dem Prinzip von Inklusion und Exklusion ergibt sich die Mächtigkeit der Vereinigung dreier Mengen <math> | A \cup B \cup C |</math> aus der Summe der Mächtigkeiten der einzelnen Mengen <math>| A | + | B | + | C |</math> minus der Summe der Mächtigkeiten der Schnittmengen von je zwei Mengen <math>| A \cap B | + | A \cap C | + | B \cap C |</math> plus der Mächtigkeit der Schnittmenge der drei Mengen <math>| A \cap B \cap C|</math>.]]

Bezeichnet

: <math>A_i = \{ \pi \in S_n \mid \pi(i) = i \}</math>

die Menge der Permutationen, die einen Fixpunkt an der Stelle <math>i</math> aufweisen, dann hat die Menge der fixpunktfreien Permutationen die Darstellung

: <math>D_n = S_n \setminus ( A_1 \cup \ldots \cup A_n )</math>.

Damit ist die Anzahl der fixpunktfreien Permutationen durch

: <math>d_n = n! - | A_1 \cup \ldots \cup A_n |</math>

gegeben. Nach dem [[Prinzip von Inklusion und Exklusion]] gilt nun für die [[Mächtigkeit (Mathematik)|Mächtigkeit]] einer Vereinigungsmenge

: <math>| 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|</math>.

Jede der Schnittmengen <math>| A_{i_1} \cap \ldots \cap A_{i_k} |</math> besteht aus den Permutationen mit mindestens den <math>k</math> Fixpunkten <math> i_1, \ldots, i_k</math>. Da die Werte <math>\pi(i_1),...,\pi(i_k)</math> dieser Permutationen festgelegt sind und die übrigen Werte durch eine beliebige Permutation der restlichen <math>n-k</math> Zahlen gewählt werden können, gilt demnach

: <math>| A_{i_1} \cap \ldots \cap A_{i_k} | = (n-k)!</math>.

Da es <math>\tbinom nk</math> Möglichkeiten gibt, <math>k</math> Fixpunkte auszuwählen, erhält man somit

: <math>| 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!}</math>

und weiter

: <math>d_n = n! - \sum_{k=1}^n (-1)^{k-1} \frac{n!}{k!} = n! \cdot \sum_{k=0}^n \frac{(-1)^k}{k!}</math>.

=== Herleitung über Rekurrenzen ===
{{Manueller Rahmen
| content =
<div style="padding:10px; border-bottom:1px solid lightgray;"><math>\begin{pmatrix} 1 & \,2\, & 3 & \cdots & n \\ 2 & \;1\; & \neq\!\!3 & \cdots & \neq\!\!n \end{pmatrix}</math></div>
<div style="padding:10px;"><math>\begin{pmatrix} 1 & 2 & 3 & \cdots & n \\ 2 & \neq\!\!1 & \neq\!\!3 & \cdots & \neq\!\!n \end{pmatrix}</math></div>
| width   = 260
| caption = Bei der Herleitung sind zwei Fälle zu unterscheiden: ist <math> \pi(1) = j</math>, dann kann entweder <math>\pi(j) = 1</math> sein (oben) und es verbleiben <math> n-2</math> Bedingungen oder es ist <math>\pi(j) \neq 1</math> (unten), dann verbleiben <math>n-1</math> Bedingungen. Im Beispiel ist <math>j=2</math>.
}}

Ist <math>\pi \in D_n</math> mit <math>n \geq 3</math> eine fixpunktfreie Permutation, dann gilt per Definition <math>\pi(1) \neq 1</math>. Nun werden die folgenden zwei Fälle unterschieden:
* Befindet sich die Zahl <math>1</math> an der Stelle <math>j = \pi(1)</math>, dann können die übrigen <math>n-2</math> Zahlen auf <math>d_{n-2}</math> Möglichkeiten fixpunktfrei auf die verbleibenden Plätze verteilt werden.
* Ansonsten betrachtet man die Menge <math>\{ 1, \ldots , n \} \setminus \{ j \}</math>. Diese Zahlen müssen nun die Positionen <math>2, 3, \ldots , n</math> einnehmen, sodass keine der Zahlen festbleibt und zudem die <math>1</math> nicht an der Stelle <math>j</math> steht. Die Anzahl der Möglichkeiten dies zu erreichen ist gerade <math>d_{n-1}</math>.
Nachdem es <math>n-1</math> mögliche Werte für <math>j</math> gibt, folgt daraus die [[Lineare Differenzengleichung|lineare Rekurrenz]]

: <math>d_n = (n-1) ( d_{n-1} + d_{n-2} )</math>

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

: <math>d_n - n d_{n-1} = - ( d_{n-1} - (n-1) d_{n-2})</math>.

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

: <math>d_n = n d_{n-1} + (-1)^n</math>.

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

: <math>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</math>

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

== Partielle Derangements ==
{| class="wikitable float-right" style="text-align:right"
|+ Rencontres-Zahlen ''d<sub>n,k</sub>''
|- class="hintergrundfarbe8"
|style="width:2em"| <math>{}_{n} \! \diagdown \!\! {}^{k}</math>
|style="width:1.8em"| 0
|style="width:1.8em"| 1
|style="width:1.8em"| 2
|style="width:1.8em"| 3
|style="width:1.8em"| 4
|style="width:1.8em"| 5
|style="width:1.8em"| Summe
|-
|class="hintergrundfarbe8"|  0 ||   1 ||     ||     ||     ||     ||     || 1
|-
|class="hintergrundfarbe8"|  1 ||   0 ||   1 ||     ||     ||     ||     || 1
|-
|class="hintergrundfarbe8"|  2 ||   1 ||   0 ||   1 ||     ||     ||     || 2
|-
|class="hintergrundfarbe8"|  3 ||   2 ||   3 ||   0 ||   1 ||     ||     || 6
|-
|class="hintergrundfarbe8"|  4 ||   9 ||   8 ||   6 ||   0 ||   1 ||     || 24
|-
|class="hintergrundfarbe8"|  5 ||  44 ||  45 ||  20 ||  10 ||   0 ||   1 || 120
|}

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

: <math>\begin{pmatrix} 1 & 2 & 3 \\ 1 & 3 & 2 \end{pmatrix}, \begin{pmatrix} 1 & 2 & 3 \\ 3 & 2 & 1 \end{pmatrix}</math> &nbsp; und &nbsp; <math>\begin{pmatrix} 1 & 2 & 3 \\ 2 & 1 & 3 \end{pmatrix}</math>.

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

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

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

== Anwendungen ==
[[Datei:Enigma-action-de.svg|mini|Vertauschung von Buchstaben im Walzensatz der ENIGMA]]

Die deutsche [[Rotor-Chiffriermaschine|Schlüsselmaschine]] [[Enigma (Maschine)|ENIGMA]], die während des [[Zweiter Weltkrieg|Zweiten Weltkriegs]] zum Einsatz kam, führte konstruktionsbedingt fixpunktfreie (und [[Selbstinverse Permutation|selbstinverse]]) Permutationen durch. Eine spezielle Walze, nämlich die ganz links liegende [[Enigma-Walzen|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 zwar die Konstruktion und Bedienung der Maschine vereinfachte, da Verschlüsselung und Entschlüsselung hierdurch gleich waren, zugleich allerdings eine signifikante [[Kryptographie|kryptographische]] Schwächung bewirkte (siehe auch: [[Enigma (Maschine)#Kryptographische Schwächen|Kryptographische Schwächen der ENIGMA]]).

Das [[Wichteln]] ist ein vorweihnachtlicher Brauch, bei dem eine Gruppe von Personen auf [[Zufällige Permutation|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.<ref>{{Literatur |Autor=Stefan Bartz |Titel=Selbst-Bewichtelungen in 2 von 3 Spielen |Sammelwerk=Stochastik in der Schule |Nummer=33 |Datum=2013 |Online=[https://www.stefanbartz.de/dateien/Selbst-Bewichtelungen.pdf stefanbartz.de] |Format=PDF |KBytes=684}}</ref>

== Literatur ==

* {{Literatur
   |Autor=[[Martin Aigner]]
   |Titel=Diskrete Mathematik
   |Verlag=Vieweg
   |Datum=2006
   |ISBN=3-8348-0084-8
   |Seiten=38–39}}
* {{Literatur
   |Autor=[[Albrecht Beutelspacher]], Marc-Alexander Zschiegner
   |Titel=Diskrete Mathematik für Einsteiger
   |Verlag=Springer
   |Datum=2007
   |ISBN=3-8348-9182-7
   |Seiten=57–59}}
* {{Literatur
   |Autor=[[Julian Havil]]
   |Titel=Verblüfft?! Mathematische Beweise unglaublicher Ideen
   |Verlag=Springer
   |Datum=2009
   |ISBN=978-3-540-78235-3
   |Seiten=45–58}}
* [[Norbert Henze]]: ''Stochastik für Einsteiger.'' 10. Auflage. Springer Spektrum, Wiesbaden 2013, ISBN 978-3-658-03076-6, S. 75 ff.
* {{Literatur
   |Autor=Herbert Kütting, Martin J. Sauer
   |Titel=Elementare Stochastik: Mathematische Grundlagen und didaktische Konzepte
   |Verlag=Springer
   |Datum=2011
   |ISBN=3-8274-2759-2
   |Seiten=155–162}}
* {{Literatur
   |Autor=Matthias Löwe, Holger Knöpfel
   |Titel=Stochastik – Struktur im Zufall
   |Verlag=Oldenbourg
   |Datum=2011
   |ISBN=3-486-70676-4
   |Seiten=59–60}}
* {{Literatur
   |Autor=[[Jiří Matoušek]], [[Jaroslav Nešetřil]]
   |Titel=Diskrete Mathematik: Eine Entdeckungsreise
   |Verlag=Springer
   |Datum=2002
   |ISBN=3-540-42386-9
   |Seiten=100–102}}
* {{Literatur
   |Autor=[[Pierre Rémond de Montmort]]
   |Titel=Essai d’analyse sur les jeux de hazard
   |Auflage=1.
   |Verlag=Jacque Quillau
   |Ort=Paris
   |Datum=1708
   |Online=[https://books.google.de/books?id=Cqk_AAAAcAAJ&dq=Essai+d%27+Analyse+sur+les+Jeux+de+Hazard&pg=PR1&redir_esc=y&hl=de#v=onepage&q&f=false Google-Books]}}
* {{Literatur
   |Autor=[[Pierre Rémond de Montmort]]
   |Titel=Essay d’analyse sur les jeux de hazard
   |Auflage=2.
   |Verlag=Jacque Quillau
   |Ort=Paris
   |Datum=1713
   |Seiten=130–143
   |Kommentar=u.&nbsp;a. mit Briefen von [[Nikolaus I. Bernoulli|Nikolaus Bernoulli]]
   |Online=[https://gallica.bnf.fr/ark:/12148/bpt6k110519q/f173.image gallica.bnf.fr]}}

== Weblinks ==
{{Wikiversity|Kurs:Diskrete Mathematik (Osnabrück 2020)/Vorlesung 3|Eine Vorlesung über fixpunktfreie Permutationen im Rahmen eines Kurses zur diskreten Mathematik}}
* {{EoM|Autor=V.M. Mikheev|Titel=Derangements|Url=https://www.encyclopediaofmath.org/index.php/Derangement}}
* {{EoM|Autor=|Titel=Montmort matching problem|Url=https://www.encyclopediaofmath.org/index.php/Montmort_matching_problem}}
* {{MathWorld|id=Derangement|title=Derangement}}
* {{PlanetMath|id=Derangement|title=Derangement|author=Chi Woo, J. Pahikkala}}
* {{Internetquelle
   |autor=Matroid
   |url=https://matheplanet.com/default3.html?article=444
   |titel=Derangements revisited
   |werk=[[Matroids Matheplanet]]
   |datum=2003-05-31
   |zugriff=2012-12-26
   |sprache=de}}

== Einzelnachweise ==
<references />

[[Kategorie:Permutationstheorie]]