Eine Wichtel-Auslosung scheitert in 63 % der Fälle, gleich wie groß die Gruppe ist

Warum die Antwort von der Gruppe unabhängig wird

Eine Person mehr fügt eine Chance hinzu, dass sie sich selbst zieht, und zugleich einen Namen, den alle anderen stattdessen ziehen könnten. Beide Effekte heben sich fast auf, und der Rest ist eine alternierende Reihe, deren Glieder wie die Kehrwerte der Fakultäten schrumpfen — genau die Reihe für 1/e. Da Fakultäten so schnell wachsen, ist der Schwanz dieser Reihe nach einer Handvoll Glieder vernachlässigbar, und die Antwort friert ein. Die Intuition erwartet, dass eine große Gruppe sicherer sei, weil der eigene Name ein kleinerer Bruchteil des Hutes ist; die Rechnung antwortet, dass die zusätzlichen Gelegenheiten zum Scheitern im selben Tempo hinzukommen.

Neu ziehen ist nicht die Lösung, für die man es hält

Erneut zu ziehen, bis niemand seinen eigenen Namen hat, liefert tatsächlich eine gültige Zuordnung, und im Mittel braucht es dafür rund 2,7 Versuche — eins geteilt durch 0,368. Was es nicht liefert, ist eine gleichverteilt zufällige gültige Zuordnung, wenn nachlässig nachgezogen wird: nur das störende Paar zu tauschen oder die Person, die sich selbst zog, aus dem Rest neu wählen zu lassen, verzerrt das Ergebnis auf eine Weise, die in einem Durchgang unsichtbar und über einige Jahre derselben Bürofeier offensichtlich ist. Saubere Wege sind: die ganze Ziehung verwerfen und neu beginnen, oder einen einzigen zufälligen Zyklus durch alle Namen bauen — der ist konstruktionsbedingt ein Derangement.

Häufige Fragen

Was genau ist eine Subfakultät?

Sie zählt die Permutationen von n Objekten, die nichts an seinem Platz lassen, geschrieben !n mit vorangestelltem Ausrufezeichen. Sie hat eine saubere Rekursion — !n ist n−1 mal der Summe der beiden vorigen Subfakultäten — und eine noch sauberere Abkürzung: !n ist die nächstgelegene ganze Zahl zu n! geteilt durch e, für jedes n ab eins. Diese zweite Tatsache erklärt, warum das Verhältnis in der Tabelle so sichtbar konvergiert; die Zahl der Derangements ist im Wesentlichen eine gerundete Fakultät durch e, und die Rundung ist das Einzige, was die Folge von der Konstanten trennt.

Deckt dieselbe Mathematik Zuordnungsprobleme allgemein ab?

Sie deckt die reine Fassung ab und endet, wo die Nebenbedingungen beginnen. Derangements beantworten die Frage, dass niemand sich selbst zieht, und nichts weiter: Sobald eine Regel hinzukommt — Paare dürfen einander nicht ziehen, die Paarungen des Vorjahrs sind gesperrt, eine Person fehlt —, ändert sich die Zahl und die hübsche Konvergenz gegen 1/e ist dahin. Diese Varianten bleiben abzählbar, meist über Inklusion und Exklusion, haben aber keine einzelne einprägsame Antwort mehr. Die 36,8 Prozent sind eine Bezugsgröße für den unbeschränkten Fall — und gerade deshalb wissenswert, weil so viele reale Ziehungen dort beginnen, bevor jemand eine Regel hinzufügt.