Suppose we have an urn with $N$ different colored balls and $b$ balls of each color, for $Nb$ balls total in the urn. From this we randomly draw $r$ balls without replacement. What is the probability that these $r$ balls will contain exactly $k$ unique colors?

Clearly it must first be that for $Nb>r>0$ and $r>k>1$ to have a positive probability. Beyond this, the closest I can get is:

\begin{equation} P(k|r)=\frac{\binom{N}{k} \binom{b}{1}^k \binom{kb-k}{r-k}}{\binom{Nb}{r}} \end{equation}

But I know it's not right. My reasoning for the above equation is that there are $\binom{Nb}{r}$ ways can choose the $r$ balls overall (though even this I'm not sure about -- should this take into account the unique colors? Something along the lines of the adjusting the number of permutations of a word with multiple letters?). And for the numerator, we select the $\binom{N}{k}$ colors, for each of these colors we select one of the $b$ balls (so $k$ balls total) to ensure that each color has at least one ball. Then we select the remaining $r-k$ balls from the remaining $kb-k$ balls of the $k$ colors.

But this isn't quite correct, which I think is either due to the denominator being wrong. Or to the fact that the $\binom{kb-k}{r-k}$ should likewise take into account the unique ways that the $r-k$ balls can be binned among the $k$ colors.

Any thoughts? Thanks!

  • $\begingroup$ Thanks for the quick response, but that doesn't seem to be right either. Checking things numerically, when I choose some values for $N$, $b$, and $r$ and sum this expression for $k=1,...,S$, it gives a probability significantly less than 1. $\endgroup$ Mar 1 '18 at 23:11
  • $\begingroup$ You are right. I will delete my suggestion. Why do you believe that your solution is wrong? $\endgroup$
    – user
    Mar 1 '18 at 23:23
  • $\begingroup$ Because it likewise doesn't sum to 1 -- it sums to something larger than 1, depending on the parameter choices. $\endgroup$ Mar 1 '18 at 23:37

What is certainly correct is the number to choose $r$ of $Nb$ balls, and $k$ of $N$ colors. Thus the error can be hidden only in the way to choose $r$ of $kb$ balls subject to the restriction that at least one ball of each of $k$ colors have to be chosen.

Let's try inclusion exclusion principle. We first take all possible combinations to choose $r$ of $kb$ balls, then subtract those which have at least one color missing, then add those which have at least two colors missing and so on. This results in the expression: $$ {b,k\brack r}=\sum_{i=0}^k (-1)^i\binom{k}{i}\binom{b(k-i)}{r}, $$ with the final result: $$ P(k|r)=\frac{\binom{N}{k}{b,k\brack r}}{\binom{Nb}{r}}. $$

  • $\begingroup$ Thanks for the answer.Would you mind explaining why you have used inclusion exclusion and also what was wrong with user3037237 equation logically?? $\endgroup$
    – NewGuy
    Mar 2 '18 at 10:53
  • $\begingroup$ Wrong was obviously that some combinations were counted several times. Assume we choose in $\binom{b}{1}$ a green ball numbered $i$. Further performing a choosing labeled by $\binom{kb-k}{r-k}$ there will be in general combinations containing a green ball numbered $j$. But we will count the same combination if we choose the $j$-th green ball in the first step and the $i$-th ball in the second one (all other balls being the same). To avoid this double counting the inclusion-exclusion principle was applied. $\endgroup$
    – user
    Mar 2 '18 at 12:21
  • $\begingroup$ Thanks! This is exactly what I was looking for, and it matches up with the numerical results. One point of clarification -- I understand that when doing the inclusion/exclusion principle we have to subtract those that have at least one color missing. But why does this "over subtract"? That is, why do we have to add back those that have at least two missing (which in turn, over-adds slightly)? It seems like if you want all of the partitions with no colors missing, this is just the total number of partitions, minus those with at least one missing? $\endgroup$ Mar 2 '18 at 20:39
  • $\begingroup$ user3037237 This "over substract" exactly by the same reason which was responsible for overestimation in your version. You cannot subtract only the number of combinations where exactly one color is missing. Instead you subtract all combinations where this color is missing. Now consider a combination with 2 colors missing. How many times will it be subracted? $\endgroup$
    – user
    Mar 3 '18 at 17:30

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.