Random proof

Proposition

For $n\ge k\ge 1$ we have the following recursion:
$S(n+1,k)=k\cdot S(n,k)+S(n,k+1)$

Proof

$S(n+1,k)=$ # ways to position $[n+1]$ into $k$ non empty parts.
Let $\pi$ be a position

1. case: ${\pi }_k=\{n+1\}$ so # $=S(n,k+1)$
2. $|{\pi }_k|\ge 2$ then ${\pi }_1,...,{\pi }_k\backslash \{n+1\}$ still non empty
   ⇒ $\exists$ Bijektion to all partitions of $[n]$ into non empty parts $S(n,k)$ with one special part where we put $(n+1)$

Proposition (non recursive Formula)

$S(n,k)=\frac{1}{k!}\sum (-1{)}^{k+j}(\genfrac{}{}{0ex}{}{k}{j})j^n$
todo add later proof