Let $S(n,k)$ be the number of surjections from an $n$-set to a $k$-set.
Prove use a combinatorial proof that:
$S(n+1,k) = kS(n,k) + kS(n,k-1)$, where $n \geq k$
this equation counts the class of distributions of $n+1$ balls labeled, $1, ..., n+1$ among $k$ urns labeled $u_1, ..., u_k$, with no urn left empty. The LHS counts by definition of $S(n+1, k)$.
The RHS splits this into two situations:
(1) The case when ball 1 is placed in an urn all by itself
(2) The case when ball 1 is placed in a urn with at least one other ball.
Case 1 would be $kS(n,k)$ and Case 2 would be $kS(n,k-1)$
This counts all cases. So the proof is complete.
I'm not sure if this is correct. Any help will be appreciated.