Permutationen/Fixpunktfreiheit/e/Textabschnitt

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.

Wir erinnern an das Konzept eines Fixpunktes.

Definition

Es sei ${}M$ eine Menge und

$f\colon M\longrightarrow M$

eine Abbildung. Ein Element ${}x\in M$ mit ${}f(x)=x$ heißt Fixpunkt der Abbildung.

Es geht also um die fixpunktfreien Permutationen. Es sei ${}n$ die Anzahl der Personen, die wichteln möchten.

${}n=1\,.$

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 ${}0$, und die Wahrscheinlichkeit, dass eine Nichtwichtelzuordnung gezogen wird, ist ${}1$.

${}n=2\,.$

Nennen wir die Personen ${}A$ und ${}B$. Hier gibt es zwei Ziehmöglichkeiten, nämlich

${}P$	${}A$	${}B$
${}Z(P)$	${}A$	${}B$

und

${}P$	${}A$	${}B$
${}Z(P)$	${}B$	${}A$

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 ${}{\frac {1}{2}}$.

${}n=3\,.$

Nennen wir die Personen ${}A,B$ und ${}C$. Hier gibt es sechs Ziehmöglichkeiten, nämlich

${}P$	${}A$	${}B$	${}C$
${}Z(P)$	${}A$	${}B$	${}C$

${}P$	${}A$	${}B$	${}C$
${}Z(P)$	${}A$	${}C$	${}B$

${}P$	${}A$	${}B$	${}C$
${}Z(P)$	${}B$	${}A$	${}C$

${}P$	${}A$	${}B$	${}C$
${}Z(P)$	${}B$	${}C$	${}A$

${}P$	${}A$	${}B$	${}C$
${}Z(P)$	${}C$	${}A$	${}B$

${}P$	${}A$	${}B$	${}C$
${}Z(P)$	${}C$	${}B$	${}A$

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 ${}{\frac {1}{3}}$.

${}n=4\,.$

Nennen wir die Personen ${}A,B,C$ und ${}D$. Wir wissen, dass es insgesamt ${}24$ Permutationen gibt. Alle aufzulisten und einfach zu schauen, welche einen Fixpunkt haben und welche nicht, ist schon ziemlich aufwändig, siehe Aufgabe. Es ergeben sich ${}9$ fixpunktfreie Permutationen.

Wir werden mit einer besseren Abzählmöglichkeit arbeiten. Auf diese Zahl kann man schneller kommen, indem man die Struktur von Permutationen besser versteht. Entscheidend dafür ist das Konzept eines Zyklus.

Definition

Es sei ${}M$ eine endliche Menge und ${}\pi$ eine Permutation auf ${}M$. Man nennt ${}\pi$ einen Zykel der Ordnung ${}r$, wenn es eine ${}r$-elementige Teilmenge ${}Z\subseteq M$ derart gibt, dass ${}\pi$ auf ${}M\setminus Z$ die Identität ist und ${}\pi$ die Elemente aus ${}Z$ zyklisch vertauscht. Wenn ${}Z=\{z,\pi (z),\,\pi ^{2}(z),\ldots ,\pi ^{r-1}(z)\}$ ist, so schreibt man einfach

${}\pi =\langle z,\pi (z),\,\pi ^{2}(z),\ldots ,\pi ^{r-1}(z)\rangle \,.$

Dabei kann man statt ${}z$ jedes andere Element aus ${}Z$ als Anfangsglied nehmen. Die Menge ${}Z$ heißt auch der Wirkungsbereich des Zykels.

Definition

Es sei ${}M$ eine endliche Menge und ${}\sigma$ eine Permutation auf ${}M$. Es seien ${}Z_{1},\ldots ,Z_{k}$ die Wirkungsbereiche der Zyklen von ${}\sigma$ mit ${}n_{i}={\#\left(Z_{i}\right)}$. Es sei ${}x_{i}\in Z_{i}$ und ${}Z_{i}=\{x_{i},\sigma (x_{i}),\ldots ,\sigma ^{n_{i}-1}(x_{i})\}$. Dann nennt man

$\langle x_{1},\sigma (x_{1}),\ldots ,\sigma ^{n_{1}-1}(x_{1})\rangle \langle x_{2},\sigma (x_{2}),\ldots ,\sigma ^{n_{2}-1}(x_{2})\rangle \cdots \langle x_{k},\sigma (x_{k}),\ldots ,\sigma ^{n_{k}-1}(x_{k})\rangle$

die Zyklendarstellung von ${}\sigma$.

Wir erläutern dies kurz an einigen Permutationen auf einer vierelementigen Menge.

${}P$	${}A$	${}B$	${}C$	${}D$
${}Z(P)$	${}D$	${}B$	${}C$	${}A$

${}P$	${}A$	${}B$	${}C$	${}D$
${}Z(P)$	${}D$	${}C$	${}A$	${}B$

${}P$	${}A$	${}B$	${}C$	${}D$
${}Z(P)$	${}D$	${}C$	${}B$	${}A$

Bei der zuletzt angeführten Permutation wird ${}A$ auf ${}D$ und ${}D$ wiederum auf ${}A$ abgebildet, und ebenso wird ${}B$ mit ${}C$ vertauscht. Insgesamt kann man diese Abbildung als

$A\leftrightarrow D,\,\,\,B\leftrightarrow C$

darstellen. Man hat zwei Zykel der Länge zwei. In der darüber stehenden Permutation hat man die Zuordnung

$A\mapsto D\mapsto B\mapsto C.$

Man spricht von einem Zyklus der Länge ${}4$. In der darüber stehenden Permutation hat man die Zuordnung

$A\leftrightarrow D,\,\,\,B,\,\,\,C.$

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 ${}n=4$ 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 ${}3!=6$ Stück. Beim zweiten Typ geht es um die Einteilung der Menge in zwei Paare, danach ist alles festgelegt. Davon gibt es ${}3$ Stück. Jedenfalls ist die Wahrscheinlichkeit für eine fixpunktfreie Permutation bei vier Personen gleich ${}{\frac {9}{24}}$.

${}n=5\,.$

Hier gibt es schon ${}120$ Permutationen, eine Auflistung erübrigt sich. Es gibt aber wieder nur zwei Typen von fixpunktfreien Permutationen, nämlich einerseits die ${}5$-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, ${}4!=24$ Möglichkeiten. Vom zweiten Typ muss man die Anzahl der Möglichkeiten bestimmen, in einer fünfelementigen Menge eine zweielementige Teilmenge zu fixieren. In der fünfelementigen Menge gibt es genau

${}{\binom {5}{2}}={\frac {5\cdot 4}{2}}=10\,$

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 ${}120$ Permutationen

${}24+10\cdot 2=44\,$

fixpunktfreie Permutationen. Die Wahrscheinlichkeit, eine erlaubte Wichtelzuordnung zu ziehen, ist somit

${}{\frac {44}{120}}={\frac {11}{30}}\,.$

Für deutlich größere ${}n$ 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.

${}n$	${}1$	${}2$	${}3$	${}4$	${}5$	${}\ldots$
${}w(n)$	${}0$	${}{\frac {1}{2}}$	${}{\frac {1}{3}}$	${}{\frac {9}{24}}$	${}{\frac {11}{30}}$	${}?$

In gerundeten Prozent ist dies

${}n$	${}1$	${}2$	${}3$	${}4$	${}5$	${}\ldots$
${}w(n)$	${}0$	${}50$	${}33{,}3$	${}37{,}5$	${}36{,}6$	${}?$

Diese Zahlen gehen hoch und runter. Wir möchten uns mit dem Problem beschäftigen, wie sich diese Zahlen verhalten, wenn ${}n$ groß und größer wird, gegen unendlich geht.

Problem

Wie verhalten sich die Wahrscheinlichkeiten, dass sich bei einer zufälligen Ziehung unter ${}n$ Personen eine wichtelkonforme Zuordnung ergibt, wenn die Personenanzahl ${}n$ gegen unendlich strebt.

Wie sieht es etwa für ${}n=1000$ aus? „Streben“ die Wahrscheinlichkeiten einer bestimmten Zahl entgegen oder varieren sie in alle Richtungen? Wenn sie gegen eine bestimmte Zahl streben, gegen welche? Gegen ${}0$, gegen ${}1$, gegen irgendwas dazwischen?

Heuristisch ist es hier schwierig, einen Tipp abzugeben. Einerseits ist, wenn ${}n$ 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 ${}n$ 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 ${}(n-1)!$ 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 ${}n-1$ Personen handelt. Falsch wäre es jetzt, diese Anzahl ${}n$-mal aufzuaddieren, da wir dann eine Permutation mit mehreren Fixpunkten mehrfach zählen würden. Stattdessen müssen wir die Siebformel anwenden.

Lemma

Die Anzahl der fixpunktfreien Permutationen auf einer Menge mit ${}n$ Elementen ist

$\sum _{k=0}^{n}(-1)^{k}{\frac {n!}{k!}}.$

Beweis

Zu jedem ${}i\in {\{1,\ldots ,n\}}$ sei ${}A_{i}$ die Menge aller Permutationen auf ${}{\{1,\ldots ,n\}}$, die ${}i$ auf sich selbst abbilden. Somit ist ${}A_{1}\cup A_{2}\cup \ldots \cup A_{n}$ die Menge aller Permutationen, die mindestens einen Fixpunkt haben. Um die Siebformel anwenden zu können, müssen wir zu ${}J\subseteq {\{1,\ldots ,n\}}$ die Durchschnitte ${}\bigcap _{i\in J}A_{j}$ verstehen. Bei dieser Menge handelt es sich um diejenigen Permutationen, für die alle Elemente aus ${}J$ Fixpunkte sind (und die auch noch weitere Fixpunkte außerhalb von ${}J$ haben können). Wenn die Anzahl von ${}J$ gleich ${}k$ ist, so gibt es ${}(n-k)!$ solche Permutationen, da ja die Permutation auf ${}J$ die Identität sein muss und es außerhalb von ${}J$ keine Einschränkung gibt. Bei fixiertem ${}k$ wissen wir auch, wie viele Teilmengen ${}J$ mit ${}k$ Elementen zu berücksichtigen sind, nämlich ${}{\binom {n}{k}}$. Mit diesen Zahlen ergibt sich nun mit Hilfe der Siebformel der Ausdruck

${}{\begin{aligned}{\#\left(A_{1}\cup A_{2}\cup \ldots \cup A_{n}\right)}&=\sum _{k=1}^{n}(-1)^{k+1}{\binom {n}{k}}(n-k)!\\&=\sum _{k=1}^{n}(-1)^{k+1}{\frac {n!}{k!(n-k)!}}(n-k)!\\&=\sum _{k=1}^{n}(-1)^{k+1}{\frac {n!}{k!}}.\end{aligned}}$

Somit ist die Anzahl der fixpunktfreien Permutationen gleich

${}n!-\sum _{k=1}^{n}(-1)^{k+1}{\frac {n!}{k!}}=n!+\sum _{k=1}^{n}(-1)^{k}{\frac {n!}{k!}}=\sum _{k=0}^{n}(-1)^{k}{\frac {n!}{k!}}\,.$

$\Box$

Die Wahrscheinlichkeit, eine wichtelkonforme (fixpunktfreie) Permutation zu ziehen, ist somit gleich

${}{\frac {\sum _{k=0}^{n}(-1)^{k}{\frac {1}{k!}}}{n!}}=\sum _{k=0}^{n}(-1)^{k}{\frac {1}{k!}}\,.$

Das Schöne an der jetzt gefundenen Formel ist, dass sich der nächste Wert (wenn man ${}n$ auf ${}n+1$ erhöht) durch Hinzunahme oder Abzug eines einfachen Bruches aus der zuvor berechneten Zahl ergibt. Vor allem aber erinnert die Formel an die Definition der Exponentialreihe, die die Exponentialfunktion beschreibt.

Definition

Die Funktion

$\mathbb {R} \longrightarrow \mathbb {R} ,\,x\longmapsto \exp x:=\sum _{k=0}^{\infty }{\frac {x^{k}}{k!}},$

heißt (reelle) Exponentialfunktion.

Dabei ist

${}e=\exp 1=\sum _{k=0}^{n}{\frac {1}{k!}}=1+1+{\frac {1}{2}}+{\frac {1}{6}}+{\frac {1}{24}}+{\frac {1}{120}}+\ldots =2{,}71828\ldots \,$

die eulersche Zahl und

${}e^{-1}=\sum _{k=0}^{n}(-1)^{k}{\frac {1}{k!}}=1-1+{\frac {1}{2}}-{\frac {1}{6}}+{\frac {1}{24}}-{\frac {1}{120}}\pm \ldots \,$

ist die inverse eulersche Zahl. Somit ist die oben ermittelte Formel für die Wahrscheinlichkeit, eine fixpuntfreie Permutation zu ziehen, gleich der Anfangssumme von ${}e^{-1}$. Insbesondere konvergiert diese Wahrscheinlichkeit ${}w(n)$ gegen ${}e^{-1}$ für ${}n$ gegen unendlich. Der numerische Wert ist

${}e^{-1}=0{,}367879\ldots \,,$

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 ${}n\geq 3$. Wir besprechen zwei mögliche Ansätze.

Methode 1

Statt leerer Zettel nimmt man einseitig mit von ${}1$ bis ${}n$ 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 wieder nicht sehen dürfen. Im letzten Schritt zieht nun jede Person ihre Nachfolgerzahl, wenn also eine Person die Nummer ${}k$ gezogen hat, muss sie jetzt den Zettel mit der Nummer ${}k+1$ rausgreifen (was im Fall ${}k=n$ als ${}1$ 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 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 ${}n$ 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 zusammen ü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.