Stirling Numbers Second Kind

Number of partitions of $[n]$ into $k$ non-empty parts $n\ge k\ge 1$

Formula

$$S(n+1,k)=kS(n,k)+S(n,k-1)$$ $$S(n,0)=\{\begin{array}{ll}0& \text{if }n\ne 0\\ 1& \text{if }n=0\end{array}$$ $$S(n,k)=0\text{ if }k>n$$

Non recursive Formula

$$S(n,k)=\frac{1}{k!}\sum _{j<1}^k(-1{)}^{k-j}(\genfrac{}{}{0ex}{}{k}{j})\cdot j^n$$

$\tilde{s}(n,k)$ is the number of permutations of the set $[n]$ whose cycle representation hast exactly k cycles

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)$