Derangement- & Subfakultät-Rechner
Berechnen Sie !n = D(n) — Permutationen ohne Fixpunkte — mit Wahrscheinlichkeit, Schritt-für-Schritt-Rekursion & Tabelle
P(Derangement) = D(n) / n! → 1/e ≈ 0.367879...
Schritt-für-Schritt-Rekursionsberechnung
Was ist ein Derangement?
Ein Derangement ist eine Permutation einer Menge von Elementen, bei der kein Element an seiner ursprünglichen Position steht — jedes einzelne Element wird verschoben. Anders gesagt: Nummeriert man die Positionen von 1 bis n und beginnt mit den Elementen in geordneter Reihenfolge, ist ein Derangement jede Umordnung, bei der Element i für kein i die Position i einnimmt.
Ein einfaches Beispiel: Angenommen, 3 Buchstaben A, B, C stehen auf den Positionen 1, 2, 3. Die Anordnung (B, C, A) ist ein Derangement, weil A nun auf Position 3, B auf Position 1 und C auf Position 2 steht — keiner ist an seinem Ursprungsplatz. Die Anordnung (B, A, C) ist KEIN Derangement, da C weiterhin auf Position 3 steht.
Für n = 3 gibt es genau 2 Derangements: (B, C, A) und (C, A, B). Das sind alle Permutationen von 3 Elementen, die jeden Fixpunkt vermeiden.
Die Subfakultät (!n) erklärt
Die Anzahl der Derangements von n Elementen wird mit D(n) bezeichnet oder in der Subfakultät-Schreibweise !n (gesprochen „Subfakultät n“) notiert. Das Ausrufezeichen steht vor der Zahl, im Gegensatz zur gewöhnlichen Fakultät n!, bei der es danach steht.
Die ersten elf Subfakultät-Werte lauten:
| n | !n = D(n) | n! | Wahrscheinlichkeit D(n)/n! |
|---|---|---|---|
| 0 | 1 | 1 | 1,000000 |
| 1 | 0 | 1 | 0,000000 |
| 2 | 1 | 2 | 0,500000 |
| 3 | 2 | 6 | 0,333333 |
| 4 | 9 | 24 | 0,375000 |
| 5 | 44 | 120 | 0,366667 |
| 6 | 265 | 720 | 0,368056 |
| 7 | 1.854 | 5.040 | 0,367857 |
| 8 | 14.833 | 40.320 | 0,367882 |
| 9 | 133.496 | 362.880 | 0,367879 |
| 10 | 1.334.961 | 3.628.800 | 0,367879 |
Derangement-Formel: Zwei Ansätze
1. Inklusions-Exklusions-Formel
Mit dem Inklusions-Exklusions-Prinzip ziehen wir die Permutationen ab, bei denen mindestens ein Element fixiert ist, addieren jene mit mindestens zwei fixierten Elementen wieder hinzu, und so weiter:
D(n) = n! × Σₖ₌₀ⁿ (−1)ᵏ / k!
Zum Beispiel: D(4) = 4! × (1 − 1 + 1/2 − 1/6 + 1/24) = 24 × (3/8) = 9.
2. Rekursionsformel
Die effizienteste Formel für die Berechnung nutzt eine zweigliedrige Rekursion:
Basisfälle: D(0) = 1, D(1) = 0
Die Rekursion hat eine elegante kombinatorische Bedeutung: Beim Platzieren von Element 1 gibt es (n−1) Möglichkeiten. Angenommen, Element 1 wandert auf Position j. Dann geht entweder Element j auf Position 1 (es bleiben n−2 Elemente übrig, was D(n−2) Möglichkeiten ergibt), oder Element j geht nicht auf Position 1 (was sich effektiv auf D(n−1) Möglichkeiten für die verbleibenden n−1 Elemente reduziert).
3. Formel mit Rundung (für n ≥ 1)
Da die Reihe 1/e = 1 − 1 + 1/2! − 1/3! + … sehr schnell konvergiert, liegt D(n)/n! innerhalb von 1/(2(n+1)!) von 1/e entfernt. Für n ≥ 1 bedeutet das, dass D(n) genau die nächstliegende ganze Zahl zu n!/e ist.
Das Hutproblem
Das Hutproblem ist die berühmteste Anwendung von Derangements. Das Szenario: n Gäste kommen zu einer Feier und geben ihre Hüte ab. Ein vergesslicher Garderobier gibt die Hüte in völlig zufälliger Reihenfolge zurück. Wie hoch ist die Wahrscheinlichkeit, dass kein Gast seinen eigenen Hut erhält?
Die Antwort ist genau die Derangement-Wahrscheinlichkeit:
Für n = 4 Gäste: D(4) = 9 Derangements von 4! = 24 möglichen Anordnungen. Wahrscheinlichkeit = 9/24 = 0,375 = 37,5 %.
Bemerkenswert ist, dass diese Wahrscheinlichkeit extrem schnell gegen 1/e ≈ 36,79 % konvergiert. Für n = 10 liegt die Wahrscheinlichkeit bereits bei 0,367879... — ununterscheidbar vom Grenzwert auf 6 Nachkommastellen. Egal wie groß die Feier ist, es besteht immer eine Chance von rund 37 %, dass das Chaos total ist und niemand seinen eigenen Hut bekommt.
Warum nähert sich die Derangement-Wahrscheinlichkeit 1/e an?
Die Wahrscheinlichkeit P(n) = D(n)/n! entspricht der Partialsumme der Taylorreihe für e^(−1):
Die vollständige Reihe 1/e = e^(−1) = Σₖ₌₀^∞ (−1)ᵏ/k! konvergiert absolut. Die Partialsummen alternieren ober- und unterhalb von 1/e und nähern sich mit jedem weiteren Term exponentiell schneller an. Nach der Fehlerabschätzung für alternierende Reihen ist der Fehler nach n Termen kleiner als 1/(n+1)!. Für n = 5 ist das bereits kleiner als 1/720 ≈ 0,0014, und für n = 10 kleiner als 1/39.916.800 — praktisch Maschinengenauigkeit.
Praxisbeispiele
- Wichteln (Secret Santa): In einer Gruppe von n Personen, von denen jede genau einer anderen Person ein Geschenk kauft, ohne sich selbst zu beschenken, entspricht die Anzahl der gültigen Zuordnungen D(n). Für 10 Personen gibt es D(10) = 1.334.961 gültige Zuordnungen von 10! = 3.628.800 möglichen insgesamt.
- Kartenspiele: Das „problème des ménages“ fragt, auf wie viele Arten n Ehepaare so an einem runden Tisch Platz nehmen können, dass kein Ehemann neben seiner Frau sitzt. Ein verwandtes derangement-ähnliches Problem taucht in vielen Karten-Zuordnungsspielen auf.
- Briefumschlag-Problem: Werden 3 Briefe zufällig in 3 Umschläge gesteckt, gibt D(3) = 2 die Anzahl der Möglichkeiten an, bei denen alle Briefe im falschen Umschlag landen. Die Wahrscheinlichkeit beträgt D(3)/3! = 2/6 = 1/3 ≈ 33,3 %.
- Terminplanung & Zuweisung: Bei Zuweisungsproblemen, bei denen jede Aufgabe einem anderen Mitarbeiter als der bisherigen Zuweisung zugeteilt werden muss, entspricht die Anzahl gültiger Neuzuweisungen D(n).
- Kryptografie: Derangements treten bei der Analyse bestimmter Chiffrierverfahren auf, insbesondere bei Substitutionspermutationen, bei denen ein Wert sich niemals selbst zugeordnet werden darf.
- Biologie: In der Genetik nutzt die Analyse chromosomaler Umlagerungen, bei denen kein Gen an seinem ursprünglichen Locus verbleibt, eine derangement-artige Zählweise.