Beweis der Formel für Fixpunktfreie Permutationen anhand Inklusion Exklusion?

Neue Frage »

Asgaroth Auf diesen Beitrag antworten »
Beweis der Formel für Fixpunktfreie Permutationen anhand Inklusion Exklusion?
Hallo. Beweisen Sie Satz 1.19: Es gibt genau

fixpunktfreie Permutationen von n Elementen.
(Hinweis: Man berechne zuerst die Anzahl der nicht fixpunktfreien Permutationen
mittels Inklusion-Exklusion.)

Hat da irgendjemand ne Idee dazu? Ich hab keine ahnung wie ich anfangen soll da ich nichtmal die Formel für die Anzahl der nicht fixpunktfreien Permutationen finde. (für alle permutationen ist es ja wohl ) aber keine ahnung wie ich dann weitermachen soll.

MfG Asgaroth
Vielen dank schon im Vorraus.

P.S.: Inklusion Exklusion ist doch: \ oder?
AD Auf diesen Beitrag antworten »

Das war wirklich schon sehr, sehr oft hier im Board. Benutz mal "Suchen" mit den Begriffen Fixpunkt und Permutation .
Asgaroth Auf diesen Beitrag antworten »

Vielleicht mach ich da irgendwas falsch aber bei mir hat der da nur meinen Beitrag gefunden bzw unter "Fixpunktfreie Permutation" gar nichts. Hast du ev. einen link zu einem der von dir angesprochenen Beiträge?
MfG Asgaroth.

P.S.: Falls das wirklich schon mal da war was ja gut sein kann dann tut es mir leid das ich es nicht gefunden habe und nochmal danach gefragt hab.
Achja, bei google hatte ich dazu nichts gefunden nur einen beweis der Rekursiven Formel für die Fixpunktfreie Permutation.
Leopold Auf diesen Beitrag antworten »

z.B. hier
Asgaroth Auf diesen Beitrag antworten »

Ok den Beitrag hatte ich nicht gefunden. Jetzt ist mir wenigstens der Anfang klar, allerdings habe ich eine andere Siebformel bei mir im Skript stehen (vielleicht seh ich das auch nur anders...)
Aufjedenfall schonmal danke für die antwort.

Mir ist allerdings auch nicht klar wie man von

auf

kommt.

Und wie man dann von auf kommen soll?

( also wahrscheinlich n! - dem obigen Term... aber trotzdem keine lösung in sicht...)

P.S.: hier bzw in dem anderen beitrag benutzte Siebformel: =

Die Siebformel aus meinem Script:
=
Leopold Auf diesen Beitrag antworten »

Verfolge diese Diskussion ab hier.
 
 
Asgaroth Auf diesen Beitrag antworten »

Wahrscheinlich bin ich zu blöd dafür. Aber danke für die mühe.
Ich hab die Siebformel jetzt verstanden, man berechnet also die Menge der nicht fixpunktfreien Permutationen und fort sie dann über n!- formel der nichtfixpunktfreien Permutationen zu der zu beweisenden Formel.
Soweit so gut wie das funktionieren soll weiß ich immer noch nicht aber ich werde jetzt einfach nochmal ne h drann rumprobieren.

MfG Asgaroth

P.S.: [Edit] Jetz hab ichs wenigstens einigermaßen verstanden, das einzige was mir nicht klar ist ist wie ich von auf komme. Falls das jemand versteht könnte er die antwort ja hier posten.
phi Auf diesen Beitrag antworten »

Da es um den Beweis geht, hilft vielleicht das weiter: http://www.math.ethz.ch/undergraduate/le...ik_itet/ml5.pdf
Asgaroth Auf diesen Beitrag antworten »

Danke phi, das hatte ich schon gefunden aber da ist leider nicht der Beweis über das Inklusions Exklusions Prinzip erklärt. Sie stellen dort nach Regeln der Logik eine Rekursionsgleichung auf das habe ich verstanden, aber sie benutzen die von mir zu beweisende Formel schon und verweisen nur auf die Vorlesung von der ich leider kein Script gefunden habe.

MfG Asgaroth

P.S.: Danke für die vielen antworten.
AD Auf diesen Beitrag antworten »

Zitat:
Original von Asgaroth
das einzige was mir nicht klar ist ist wie ich von auf komme.

Die Darstellung



des Binomialkoeffizienten sollte bekannt sein. Und das andere - naja:

Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »