Endliche Mengen/Surjektive Abbildungen/Rekursionsformel/Fakt

Rekursionsformel für die Anzahl der surjektiven Abbildungen

Zu ${}n,k\in \mathbb {N}$ bezeichne ${}\operatorname {Surj} (n,k)$ die Anzahl der surjektiven Abbildungen einer ${}n$-elementigen Menge in eine ${}k$-elementige Menge.

Dann gilt die Rekursionsformel

${}\operatorname {Surj} (n+1,k)=k\cdot \operatorname {Surj} (n,k)+k\cdot \operatorname {Surj} (n,k-1)\,.$

Einen Beweis erstellen