In its article on "Stirling numbers of the second kind", Wikipedia gives this formula for $S(n, k)$ -- the number of ways of putting $n$ distinct balls into $k$ boxes (where the boxes aren't distinct).
$S(n, k) = \frac{1}{k!}\sum_{j=0}^k (-1)^{k-j}\binom{k}{j}j^n$
Does anyone have an intuitive or just semi-intuitive way of explaining this? Or is there some more general thing I should look at that will make it make sense -- Wikipedia says it's a special case of something or other.
We seem to be missing "...where none of the boxes are empty."
Assume the boxes are labeled (we divide by $k!$ at the end for unlabeled boxes).
We can put the balls in the boxes in $k^n$ ways: but this overcounts since it allows the possibility for some of the boxes to be empty. So we need to subtract the number of balls-in-box-arrangements in which there are empty boxes.
The number of balls-in-box-arrangements with $\geq j$ empty boxes is $$\binom{k}{j} j^n$$ and we include-exclude over $j$, thus giving $$\sum_{j \geq 0} (-1)^{k-j} \binom{k}{j} j^n.$$
The relation between the balls-in-box-arrangements and the Stirling numbers of the second kind is immediate by definition.