Angenommen, wir haben zwei Mengen \(A\) und \(B\) mit \(|A|=n\) und \(|B|=m\). Klar sollte sein, dass es im Fall \(n<m\) keine surjektiven Funktionen \(A\to B\) gibt.
Ist \(n\geq m\), gibt es genau \(m^n\) Funktionen von \(A\) nach \(B\). Nun subtrahieren wir davon alle nichtsurjektiven Funktionen. Das sind alle Funktionen, die von \(A\) in eine \((m-1)\)-elementige Teilmenge von \(B\) abbilden. Es gibt \(\binom{m}{m-1}\) viele solche Teilmengen und jeweils \((m-1)^{n}\) viele Funktionen in diese Mengen. Bis jetzt lautet unsere Formel also \(m^n-\binom{m}{m-1}(m-1)^n\).
Allerdings ziehen wir in diesem Schritt manche Funktionen doppelt ab, nämlich genau die, die in eine \((m-2)\)-elementige Teilmenge von \(B\) abbilden. Diese müssen wir also wieder hinzuzählen; analog zu oben ist deren Anzahl \(\binom m{m-2}(m-2)^n\). Jetzt zählen wir aber wieder manche Funktionen zuviel, und zwar die, die in eine \((m-3)\)-elementige Teilmenge abbilden u.s.w.
Als gesamte Formel ergibt sich so $$m^n-\binom m{m-1}(m-1)^n+\binom m{m-2}(m-2)^n-\ldots\pm\binom m11^n=\sum_{i=1}^m(-1)^{m-i}\binom{m}{i}i^n.$$
Ein anderer Ansatz ist, mit Rekursionsformeln zu arbeiten. Sei \(S(n,m)\) die Anzahl der surjektiven Funktionen \(\{1,\ldots,n\}\to\{1,\ldots,m\}\). Dann gelten offenbar die Basisfälle $$S(n,m)=\begin{cases}1,&n=m=0,\\0,&n>m=0,\\0,&n<m,\\n!,&n=m.\end{cases}$$ Indem man die surjektiven Funktionen danach unterscheidet, ob \(f(n)\in f(\{1,\ldots,n-1\})\), erhält man die Rekursionsformel $$S(n,m)=m(S(n-1,m-1)+S(n-1,m)).$$
Ich hoffe, das hilft dir weiter. Wenn du noch Fragen hast - auch zu einem konkreten Problem - kannst du diese gern noch stellen.
Punkte: 11.27K
vielen dank im vorhinein ─ lena10202 31.10.2020 um 10:06