3
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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}$$

$\endgroup$
  • $\begingroup$ Really cool! If I may ask, why the alternating signs in Eq. $(1)$? Aren't we supposed to subtract all those ways of missing from the total of $k^n?$ $\endgroup$ – user929304 Apr 4 at 12:02
  • $\begingroup$ I mean I didn't understand the reasoning in the paragraph afterwards, namely "..counting sequencies with two missing colors twice...", when all we had counted was sequencies with only 1 color missing. Is there a simple way to see that? $\endgroup$ – user929304 Apr 4 at 12:26
  • $\begingroup$ @user929304 You have to understand the inclusion-excluison principle. The link provided in my answer is an excellent start and you find many more sources on the net. $\endgroup$ – Oldboy Apr 4 at 13:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.