Show that there are $\sum_{k=1}^{n}S_{n, k}$ equivalence relations on an n-element set. The numbers Sn,k are Stirling numbers of the second kind.
I am learning discrete mathematics from different books and I have come across the problem above and I couldn't find a way to prove it.
$S_{n, k}$ is the number of surjections from the set of size $n$ to one of size $k.$ Such a surjection corresponds to an equivalence relation with $k$ classes. I think you can take it from there.