Combinatorics pigeonhole probems

86 Views Asked by At

Let there be $R$ red and $B$ blue balls, with each ball distinct from the other (even of the same colour). $M$ balls ($(1)$ assume $M<R,B$) are to be chosen. What is the probability that the number of red balls chosen, $n(R)$, is $\ge x$ ($x<M$)?

Uncivilised solution ($N(...)$ is the number of ways of doing $...$):

$$\large P(n(R) \ge x)=\frac{N(n(R)\ge x)}{N(n(R)< x)+N(n(R)\ge x)}$$

$$N(n(R)\ge x)=N(n(R)= x)+N(n(R)= x+1)+...+N(n(R)= M)$$ $$=\frac{R!}{x!(R-x)!}\cdot\frac{B!}{(M-x)!(B-M+x)!}+...$$ $$=\sum_{i=x}^M\frac{R!}{i!(R-i)!}\cdot\frac{B!}{(M-i)!(B-M+i)!}$$ $$=\sum_{i=x}^M\binom{R}{i}\binom{B}{M-i}$$ Similarly, $$N(n(R)< x)=\sum_{i=0}^{x-1}\binom{R}{i}\binom{B}{M-i}$$

But like all uncivilised solutions, I feel it's necessarily long and overcomplicated. Is there a better way to solve this problem? Does this way work if restriction $(1)$ doesn't apply?

It feels a little like the territory of the principle of inclusion and exclusion, but I'm not sure how to apply it here.

1

There are 1 best solutions below

1
On BEST ANSWER

It is uncivilized to use caps. So assume that there are $r$ red and $b$ blue, and we are choosing $m$ balls.

There are $\binom{r+b}{m}$ equally likely ways to choose $m$ balls from the $r+b$.

The number of ways to choose $i$ red and therefore $m-i$ black is $\binom{r}{i}\binom{b}{m-i}$. So our probability is $$\frac{\sum_{i=x}^m \binom{r}{i}\binom{b}{m-i}}{\binom{r+b}{m}}.$$ There is no nice closed form for the above sum.