Permutation/Fixpunktfrei/Formel/Fakt/Beweis

Zu jedem ${\displaystyle {}i\in {\{1,\ldots ,n\}}}$ sei ${\displaystyle {}A_{i}}$ die Menge aller Permutationen auf ${\displaystyle {}{\{1,\ldots ,n\}}}$, die ${\displaystyle {}i}$ auf sich selbst abbilden. Somit ist ${\displaystyle {}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 ${\displaystyle {}J\subseteq {\{1,\ldots ,n\}}}$ die Durchschnitte ${\displaystyle {}\bigcap _{i\in J}A_{j}}$ verstehen. Bei dieser Menge handelt es sich um diejenigen Permutationen, für die alle Elemente aus ${\displaystyle {}J}$ Fixpunkte sind (und die auch noch weitere Fixpunkte außerhalb von ${\displaystyle {}J}$ haben können). Wenn die Anzahl von ${\displaystyle {}J}$ gleich ${\displaystyle {}k}$ ist, so gibt es ${\displaystyle {}(n-k)!}$ solche Permutationen, da ja die Permutation auf ${\displaystyle {}J}$ die Identität sein muss und es außerhalb von ${\displaystyle {}J}$ keine Einschränkung gibt. Bei fixiertem ${\displaystyle {}k}$ wissen wir auch, wie viele Teilmengen ${\displaystyle {}J}$ mit ${\displaystyle {}k}$ Elementen zu berücksichtigen sind, nämlich ${\displaystyle {}{\binom {n}{k}}}$. Mit diesen Zahlen ergibt sich nun mit Hilfe der Siebformel der Ausdruck

${\displaystyle {}{\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

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