Wie viele injektive Funktionen gibt es?

Question

Betrachte die Menge X = {1,2,3,4,5} und Y = {A,B,C}. M sei die Menge von Funktionen f:X-->Y. Wie viele injektive Funktionen gibt es?

Eine Funktion ist injektiv, solange keine zwei Elemente aus X auf dasselbe Element in Y abgebildet werden. Das bedeutet, wir könnten auch nur ein oder zwei Elemente aus X abbilden und es wäre immer noch injektiv.

Gehen wir die verschiedenen Möglichkeiten durch

 Ein Element aus X wird abgebildet:
Es gibt 5 Möglichkeiten, ein Element aus X auszuwählen und 3 Möglichkeiten, es auf ein Element aus Y abzubilden. Das ergibt 5×3=15 mögliche Funktionen.

  Zwei Elemente aus X werden abgebildet:
Es gibt (5 über 2) Möglichkeiten, zwei Elemente aus X auszuwählen. Für die Abbildung des ersten Elements gibt es 3 Möglichkeiten und für das zweite 2. Das ergibt (5 über 2)×3×2=30×6=180 mögliche Funktionen.

  Drei Elemente aus X werden abgebildet (wie bereits zuvor berechnet):
Es gibt (5 über 3) Möglichkeiten, drei Elemente aus X auszuwählen und 6 Möglichkeiten, diese drei Elemente injektiv auf Y abzubilden. Das ergibt (5 über 3)×6=10×6=60 mögliche Funktionen.

Die Gesamtzahl der injektiven Funktionen ist daher 15+180+60=255.

Also gibt es insgesamt 255 injektive Funktionen von X nach Y. Liege ich richtig oder habe ich mich vertan?

Comments

wir könnten auch nur ein oder zwei Elemente aus X abbilden und es wäre immer noch injektiv.

Eine Funktion   f:X-->Y   muss  jedem Element von X genau ein Element von Y zuordnen.

Eine injektive Funktion muss jedem Element von X genau ein anderes Element zuordnen.

f:X-->Y könnte also nur injektiv sein, wenn Y mindestens so viele Elemente wie x hat.

Es gibt hier also keine injektive Funktion f

---

Das bedeutet, wir könnten auch nur ein oder zwei Elemente aus X abbilden und es wäre immer noch injektiv.

Eine solche Relation ist natürlich denkbar, aber sie ist unter diesen Umständen keine Funktion mehr, da sie nicht linksvollständig ist.

---

Ok ja das habe ich anfangs auch gedacht. Ich meine solch eine Funktion kann niemals injektiv werden, falls man eben alle Elemente aus X nach Y zuordnen möchte. Die wichtigsten Axiome einer Funktion habe ich vergessen. Die Rechtseindeutigkeit habe ich zwar berücksichtigt aber nicht die Linksvollständigkeit. Danke

Answer 1

Damit es eine Funktion ist, muss jedem \(x\in X\) ein \(y\in Y\) zugeordnet werden.

Wenn Du Dich der Sache über "Anzahl Möglichkeiten" nähern willst:
Fang mit \(x=1\) an. Wieviele Möglichkeiten für den Funktionswert, also für \(f(1)\) gibt es?

Dann \(x=2\): wieviele Möglichkeiten für \(f(2)\) gibt es, so dass \(f\) injektiv bleibt?

Usw.. Dann kommst Du auf das oben schon erwähnte Ergebnis.

Comments

Ja aber es gibt ja keine injektive Funktion f

---

Es ging mir darum einen Weg aufzuzeigen, wie Du das nachweisen kannst. Auf demselben Weg kannst Du auch berechnen, wieviele injektive Funktionen es gibt, wenn es doch mal welche gibt.

---

Asooo so war das gemeint. Danke für die Klarstellung