Permutation/Fixpunktfrei/Formel/Fakt/Beweis

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!}}\,.$

Zur bewiesenen Aussage