🎓 Ui, fast schon Prüfungszeit? Hier geht's zur Mathe-Prüfungsvorbereitung.
Springe zum Inhalt oder Footer
SerloDie freie Lernplattform

4Wie oft muss im Schnitt neu gezogen werden?

Wir haben uns schon überlegt, wie wir Wichteln mathematisch beschreiben können: Gesucht ist eine fixpunktfreie Permutation der Mitspieler, also eine bijektive Abbildung σ ⁣:{1,,n}{1,,n}\sigma\colon\left\{1,\ldots,n\right\}\to\left\{1,\ldots,n\right\} ohne Fixpunkte. Das heißt, es soll σ(k)k\sigma\left(k\right)\ne k für alle k{1,,n}k\in\left\{1,\ldots,n\right\} gelten. Üblicherweise versucht man, eine Permutation durch Ziehen von Namenszetteln aus einem Hut zu erzeugen: Das entspricht genau einer bijektiven Zuordnung zwischen Wichteln (das sind die Personen {1,,n}\left\{1,\ldots,n\right\}) und Co-Wichteln (ebenfalls die Personen {1,,n}\left\{1,\ldots,n\right\}). Die so entstandene Permutation ist aber nicht fixpunktfrei, wenn eine Person ihren eigenen Namen zieht. In diesem Fall muss man neu ziehen. Aber wie wahrscheinlich ist es eigentlich, dass das passiert?

Wir gehen davon aus, dass die Namenszettel im Hut gut gemischt sind. Dann liefert jede Ziehung von Namen aus dem Hut mit gleicher Wahrscheinlichkeit eine der n!n! möglichen Permutationen. Es handelt sich hier also um ein Urnenmodell: Aus den n!n! möglichen Permutationen wird durch eine Ziehung gleichverteilt eine ausgewählt. Wenn wir wissen wollen, wie wahrscheinlich es ist, dass die durch die Ziehung bestimmte Permutation fixpunktfrei ist, müssen wir uns zunächst überlegen, wie viele fixpunktfreie Permutationen von {1,,n}\left\{1,\ldots,n\right\} es gibt.

Beispiel. Für n=1n=1 ist die einzig mögliche Permutation die Abbildung σ:{1}{1}\sigma:\left\{1\right\}\to\left\{1\right\}, welche 11 auf 11 abbildet. Diese ist nicht fixpunktfrei. Für n=2n=2 gibt es zwei mögliche Permutationen: Erstens die Permutation σ1:{1,2}{1,2}\sigma_1:\left\{1{,}2\right\}\to\left\{1{,}2\right\} mit σ1(1)=1\sigma_1\left(1\right)=1 und σ1(2)=2\sigma_1\left(2\right)=2, und zweitens die Permutation σ2:{1,2}{1,2}\sigma_2:\left\{1{,}2\right\}\to\left\{1{,}2\right\} mit σ2(1)=2\sigma_2\left(1\right)=2 und σ2(2)=1\sigma_2\left(2\right)=1. Von diesen ist die zweite fixpunktfrei, die erste nicht. Es gibt also genau eine fixpunktfreie Permutation. Von den sechs möglichen Permutationen im Fall n=3n=3 sind nur zwei Permutationen σ1,σ2\sigma_1,\sigma_2 fixpunktfrei, wobei σ1(1)=2\sigma_1\left(1\right)=2, σ1(2)=3\sigma_1\left(2\right)=3, σ1(3)=1\sigma_1\left(3\right)=1 bzw. σ2(1)=3\sigma_2\left(1\right)=3, σ2(2)=1\sigma_2\left(2\right)=1, σ2(3)=2\sigma_2\left(3\right)=2.

Allgemein gilt: Die Anzahl dnd_n der fixpunktfreien Permutationen von {1,,n}\left\{1,\ldots,n\right\} ist

Das kann man mithilfe des sogenannten Einschluss-Ausschluss-Prinzips berechnen, wie du zum Beispiel auf Wikipedia nachlesen kannst. Weil es insgesamt n!n! Permutationen von {1,,n}\left\{1,\ldots,n\right\} gibt, beträgt der Anteil der fixpunktfreien Permutationen somit

Da beim Ziehen aus dem Hut jede Permutation mit der gleichen Wahrscheinlichkeit herauskommen kann, ist die Wahrscheinlichkeit pnp_n, dass die zufällig gezogene Permutation von {1,,n}\left\{1,\ldots,n\right\} fixpunktfrei ist, genau der Anteil der fixpunktfreien Permutationen. Es gilt also pn=dnn!p_n=\frac{d_n}{n!}.

Beispiel. Für die Menge {1,,n}\left\{1,\ldots,n\right\}, n10n\le10, zeigt die Tabelle die Anzahl dnd_n der fixpunktfreien Permutationen, die Anzahl n!n! aller möglichen Permutationen und den Anteil pn=dnn!p_n=\frac{d_n}{n!} der fixpunktfreien Permutationen (Quelle: Wikipedia):

nn

dnd_n

n!n!

pnp_n

1

0

1

0

2

1

2

0,5

3

2

6

0,33333333…

4

9

24

0,375

5

44

120

0,36666666…

6

265

720

0,36805555…

7

1.854

5.040

0,36785714…

8

14.833

40.320

0,36788194…

9

133.496

362.880

0,36787918…

10

1.334.961

3.628.800

0,36787946…

Nun können wir für eine gegebene feste Teilnehmerzahl nn berechnen, was die erwartete Anzahl an Ziehungen ist, die notwendig sind, um eine fixpunktfreie Permutation zu erwischen. Die Wahrscheinlichkeit, eine fixpunktfreie Permutation zu erwischen, bleibt in jeder Ziehung gleich und beträgt pnp_n. Mithilfe der sogenannten geometrischen Verteilung kann man sich überlegen, dass die erwartete Anzahl an benötigten Ziehungen gleich 1pn\frac{1}{p_n} ist. Intuitiv ergibt das Sinn: Wenn beispielsweise die Wahrscheinlichkeit für das Eintreten eines bestimmten Ergebnisses 13\frac{1}{3} beträgt, dann erwarten wir, dass „im Durchschnitt“ drei, also 113\frac{1}{\frac{1}{3}} Versuche nötig sind, um dieses Ergebnis zu erzielen.

Beispiel. Aufbauend auf der vorherigen Tabelle, können wir für n10n\le10 die erwartete Anzahl 1pn=n!dn\frac{1}{p_n}=\frac{n!}{d_n} an benötigten Ziehungen angeben. Den Fall n=1n=1 müssen wir natürlich weglassen, da ja die Wahrscheinlichkeit p1p_1, eine fixpunktfreie Permutation von {1}\left\{1\right\} zu ziehen, gleich null ist.

nn

dnd_n

n!n!

1/pn1/p_n

2

1

2

2

3

2

6

3

4

9

24

2,6666666

5

44

120

2,7272727…

6

265

720

2,7169811…

7

1.854

5.040

2,7184466…

8

14.833

40.320

2,7182633

9

133.496

362.880

2,7182836…

10

1.334.961

3.628.800

2,7182816…

Wenn wir die Werte für 1pn\frac{1}{p_n} auf eine ganze Zahl runden, erhalten wir, dass im Schnitt etwa drei Ziehungen nötig sind, bis man eine fixpunktfreie Permutation erwischt! Wir wollen uns nun eine Methode überlegen, mit der man garantiert nur eine Ziehung braucht, um jedem Wichtel seinen Co-Wichtel zuzuordnen.


Dieses Werk steht unter der freien Lizenz
CC BY-SA 4.0Was bedeutet das?