I randomly assign $m$ objects into one of $n$ sets. How do I compute expected value of the number of non-empty sets? To put it into more colorful terms, let's say I have $m$ balls and $n$ boxes.  I select one of the $m$ balls and randomly place it into one of the $n$ boxes.  I do this with each ball until I have none left.  I then take all of the boxes with no balls left in them and set them aside.  What is the expected value of the number of boxes left?
This question is derived from a math competition I participated in a year ago.  I spent weeks trying to figure this one out, but I never quite managed to wrap my head around the solution.
 A: For $i=1,2,\cdots{},n$ define $X_i$ as $X_i=1$ if box $i$ ends up with non-zero balls and $X_i=0$ if not. Set $$X=X_1+X_2+\cdots{}X_n.$$
Notice that $X$ is the total number of boxes which are non-empty. Therefore,
$$\mathbb{E}(X)=\mathbb{E}\left(X_1+X_2+\cdots{}+X_n\right)=\mathbb{E}(X_1)+\mathbb{E}(X_2)+\cdots{}+\mathbb{E}(X_n).$$
For all $i$, we have $X_i=0$ if all the $m$ balls end up in one of the other boxes. Hence $$\mathbb{E}(X_i)=P(X_i=1)=1-P(X_i=0)=1-\left(\dfrac{n-1}{n}\right)^m.$$
Summing this up gives us,
$$\mathbb{E}(X)=\sum \mathbb{E}(X_i)=n\left(1-\left(\dfrac{n-1}{n}\right)^m\right).$$
A: Here is  an algebraic  proof that I  present for variety.   Did anyone
notice  that  the  subject  line  and  the  problem  statement  switch
variables?

We have by inspection that the desired quantity is given by
$$n^{-m} \sum_{q=1}^n q\times {m\brace q} 
\times q! \times {n\choose q}.$$
The  first  factor  in  the  sum  is  the value  of  the  RV  for  the
expectation. The  second and third  count partitions of the  $m$ balls
into  $q$ sets  where  the order  of  the sets  matters. The  binomial
coefficient represents the  choice of $q$ boxes for  the set partition
from among the $n$ available boxes.

Recall the species of set partitions which is
$$\mathfrak{P}(\mathcal{U}\mathfrak{P}_{\ge 1}(\mathcal{Z}))$$
so that the bivariate generating function is
$$G(z, u) = \exp(u(\exp(z)-1))$$
which finally yields
$${m\brace q} =
m! [z^m] \frac{(\exp(z)-1)^q}{q!}.$$
This yields for the sum
$$m! [z^m] 
\sum_{q=1}^n q\times q! \times {n\choose q} 
\frac{(\exp(z)-1)^q}{q!}
\\ = m! [z^m] 
\sum_{q=1}^n {n\choose q} \times q \times
(\exp(z)-1)^q.$$
Now observe that
$$\sum_{q=1}^n {n\choose q} \times q \times x^q
= x ((1+x)^n)' = n x (1+x)^{n-1}$$
which yields for the sum
$$m! [z^m] \times n \times (\exp(z)-1) \exp(z(n-1))
\\ = n \times m! [z^m] (\exp(nz)-\exp((n-1)z)).$$
Extracting coefficients and including the scalar before the sum yields
$$n^{-m} \times n \times m! \times
\left(\frac{n^m}{m!}-\frac{(n-1)^m}{m!}\right)
\\ = n \times 
\left(1 - \left(1-\frac{1}{n}\right)^m\right).$$
