Expected value of empty baskets with unlimited capacity? You put m apples randomly in n baskets. Suppose each basket has unlimited capacity, what is the expected number of empty baskets?
 A: We make a probability model. Assume that the apples are assigned to baskets one at a time. For each apple, each basket is equally likely, and the assignments are independent.
The standard tool here is the method of indicator random variables. For $i=1$ to $n$, let random variable $X_i$ be $1$ if Basket $i$ remains empty, and $0$ otherwise. 
Then the number $Y$ of empty baskets is $X_1+\cdots+X_n$, and by the linearity of expectation
$$E(Y)=E(X_1)+\cdots+E(X_n).$$
The probability that any individual apple toss misses Basket $i$ is $\frac{n-1}{n}$. Thus the probability that all $m$ tosses miss Basket $i$ is $\left(\frac{n-1}{n}\right)^m$. 
It follows that $E(X_i)=\left(\frac{n-1}{n}\right)^m$, and therefore $E(Y)=n\left(\frac{n-1}{n}\right)^m$.
A: We have from first principles that the expectation is given by
$$n^{-m} \sum_{k=0}^n k {n\choose k}
\times {m\brace n-k} (n-k)!$$
Now the species of set partitions is given by
$$\mathfrak{P}(\mathcal{U}\mathfrak{P}_{\ge 1}(\mathcal{Z}))$$
which gives the generating function
$$\exp(u(\exp(z)-1))$$
and hence
$${m\brace n-k} = m! [z^m] \frac{(\exp(z)-1)^{n-k}}{(n-k)!}.$$
Substitute this into the sum to get
$$n^{-m} m! [z^m] 
\sum_{k=0}^n k {n\choose k} (\exp(z)-1)^{n-k}
\\ = n^{-m} m! [z^m] 
\sum_{k=0}^n (n-k) {n\choose k} (\exp(z)-1)^{k}
.$$
The first term here is
$$n^{-m} m! [z^m] n \exp(zn)
= n.$$
Now we have
$$\sum_{k=0}^n k {n\choose k} x^k
= \sum_{k=1}^n k {n\choose k} x^k
=  x ((1+x)^n)'
= nx (1+x)^{n-1}.$$
We thus have for the second term
$$n^{-m} m! [z^m] n (\exp(z)-1) \exp(z(n-1))
\\= n^{-m} \times n \times (n^m-(n-1)^m)
= n (1-(1-1/n)^m).$$
Joining the two terms we get
$$n - n (1-(1-1/n)^m) =
n (1-1/n)^m.$$
