+1 Punkt
42 Aufrufe

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?

von

1 Antwort

0 Daumen

• 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)|= kn

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

von

Ein anderes Problem?

Stell deine Frage

Ähnliche Fragen

0 Daumen
1 Antwort
0 Daumen
1 Antwort
0 Daumen
0 Antworten

Willkommen bei der Mathelounge! Stell deine Frage sofort und kostenfrei

x
Made by a lovely community
...