I wonder if the following probability+number theory problem is solved already:
We have a basket containing $x$ colored balls, where each ball is colored uniquely.
Each time we draw a ball randomly (uniformly) from the basket, write its color down and put back the ball into the basket again. We repeat this process $n$ times.
The question is, what is probability of drawing $k$ different colors (i.e. set of drawn colors is of size $k$), having tried $n$ times and given the total of $x$ uniquely colored balls?
Best Answer
Pick a single set of $k$ colors from the set of $x$ available colors and forget the remaining colors for the time being. Obviously you can do that in $\binom xk$ different ways.
How many sequencies of length $n$ are there with all balls having a color from the chosen set of $k$ colors, with every color appearing in the sequence at least once?
We'll use the inclusion-excluison principle. Let's start with the total number of sequencies, which is $k^n$.
Then we'll remove all sequencies with one color missing. That number is $\binom k1 (k-1)^n$. Why is that so? You can choose one missing color in $\binom k1$ different ways, with $n$ balls in the sequence having the remaining (k-1) colors.
But in that set you are counting sequencies with two missing colors twice, so we need to add the number of sequencies with two colors missing. And that number is is $\binom k2 (k-2)^n$. You can choose two missing colors in $\binom k2$ different ways, with $n$ balls in the sequence having the remaining (k-2) colors.
Repeat the same proces up to $(k-1)$ missing colors and you'll get the total number of sequencies of length $n$ with colors from the predefined set of $k$ colors and no color missing:
$$k^n-\binom k1 (k- 1)^n\tag{1}+\binom k2 (k- 2)^n-\binom k3 (k- 3)^n+\dots=\sum_{i=0}^{k}(-1)^i\binom ki(k-i)^n$$
But you can select a set of $k$ different colors in $\binom xk$ different ways. So the total number of all sequencies with exactly $k$ different colors is:
$$\binom xk\sum_{i=0}^{k}(-1)^i\binom ki(k-i)^n$$
Note that multiplication is allowed here: two sequencies having two different sets of $k$ colors are always different so nothing is counted twice here.
The total number of sequencies, with no restrictions placed on ball colors is simply $x^n$. Therefore, the probability should be:
$$P=\frac{\binom xk\sum_{i=0}^{k}(-1)^i\binom ki(k-i)^n}{x^n}$$