Deriving a simple formula for $S(m,2)$

Question

I need to derive a simple formula for $S(m,2)$ and these are the Stirling number of the second kind.

My thinking is that we need to count the number of ways to distribute $m$ distinct objects onto $2$ identical containers (non empty).Is it just the same like counting the number of onto functions from a set of size $m$ to a set of size $2$ so we have $$\sum_{i = 0}^{2} (-1)^{i} {2 \choose 2-i} (2-i)^m = 2^m -2$$

Now the thing is that we have identical containers right so what we need to do here is divide by $2!$ but my questions is why ? so the final answer I know should be $$\frac{1}{2} (2^m - 2) = 2^{m-1} - 1$$

But why do we need the divide by the two, I know it has to do with the two containers being identical but is there any intuition or further explanation, It didn't quite sink in for me.

Answer 1

Suppose that $m=3$, just to keep things simple, and the objects are $A,B$ and $C$. Since the containers are indistinguishable, the possible arrangements are identifiable only be which objects are together in one container:

• $A$ and $B$ in one container and $C$ in the other;
• $A$ and $C$ in one container and $B$ in the other; and
• $B$ and $C$ in one container and $A$ in the other.

Now suppose that the containers are identifiable; say one is Box $1$, and the other is Box $2$. Now each of the arrangements above corresponds to two possibilities. The first, for instance, could be $A$ and $B$ in Box $1$ and $C$ in Box $2$, or it could be $A$ and $B$ in Box $2$ and $C$ in Box $1$. Thus, the number of arrangements with labelled containers is twice the number with indistinguishable containers.

You can, if you wish, look at it from the other end. Let $m$ be arbitrary, and say that I have Box $1$ and Box $2$. In how many ways can I choose the contents of Box $1$? I can put into Box $1$ any subset of the objects except the empty set and the whole set, so there are $2^m-2$ possibilities. Of course once I’ve chosen what goes into Box $1$, the contents of Box $2$ are determined, so there are $2^m-2$ ways to distribute the $m$ objects between the two boxes with at least one object in each box. Now take any one of those distributions, and interchange the contents of the boxes. Those two distributions are counted separately in the figure $2^m-2$, but they produce exactly the same sets of objects lumped together with one another. That is, if we removed the labels from the (otherwise indistinguishable) boxes, we couldn’t tell those two distributions apart. Thus, we must divide by $2$ to get the number of distributions that can actually be distinguished when the boxes are indistinguishable.