Fixpunktfreie Permutationen

Aufgabe

Vor einigen Jahren haben wir eine Klausuraufgabe gestellt bei der sechs Zuordnungen machen: gegeben sind sechs Grafiken (A bis F), sowie sechs Datensätze (1 bis 6). Die Datensätzen sollen den zugehörigen Grafiken zugeordnet werden. Bei der Korrektur der Klausur fiel auf, dass es viele Studenten gab, die einen oder gar keine richtige Zuordnung gemacht hat. Dies waren offenbar die Studenten, die sich nicht vorbereitet haben. Es stellen sich sofort die folgenden Fragen:

• Wie viele Möglichkeiten hat man eine, zwei, drei, …, sechs richtige Zuordnungen zu machen?
• Wenn die Studenten und Studentinnen raten, wie viele richtige Zuordnungen haben diese im Mittel?
• Wie schaut das Problem bei mehr oder weniger als sechs Zuordnungen aus?

Aber fangen wir von vorne an.

Permutationen

Gegeben sind \(n\) (unterscheidbaren) Elemente. Unter einer Permutation versteht man in der Stochastik eine Anordnung der \(n\) Elemente. Dabei gibt es

\[ \begin{aligned} n! & := \prod_{k=1}^{n} k = 1 \cdot 2 \cdot \cdots \cdot n \end{aligned} \]

verschiedene Anordnungen der \(n\) Elemente.

Beispiele

• Die drei Buchstaben ABC können auf \(3 \cdot 2 \cdot 1 = 6\) verschiedene Weisen angeordnet werden ABC, ACB, BAC, BCA, CAB und CBA.

• Anagramme sind Permutationen. So ist STAUBTUCH eine Permutation von BAUSCHUTT und MEHL von HELM.

Fixpunktfreie Permutationen (Derangements)

Unter einer fixpunktfreien Permutation (oder auch Derangement) versteht man eine Permutation bei der keines der Elemente an der ursprünglichen Stelle ist. So gibt es von ABC genau zwei fixpunktfreie Permutationen, nämlich BCA und CAB. Bei allen anderen Permutationen ist zumindest ein Element an der ursprünglichen Stelle.

Die Anzahl der fixpunktfreien Permutationen \(D_n\) wird auch als Subfakultät (Notation: \(!n\)) bezeichnet und kann wie folgt berechnet werden:

\[ D_n = !n = n! \sum_{j = 0}^{n} \frac{(-1)^j}{j!} = n!\left(\frac{1}{0!} - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} \cdots \right) \]

Schauen wir uns die ersten 10 Fakultäten und Subfakultäten, sowie den anteil der fixpunktfreien Permutationen an allen Permutationen einmal an.

\(n\)	\(n!\)	\(D_n = !n\)		\(\frac{!n}{n!}\)
\(1\)	\(1\)	\(0\)		\(0\)
\(2\)	\(2\)	\(1\)		\(0.5\)
\(3\)	\(6\)	\(2\)		\(0.\overline{3}\)
\(4\)	\(24\)	\(9\)		\(0.375\)
\(5\)	\(120\)	\(44\)		\(0.\overline{6}\)
\(6\)	\(720\)	\(265\)		\(0.3680\overline{5}\)
\(7\)	\(5040\)	\(1854\)		\(0.36785714...\)
\(8\)	\(40320\)	\(14833\)		\(0.36788194...\)
\(9\)	\(363880\)	\(133496\)		\(0.36787918...\)
\(10\)	\(3638800\)	\(1334961\)		\(0.36787946...\)

Man kann erkennen, dass der Anteil der fixpunktfreien Permutationen von allen Permuatationen gegen einen festen Wert strebt, nämlich etwa 36.8 Prozent. Dies kommt daher, dass der Wert in der Klammer die Reihendarstellung von \(\mathrm{e}^{-1}\) ist, denn es gilt

\[ \mathrm{e}^x = \lim\limits_{n\to \infty} \sum_{k=0}^{n}\frac{x^k}{k!} \] mit \(x =-1\) ergibt sich die obige Reihe.

Gehen wir zu unserem ausgangsbeispiel zurück und berechnen wie groß die Wahrscheinlichkeit ist bei zufälligem Zuordnen der 6 Graphen keinen richtig zu haben, so ergibt sich:

\[ \begin{aligned} p & = \frac{\text{Anzahl der fixpunktfreien Permutationen}}{\text{Anzahl aller Permutationen}} \\ & = \frac{!6}{6!} \\ & = \frac{1}{6!} \cdot 6! \cdot \sum_{j = 0}^{6} \frac{(-1)^j}{j!} \\ & = 1 - \frac{1}{2} + \frac{1}{6} - \frac{1}{24} + \frac{1}{120} - \frac{1}{720} \\ & = \frac{53}{144} \\ & = 0,3680\overline{5} \end{aligned} \]

Interessant zu sehen ist nun, dass es ab \(n=4\) in etwa egal ist wie viele Zuordnungen man machen sollen, die Wahrscheinlichkeit keine richtig zu haben bleibt bei etwa 37 Prozent.

Zwei Anwendungen:

1. Wichteln: Beim Wichteln möchten wir eine fixpunktfreie Permutation der Teilnehmer haben, da sich keiner selbst beschenken soll. Beim klassischen Wichteln schreibt jeder seinen Namen auf einen Zettel. Diese werden eingesammelt und jeder zieht einen Zettel auf dem der Name der zu bewichtelnden Person steht. Offenbar kann man sich selbst ziehen und das ist wie wir oben gelernt haben gar nicht so unwahrscheinlich, da nur in etwa 37 Prozent der Fälle das Wichteln erfolgreich ist.

Als Schlußbemerkung sei noch erwähnt, dass es für die Anzahl der fixpunktfreien Permutationen, den Derangements \(D_n\), auch eine rekursive Formel gibt:

\[ D_n = (n-1) (D_{n-1} + D_{n-2}) \qquad \text{mit} \qquad D_1 = 0, \quad D_2 = 1 \]

Recontres-Zahlen

Die Recontres-Zahlen \(D_{n,k}\) ist der Anzahl der Permutationen einer Menge \(n\) unterscheidbarer Elemente bei denen \(k\) ihren ursprünglichen Platz behalten. Damit sind \(D_{n,0}\) genau die fixpunktfreien Permutationen. Außerdem ist \(D_{n,n} = 1\), da es nur eine Möglichkeit gibt, dass alle Elemente am selben Platz sind und \(D_{n,n-1} = 0\), da es nicht möglich ist, dass nur ein Element den Platz ändert.

Es gibt auch eine schöne Formel um diese Zahlen zu berechnen:

\[ D_{n,k} = \frac{n!}{k!} \sum_{j = 0}^{n-k} \frac{(-1)^j}{j!} \]

n↓ k➔	0	1	2	3	4	5	6	7	8	9	10	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
6	265	264	135	40	15	0	1					720
7	1854	1855	924	315	70	21	0	1				5040
8	14833	14832	7420	2464	630	112	28	0	1			40320
9	133496	133497	66744	22260	5544	1134	168	36	0	1		362880
10	1334961	1334960	667485	222480	55650	11088	1890	240	45	0	1	3628800

Programm zur Bestimmung der Recontrezahlen

Zum Schluss noch ein kleines (vermutlich nicht sehr effizientes) Programm zur Bestimmung der Recontrezahlen. Da die Fakultät sehr schnell wächst, dauert es ab etwa \(n = 10\) recht lange die Recontres-Zahlen zu bestimmen.

library(pacman)
p_load(gtools)


recontres <- function(n) {
 x <- 1:n 
 y <- permutations(n=n, r = n, v = x)
 rval <- apply(t(t(y)==x), 1, sum) |>  table()
 return(rval)
}

recontres(6)

  0   1   2   3   4   6 
265 264 135  40  15   1