Aufgabe:
$$\begin{array} { l } { \text { Sei } X \text { eine endliche Menge mit } n \text { Elementen, und sei } Y \text { eine endliche Menge } } \\ { \text { mit } m \text { Elementen. } } \\ { \text { (a) Wie viele Funktionen von } X \text { nach } Y \text { gibt es? } } \\ { \text { (b) Wie viele injektive Funktionen von } X \text { nach } Y \text { gibt es? } } \\ { \text { (c) Wie viele bijektive Funktionen von } X \text { nach } Y \text { gibt es? } } \end{array}$$
Meine Lösung:
Teilaufgabe a)
Es geht darum, wieviele Funktionen es generell hat.
Also gilt folgendes
x1 hat m Möglichkeiten.
x2 hat m Möglichkeiten.
...
xn hat m Möglichkeiten.
Also haben wir m*m*m*m*...*m Das ganze n mal,
Also gibt es mn Funktionen von X nach Y.
Ich muss auch den Extremfall betrachten, wenn X und Y leer sind haben beide die Kardinalität 0,
nach obiger formel mn gilt dann 00 = 1.
Teilaufgabe b)
Jetzt sind wir eingeschränkt, denn die Funktion soll injektiv sein.
Wieder gilt |X|=n und |Y|=m.
x1 hat m Möglichkeiten, kann also auf jedes Element von Y abgebildet werden.
x2 hat m-1 Möglichkeiten, also Y \ { f(x1) }
x3 hat m-2 Möglicheiten, also Y \ { f(x1), f(x2) }
...
xn hat ... (das ist meine Frage). Wohl aber Y \ { f(x1), f(x2), f(x3), ..., f(xn-1) }
Formulierung der Frage
Jetzt fällt mir die Bestimmung für die Möglichkeiten von xn nicht so leicht,
Ich erkenne aber ein Muster:
x1 hat m - 1 + 1 = m - 0 ⇒ Anzahl Möglichkeiten für x1 = m.
x2 hat m - 2 + 1 ⇒ Anzahl Möglichkeiten für x2 = m-1.
x3 hat m - 3 + 1 ⇒ Anzahl Möglichkeiten für x3 = m-2.
Das Muster: Die Anzahlmöglichkeiten für jedes Element x ist immer:
m minus (eins weniger als sein Index).
Also müsste für xn gelten m - (n-1) = m - n + 1
xn hat also m - n + 1 Möglichkeiten abgebildet zu werden.
Frage (1)
Also ist die Anzahl aller injektiven Abbildungen gegeben durch:
m * (m-1) * (m-2) * (m-3) * ... * m-n+1 = m! Die Lösung sagt aber m!/(m-n)!
Das gilt für den Fall n ≤ m.
Frage (2)
Wenn n=m ist, wäre es dann nicht automatisch gerade bijektiv?
Frage (3)
Wenn n>m ist gibt es keine Injektive Abbildung von X nach Y.
Ich bin mir nicht sicher wieso das so ist. Muss jedes Element von x abgebildet werden damit man überhaupt von einer Funktion sprechen darf? Im Fall n>m blieben n-m Elemente aus X übrig und nicht abgebildet.
