- Wichteln
Eine gewisse Gruppe von Personen möchte wichteln. D.h. jeder Person wird eine weitere Person zugelost, die die erste Person beschenken soll, und dabei wird größtmögliche Geheimhaltung angestrebt. Typischerweise legt man die Zuordnung so fest, dass man die Namen der beteiligten Personen einzeln auf einen Zettel schreibt und dann die Leute ziehen lässt. Die ziehende Person beschenkt die Person, deren Namen auf dem gezogenen Zettel steht. Wenn eine Person sich selbst zieht, so hat man ein Problem. Die übliche praktische Lösung ist, alles zurück in den Topf zu werfen und nochmal probieren, solange, bis es keine Selbstziehungen mehr gibt.
Wir wollen verstehen, wie hoch die Wahrscheinlichkeit ist, dass sich jemand bei einer Ziehung selbst zieht, und daher das Ganze wiederholt werden muss. Insbesondere wollen wir die Asymptotik verstehen, wenn die Anzahl der beteiligten Personen sehr groß ist bzw. wird.
Es sei 
die Anzahl der Personen, die wichteln möchten.
-
Hier gibt es nur eine Ziehung, die eine Person zieht sich selbst, dies ist unvermeidbar. Die Wahrscheinlichkeit, dass eine
(erlaubte)
Wichtelzuordnung gezogen wird, ist also 
, und die Wahrscheinlichkeit, dass eine Nichtwichtelzuordnung gezogen wird, ist 
.
-
Nennen wir die Personen
und 
.
Hier gibt es zwei Ziehmöglichkeiten, nämlich
|
|
|
|
|
|
und
|
|
|
|
|
|
|
|
Die erste Möglichkeit ist die Identität, die zweite die Vertauschung. Die erste ist nicht erlaubt, die zweite ist eine erlaubte Wichtelzuordnung. Die Wahrscheinlichkeit is also 
. Die Ziehmöglichkeiten werden hier durch eine Wertetabelle angegeben, und zwar eine solche, bei der jede Person genau einmal als Wert
(in der unteren Reihe)
auftritt. Eine solche Zuordnung heißt bijektive Abbildung oder Permutation. Wir interessieren uns also für den Anteil derjenigen Permutation, wo keine Person auf sich selbst abgebildet wird, innerhalb der Gesamtheit aller Permutationen.
-
Nennen wir die Personen
und 
.
Hier gibt es sechs Ziehmöglichkeiten, nämlich
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Von den sechs Möglichkeiten sind nur die vierte und die fünfte ohne Selbstziehung
(ohne Fixpunkt).
Die Wahrscheinlichkeit für eine fixpunktfreie Ziehung ist demnach 
.
Wie kommt man auf die Liste dieser insgesamt sechs Ziehmöglichkeiten? Um sich dies klar zu machen, vergessen wir kurz die Frage nach den Selbstziehungen. Die erste Person hat drei Ziehmöglichkeiten, nämlich 
. Wenn dies festgelegt ist, so hat die zweite Person, , nur noch zwei Ziehmöglichkeiten, die jeweils von gezogene Person ist ja nicht mehr möglich. Für die letzte Person, , gibt es nur noch eine Möglichkeit, sie muss den verbliebenen Zettel ziehen. Diese Beobachtung gilt stets. Bei Personen gibt es insgesamt
-
Permutationen. Diese von abhängige Zahl bekommt einen eigenen Namen, man nennt sie die Fakultät von und bezeichnet sie mit 
. Diese Funktion wächst ziemlich schnell.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Der Wert 
mag überraschen, ist aber sinnvoll. Die Grundmenge aller Permutationen besitzt also Elemente, darin müssen wir diejenigen Permutationen zählen, die keinen Fixpunkt besitzen.
-
Nennen wir die Personen
und 
.
Wir wissen, dass es insgesamt Permutationen gibt. Alle aufzulisten und einfach zu schauen, welche einen Fixpunkt haben und welche nicht, ist schon ziemlich aufwändig. Wir werden gleich bessere Abzählmöglichkeiten finden.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Eine Durchsicht der Liste zeigt, dass es unter den Permutationen 
fixpunktfreie Permutationen gibt. Auf diese Zahl kann man schneller kommen, indem man die Struktur von Permutationen besser versteht. Entscheidend dafür ist das Konzept eines Zyklus. Bei der zuletzt angeführten Permutation wird beispielsweise auf und wiederum auf abgebildet, und ebenso wird mit vertauscht. Insgesamt kann man diese Abbildung als
-
darstellen. Man hat zwei Zykel der Länge zwei. In der darüber stehenden Permutation hat man die Zuordnung
-
Man spricht von einem Zyklus der Länge . In der darüber stehenden Permutation hat man die Zuordnung
-
Man hat einen Zyklus der Länge zwei und zwei Fixpunkte, ein Fixpunkt ist ein Zyklus der Länge eins. Die Zerlegung einer Permutation in die Zykel verschiedener Länge nennt man den Typ der Permutation. Es geht also darum, wie viele Zykel welcher Länge es gibt.
Im Falle
gibt es nun lediglich zwei Typen, wie eine fixpunktfreie Permutation aussehen kann, nämlich den Viererzyklus und den doppelten Zweierzyklus. Beim ersten Typ kann man an jeder Stelle anfangen, die Reihenfolge der Elemente legt dann den Zyklus fest. Davon gibt es also
Stück. Beim zweiten Typ geht es um die Einteilung der Menge in zwei Paare, danach ist alles festgelegt. Davon gibt es Stück. Jedenfalls ist die Wahrscheinlichkeit für eine fixpunktfreie Permutation bei vier Personen gleich 
.
-
Hier gibt es schon Permutationen, eine Auflistung erübrigt sich. Es gibt aber wieder nur zwei Typen von fixpunktfreien Permutationen, nämlich einerseits die -Zykel und andererseits diejenigen Permutationen, die aus einem Zweier-Zyklus und einem Dreier-Zyklus bestehen. Vom ersten Typ gibt es, mit dem gleichen Argument wie oben,
Möglichkeiten. Vom zweiten Typ muss man die Anzahl der Möglichkeiten bestimmen, in einer fünfelementigen Menge eine zweielementige Teilmenge zu fixieren. Diese Zahlen werden wir gleich allgemeiner benötigen: Wie viele Möglichkeiten gibt es, in einer -elementigen Menge eine 
-elementige Teilmenge zu fixieren?
Hier treten wieder die Fakultäten auf.
Die Anzahl der -elementigen Teilmengen in einer -elementigen Menge ist
der Binomialkoeffizient
-
Insbesondere sind die Binomialkoeffizienten natürliche Zahlen.
Der Grund für diese Formel ist im Wesentlichen: Wenn man eine -elementige Teilmenge fixieren möchte, so hat man zunächst Wahlmöglichkeiten, dann 
Wahlmöglichkeiten bis man schließlich 
Wahlmöglichkeiten für das letzte, -te Element hat. Allerdings gibt es dabei 
viele Reihenfolgen, letztlich die gleiche Menge auszuwählen. Daher ist die richtige Anzahl gleich
-
Somit gibt es in der fünfelementigen Menge genau
-
zweielementige Teilmengen. Wenn diese fixiert ist, muss man noch sagen, wie der Dreierzyklus auf dem Komplement aussehen soll. Dafür gibt es jeweils zwei Möglichkeiten. Insgesamt gibt es also unter den Permutationen
-
fixpunktfreie Permutationen. Die Wahrscheinlichkeit, eine erlaubte Wichtelzuordnung zu ziehen, ist somit
-
Für deutlich größere wird es auch mit der Zykelmethode schwierig, die genaue Anzahl der fixpunktfreien Permutationen zu bestimmen. Wir werden gleich eine bessere Methode kennenlernen. Wir fassen kurz die berechneten Wahrscheinlichkeiten zusammen.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
In gerundeten Prozent ist dies
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Diese Zahlen gehen hoch und runter. Wir möchten uns mit dem Problem beschäftigen, wie sich diese Zahlen verhalten, wenn groß und größer wird, gegen unendlich geht.
Wie sieht es etwa für
aus? „Streben“ die Wahrscheinlichkeiten einer bestimmten Zahl entgegen oder varieren sie in alle Richtungen? Wenn sie gegen eine bestimmte Zahl streben, gegen welche? Gegen , gegen , gegen irgendwas dazwischen?
Heuristisch ist es hier schwierig, einen Tipp abzugeben. Einerseits ist, wenn groß ist, die Wahrscheinlichkeit, dass eine Person sich selbst zieht, sehr klein. Andererseits darf aber gar keine Person sich selbst ziehen, und das sind wiederum viele Bedingungen, und viele kleine Wahrscheinlichkeiten können sich zu einer großen Zahl aufaddieren.
Wir beschreiben nun eine einfache Möglichkeit, für jedes die Anzahl der fixpunktfreien Permutationen anzugeben. Betrachten wir zuerst das Problem, dass bei einer Permutation eine bestimmte Person auf sich selbst abgebildet wird. Dies haben wir schon weiter oben für einzelne Zahlen bestimmt, es gibt 
Permutationen von dieser Art, da ja die eine Person auf sich selbst abgebildet wird, und es ansonsten keine weitere Bedingung gibt, es sich also einfach um die Gesamtzahl der Permutationen von Personen handelt. Falsch wäre es jetzt, diese Anzahl -mal aufzuaddieren, da wir dann eine Permutation mit mehreren Fixpunkten mehrfach zählen würden.
Wir müssen die sogenannte Siebformel anwenden. Sie berechnet die Anzahl in einer Vereinigung von Mengen, wenn die einzelnen Anzahlen der Mengen und ihrer Durchschnitte bekannt sind. Im einfachsten Fall, bei
-
ist
-
Um die Elemente, die sowohl in als auch in sind, nicht doppelt zu zählen, muss man deren Anzahl abziehen. Bei drei Mengen
-
ist
-
Die allgemeine Formel für eine Vereinigung von Mengen 
wird im folgenden Satz beschrieben.
Es sei 
eine Menge und es seien
, 
,
endliche Teilmengen.
Für eine Teilmenge
sei
-
Dann ist
-
Kehren wir zu unserer Frage zurück. Zu jedem 
sei 
die Menge aller Permutationen auf 
, die 
auf sich selbst abbilden. Somit ist 
die Menge aller Permutationen, die mindestens einen Fixpunkt haben. Um die Siebformel anwenden zu können, müssen wir zu
die Durchschnitte 
verstehen. Bei dieser Menge handelt es sich um diejenigen Permutationen, für die alle Elemente aus 
Fixpunkte sind
(und die auch noch weitere Fixpunkte außerhalb von haben können).
Wenn die Anzahl von gleich ist, so gibt es 
solche Permutationen, da ja die Permutation auf die Identität sein muss und es außerhalb von keine Einschränkung gibt. Bei fixiertem wissen wir auch, wie viele Teilmengen mit Elementen zu berücksichtigen sind, nämlich 
. Mit diesen Zahlen ergibt sich nun mit Hilfe der Siebformel der Ausdruck
Die Wahrscheinlichkeit, eine wichtelkonforme
(fixpunktfreie)
bijektive Abbildung zu ziehen, ist somit gleich
Wir berechnen diese Ausdrücke für
und vergleichen sie mit den oben gefundenen. Es ist
-
-
-
-
-
Das Schöne an der jetzt gefundenen Formel ist, dass sich der nächste Wert durch Hinzunahme oder Abzug eines einfachen Bruches aus der zuvor berechneten Zahl ergibt.
- Die eulersche Zahl
Die eulersche Zahl
-
gehört zu den wichtigsten Zahlen der Mathematik überhaupt, und kommt in sehr vielen verschiedenen Gebieten der Mathematik vor. Das gleiche gilt für die zugehörige Exponentialfunktion, also die Abbildung
-
Die Exponentialfunktion hat die folgende Darstellung.
Für die
Exponentialfunktion
zur Basis 
gilt die Darstellung
-
Insbesondere ist also
-
und
-
Somit ist die oben ermittelte Formel für die Wahrscheinlichkeit, eine fixpuntfreie Permutation zu ziehen, gleich der Anfangssumme von 
. Insbesondere konvergiert diese Wahrscheinlichkeit gegen für gegen unendlich. Der numerische Wert ist
-
die oben zuletzt ausgerechneten Werte sind also schon ziemlich gut.
- Andere Auswahlverfahren
Beim üblichen Ziehen ist, wie wir gesehen haben, die Wahrscheinlichkeit, dass jemand sich selbst zieht und die Ziehung dann wiederholt werden muss, nicht zu vernachlässigen. Gibt es andere Auswahlverfahren? Es soll jede (fixpunktfreie) Zuordnung gleichwahrscheinlich sein und jede Person sollte außer der zu beschenkenden Person keinerlei weitere Information haben. Es sei zumindest
.
Wir besprechen zwei mögliche Ansätze.
Methode 1
Statt leerer Zettel nimmt man einseitig mit von bis durchnummerierte Zettel. Diese werden mit der Nummer nach unten hingelegt und jede Person zieht zufällig einen Zettel mit der Nummer, und zwar ohne den Zettel zurück zu legen. Nach diesem ersten Schritt besitzt also jede Person genau einen Zettel mit einer Nummer. Jede Person merkt sich ihre Nummer und schreibt auf ihrem Zettel den eigenen Namen auf der leeren Seite drauf. Die Zettel werden nun mit der Nummer nach oben wieder hingelegt, was die anderen nicht sehen dürfen. Im letzten Schritt zieht nun jede Person ihre Nachfolgerzahl, wenn also eine Person die Nummer gezogen hat, muss sie jetzt den Zettel mit der Nummer 
rausgreifen
(was im Fall 
als zu verstehen ist),
den Zettel umdrehen und den Namen lesen. Die darauf stehende Person ist zu beschenken, der Zettel wird mit der Nummer nach oben wieder zurückgelegt. Bei diesem letzten Schritt müssen wieder alle anderen Personen wegschauen, da es ja geheim sein soll, welche Nummer zu welcher Person gehört.
Diese Methode ist nicht ganz korrekt, da sie etwas Information über die Gesamtzuordnung mitliefert. Man weiß nämlich, dass die Person, der ich etwas schenken soll, definitiv nicht mein Schenker sein kann. Bei einer zufälligen Ziehung kann es aber sein, dass man selbst in einem Zweierzyklus landet.
Methode 2
Man macht für jede mögliche fixpunktfreie Permutation einen großen Umschlag
(das sind also sehr viele Umschläge),
der wiederum kleine Umschläge enthält. Auf jedem kleinen Umschlag steht außen ein Name und im Innern ist ein Zettel mit einem weiteren Namen. Jede Permutation kann man ja durch solche Umschläge kodieren, die kleinen Umschläge übernehmen also die Rolle der Wertetabelle.
Die Gruppe muss dann einen großen Umschlag wählen, ihn öffnen und jede Person öffnet dann den kleinen Umschlag, auf dem ihr Name steht. Die im kleinen Umschlag innen benannte Person ist zu bewichteln.
Diese Methode ist mathematisch völlig korrekt, aber praktisch undurchführbar.
