Endliche Mengen/Surjektive Abbildungen/Rekursionsformel/Fakt

Rekursionsformel für die Anzahl der surjektiven Abbildungen

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

Dann gilt die Rekursionsformel

$\mathrm{surj}(n+1,k)=k\cdot \mathrm{surj}(n,k)+k\cdot \mathrm{surj}(n,k-1).$

Zum Beweis, Alternativen Beweis erstellen