Inklusions-Exklusions-Prinzip

Neue Frage »

sigmund7 Auf diesen Beitrag antworten »
Inklusions-Exklusions-Prinzip
Hallo Allerseits!

Ich stehe vor folgender Aufgabe:
Bestimmen Sie mit Hilfe des Inkl.-Exkl.-Prinzips die Anzahl aller Funktion f : {1,...,5}->{1,...,5} deren Bildmenge {f(x)|1<= x <= 5} die Kardinalität 3 hat.

Das scheint mir eine Kombination ohne Wiederholung zu sein d.h. es gibt 10 solcher Bildmengen. Gibt es somit 10 Funktionen? Das scheint mir aber nicht richtig da ja 1. die anz. d. Fkt. gefragt ist und 2. das Inkl.-Exkl.P. verwendet werden soll. Leider habe ich keine Idee wie ich hier dieses anwenden könnte.

Freue mich über jeden konstruktiven Hinweis!

Grüße,
Sigmund
AD Auf diesen Beitrag antworten »

Richtig, es gibt hier verschiedene Bildmengen der Kardinalität 3. Jetzt kannst du zu einer konkreten dieser Bildmengen - sagen wir mal o.B.d.A. - die Anzahl solcher Funktionen bestimmen, dann ist das gesuchte Gesamtergebnis für alle möglichen dreielementigen Bildmengen die Anzahl .


Die Bestimmung von geht mit der Siebformel, indem du etwa die Grundmenge aller Funktionen betrachtest, und aus dieser diejenigen heraussiebst, die nicht die volle Menge als Bild haben. Das lässt sich mit den Teilmengen

für

beschreiben: Denn dann ist , und die Kardinalität dieser Vereinigung bestimmt man eben über die Siebformel. Die Kardinalität der sowie auch der Durchschnitte mehrerer ist nämlich mit kombinatorischen Grundformeln unmittelbar berechenbar.
sigmund7 Auf diesen Beitrag antworten »

Danke das hilft mir schon um einiges weiter. Jedoch bin ich noch unschlüssig wie ich denn nun die Grundmenge Omega bestimmen soll.

Ich habe mir überlegt, dass es 5 Funktionen gibt welche {1,...,5} auf 1 abbilden d.h. in Summe 15 Funktion die auf 1-3 abbilden. Wieder scheint mir diese Überlegung jedoch falsch, schließlich geht es ja darum eine Menge auf eine andere Menge und nicht auf ein einzelnes Element abzubilden. Gibt es nicht überhaupt unendlich viele Möglichkeiten das Urbild auf das Bild abzubilden? Einzige Bedingung ist ja bekanntlich das es für jedes Element von {1,...,5} ein Element im Bild geben muss.
AD Auf diesen Beitrag antworten »

Oje, kombinatorisches Denken scheint dir gar nicht zu liegen:

In gibt es für jeden Funktionswert die 3 Möglichkeiten 1, 2 und 3, und das für k=1,2,3,4,5 völlig getrennt voneinander. Das macht .

Für beispielsweise bleiben für die Funktionswerte nur noch die 2 Möglichkeiten 1 und 3, da ja Funktionswert 2 hier nicht gestattet ist. Das macht dann , usw.
sigmund7 Auf diesen Beitrag antworten »

Wohl oder übel muss ich Dir rechtgeben, Kombinatorik ist nicht mein Ding.

Um dieses Beispiel nun doch zu einem Ende zu bringen:



Nun fehlen noch die Schnittmengen:



Eingesetzt:



Da es ja 10 solche 3 Elementigen Mengen gibt, lautet das Ergebnis: 162 * 10 = 1620

Vielen Dank!
AD Auf diesen Beitrag antworten »

Zitat:
Original von sigmund7
1^5 = 5

Bitte - nur das nicht. geschockt

Wenn du aber mit 1^5 = 1 weiterrechnest, müsste dann das richtige Ergebnis rauskommen.
 
 
sigmund7 Auf diesen Beitrag antworten »

Oh das ist nun wirklich peinlich ... wie war das nochmal mit dem neutralen Element :|



Eingesetzt:



Somit gibt es nun 1500 solcher Funktionen
AD Auf diesen Beitrag antworten »

Jetzt stimmt's. Freude
Neue Frage »
Antworten »



Verwandte Themen

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