What is the expectation of observing unique colors in a combinatorial problem? Suppose I have $K$ colors and for each color there are $N$ balls, so there are $K*N$ balls in total. Now I draw $M$ balls from them. For these $M$ balls, some balls have the same color and some don't. Let $K_u$ be the number of colors that are unique in the $M$ balls. My question is: what is the expectation of $K_u/K$?
 A: I suspect asymptotics are what would be most useful here. For an exact value of the expectation of $K_u$ we have from first principles (the $M!$ from the EGF cancels):
$$\frac {[z^M] \sum_{p=1}^K {K\choose p} p
\left(\sum_{q=1}^N \frac{z^q}{q!} \right)^p}
{[z^M] \left(\sum_{q=0}^N \frac{z^q}{q!}\right)^K}.$$
We may simplify the numerator to
$$[z^M] K \sum_{p=1}^K {K-1\choose p-1}
\left(\sum_{q=1}^N \frac{z^q}{q!} \right)^p
= [z^M] K \left(\sum_{q=1}^N \frac{z^q}{q!} \right)
\left(\sum_{q=0}^N \frac{z^q}{q!} \right)^{K-1}
\\ = [z^M] K 
\left(\sum_{q=0}^N \frac{z^q}{q!} \right)^{K}
- [z^M] K
\left(\sum_{q=0}^N \frac{z^q}{q!} \right)^{K-1}.$$
We get for the expectation $K_u$ divided by $K$
$$\bbox[5px,border:2px solid #00A000]{
1 - \frac{
[z^M] \left(\sum_{q=0}^N \frac{z^q}{q!} \right)^{K-1}}
{[z^M] \left(
\sum_{q=0}^N \frac{z^q}{q!} \right)^{K}}.}$$
As a sanity check, this will produce the correct value one when $M\gt
N(K-1).$ Furthermore with $M=1$ we get $1-{K-1\choose 1}/{K\choose 1} =
1/K$ which is correct as well.
A: Ah, I see Marko answered while I was typing. Probably a much better answer! :)
To me this looks like a multivariate hypergeometric experiment. And if that is the case I don't see a way to write out the expectation in a simple way. Especially since you have to consider both $M > K$ and $M\leq K$.
If we say that $K$ is a constant, then we get:
$$
\Bbb{E}\left[\frac{K_u}{K}\right] = \frac{\Bbb{E}[K_u]}{K}
$$
I can show my thinking with a simplified example with $K=3$ (red, white, blue), $N = 3$ and $M = 2$. The probability mass function is:
$$
P(Y_r = y_r, Y_w = y_w, Y_b = y_b) = \frac{{3\choose y_r}{3\choose y_w}{3\choose y_b}}{{9\choose 2}}
$$
Drawing one color is the same as drawing either 2 red, 2 white or 2 blue balls.
$$
P(K_u = 1) = P(Y_r = 2, Y_w = 0, Y_b = 0) + P(Y_r = 0, Y_w =2, Y_b = 0) + P(Y_r = 0, Y_w = 0, Y_b = 2)
$$
So:
$$
P(K_u = 1) = 3\cdot \frac{{3\choose 2}{3\choose 0}{3\choose 0}}{{9\choose 2}}
$$
And when you draw two colors, that is the same as drawing a white and red ball, red and blue ball, or white and blue, which can also be done in 3 ways.
$$
P(K_u = 2) = 3\cdot \frac{{3\choose 1}{3\choose 1}{3\choose 0}}{{9\choose 2}}
$$
In this simplified case, the expectation becomes:
$$
\Bbb{E}[K_u] = 1\cdot P(K_u = 1) + 2\cdot P(K_u = 2)
$$
which is then divided by $K$ to get $7/12 \approx 0.58333$.
Here is some R code for simulating.
K = 3;N = 3;M = 2

NSIM = 100000
Ku = rep(0, NSIM)
for (i in 1:NSIM) {
  ss = sample(c("w", "w", "w", "b", "b", "b", "r", "r", "r"), size = M, replace = FALSE)
  Ku[i] = length(unique(ss))
} 

P1 = 3*choose(3, 2)*choose(3, 0)*choose(3, 0)/choose(9,2)
P2 = 3*choose(3, 1)*choose(3,1)*choose(3, 0)/choose(9,2)

mean(Ku)/K
(1*P1 + 2*P2)/K

Please let me know if I did anything wrong!
