Beweis einer Summenformel in der die Anzahl aller surjektiver Abbildungen von M nach N vorkommt

Question

Aufgabe:

Es sei A_m,n die Anzahl der surjektiven Abbildungen von M nach N. Begründen Sie, dass

\( \sum\limits_{k=1}^{n} \)  \( \begin{pmatrix} n\\k \end{pmatrix} \) A_m,k = n^m

Problem/Ansatz:

Habe es versucht ganz einfach über den binomischen Lehrsatz zu beweisen. Bis ich entdeckt habe dass es n hoch m ist. Daher meine Frage kann ich den binomischen Lehrsatz noch verwenden dafür oder geht das wegen dem m nicht? Und welche Beweismethode würdet ihr mir empfehlen dafür?

Answer 1

Tipp: Benutze die Diskussionen hier https://www.mathelounge.de/665124/anzahl-aller-bijektiven-injektiven-usw-abbildungen-von-nach#c665184 und in den Links im Link für eine einleuchtende Antwort.

Comments

Du hast wie teilweise im angegebenen Link vergessen anzugeben, dass |M| = m und |N| = n.

---

Danke für deine Antwort ich habe es einfach überlesen. Dachte die Bedingung sei nur für die vorherige Aufgabe gedacht *facepalm*

---

Gut: Jetzt einfach interpretieren.

A_(n,k) ist die Anzahl der Abbildungen, die genau k Bildelemente haben.

(n tief k) * A_(n,k) ist die Anzahl der Abbildungen, die genau k Bildelemente haben und auf k beliebige Elemente von N abgebildet werden.

Die Anzahl aller Abbildungen  von M nach N kannst du nun zählen, als Summe der Abbildungen, die genau genau k Bildelemente in N haben.

Nun Resultat bei a) im Link verwenden und

q.e.d. hinschreiben.

---

Endlich so richtig das Prinzip verstanden. Wie einfach eine kleine Stelle alles verändert hahaha. Danke nochmals :)))