Wichteln/n Personen/Fixpunktfrei/Wahrscheinlichkeit/Limes/Aufgabe/Lösung

Eine Ziehung bedeutet eine bijektive Abbildung von ${}{\{1,\ldots ,n\}}$ nach ${}{\{1,\ldots ,n\}}$, eine wichtelkonforme Ziehung bedeutet eine fixpunktfreie bijektive Abbildung.

1. Es gibt nur die beiden Möglichkeiten Identität und Vertauschung, die Wahrscheinlichkeit, dass die Ziehung wichtelkonform ist, ist somit gleich ${}{\frac {1}{2}}$.
2. Es gibt ${}n!$ bijektive Abbildungen (Permutationen) einer ${}n$-elementigen Menge in sich selbst.
3. Zu jedem ${}i\in {\{1,\ldots ,n\}}$ sei ${}E_{i}$ das Ereignis, dass bei einer bijektiven Abbildung ${}i$ auf sich selbst abgebildet wird. Somit ist ${}E_{1}\cup E_{2}\cup \ldots \cup E_{n}$ das Ereignis, dass eine bijektive Abbildung mindestens einen Fixpunkt besitzt. Nach der Siebformel ist

   ${}{\#\left(E_{1}\cup E_{2}\cup \ldots \cup E_{n}\right)}=\sum _{k=1}^{n}(-1)^{k+1}{\left(\sum _{J\subseteq \{1,\ldots ,n\},\,{\#\left(J\right)}=k}{\#\left(E_{J}\right)}\right)}\,$

   mit

   ${}E_{J}=\bigcap _{i\in J}E_{i}\,.$

   Das Ereignis ${}E_{J}$ bedeutet also, dass alle Indizes aus ${}J$ Fixpunkte sind (und eventuell weitere). Dazu gibt es ${}(n-k)!$ Möglichkeiten, da die bijektiven Abbildungen mit ${}J$ als Fixpunkt den bijektiven Abbildungen von ${}{\{1,\ldots ,n\}}\setminus J$ in sich entsprechen. Da es ${}{\binom {n}{k}}$ ${}k$-elementige Teilmengen gibt, erhält man

   ${}{\begin{aligned}{\#\left(E_{1}\cup E_{2}\cup \ldots \cup E_{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}}$

   Das Ereignis, eine wichtelkonforme (fixpunktfreie) bijektive Abbildung zu ziehen, ist somit gleich

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

4. Für die Exponentialfunktion zur Basis ${}e$ gilt nach Fakt die Darstellung

   ${}e^{x}=\sum _{k=0}^{\infty }{\frac {x^{k}}{k!}}\,.$

   Somit ist die oben ermittelte Formel ${}\sum _{k=0}^{n}(-1)^{k}{\frac {1}{k!}}$ die Anfangssumme von ${}e^{-1}$. Insbesondere konvergiert ${}p(n)$ gegen ${}e^{-1}$.

Zur gelösten Aufgabe