Permutation/Fixpunktfrei/Formel/Fakt/Beweis

Aus Wikiversity
Zur Navigation springen Zur Suche springen
Beweis

Zu jedem sei die Menge aller Permutationen auf , die auf sich selbst abbilden. Somit ist die Menge aller Permutationen, die mindestens einen Fixpunkt haben. Um die Siebformel anwenden zu können, müssen wir zu die Durchschnitte verstehen. Bei dieser Menge handelt es sich um diejenigen Permutationen, für die alle Elemente aus Fixpunkte sind (und die auch noch weitere Fixpunkte außerhalb von haben können). Wenn die Anzahl von gleich ist, so gibt es solche Permutationen, da ja die Permutation auf die Identität sein muss und es außerhalb von keine Einschränkung gibt. Bei fixiertem wissen wir auch, wie viele Teilmengen mit Elementen zu berücksichtigen sind, nämlich . Mit diesen Zahlen ergibt sich nun mit Hilfe der Siebformel der Ausdruck

Somit ist die Anzahl der fixpunktfreien Permutationen gleich