Q:

Number of distinct balls selected from n balls.

$n$ distinct balls are placed in a box. $m$ balls are selected with substitution. Let X be the number of the distinct balls that have been taken out. Find $E(X)$. I have tried to write $X$ as the sum of $n$ Bernoulli random variables $Y_i$ where 
$Y_i$ is 1 if at least $i$ distinct balls have been taken out and 0 otherwise. But I get into very deep computational trouble when dealing with summations. Is there an easier way to do this?

A:

For any of the $n$ balls, let $X_i=1$ if Ball $i$ is chosen at some stage, and let $X_i=0$ if Ball $i$ is never chosen. Then the number $Y$ of distinct balls is given by $Y=\sum_1^n X_i$. By the linearity of expectation we have $E(Y)=\sum_1^n E(X_i)$.
The probability Ball $i$ is picked at some stage is $1$ minus the probability it is never picked. The probability it is never picked is $\left(\frac{n-1}{n}\right)^m$.
It follows that our expectation is $n\left(1-\left(\frac{n-1}{n}\right)^m\right)$.

