TU Wien:Diskrete Mathematik für Informatik UE (Drmota)/Übungen WS10/Beispiel 13

Surjektive Abbildungen f: A->B |A|=n |B|=k

Lösung: $k!S_{n,k}$

kombinatorische Interpretation: es gibt $S_{n,k}$ Möglichkeiten die Menge A in k Teile aufzuteilen, jedes Teil bildet auf das selbe Element aus B ab.

Das erste Teil hat k Möglichkeiten um auf B abzubilden, das zweite (k-1) usw. -> k!

Da jedes b aus B getroffen werden muss, kann es nicht sein dass zwei Teile auf das selbe abbilden, es würde ein b aus B fehlen.

Alternative Formulierung

Elemente der Zielmenge werden als nichtleere Partitionen gesehen. Man kann sie auf $S_{n,k}$ Möglichkeiten "befüllen".

Jetzt ist aber die Zuordnung der Partitionen auf die Elemente der Zielmenge noch egal. Also 34|12 ist das gleiche wie 12|34. Bei uns ist das aber nicht egal, weil wenn 12 auf 1 und 34 auf 2 abgebildet wird ist das nicht dasselbe wie 12 auf 2 und 34 auf 1.

Wieviele Variationen gibt es die schon konstruierten Partitionen auf k Elemente der Zielmenge zuzuweisen -> k!.