Stirling Numbers of the Second Kind (Set Partitions)

$S(n,k)$ counts the ways to split an $n$-set into exactly $k$ nonempty, unlabeled blocks; use the recurrence $S(n,k)=k\,S(n-1,k)+S(n-1,k-1)$ or direct case-by-size counting.