Stirling Number - a proof

Question

I am stuck on the following question.

Prove that $S(n+1, n) = \frac{n(n+1)}{2}$ for any $n \ge 1$

This is where $S(n+1,n)$ is the Stirling number, partitioning a $n+1$-element set into $n$ parts.

What first steps should be taken to try and derive this?

Answer 1

Let's suppose you have a set of eleven distinguishable balls and ten blank boxes to put them in. Also you are commanded to put at least one ball in each box. Then you have to have one box with two balls and nine boxes with one ball each. You can distinguish the two-ball box now, but not the one-ball boxes. So you can only tell apart these arrangements by seeing which balls are in the two-ball box. But these are two balls from eleven. Therefore $S(11,10)=\binom{11}2$.

Answer 2

You have to partition $n+1$ element set in $n$ parts. Now each of the $n$ part is non empty. So, the only possibility the partition case is that, $n-1$ singleton subsets and a subset of $2$ element.So, we have to just focus on the $2$ element set. Now the possible no of $2$ element set is ${n+1\choose 2}$, which is the required result.