> [!NOTE] > For natural numbers $n,k$ $S(k,n)= S(k-1, n-1) + nS(k-1,n)$where $S(k,n)$ denotes a [[Stirling numbers of the second kind|Stirling number of the second kind]]. ###### Proof We divide set partitions of $[k]$ into $n$ parts into two types - those in which $\{k\}$ is one of the parts, and those in which $k$ appears in a part with at least one other element. Set partitions of the first type are in bijection with set partitions of the $(k-1)$ element set $\{1, \ldots, k-1\}$ into $n-1$ parts. The bijection is by deleting the part $\{k\}$, whose inverse adding a part $\{k\}$. Let $A$ be the set of partitions of the second type. There is a surjection $F:A\to B$, where $B$ is the set of set partitions of $\{1, \ldots, k-1\}$ into $n$ parts, by deleting the element $k$ from its part. For any set partition $Q \in B$, there are exactly $n$ elements $P \in A$ such that $F(P)=Q$ (these are the $n$ set partitions of $[k]$ obtained from $Q$ by adding $k$ to one of the parts). Thus $|A|=n \cdot|B|=n \cdot S(k-1, n)$ [^1]. [^1]: Define an equivalence relation $\sim$ on A by $P\;\sim\;P' \Longleftrightarrow F(P)=F(P').$ The universal property of quotients guarantees a unique map $\bar{F}: A/\sim\;\to B$ such that $F = \bar{F}\circ \pi$ where $\pi:A\to A/\sim$ is the quotient map. The induced map $\bar{F}$ is bijective: it's surjective since $F$ is surjective; and $\bar{F}$ is injective since $P \not\sim P' \iff F(P)\neq F(P')$. Thus $|A/\sim|=|B|$. Moreover, $|A/\sim|=|A|/n$ since each equivalence class contains $n$ elements.