Lasst uns wichteln! Nehmen wir an, wir wären $n$ Freunde. Wir schreiben unsere Namen auf Kärtchen, werfen diese in einen Hut, und ziehen der Reihe nach jeweils eine Karte wieder heraus. Es kann natürlich passieren, dass jemand von uns seinen eigenen Namen zieht, worauf wir den Vorgang wiederholen müssten. Doch wie groß ist die Wahrscheinlichkeit, dass niemand von uns seinen eigenen Namen zieht?
Das Problem ist kombinatorischer Natur: Es gibt genausoviele Möglichkeiten, die Karten wieder unter uns aufzuteilen, wie es Permutationen der Karten gibt: Das wären $n!=1\cdot2\cdot 3\dots\cdot n$. Unter diesen möglichen Permutationen gibt es nur einige sogenannte fixpunktfreie Permutationen, also solche, bei denen niemand seine eigene Karte zieht. Die Anzahl der fixpunktfreien Permutationen ist
$$!n = n! \cdot \sum_{k=0}^n \frac{(-1)^k}{k!}$$
Sind wir nur zu zweit ($n=2$), gibt es natürlich nur zwei Permutationen, und nur eine davon ist fixpunktfrei. Die Wahrscheinlichkeit, dass wir beim ersten Ziehen bereits erfolgreich sind, liegt bei 50%. Spielen wir zu dritt, gibt es sechs Permutationen, wovon zwei fixpunktfrei sind (die zufälligerweise auch gleichzeitig Rotationen sind). Die Wahrscheinlichkeit sinkt also schnell auf ca. 33%. Interessant wird es, wenn wir $n$ wachsen lassen: Es zeigt sich, dass die Wahrscheinlichkeit sehr schnell gegen den Grenzwert $1/e$ konvergieren: Die Wahrscheinlichkeit, dass wir beim ersten Ziehen erfolgreich sind, liegt für vier oder mehr Spieler ungefähr bei 37%, und das unabhängig von der Anzahl der Spieler!
Etwas schwieriger wird es, wenn eine Gruppe von Paaren sich entscheidet zu wichteln: Die Regeln verändern sich dahingehend, dass man nicht nur sich selbst nicht ziehen darf, sondern auch seinen Partner nicht -- das wäre ja zu einfach! Und genau diese Situation trat in unserer Familie auf: Wir schrieben Zettel, warfen sie in einen Hut, zogen, und erhielten eine ungültige Zuordnung. Auch der zweite Versuch schlug fehl. Erst beim dritten Mal klappte es. Ich hatte das dumpfe Gefühl, dass wir beim dritten Mal bereits außerordentliches Glück hatten und wollte der Sache auf den Grund gehen.
Wenn wir $n$ Paare betrachten (also $2n$ Personen), dann gibt es $(2n)!$ Permutationen, von denen $!(2n)$ fixpunktfrei sind. Allerdings sind nicht alle diese fixpunktfreien Permutationen gültig: Die Permutation, in der jede Person ihren Partner zieht ist zum Beispiel fixpunktfrei. Es gibt also höchstens $!(2n)$ gültige Permutationen. Eine gültige Permutation wäre zum Beispiel eine solche, in der jedes Paar ein anderes Paar zieht; innerhalb dieses Paares gibt es dann zwei mögliche Zuordnungen: Mann-Mann und Frau-Frau oder Mann-Frau und Frau-Mann. Davon gibt es natürlich $2\cdot !n$ mögliche Permutationen ($!n$ für die Auswahl der Paare, und $2$ für die Zuordnung innerhalb der Paare). Nachdem das nicht alle gültigen Permutationen sind ist das eine untere Grenze, so wie $!(2n)$ eine obere ist. Die obere Grenze für die Wahrscheinlichkeit einer gültigen Permutation ist also (wie oben) bei 37%, the untere Grenze1 ist eng mit dem quadrupel factorial verknüpft:
$$\frac{2 \cdot !n}{(2n)!}= \frac{2 \cdot n!}{(2n)!} \cdot \sum_{k=0}^n \frac{(-1)^k}{k!}$$
Bei zwei Paaren ($n=2$, vier Personen) gibt es also höchstens neun und mindestens zwei gültige Permutationen. In der Tat kann man zeigen, dass es genau vier gültige Permutationen bei zwei Paaren gibt. Bei drei Paaren, so wie in unserer Familie, gibt es bereits 720 mögliche Permutationen, von denen 265 fixpunktfrei sind, wovon wiederum nur 80 der Regel entsprechen, dass niemand den eigenen Partner ziehen darf! Die Wahrscheinlichkeit, bei drei Paaren gültig zu ziehen liegt also bei ca. 11%. Wenden wir nun noch die geometrische Verteilung an, welche die Wahrscheinlichkeit berechnet, den ersten Erfolg nach genau $k$ Zügen zu haben, stellt sich heraus dass man nur mit einer Wahrscheinlichkeit von ca. 30% innerhalb der ersten drei Versuche eine gültige Zuordnung bekommt. Wir hatten tatsächlich Glück!
Es geht aber noch ein wenig komplizierter: Nehmen wir an, wir haben $N$ Gruppen von Personen, und jede dieser Gruppen hat eine unterschiedliche Anzahl von Personen: Gruppe 1 hat $n_1$ Mitglieder, Gruppe 2 $n_2$, und so weiter. Wie groß ist die Wahrscheinlichkeit, dass bei der Auslosung niemand sich selbst oder ein Mitglied der eigenen Gruppe zieht? (Wichteln mit Paaren ist davon natürlich ein Sonderfall, und zwar mit $N=n$ und $n_1=n_2=\cdots=n_n=2$.) Die Fragestellung ist äußerst kompliziert, aber die Lösung existiert seit 19742. Sie ist über ein kompliziertes Integral über das Produkt mehrerer Laguerre-Polynome gegeben. Mehr will ich dazu jetzt nicht sagen.
Übrigens: Wenn die Anzahl $n$ der Pärchen wächst, erhält man als Grenzwert für die Wahrscheinlichkeit einer gültigen Zuordnung $1/e^2$! Für diesen Fall ist das oben genannte Integral nämlich relativ einfach lösbar.
Weiterführende Literatur/Further Reading:
1 Diese untere Grenze ist übrigens, für großes $n$, sehr schlecht: das quadrupel factorial wächst sehr schnell, weshalb die untere Grenze für die Wahrscheinlichkeit schnell gegen null geht.↩
2 Derangements and Laguerre polynomials, S. Even and J. Gillis (1976). Mathematical Proceedings of the Cambridge Philosophical Society, Volume 79, Issue 01, January 1976, pp 135-143.↩