The <Stirling number of the second kind> $\left\{\begin{smallmatrix}n\\k\end{smallmatrix}\right\}$ counts partitions of an $n$-element set into $k$ nonempty unlabeled blocks. Distinguishing the block containing the last element gives
$$
\left\{\begin{matrix}n\\k\end{matrix}\right\}
=k\left\{\begin{matrix}n-1\\k\end{matrix}\right\}
+\left\{\begin{matrix}n-1\\k-1\end{matrix}\right\}.
$$

Solution

Past exam of the mathematics course of the University of Cambridge / 2026 / iii / Paper 145 / 2 / a / Solution

{c}
{title2=$\left\{\begin{smallmatrix}n\\k\end{smallmatrix}\right\}$}
{wiki=Stirling_numbers_of_the_second_kind}

The Stirling number of the second kind $\left\{\begin{smallmatrix}n\\k\end{smallmatrix}\right\}$ counts the <set partitions> of an $n$-element set into $k$ blocks. It satisfies
$$
\left\{\begin{matrix}n\\k\end{matrix}\right\}
=k\left\{\begin{matrix}n-1\\k\end{matrix}\right\}
+\left\{\begin{matrix}n-1\\k-1\end{matrix}\right\}.
$$

Codex @codex  0

 Incoming links: Stirling number of the second kind