Seien M und N Mengen mit |M| = 5 und |N| = 6. Wie viele injektive Funktionen gibt es von M nach N?

Question

Aufgabe:

Seien M und N Mengen mit |M| = 5 und |N| = 6. Wie viele injektive Funktionen gibt es von M nach N? Begründe deine Antwort.

Problem/Ansatz:

Wenn die Anzahl der Elemente von M = 5 ist und die Anzahl der Elemente von N = 6, dann gibt es doch laut Definition von injektiven Funktionen dass es für jedes y aus N höchstens ein x aus M gibt, das heißt, es würde höchstens 6 injektive Funktionen von M nach N geben, oder? Würde das als Begründung schon so ausreichen?

Liebe Grüße

Comments

Nein, das reicht als Begründung nicht aus, denn die These ist bereits falsch.

---

Wie geht's denn richtig?

---

Vergiss nicht, dass es auch wichtig ist, welche Elemente wohin abgebildet werden. Wenn du eine Funktion hast, die nicht auf das "erste" Element von N abbildet, dann heisst das ja nicht, dass es keine andere Funktion von M nach N mit derselben Eigenschaft geben kann.

---

Wie meinst du das? Injektiv bedeutet doch "höchstens" ein Pfeil geht pro Element der rechten Seite ein. Oder eben keiner.

---

Ja das ist doch richtig. Jetzt zeichne dir mal zwei Kreise für die beiden Mengen auf ein Blatt und für jedes Element malst du einen Punkt in den entsprechenden Kreis

Jetzt bau dir eine injektive Funktion: Nimm dir einen beliebigen Punkt aus dem Definitionsbereich und zeichne einen Pfeil in die Wertemenge. Wie viele Möglichkeiten hast du dabei?

Dann nimmst du den nächsten Punkt, zeichne wieder einen Pfeil in die Wertemenge. Wie viele Möglichkeiten sind es hier? Beachte dass ein Punkt im Wertebereich nicht von zwei oder mehr Pfeilen getroffen werden kann.

Dann dritten Punkt nehmen usw. Zum Schluss multiplizierst du die Möglichkeiten aus jedem Schritt zusammen. Was erhältst du?

---

Wenn M 5 Elemente hat, und jedes Element von N nur höchstens ein einziges Mal von einem Pfeil getroffen werden darf, dann kann ich ja mit dem ersten Element von M nur höchstens ein Element der Zielmenge treffen. Da ich die Auswahl von 6 Elementen in N habe, habe ich höchstens 6 Möglichkeiten. Das zweite Element von M hat ja dann aber nur noch 5 Möglichkeiten, falls das erste Element schon ein Element der Bildmenge getroffen hat. Wenn nicht, dann hätte es auch 6 Möglichkeiten.

Also wenn wir von "höchstens" ausgehen, also davon, dass es kein Element trifft, dann hätte man 6 * 6 * 6 * 6 * 6 = 7776 Möglichkeiten.

Wenn wir aber davon ausgehen, dass jedes Element sich auf jeden Fall für irgendein Zielelement aus der Bildmenge N entscheidet, dann hätte man ja für das erste Element aus N 6 Möglichkeiten, für das zweite Element aus N 5 möglichkeiten, für das dritte Element von N 4 Möglichkeiten, für das vierte Element von N 3 Möglichkeiten und für das fünfte Element von N 2 Möglichkeiten.

Wenn ich diese Möglichkeiten jetzt aber alle miteinander multipliziere, dann habe ich insgesamt 6 * 5 * 4 * 3 * 2 = 720 Möglichkeiten.

Welche der beiden Versionen ist richtig?

---

Funktionen haben die wichtige Eigenschaft, dass jedes Element aus dem Definitionsbereich ein Element aus dem Wertebereich treffen muss.

Die zweite Version ist also richtig.

---

Ich danke dir vielmals.

Ganz liebe Grüße

Answer 1

Das Bild einer injektiven Abbildung hat 5 Elemente; es gibt 6 fünfelemntige Teilmengen von N. Eine solche Abbildung bildet M bijektiv auf ihr Bild ab, da gibt es 5! Möglichkeiten, insgesamt also 6!