# Probability of getting k different colored balls from an urn with K different colors of balls, each color has the same number of balls

TLDR:

Let's say I have an urn with $$n$$ balls, with $$K$$ different colors of balls, where each color has the same number of balls: $$\frac{n}{K}$$. Given I reach into the urn and grab a ball (without replacement) $$m$$ times, what is the probability of getting $$k$$ different colors of balls?

Further explanation:

Example: I have an urn with $$GGRRBBYY = n = 8$$ number of balls, with $$K = 4$$ different colors of balls (Green, Red, Blue Yellow). What is the probability of me getting exactly $$k = 3$$ different colors of balls given I grab $$m = 5$$ balls from the urn.

Success: $$YGGBB$$

Failure: $$YRGBB$$

I want to find a way to solve this for any value of $$m$$,$$k$$,$$K$$,$$n$$.

This is essentially a more complicated version of figuring out the probability of $$m$$ balls falling into $$k \leq n$$ bins, for the 'balls into bins' question ($$m$$ balls in total, $$n$$ bins in total). See here (in equation 1) and here (at the end of the answer) solutions to solve the easier 'balls into bins' variant. The answer is:

$${n \choose k}\frac{\left\{\begin{array}{l} m \\ k \end{array}\right\} k !}{n^{m}}$$

I am looking for a similar solution to the urn problem I have stated. I believe using a multivariate hypergeometric distribution could give me the answer, although I think this will be complicated and extremely costly to compute. Basically, my idea is to count all possible combinations that exactly $$k$$ different colors of balls can be selected by applying the multivariate hypergeometric distribution formula many times. That is:

$$\frac{\sum {\frac{n}{K} \choose w_1}{\frac{n}{K} \choose w_2} \cdots {\frac{n}{K} \choose w_K}}{{n \choose m}}$$

The summation above denotes summing over all possible combinations of $$w_i$$ for all $$i$$, where $$w_1 + w_2 \cdots + w_K = m$$ and there are only $$k$$ number of $$w_i$$ that are greater than $$0$$. (excuse me on my potentially poor use of notation).

There must be a better way of formulating this... but if not, it would be nice of someone to suggest a fairly efficient way of computing this (by compute, I mean: some computer code that will calculate it for me). Or if someone could provide an approximation or a lower bound via a much more compact/simple formulation, that would also be wonderful! Perhaps modelling the problem as a 'balls into bin' scenario is a 'good enough' approximation...?

This similar question might also be inspiration for a better way to solve the problem.

• Pick $K-k$ colors and compute the likelihood of avoiding those colors. Then multiply by $\binom Kk$ to get the likelihood of no more than $k$ colors. Do it again for the likelihood of excluding $k+1$ colors. Subtract one answer from the other to get the likelihood of excluding exactly $k$ colors. Jun 27, 2022 at 21:58
• Thanks for the suggestion; it is clever yet simple! I noticed a couple grammar/logic errors. I think this is what you meant to say: "Pick $K−k$ colors and compute the probability of avoiding those colors. Then multiply by ${K \choose k}$ to get the probability of picking no more than k colors. Repeat the previous step to get the probability of avoiding $K - (k-1)$ colors (picking no more than $k-1$ colors). Subtract the second probability from the first probability to get the probability of picking exactly k colors." Jun 28, 2022 at 16:56
• hmmm... I'm a bit confused now. I tried calculating it the way you suggested and I think there is an issue with your method. Multiplying by ${K \choose k}$ results in over-counting (resulting in a probability greater than 1 in some instances). Jun 28, 2022 at 18:13
• You need to multiply the likelihood of avoiding $K-k$ specific colors by $\binom Kk$ in order to determine the likelihood of avoiding all possible sets of colors of that size. I suggest you edit the question to show this new work so we can see where the problem lies. Jun 28, 2022 at 20:02
• Cross-posted at CrossValidated here, with currently one answer masquerading as a comment. Sometimes CV is more useful for probability and combinatorics questions... Jul 23, 2022 at 7:16