20. In $n$ urns, $k$ balls are thrown independently. (For each ball, the probability of it landing in any specific urn is $1 / n$.) Find the expected number of non-empty urns.
Solution. Let $\xi$ be the number of non-empty urns. Then $\xi=\sum_{i=1}^{n} I_{A_{i}}$, where $A_{i}=\{i-$ th urn is non-empty $\}$. Note that

$$
\mathrm{P}\left(\bar{A}_{i}\right)=\mathrm{P}\{\text { no ball falls into the } i \text {-th urn }\}=\left(\frac{n-1}{n}\right)^{k} .
$$

Then

$$
\mathrm{E} \xi=\sum_{i=1}^{n} \mathrm{E} I_{A_{i}}=\sum_{i=1}^{n}\left(1-\mathrm{P}\left(\bar{A}_{i}\right)\right)=n\left(1-\left(\frac{n-1}{n}\right)^{k}\right)
$$