Stirling numbers of the second kind: a recurrence relation.

Question

This is Exercise 1.9.15 of Howie's "Fundamentals of Semigroup Theory".

Let $X$ be a finite set with $n$ elements and let $S(n, r)$ (for $0\le r\le n$) be the number of equivalences $\rho$ on $X$ such that $\lvert X/\rho\rvert=r$. Show that $$S(n, 1)=S(n, n)=1\tag{1}$$ and $$S(n, r)=S(n-1, r-1)+rS(n-1, r)\tag{2}$$ for $(2\le r\le n-1)$.

My Attempt:

Let $\mathcal{E}_X$ be the set of equivalences on $X$.

For $(1)$, we have that $$\begin{align} S(n, 1)&=\lvert\{\rho\in \mathcal{E}_X : \lvert X/\rho\rvert=1\}\rvert \\ &\stackrel{(?)}{=}\lvert\{X\times X\}\rvert \\ &=1 \end{align}$$ and

$$\begin{align} S(n, n)&=\lvert\{\rho\in \mathcal{E}_X : \lvert X/\rho\rvert=n\}\rvert \\ &\stackrel{(?)}{=}\lvert\{\operatorname{id}_X\}\rvert \\ &=1. \end{align}$$

---

I'm stuck showing $(2)$.

Thoughts:

I suppose showing $(2)$ is a matter of induction on $n$ but I don't know where to start.

Please help :)

Answer 1

From the comments:

It maybe helpful to think of an equivalence on $ X $ as a partition of $ X $. You can make a partition of $ X $ into $ r $ subsets as follows: Fix an element $ x $ of $ X $. Then either partition the other $ n- 1 $ into $ r-1 $ subsets and put $ x $ into his own subset, or, partition the other $ n-1 $ into $ r $ subsets and put $ x $ into one of those $ r $ subsets. These are the two terms in the recursion relation.