Abbildungen endlicher Mengen

Question

Aufgabe:

Wir definieren Mk := {1,2,...,k} für eine natürliche Zahl k. Dann gilt M0 = ∅, M1 = X und
M2 =Y undM5 =Z.Essei
• A(n, k) die Menge der Abbildungen Mn → Mk,
• S(n, k) die Menge der surjektiven Abbildungen Mn Mk, • I(n, k) die Menge der injektiven Abbildungen Mn → Mk, • B(n, k) die Menge der bijektiven Abbildungen Mn → Mk.

Für welche dieser Mengen können Sie die Mächtigkeit bestimmen?

Answer 1

• A(n, k) die Menge der Abbildungen Mn → Mk.
Für jedes x∈Mn gibt es k Kandidaten für sein Bild f(x).
∴|A(n, k)|= kⁿ

• S(n, k) die Menge der surjektiven Abbildungen Mn Mk,
\( |S(n,k)| = \sum_{i=0}^k (-1)^{i} {k \choose i} (k-i)^n \)
Beweis nicht trivial.

• I(n, k) die Menge der injektiven Abbildungen Mn → Mk,
Ist n>k, dann |I(n, k)|=0. Sonst
für 1∈Mn gibt es k Möglichkeiten für die Wahl von f(1).
Für 2, dann k-1 usw...
∴|I(n, k)|=k*(k-1)*...*(k-n+1)

• B(n, k) die Menge der bijektiven Abbildungen Mn → Mk. 
Ist n≠k, dann 0.
Sonst |B(n, k)|=n!, folgt direkt aus Vorherigen.