Anzahl perfekte Matchings

Neue Frage »

petaaa Auf diesen Beitrag antworten »
Anzahl perfekte Matchings
Meine Frage:
Hallo, ich bräuchte einen kleinen Tipp bei folgendem Beispiel.
Ich soll zeigen, dass die Anzahl der perfekten Matching im vollständigen Graph mit 2n Knoten, ist.

Meine Ideen:
Also meine Überlegung wäre folgendes.
Ich habe eine Menge von 2n Knoten. Jeden davon muss ich einen anderen Knoten zuordnen. Und ich suche nach der Anzahl der verschiedenen Möglichkeiten wie ich das tun kann. Das ist doch dann die Anzahl der fixpunktfreien Permutationen der Menge [2n].
Für [n] haben wir diese schon mal durch das Inklusion-Exklusion-Prinzip berechnet, nämlich

Wie komme ich jetzt aber davon, auf
Oder stimmt meine Überlegung überhaupt nicht?
HAL 9000 Auf diesen Beitrag antworten »

Ist eigentlich sehr leicht mit Permutationen mit Wiederholung erklärbar:

Wir haben Farben und wir wollen jede Farbe genau zweimal verwenden, um die Knoten zu färben. Dann gibt es genau solche Färbungen.

Da aber bei einem solchen gefundenen Matching eine Permutation der n Farben untereinander nichts an den Paarungen an sich ändert, sind jeweils dieser Färbungen im Matching-Sinne identisch, damit muss noch durch diese Farbenpermutationszahl dividiert werden: .


Zitat:
Original von petaaa
Ich habe eine Menge von 2n Knoten. Jeden davon muss ich einen anderen Knoten zuordnen. Und ich suche nach der Anzahl der verschiedenen Möglichkeiten wie ich das tun kann. Das ist doch dann die Anzahl der fixpunktfreien Permutationen der Menge [2n].

Der Zusammenhang erschließt sich mir in keinster Weise. Erstaunt1
petaaa Auf diesen Beitrag antworten »

Ja, danke! Diese Erklärung verstehe ich! smile
Bin mittlerweile schon draufgekommen, dass meine Überlegung mit den Permutationen nicht wirklich funktionieren kann.
Neue Frage »
Antworten »



Verwandte Themen

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