Stirling Number Proof Help Needed

Question

Show that, for $m > 0, S(m, 2) = 2^m-1$ Give a complete proof.

(Question is about Stirling numbers)

I have attached whatever I tried to do:

But it's not giving me the correct result.

Answer 1

You have correctly shown that $S(m,2) = \frac12(2^m - 2) = 2^{m-1}-1$. Whoever told you it should be $2^m - 1$ is wrong.

We can also see this a different way. $S(m,2)$ counts the number of ways to partition $\{1,2,\dots,m\}$ into two nonempty subsets. The two subsets are not distinguishable, so call the subset containing $1$ the first subset and the other subset the second subset.

For each of $2,3,\dots,m$, we have a choice between putting it in either the first subset or the second, for $2^{m-1}$ possibilities. (In other words, each of $2, 3, \dots, m$ can either be put in the same subset as $1$, or in a different subset.) However, one of the $2^{m-1}$ possibilities is forbidden: we can't put all of them in the first subset, because the second subset must also be nonempty. This gives another proof that $S(m,2) = 2^{m-1}-1$.