Permutation/Genau ein Fixpunkt/Formel/Aufgabe/Kommentar

Man betrachtet eine Permutation ${}\varphi$ auf ${}M=\{1,\dots ,n\}$, die einen Fixpunkt ${}i$ besitzt. Da ${}\varphi (i)=i$, bildet ${}\varphi$ die Menge ${}M\setminus \{i\}$ auf sich selbst ab. Also ist die Einschränkung ${}\varphi '$ von ${}\varphi$ auf ${}M\setminus \{i\}$ eine Permutation. Falls ${}i$ der einzige Fixpunkt von ${}\varphi$ ist, dann ist ${}\varphi '$ fixpunktfrei auf ${}M\setminus \{i\}$. Es ist daher natürlich, die Menge ${}B_{i}$ aller Permutationen auf ${}M$ mit dem einzigen Fixpunkt ${}i$ zu betrachten. (Dies ist anders als im Beweis zu Fakt, wo die ${}A_{i}$ diejenigen Permutationen sind, wo ${}i$ Fixpunkt ist, aber es auch noch weitere Fixpunkte geben kann.) Aus der obigen Beobachtung überlegt man sich, dass es eine Bijektion zwischen ${}B_{i}$ und der Menge ${}C_{i}$ aller fixpunktfreien Permutationen auf ${}M\setminus \{i\}$ gibt. Eine Formel für die Anzahl von ${}C_{i}$ ergibt sich aus Fakt. Man muss jetzt nur noch beachten, dass die Mengen ${}B_{i}$ paarweise disjunkt sind und ihre Vereinigung die Menge aller Permutationen auf ${}M$ mit genau einem Fixpunkt bildet. Somit ist

${}{\#\left(B_{i}\right)}={\#\left(C_{i}\right)}=(n-1)!\sum _{k=0}^{n-1}{\frac {(-1)^{k}}{k!}}\,$

und die Anzahl aller Permutationen mit genau eniem Fixpunkt ist

${}\sum _{i=1}^{n}{\#\left(B_{i}\right)}=n!\sum _{k=0}^{n-1}{\frac {(-1)^{k}}{k!}}\,.$

Zur kommentierten Aufgabe