exactly $k$ distinct values in $n$ $n$-sided dices

Question

We roll $n$ $n$-sided dices. What is the probability of getting exactly $k$ different values? From the union bound (as every possible $k$ sequence might contain the $k$ different results), I think the probability should relate to $\binom {n}{k}$. On the other hand if we had $k$ throws, the probability would be something like $\frac{k-1}{k} \cdot \frac{k-2}{k} \cdots \frac{1}{k}$. So now is it something like $\binom {n}{k} \cdot \frac{n-1}{n} \cdots \frac{n-k-1}{n}$? I think I am missing the $n-k$ failures part. Would it be $ \binom{n}{n-k} \cdot \frac{1}{n} \cdots \frac{n-k-1}{n}$ . Can you help me?

Answer 1

This is an extended Comment just to help you get started.

Let $n = 6$ and $k = 1.$ That means getting the same result on all $6$ rolls of an ordinary fair cubical die: $6(1/6)^6 = 0.0001286.$

Let $n = 6$ and $k = 6.$ That means getting all different faces in $6$ such rolls: $6!/6^6 = 0.0154321.$

From there is gets a little more complicated. Make sure you exclude the results you don't want as well as providing for the ones you do. And make sure the numerator counts ordered arrangements if the denominator does.

Maybe try $k=2$ or $k=5$ next. Do it soon to learn something before another Answers spoils the fun.

Below are results from a million simulations in R of the experiment for $n = 6,$ giving approximate probabilities for various values of $k.$ (You can trust the first 2 or 3 decimal places, sometimes 4.) The results are not far off for $k=1$ and $k=6$ above. You might want to use it as a reality check as you try different combinatorial approaches.

 m = 10^6;  n = 6;  k = 3;  u = numeric(m)
 for (i in 1:m) {
   faces = sample(1:n, n, rep=T)
   u[i] = length(unique(faces)) }
 table(u)/m
 ## u
 ##        1        2        3        4        5        6 
 ## 0.000114 0.019808 0.230756 0.501897 0.231939 0.015486