How many balls were drawn? (a combinatorial problem) An experiment is to draw a ball from a pool of N balls labelled with 1, 2, ..., N, with replacement. If one repeats the experiment M times independently, then what's the average number of different balls that were drawn?

For $i=1$ to $M$, let $X_i=1$ if the ball drawn on the $i$-th draw is "new," and let $X_i=0$ otherwise. Let 
$$Y=X_1+X_2+\cdots+X_M.$$
Then $Y$ is the number of different balls. By the linearity of expectation, we have
$$E(Y)=E(X_1)+E(X_2)+\cdots+E(X_M).$$
We need to find the $E(X_i)$, that is, the probability that $X_i=1$. Whatever ball is drawn on the $i$-th trial, the probability it does not occur in the first $i-1$ trials is $\left(1-\frac{1}{N}\right)^{i-1}$.  
Thus 
$$E(Y)=1+p+p^2+\cdots+p^{M-1},$$
where $p=1-\frac{1}{N}$. Sum the geometric series. We get
$$E(Y)=N\left(1-\left(1-\frac{1}{N}\right)^M\right).$$ 
