Wieviele injektive Abbildungen gibt es von M nach N?

Question

Aufgabe:

Seien M und N endliche Mengen. Wieviele
injektive Abbildungen gibt es von M nach N? Wieviele surjektive Abbildungen gibt es von
M nach N, wenn N zwei, drei oder vier Elemente enthält ?

Answer 1

Wie viele injektive Abbildungen gibt es von M nach N?

Seien m und n beziehungsweise die Mächtigkeiten von M und N.

Für n<m gibt es keine  injektive Abbildung von M nach N.

Für n=m ist jede  injektive Abbildung von M nach N auch

zugleich bijektiv, also unterscheiden sich verschiedene nur dadurch, dass

eine Permutation von M vorgeschaltet wird. Davon gibt es m! Stück.

Also gibt es in diesem Fall m! = n! verschiedene  injektive Abbildung

 von M nach N.

Im Fall n>m wird durch jede  injektive Abbildung  von M nach N

eine m-elementige Teilmenge von N als Bildmenge ausgewählt.

Von denen gibt es "n über m".  Und die mit der gleichen Bildmenge

sind als Abbildungen von M auf diese gemeinsame Bildmenge

wieder bijektiv, also gibt es n! verschiedene.

Somit ist im Fall n>m die Anzahl   "n über m" * n! .

Comments

interessant ..

und wie kann man auf zweite Frage (Wieviele surjektive Abbildungen gibt es von
M nach N, wenn N zwei, drei oder vier Elemente enthält ) beantworten !!

---

Sei M eine Menge mit |M|=m und N zweielementig N={a;b}.

Die Anzahl aller Abbildungen von M nach N ist dann ja 2^m.

Welche davon sind nun nicht surjektiv ?

Entweder wird a nicht getroffen, also alles auf b

abgebildet oder umgekehrt. Also gibt es wohl

nur 2, die nicht surjektiv sind.

==>  Anzahl  =  2^m - 2 .

---

ich habe versucht die Antwort nachzuvollziehen und bin nach langem überlegen dahinter gekommen. Allerdings finde ich die Lösung für N = {a, b, c} trotzdem nicht selbst heraus.