How many ways are there to partition an $n$-element set where $n \geq k$ into $k$ nonempty subsets?
According to the formula provided here, the answer is $\dfrac{1}{k!}\displaystyle\sum_{i=0}^k (-1)^i{k\choose i} (k-i)^n.$ However I don't understand how this formula was derived. I have a rough idea of why combinatorics are involved here as we have to choose elements from a set. Also, there are $k!$ repetitions, so we have to divide by $k!$. However, why is the sum alternating (does this have to do w/ the use of complements?) and what is the significance of the term $(k-i)^n$?
Best Answer
The alternating sum is a simple application of inclusion-exclusion. Imagine you are putting $n$ distinguishable balls into $k$ distinguishable boxes, and counting the no. of ways $M$ where all boxes are non-empty. Let $A_i$ be the set of placements where (at least) box $i$ is empty. By inclusion-exclusion,
$$M = k^n - \sum_i |A_i| + \sum_{i<j} |A_i \cap A_j| - \sum_{i<j<l} |A_i \cap A_j \cap A_l| + \dots$$
The first term $k^n$ counts placements without any restrictions, then you subtract cases where (at least) one box is empty, add back cases where (at least) two boxes are empty, etc. But e.g. $|A_i \cap A_j| = (k-2)^n$ because you're just throwing into the other $k-2$ boxes, and there are ${k \choose 2}$ of such terms.