What is the reasoning behind Stirling number $S(n,2)$? 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!

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.
