Wieviele Injektive Funktionen f: X -> Y gibt es?

Question

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

x₁ hat m Möglichkeiten.
x₂ hat m Möglichkeiten. 
...
x_n hat m Möglichkeiten.

Also haben wir m*m*m*m*...*m Das ganze n mal,

Also gibt es mⁿ 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 mⁿ gilt dann 0⁰ = 1. 

Teilaufgabe b)
Jetzt sind wir eingeschränkt, denn die Funktion soll injektiv sein. 
Wieder gilt |X|=n und |Y|=m.

x₁ hat m Möglichkeiten, kann also auf jedes Element von Y abgebildet werden.
x₂ hat m-1 Möglichkeiten, also Y \ { f(x₁) }
x₃ hat m-2 Möglicheiten, also Y \ { f(x₁), f(x₂) }
...
x_n hat ... (das ist meine Frage). Wohl aber Y \ { f(x₁), f(x₂), f(x₃), ..., f(x_n-1)  }

Formulierung der Frage
Jetzt fällt mir die Bestimmung für die Möglichkeiten von x_n nicht so leicht, 
Ich erkenne aber ein Muster:

x₁ hat m - 1 + 1  = m - 0 ⇒ Anzahl Möglichkeiten für x₁ = m.

x₂ hat m - 2 + 1 ⇒  Anzahl Möglichkeiten für x₂ = m-1.

x₃ hat m - 3 + 1 ⇒ Anzahl Möglichkeiten für x₃ = 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 x_n gelten  m - (n-1) = m - n + 1

x_n 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. 

Answer 1

m * (m-1) * (m-2) * (m-3) * ... * m-n+1 = m!

Das ist falsch m!=m*(m-1)*...*3*2*1. Fakultät geht immer bis 1. Das Ergebnis der Lösung erhältst du nach umschreiben.

2. Ja, wenn m=n, dann ist die injektive Funktion auch bijektiv.

3. Wenn n>m gibt es keine injektive Funktion. Richtig, eine Funktion muss jeden Wert aus ihrem Definitionsbereich abbilden und wenn m>n muss es mindestens zwei Elemente geben, die auf das gleiche Element geschickt werden. (Schubfachprinzip) Somit ist die Abbildung nicht injektiv.

Comments

Danke, Frage 2 und 3 sind geklärt

Aber Frage 1

Kannst du mir zeigen wie ich auf die Schreibweise der richtigen Lösung komme und wieso es nicht die Fakultät ist ? Das sehe ich noch nicht. 

---

ja, klar.

Also: Nimm z.B einfach mal n=3, m=5

Dann ist

m * (m-1) * (m-2) * (m-3) * ... * m-n+1 = 5*4*3

Und das wars, denn m-n+1=3.

m!=5*4*3*2*1

ist ja aber das doppelte von oben, also kann das oben nicht die Fakultät von m sein.

$$ \frac{m!}{(m-n)!} =\frac{m*(m-1)*...*(m-n+1)*(m-n)*...*3*2*1}{(m-n)*...*3*2*1}$$

jetzt den hintere Teil kürzen.