Fixpunktfreie Permutationen

Studium

D_n = n! \sum_{j=0}^{n} \frac{(-1)^j}{j!}

Voraussetzung: $n \in \mathbb{N}_0$

$D_n$: Anzahl der Permutationen von n Elementen, bei denen kein Element an seiner Stelle bleibt (Subfakultät !n)
$n$: Anzahl der Elemente
$n!$: Anzahl aller Permutationen von n Elementen
$j$: Summationsindex

Die Anzahl der Permutationen von n Elementen ohne Fixpunkt ist n! mal die alternierende Summe der Kehrwerte von 0! bis n!.

Erklärung

Eine Permutation heißt fixpunktfrei (englisch derangement), wenn kein Element an seinem ursprünglichen Platz bleibt. Ihre Anzahl $D_n$ wird auch Subfakultät $!n$ genannt. Die ersten Werte sind

D_0 = 1,\ D_1 = 0,\ D_2 = 1,\ D_3 = 2,\ D_4 = 9,\ D_5 = 44,\ D_6 = 265

Herleitung mit Inklusion-Exklusion: Sei $A_i$ die Menge der Permutationen, die $i$ festlassen. Für $j$ fest vorgegebene Fixpunkte gibt es $(n-j)!$ Permutationen, und es gibt $\binom{n}{j}$ Möglichkeiten, diese Fixpunkte zu wählen. Also hat mindestens einen Fixpunkt

\sum_{j=1}^{n} (-1)^{j+1} \binom{n}{j} (n-j)! = \sum_{j=1}^{n} (-1)^{j+1} \frac{n!}{j!}

Zieht man das von $n!$ ab, entsteht die Formel.

Weitere Darstellungen:

Rekursion: $D_n = (n-1)\,(D_{n-1} + D_{n-2})$ für $n \geq 2$ , mit $D_0 = 1$ , $D_1 = 0$ .
Rundungsformel: $D_n$ ist für $n \geq 1$ die nächste ganze Zahl an $\frac{n!}{e}$ .

Die Summe ist eine Partialsumme der Reihe für $e^{-1}$ . Deshalb strebt die Wahrscheinlichkeit, dass eine zufällige Permutation fixpunktfrei ist, gegen $\frac{1}{e} \approx 0{,}3679$ , und das schon für kleine $n$ sehr schnell.

Beispiele

Wichteln mit 5 Personen: Alle ziehen einen Namen. Wie viele Ziehungen gibt es, bei denen niemand sich selbst zieht?

D_5 = 5! \left(1 - 1 + \frac{1}{2} - \frac{1}{6} + \frac{1}{24} - \frac{1}{120}\right) = 44

Von allen $5! = 120$ Ziehungen funktionieren also $44$ ; die Wahrscheinlichkeit ist $\frac{44}{120} \approx 0{,}3667$ .

Rekursion: Aus $D_3 = 2$ und $D_4 = 9$ folgt $D_5 = 4 \cdot (9 + 2) = 44$ und $D_6 = 5 \cdot (44 + 9) = 265$ .

Rundung: $\frac{120}{e} \approx 44{,}15$ , gerundet $44$ .

Typische Fehler

Mit $(n-1)!$ verwechseln. $(n-1)!$ zählt die zyklischen Anordnungen (z.B. Sitzordnungen am runden Tisch), nicht die fixpunktfreien Permutationen. Für $n = 5$ ist $(n-1)! = 24 \neq 44$ .
Erwarten, dass die Wahrscheinlichkeit mit $n$ gegen $0$ oder $1$ geht. Sie liegt ab $n = 4$ immer zwischen $36\,\%$ und $38\,\%$ , z.B. $\frac{9}{24} = 0{,}375$ und $\frac{265}{720} \approx 0{,}3681$ .
Die Rundungsformel für $n = 0$ verwenden. $\frac{0!}{e} \approx 0{,}37$ rundet zu $0$ , aber $D_0 = 1$ .

Fixpunktfreie Permutationen