# Stirling Number of the Second Kind (intuition for formula)

The Stirling number of the second kind is the way of putting $n$ objects into $k$ nonempty boxes. I would like to understand the right hand side of this equation by a counting argument $$S(n,k) = \frac{1}{k!} \sum_{i=0}^k(-1)^{i}\binom{k}{i}(k-i)^n$$

• Hi..the right side of that formula is gained by inclusion exclusion.If you think about how to count surjective functions by counting all functions from $[n]=\{1,2,\ldots n\}$ to $[k]$ you will see it. Think that $(k-i)^n$ is like countig functions from $[n]$ to $[k-i]$ and the combinations you use are counted by the binomial. – Phicar May 22 '14 at 17:06
• okaay. i get it now. thanks. – user103828 May 22 '14 at 19:52

\begin{align*} S(n,k) &= \frac{1}{k!} \sum_{i=0}^k(-1)^{i}\binom{k}{i}(k-i)^n \\ &= \frac{1}{k!}\left(k^n -\binom{k}{1}(k-1)^n \ldots (-1)^i\binom{k}{i}(k-i)^n \ldots \right) \end{align*} The first term, $k^n$, counts the number of ways of putting $n$ items into $k$ boxes when some of the boxes can be empty. We've double counted these boxes so subtract the number of ways of placing $n$ objects into $k-1$ boxes (this is the second term), now we've double counted the number of ways of placing $n$ objects into $k-2$ boxes and so forth using inclusion-exclusion as mentioned in comments.