What's the expected number of distinct values within a binomial distribution sample? Given $X$ has a binomial distribution $B(n,p)$. Now I take $k$ samples from $X$. What's the expected value of how many distinct values I sampled?
My rather futile approach was: Given after $k$ draws, I have drawn the set $M_k$ of values. The probability of now drawing a previously undrawn value is
$$a_k := 1-\sum_{v\in M_k}P(X = v).$$
I think I could compute $E[a_k]$ from $B(n,p)$. However, even then, how do I use this to answer the original question about the cardinality of $M_k$?
 A: Let us reformulate and generalize a bit. Say we have a collection of $n$ objects ($n \ge 1$). We sample with replacement from this collection $k$ times.  Each time the probability of selecting object $i$ is $p_i$.  How many distinct objects do we see in the sample? If you for the $p_i$'s replace the binomial probabilities you recover your problem. 
One interpretation of this reformulation is via the birthday problem, what is expected value of distinct birthdays present in a party of $k$ people ($n=366$). Introduce indicator variables $I_1, \dotsc, I_n$, $I_i=1$ if object $i$ was seen, 0 else. Then the number of distinct objects is $I=\sum_1^n I_i$ with expectation 
$$ \DeclareMathOperator{\E}{\mathbb{E}}
\E I = \sum_1^n \E I_i = \sum_1^n (1-p_i^k)=n-\sum_1^n p_i^k
$$
Here we used that $\DeclareMathOperator{\P}{\mathbb{P}} \P(I_i=1)=1-\P(I_i=0)=1-p_i^k$. 
Returning to the original problem, first we must replace the index set $1,2,\dotsc,n$ with $0,1,2,\dotsc,n$ so the expression becomes $\E I = n+1-\sum_0^n p_i^k$ with $p_i=\left(\binom{n}{i}p^i(1-p)^{n-i}\right)^k$ so
$$
  \E I = n+1-\sum_0^n \left(\binom{n}{i}p^i(1-p)^{n-i}\right)^k
$$
and I will leave for later if that can be simplified.
