1
$\begingroup$

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$$

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Phicar May 22 '14 at 17:06
  • $\begingroup$ okaay. i get it now. thanks. $\endgroup$ – user103828 May 22 '14 at 19:52
1
$\begingroup$

\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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.