What is the reasoning behind Stirling number $S(n,2)$?

Question

The answer that was given in class was $(2^n -2)/2$.

I think it's trying to use the theorem that the number of $k$-digit strings that can be formed over $n$ element set is $n^k$. Or, I think it might be counting the number of ways that each number can be placed in each of the two subsets.

Also, why are we subtracting the two?

Can someone provide an explanation? Thanks!

Answer 1

The Stirling number of the second kind $S(n, k)$ counts the number of ways of placing $n$ distinct objects in $k$ indistinguishable boxes when no box is left empty.

The formula $$S(n, 2) = \frac{2^n - 2}{2}$$ may be derived in the following manner. Suppose initially that we wish to place $n$ objects in two distinct boxes so that no box is left empty. Without the restriction that no box is left empty, we have two ways to place each of the $n$ objects, giving $2^n$ possible distributions. Since two of these distributions leave us with an empty box, there are $2^n - 2$ ways to distribute $n$ distinct objects to two distinct boxes so that no box is left empty. Since we wish to count the number of distributions of $n$ distinct objects to two indistinguishable boxes that leave no box empty, we must divide the $2^n - 2$ ways we could distribute the objects to two distinct boxes so that no box is left empty by the two ways we could label the boxes, which yields the formula stated above.

Answer 2

There is another way to see this. This proof is not self-contained and it uses the double counting technique. We count the number of surjective functions from $[n]$ to $[2]$ in two ways and then set them equal to draw some conclusion.

Note that (a combinatorial proof can be given for this) the number of surjective functions from an $m$-element set to a $n$-element set is given by $n!\cdot S(m,n)$.

Define $[n] = \{1,2,\ldots, n\}$. The number of surjective functions from the set $[n]$ to the set $[2]$ is $$2!\cdot S(n,2) \ldots (*)$$.

Further, the total number of functions from $[n]$ to $[2]$ is $2^n$ (for each element in the domain $[n]$, we have two choices to map it to). Out of these, exactly $2$ functions are not surjective:

1. The one that maps everything in $[n]$ to $1$ in the codomain.
2. The one that maps everything in $[n]$ to $2$ in the codomain.

Thus, the total number of surjective functions from $[n]$ to $[2]$ is $2^n-2 \ldots (**)$.

As $(*)$ and $(**)$ counts the same thing, we essentially have $$2!\cdot S(n,2) = 2^n-2 \\\implies S(n,2) = \frac{2^n-2}{2} \\\implies S(n,2) = 2^{n-1}-1 \; \blacksquare$$

Answer 3

Here's an interesting way to count the same situation. Let's say that there are $n$ people and $k$ identical boxes ($1\leq k \leq n$). We wish to count the number of ways to put these $n$ people in these $k$ boxes. Let us begin by fixing person $n$ in any one of the boxes. As of this moment the boxes are no more identical. So now we just have to count the number of ways to put $n-1$ people in $2$ distinct boxes i.e. $2^{n-1}$, however we will have to subtract one from this count as there is one arrangement which is illegal i.e. all $n$ people in the same box. Therefore the final number turns out to be $2^{n-1}-1$, same as yours.