Number of ways to partition a set with cardinality at least $k$ into $k$ nonempty subsets. 
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$?
 A: 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. 
A: The usual  approach is  via inclusion-exclusion. It  can also  be done
with combinatorial  classes, however. We  get for partitions  into $k$
non-empty subsets the marked class
$$\def\textsc#1{\dosc#1\csod}
\def\dosc#1#2\csod{{\rm #1{\small #2}}}
\textsc{SET}(\mathcal{U} \times \textsc{SET}_{\ge 1}(\mathcal{Z})).$$
This gives the mixed bivariate generating function
$$G(z, u)  = \exp(u(\exp(z)-1)).$$
Extracting first the coefficient in $k$:
$$\sum_{n\ge k} {n\brace k} \frac{z^n}{n!} =
[u^k] \exp(u(\exp(z)-1))
= \frac{(\exp(z)-1)^k}{k!}$$
and next the coefficient in $z$:
$${n\brace k} = n! [z^n] \frac{(\exp(z)-1)^k}{k!}
= \frac{n!}{k!} [z^n]
\sum_{q=0}^k {k\choose q} (-1)^q \exp((k-q)z).$$
This is
$$\bbox[5px,border:2px solid #00A000]{{n\brace k} = \frac{1}{k!}
\sum_{q=0}^k {k\choose q} (-1)^q (k-q)^n.}$$
