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?
