Kurs:Diskrete Mathematik (Osnabrück 2020)/Vorlesung 3/latex
\setcounter{section}{3}
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Waeller356.jpg} }
\end{center}
\bildtext {Zu Beginn der Vorlesung ist sie schon da, kommt auf dich zu und begrüßt dich. Da macht gleich alles noch viel mehr Spaß!} }
\bildlizenz { Waeller356.jpg } {} {Odatrulle} {Commons} {CC-by-sa 4.0} {}
\zwischenueberschrift{Die Siebformel}
Die Siebformel berechnet die Anzahl in einer Vereinigung von Mengen, wenn die einzelnen Anzahlen der Mengen und ihrer Durchschnitte bekannt sind. Im einfachsten Fall, bei
\mavergleichskettedisp
{\vergleichskette
{M
}
{ =} {A \cup B
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{,}
ist
\mavergleichskettedisp
{\vergleichskette
{ { \# \left( M \right) }
}
{ =} { { \# \left( A \right) } + { \# \left( B \right) } - { \# \left( A \cap B \right) }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Um die Elemente, die sowohl in $A$ als auch in $B$ sind, nicht doppelt zu zählen, muss man deren Anzahl abziehen.
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Inclusion-exclusion.svg} }
\end{center}
\bildtext {} }
\bildlizenz { Inclusion-exclusion.svg } {} {Chris-martin} {Commons} {CC-by-sa 3.0} {}
Bei drei Mengen
\mavergleichskettedisp
{\vergleichskette
{M
}
{ =} {A \cup B \cup C
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{,}
ist
\mavergleichskettedisp
{\vergleichskette
{ { \# \left( M \right) }
}
{ =} { { \# \left( A \right) } + { \# \left( B \right) } + { \# \left( C \right) } - { \# \left( A \cap B \right) }- { \# \left( A \cap C \right) }- { \# \left( B \cap C \right) } + { \# \left( A \cap B \cap C \right) }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
\inputfaktbeweis
{Endliche Menge/Siebformel/Fakt}
{Satz}
{}
{
\faktsituation {Es sei $G$ eine Menge und es seien
\mathbed {A_i \subseteq G} {}
{i =1 , \ldots , n} {}
{} {} {} {,}
\definitionsverweis {endliche Teilmengen}{}{.}
Für eine Teilmenge
\mavergleichskette
{\vergleichskette
{J
}
{ \subseteq }{ { \{ 1 , \ldots , n \} }
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
sei
\mavergleichskettedisp
{\vergleichskette
{ A_J
}
{ =} { \bigcap_{i \in J} A_i
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}}
\faktfolgerung {Dann ist
\mavergleichskettedisp
{\vergleichskette
{ { \# \left( \bigcup_{i = 1}^n A_i \right) }
}
{ =} { \sum_{k = 1}^n (-1)^{k+1} { \left( \sum_{J \subseteq \{1 , \ldots , n \} ,\, { \# \left( J \right) } = k } { \# \left( A_J \right) } \right) }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}}
\faktzusatz {}
\faktzusatz {}
}
{
Wir beweisen die Aussage durch Induktion über $n$, wobei der Fall
\mavergleichskette
{\vergleichskette
{n
}
{ = }{1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
klar ist. Für
\mavergleichskette
{\vergleichskette
{n
}
{ = }{2
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
siehe
Aufgabe 1.18.
Es ist
\mavergleichskettealignhandlinks
{\vergleichskettealignhandlinks
{ { \# \left( \bigcup_{i = 1}^{n+1} A_i \right) }
}
{ =} { { \# \left( { \left( \bigcup_{i = 1}^{n} A_i \right) } \cup A_{n+1} \right) }
}
{ =} { { \# \left( \bigcup_{i = 1}^{n} A_i \right) } + { \# \left( A_{n+1} \right) } - { \# \left( { \left( \bigcup_{i = 1}^{n} A_i \right) } \cap A_{n+1} \right) }
}
{ =} { \sum_{k = 1}^n (-1)^{k+1} { \left( \sum_{J \subseteq \{1 , \ldots , n \} ,\, { \# \left( J \right) } = k } { \# \left( A_J \right) } \right) } + { \# \left( A_{n+1} \right) } - { \# \left( \bigcup_{i = 1}^{n} { \left( A_i \cap A_{n+1} \right) } \right) }
}
{ =} { \sum_{k = 1}^n (-1)^{k+1} { \left( \sum_{J \subseteq \{1 , \ldots , n \} ,\, { \# \left( J \right) } = k } { \# \left( A_J \right) } \right) } + { \# \left( A_{n+1} \right) } -\sum_{\ell = 1}^n (-1)^{\ell+1} { \left( \sum_{L \subseteq \{1 , \ldots , n \} ,\, { \# \left( L \right) } = \ell } { \# \left( A_L \cap A_{n+1} \right) } \right) }
}
}
{
\vergleichskettefortsetzungalign
{ =} { \sum_{k = 1}^{n+1} (-1)^{k+1} { \left( \sum_{J \subseteq \{1 , \ldots , n ,n+1 \} ,\, n+1 \notin J ,\, { \# \left( J \right) } = k } { \# \left( A_J \right) } \right) } + \sum_{k = 1}^{n+1} (-1)^{k+1} { \left( \sum_{J \subseteq \{1 , \ldots , n ,n+1 \} ,\, { \# \left( J \right) } = k,\, n+1 \in J } { \# \left( A_J \right) } \right) }
}
{ =} { \sum_{k = 1}^{n+1} (-1)^{k+1} { \left( \sum_{J \subseteq \{1 , \ldots , n ,n+1 \} ,\, { \# \left( J \right) } = k } { \# \left( A_J \right) } \right) }
}
{ } {}
{ } {}
}
{}{,}
wobei wir für die zweite Gleichung den Fall von zwei Teilmengen und für die dritte und die vierte Gleichung die Induktionsvoraussetzung verwendet haben. Für die fünfte Gleichung führen wir hinten die Indexverschiebung
\mavergleichskette
{\vergleichskette
{ k
}
{ = }{ \ell +1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
durch und der mittlere Term wird in die rechte Summe integriert. Die sechste Gleichung ergibt sich von unten nach oben gelesen, wenn man die Teilmengen
\mavergleichskettedisp
{\vergleichskette
{J
}
{ \subseteq} { \{1 , \ldots , n ,n+1 \}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
je nachdem aufspaltet, ob $n+1$ dazu gehört oder nicht.
Man spricht auch vom \stichwort {Prinzip der Inklusion und Exklusion} {.} Wir geben noch einen zweiten Beweis für die vorstehende Aussage.
Beide Seiten der Siebformel verhalten sich additiv, wenn eine disjunkte Zerlegung der Grundmenge vorliegt. Deshalb genügt es, die Aussage für eine einelementige Menge zu zeigen
\zusatzklammer {man fragt sich für jedes Element, wie oft es links und wie oft es rechts gezählt wird} {} {.}
Sei also
\mavergleichskette
{\vergleichskette
{G
}
{ = }{ \{x\}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Dann gibt es für die Teilmengen $A_i$ nur die Möglichkeiten
\mavergleichskette
{\vergleichskette
{A_i
}
{ = }{\{x\}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
oder
\mavergleichskette
{\vergleichskette
{A_i
}
{ = }{ \emptyset
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Wir können annehmen, dass
\mavergleichskettedisp
{\vergleichskette
{A_1
}
{ =} { \ldots
}
{ =} {A_r
}
{ =} { \{x\}
}
{ } {
}
}
{}{}{}
und
\mavergleichskettedisp
{\vergleichskette
{A_{r+1}
}
{ =} { \ldots
}
{ =} {A_n
}
{ =} { \emptyset
}
{ } {
}
}
{}{}{}
ist. Zu einer Teilmenge
\mavergleichskette
{\vergleichskette
{J
}
{ \subseteq }{ { \{ 1 , \ldots , n \} }
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist dann
\mavergleichskette
{\vergleichskette
{A_J
}
{ = }{ \{x\}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
einelementig genau dann, wenn
\mavergleichskette
{\vergleichskette
{J
}
{ \subseteq }{ { \{ 1 , \ldots , r \} }
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist, und sonst immer leer. Daher ist die rechte Seite gleich
\mavergleichskettealignhandlinks
{\vergleichskettealignhandlinks
{\sum_{k = 1}^r (-1)^{k+1} { \left( \sum_{J \subseteq \{1 , \ldots , r \} ,\, { \# \left( J \right) } = k } { \# \left( A_J \right) } \right) }
}
{ =} { \sum_{k = 1}^r (-1)^{k+1} \sum_{J \subseteq \{1 , \ldots , r \} ,\, { \# \left( J \right) } = k } 1
}
{ =} { \sum_{k = 1}^r (-1)^{k+1} \binom { r } { k }
}
{ } {
}
{ } {}
}
{}
{}{.}
Dies ist bei
\mavergleichskette
{\vergleichskette
{r
}
{ = }{0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gleich $0$ und sonst nach
Aufgabe 3.2
gleich $1$, was mit der linken Seite übereinstimmt.
\inputbemerkung
{}
{
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Laboratory_sieves_BMK.jpg} }
\end{center}
\bildtext {} }
\bildlizenz { Laboratory_sieves_BMK.jpg } {} {User:BMK} {Commons} {CC-by-sa 3.0} {}
Die Bezeichnung \anfuehrung{Siebformel}{} kann man sich folgendermaßen erklären: Es sei eine Menge von Sandkörnern, Kristallen oder Diamanten gegeben, die unterschiedliche Größen und Formen besitzen. Es sei eine Menge von Sieben
\mathl{S_1 , \ldots , S_n}{} gegeben, mit denen man den Sand sieben möchte. Dann ist $A_i$ die Menge der Sandkörner, die durch das Sieb $S_i$ durchfallen, und zu einer Teilmenge
\mavergleichskette
{\vergleichskette
{J
}
{ \subseteq }{ { \{ 1 , \ldots , n \} }
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist dann $A_J$ die Menge der Sandkörner, die durch die Siebe
\mathbed {S_i} {}
{i \in J} {}
{} {} {} {,}
\zusatzklammer {wenn man sie übereinander hält} {} {}
durchfallen.
}
Als eine erste Anwendung der Siebformel besprechen wir fixpunktfreie Permutationen.
\zwischenueberschrift{Fixpunktefreie Permutationen}
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.
\inputdefinition
{}
{
Es sei $M$ eine Menge und
\maabbdisp {f} {M} {M
} {}
eine
\definitionsverweis {Abbildung}{}{.}
Ein Element
\mavergleichskette
{\vergleichskette
{x
}
{ \in }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
mit
\mavergleichskette
{\vergleichskette
{f(x)
}
{ = }{x
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
heißt \definitionswort {Fixpunkt}{} der Abbildung.
}
Es geht also um die fixpunktfreien Permutationen. Es sei $n$ die Anzahl der Personen, die wichteln möchten.
\mavergleichskettedisp
{\vergleichskette
{n
}
{ =} {1
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Hier gibt es nur eine Ziehung, die eine Person zieht sich selbst, dies ist unvermeidbar. Die Wahrscheinlichkeit, dass eine
\zusatzklammer {erlaubte} {} {}
Wichtelzuordnung gezogen wird, ist also $0$, und die Wahrscheinlichkeit, dass eine Nichtwichtelzuordnung gezogen wird, ist $1$.
\mavergleichskettedisp
{\vergleichskette
{n
}
{ =} {2
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Nennen wir die Personen
\mathkor {} {A} {und} {B} {.}
Hier gibt es zwei Ziehmöglichkeiten, nämlich
\wertetabellezweiausteilzeilen { $P$ }
{\mazeileundzwei {A} {B
} }
{ $Z(P)$ }
{\mazeileundzwei {A} {B} }
und
\wertetabellezweiausteilzeilen { $P$ }
{\mazeileundzwei {A} {B
} }
{ $Z(P)$ }
{\mazeileundzwei {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
\mathl{{ \frac{ 1 }{ 2 } }}{.}
\mavergleichskettedisp
{\vergleichskette
{n
}
{ =} {3
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Nennen wir die Personen
\mathkor {} {A,B} {und} {C} {.}
Hier gibt es sechs Ziehmöglichkeiten, nämlich
\wertetabelledreiausteilzeilen { $P$ }
{\mazeileunddrei {A} {B} {C
} }
{ $Z(P)$ }
{\mazeileunddrei {A} {B} {C} }
\wertetabelledreiausteilzeilen { $P$ }
{\mazeileunddrei {A} {B} {C
} }
{ $Z(P)$ }
{\mazeileunddrei {A} {C} {B} }
\wertetabelledreiausteilzeilen { $P$ }
{\mazeileunddrei {A} {B} {C
} }
{ $Z(P)$ }
{\mazeileunddrei {B} {A} {C} }
\wertetabelledreiausteilzeilen { $P$ }
{\mazeileunddrei {A} {B} {C
} }
{ $Z(P)$ }
{\mazeileunddrei {B} {C} {A} }
\wertetabelledreiausteilzeilen { $P$ }
{\mazeileunddrei {A} {B} {C
} }
{ $Z(P)$ }
{\mazeileunddrei {C} {A} {B} }
\wertetabelledreiausteilzeilen { $P$ }
{\mazeileunddrei {A} {B} {C
} }
{ $Z(P)$ }
{\mazeileunddrei {C} {B} {A} }
Von den sechs Möglichkeiten sind nur die vierte und die fünfte ohne Selbstziehung
\zusatzklammer {ohne Fixpunkt} {} {.}
Die Wahrscheinlichkeit für eine fixpunktfreie Ziehung ist demnach
\mathl{{ \frac{ 1 }{ 3 } }}{.}
\mavergleichskettedisp
{\vergleichskette
{n
}
{ =} {4
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Nennen wir die Personen
\mathkor {} {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 3.14.
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.
\inputdefinition
{}
{
Es sei $M$ eine endliche Menge und $\pi$ eine
\definitionsverweis {Permutation}{}{}
auf $M$. Man nennt $\pi$ einen \definitionswort {Zykel der Ordnung}{} $r$, wenn es eine $r$-elementige Teilmenge
\mavergleichskette
{\vergleichskette
{Z
}
{ \subseteq }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
derart gibt, dass $\pi$ auf
\mathl{M \setminus Z}{} die Identität ist und $\pi$ die Elemente aus $Z$ zyklisch vertauscht. Wenn
\mavergleichskette
{\vergleichskette
{Z
}
{ = }{ \{z, \pi(z),\, \pi^2(z) , \ldots , \pi^{r-1}(z)\}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist, so schreibt man einfach
\mavergleichskettedisp
{\vergleichskette
{ \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 \stichwort {Wirkungsbereich} {} des Zykels.
\inputdefinition
{}
{
Es sei $M$ eine endliche Menge und $\sigma$ eine
\definitionsverweis {Permutation}{}{}
auf $M$. Es seien
\mathl{Z_1 , \ldots , Z_k}{} die Wirkungsbereiche der
\definitionsverweis {Zyklen}{}{}
von $\sigma$ mit
\mavergleichskette
{\vergleichskette
{n_i
}
{ = }{ { \# \left( Z_i \right) }
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Es sei
\mavergleichskette
{\vergleichskette
{x_i
}
{ \in }{Z_i
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskette
{\vergleichskette
{Z_i
}
{ = }{\{x_i, \sigma(x_i) , \ldots , \sigma^{n_i-1}(x_i)\}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Dann nennt man
\mathdisp {\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 \definitionswort {Zyklendarstellung}{} von $\sigma$.
}
Wir erläutern dies kurz an einigen Permutationen auf einer vierelementigen Menge.
\wertetabellevierausteilzeilen { $P$ }
{\mazeileundvier {A} {B} {C} {D
} }
{ $Z(P)$ }
{\mazeileundvier {D} {B} {C} {A} }
\wertetabellevierausteilzeilen { $P$ }
{\mazeileundvier {A} {B} {C} {D
} }
{ $Z(P)$ }
{\mazeileundvier {D} {C} {A} {B} }
\wertetabellevierausteilzeilen { $P$ }
{\mazeileundvier {A} {B} {C} {D
} }
{ $Z(P)$ }
{\mazeileundvier {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
\mathdisp {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
\mathdisp {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
\mathdisp {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
\mavergleichskette
{\vergleichskette
{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
\mavergleichskette
{\vergleichskette
{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
\mathl{{ \frac{ 9 }{ 24 } }}{.}
\mavergleichskettedisp
{\vergleichskette
{n
}
{ =} {5
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Hier gibt es schon
\mathl{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,
\mavergleichskette
{\vergleichskette
{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
\mavergleichskettedisp
{\vergleichskette
{ \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
\mavergleichskettedisp
{\vergleichskette
{ 24+ 10 \cdot 2
}
{ =} { 44
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
fixpunktfreie Permutationen. Die Wahrscheinlichkeit, eine erlaubte Wichtelzuordnung zu ziehen, ist somit
\mavergleichskettedisp
{\vergleichskette
{ { \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.
\wertetabellesechsausteilzeilen { $n$ }
{\mazeileundfuenf {1} {2} {3} {4} {5} }
{ { \ldots
} }
{ $w(n)$ }
{\mazeileundfuenf {0} { { \frac{ 1 }{ 2 } } } { { \frac{ 1 }{ 3 } } } { { \frac{ 9 }{ 24 } } } { { \frac{ 11 }{ 30 } } } }
{ { ? } }
In gerundeten Prozent ist dies
\wertetabellesechsausteilzeilen { $n$ }
{\mazeileundfuenf {1} {2} {3} {4} {5} }
{ { \ldots
} }
{ $w(n)$ }
{\mazeileundfuenf {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.
\inputproblem{}
{
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
\mavergleichskette
{\vergleichskette
{n
}
{ = }{1000
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
aus? \anfuehrung{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
\mathl{(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.
\inputfaktbeweis
{Permutation/Fixpunktfrei/Formel/Fakt}
{Lemma}
{}
{
\faktsituation {Die Anzahl der
\definitionsverweis {fixpunktfreien}{}{}
\definitionsverweis {Permutationen}{}{}
auf einer Menge mit $n$ Elementen ist}
\faktfolgerung {
\mathdisp {\sum_{k = 0}^n (-1)^{k} { \frac{ n! }{ k! } }} { . }
}
\faktzusatz {}
\faktzusatz {}
}
{
Zu jedem
\mavergleichskette
{\vergleichskette
{i
}
{ \in }{{ \{ 1 , \ldots , n \} }
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
sei $A_i$ die Menge aller Permutationen auf
\mathl{{ \{ 1 , \ldots , n \} }}{,} die $i$ auf sich selbst abbilden. Somit ist
\mathl{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
\mavergleichskette
{\vergleichskette
{J
}
{ \subseteq }{ { \{ 1 , \ldots , n \} }
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
die Durchschnitte
\mathl{\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
\zusatzklammer {und die auch noch weitere Fixpunkte außerhalb von $J$ haben können} {} {.}
Wenn die Anzahl von $J$ gleich $k$ ist, so gibt es
\mathl{(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
\mathl{\binom { n } { k }}{.} Mit diesen Zahlen ergibt sich nun mit Hilfe der Siebformel der Ausdruck
\mavergleichskettealign
{\vergleichskettealign
{{ \# \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! } }
}
{ } {
}
}
{}
{}{.}
Somit ist die Anzahl der fixpunktfreien Permutationen gleich
\mavergleichskettedisp
{\vergleichskette
{ 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! } }
}
{ } {
}
{ } {
}
}
{}{}{.}
Die Wahrscheinlichkeit, eine wichtelkonforme
\zusatzklammer {fixpunktfreie} {} {}
Permutation zu ziehen, ist somit gleich
\mavergleichskettedisp
{\vergleichskette
{ { \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
\zusatzklammer {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.
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Exponential function.svg} }
\end{center}
\bildtext {} }
\bildlizenz { Exponential function.svg } {} {Luks} {Commons} {gemeinfrei,} {}
\inputdefinition
{}
{
Die \definitionsverweis {Funktion}{}{} \maabbeledisp {} {\R} {\R } {x} { \exp x \defeq \sum_{ k =0}^\infty \frac{ x^{ k } }{k!} } {,} heißt \zusatzklammer {reelle} {} {} \definitionswort {Exponentialfunktion}{.}
}
Dabei ist
\mavergleichskettedisp
{\vergleichskette
{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 \stichwort {eulersche Zahl} {} und
\mavergleichskettedisp
{\vergleichskette
{ 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
\mathl{e^{-1}}{.} Insbesondere konvergiert diese Wahrscheinlichkeit
\mathl{w(n)}{} gegen
\mathl{e^{-1}}{} für $n$ gegen unendlich. Der numerische Wert ist
\mavergleichskettedisp
{\vergleichskette
{e^{-1}
}
{ =} { 0{,}367879 \ldots
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{,}
die oben zuletzt ausgerechneten Werte sind also schon ziemlich gut.
\zwischenueberschrift{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
\mavergleichskette
{\vergleichskette
{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
\mathl{k+1}{} rausgreifen
\zusatzklammer {was im Fall
\mathl{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 \zusatzklammer {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.