3
$\begingroup$

I see that the below formula is the explicit formula of the Stirling numbers of the second kind. I know that the Stirling number of the second kind is the number of ways to partition set of $n$ objects into $k$ non-empty subsets. But, I don't at all see from where the below formula comes from. Clearly, there is some kind of inclusion-exclusion going on, but I cannot figure it out. If someone can give me some kind of combinatorial interpretation of the formula, I would be glad.

$$ \begin{Bmatrix} n\\ k \end{Bmatrix} =\frac{1}{k!}\sum_{j=0}^{k}(-1)^{k-j}\binom{k}{j}j^n$$

$\endgroup$
5
$\begingroup$

$\begin{Bmatrix} n\\ k \end{Bmatrix}$ is the number of ways to distribute $n$ distinct objects into $k$ identical boxes with no empty boxes allowed/each box containing at least $1$ object. We will first consider distributions into $k$ distinct boxes.

The total number of ways to distribute $n$ distinct objects into $k$ distinct boxes with empty boxes allowed is: $$k^n$$

Let $A_i$ be the number of ways to perform the distribution with the condition that box $i$ must be an empty box. There are no restrictions on the other boxes. (This is equivalent to distributing the $n$ objects into the remaining $k-1$ boxes, empty boxes allowed.)

For example $A_1$ is the number of ways to distribute the objects into the $k$ boxes with box 1 being empty and is equivalent to distributing the objects into the remaining $k-1$ boxes, empty boxes allowed.

$$\implies |A_1| = (k-1)^n $$

Now we notice that $|A_1|=|A_2|=|A_3|=\dots$ since it doesn't matter which box is empty. (We are always distributing into the remaining $k-1$ boxes).

We know there are $\binom{k}{1}$ possible $A_i $

$$\sum_{i=1}^k|A_i| = \binom{k}{1}(k-1)^n$$

Using a similar argument, $|A_i\cap A_j|=(k-2)^n$ because it involves distribution into $k-2$ remaining boxes. Also, using the fact that $|A_1\cap A_2|=|A_1\cap A_3|=|A_1\cap A_4|...$ and that there are $\binom{k}{2}$ such terms,

$$\sum_{1\leq i,j\leq k}|A_i\cap A_j| = \binom{k}{2}(k-2)^n$$

On a similar note, we try extending this to when $l$ boxes must be empty:

$$\sum_{1\leq i,j\dots l\leq k}|A_i\cap A_j\cap \dots\cap A_l| = \binom{k}{l}(k-l)^n$$

$|A_1\cup A_2\cup \dots \cup A_k|$ is the number of ways to distribute $n$ distinct objects into $k$ distinct boxes with at least one empty box.

We are trying to find the distribution with no empty boxes: $$|\overline{A_1\cup A_2\cup \dots \cup A_k}|=k^n -|A_1\cup A_2\cup \dots \cup A_k|$$

By the principle of inclusion and exclusion,

$$=k^n-(|A_1|+|A_2|+|A_3|+...)+(|A_1\cap A_2|+|A_1\cap A_3|+|A_1\cap A_4|+...)-...$$

$$=k^n-\binom{k}{1}(k-1)^n+\binom{k}{2}(k-2)^n-\binom{k}{3}(k-3)^n+\dots +(-1)^l\binom{k}{j}(k-j)^n$$

$$=\sum_{l=0}^{k}(-1)^l\binom{k}{l}(k-l)^n$$

Let $j=k-l$, when $l=0$, $j=k$. When $l=k$, $j=0$.

$$=\sum_{j=k}^{0}(-1)^{k-j}\binom{k}{k-(k-j)}j^n (\text{this is technically wrong notation})$$

This is just the sum backwards. So we have:

$$=\sum_{j=0}^{k}(-1)^{k-j}\binom{k}{j}j^n$$

Now we divide by $k!$ since we are dealing with identical boxes:

$$\begin{Bmatrix} n\\ k \end{Bmatrix} =\frac{1}{k!}\sum_{j=0}^{k}(-1)^{k-j}\binom{k}{j}j^n$$

$\endgroup$
  • 1
    $\begingroup$ I didn't exactly understood the sums at the top, what do they correspond to, how did we find them, and why do we need to check all the intersections? In the below sum $\sum_{l=0}^{k}(-1)^l\binom{k}{l}(k-l)^n$, shouldn't be go up to $j$ and not $k$, cause in the inclusion exclusion we have $(-1)^l\binom{k}{j}(k-j)^n$, and lastly how do we get that these two sums are equal $\sum_{l=0}^{k}(-1)^l\binom{k}{l}(k-l)^n=\sum_{j=0}^{k}(-1)^{k-j}\binom{k}{j}j^n$? Please don't jump over any algebraic step. $\endgroup$ – user72151 Nov 16 '15 at 16:00
  • $\begingroup$ What do you mean with distinct and identical boxes? Does identical mean that all the boxes have same size, and distinct they all are of different size? $\endgroup$ – user72151 Nov 16 '15 at 18:09
  • $\begingroup$ @terett Let's say we have objects $a,b,c$. If we were to distribute them into two identical boxes, then $(a)(b,c)$ would be the same as $(b,c)(a)$. Now, if we were distribute them into two distinct boxes, say, box $A$ and $B$, $A:(a)$ $B:(b,c)$ would not be the same as $A:(b,c)$ $B:(a)$ $\endgroup$ – Nicholas Nov 17 '15 at 4:24
  • 2
    $\begingroup$ @Nicholas So, all you did was actually label the two boxes so you can distinguish them, you see that they are separate. $\endgroup$ – user72151 Nov 17 '15 at 8:15

Your Answer

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