Wir definieren
\( A_{i}=\{\pi \mid \pi(i)=i\} \)
also die Menge aller Permutationen, welche einen Fixpunkt an der Stelle \( i \) haben. Wir wollen
\(\begin{aligned} n !-\left|\bigcup_{1 \leq i \leq n} A_{i}\right| \end{aligned} \)
berechnen. Mit der Siebformel ergibt sich
\(\begin{aligned} \left|\bigcup_{1 \leq i \leq n} A_{i}\right|=\sum \limits_{\varnothing \neq I \subseteq\{1,2, \ldots, n\}}(-1)^{|I|+1}\left|\bigcap_{i \in I} A_{i}\right| .\end{aligned} \)
Berechnen wir jetzt also ein allgemeines Glied: Nehmen wir an, wir möchten die Menge an Permutationen bestimmen welche an den Stellen \( i \in\left\{i_{1}, i_{2}, \ldots, i_{k}\right\} \) einen Fixpunkt haben. Dann gibt es ja exakt \( (n-k) ! \) von diesen, da wir \( k \) Stellen fixieren, für welche es jeweils nur eine mögliche Belegung gibt, und die anderen Stellen beliebig permutieren können. Damit ergibt sich also
\(\begin{aligned} \sum_{\varnothing \neq I\subseteq \{1, 2, \ldots, n\}}^{} (-1)^{|I|+1}\left| \bigcap_{i \in I}^{} A_{i} \right | &= \sum_{k=1}^{n} \sum_{\substack{\varnothing \neq I\subseteq \{1, 2, \ldots, n\}, \\ |I|=k}}^{}(-1)^{k+1} \left| \bigcap_{i \in I}^{} A_{i} \right | \\[5pt] &= \sum_{k=1}^{n}(-1)^{k+1} \binom{n}{k} (n-k)! \\[5pt] &= \sum_{k=1}^{n}(-1)^{k+1} \frac{n!}{(n-k)!k!} (n-k)! \\[5pt] &= \sum_{k=1}^{n}(-1)^{k+1} \frac{n!}{k!} = n! \sum_{k=1}^{n} (-1)^{k+1} \frac{1}{k!}.\end{aligned}\)
Damit haben wir also
\( n !-n ! \sum \limits_{k=1}^{n}(-1)^{k+1} \frac{1}{k !}=n !\left(1-\sum \limits_{k=1}^{n}(-1)^{k+1} \frac{1}{k !}\right)=n ! \sum \limits_{k=0}^{n}(-1)^{k} \frac{1}{k !} . \)
Schöne Aufgabe, hatte ich bisher noch nicht gesehen!
