# Probability of objects being grouped together in a set of sets

Say we have a collection of $b$ distinct, uncoloured balls distributed among $s$ nonempty sets of known sizes. We randomly select one ball and paint it black, and another $r$ balls and paint them red. What's the probability that the black ball is in the same set as a red ball?

I found a formula which works for the case where $r = 1$. Let $C$ be the set of ball sets, so $\left|C\right| = s$. Then the probability that the black ball is in the same set as the red ball is $$\frac{\sum_{c \in C} \left|c\right| \left(\left|c\right| - 1\right)}{b \left(b-1\right)}.$$

However, I don't see how to generalize this formula to arbitrary values of $r$.

The total number of ways to color one ball black and $r$ balls red is $$b\cdot{{b-1}\choose{r}}=\frac{b!}{r!(b-r-1)!}.$$ Of these, the number that place the black ball in a set with no red balls is $$\sum_{c\in C}\left|c\right|{{b - \left|c\right|}\choose{r}}=\sum_{c\in C}\frac{\left|c\right|(b-\left|c\right|)!}{r!(b-\left|c\right|-r)!},$$ where the sum is over sets such that $b-\left|c\right|\ge r.$ The probability that the black ball is in a set with at least one red ball is therefore $$1-\sum_{c\in C}\frac{\left|c\right|(b-\left|c\right|)!(b-r-1)!}{b!(b-\left|c\right|-r)!}.$$ In the $r=1$ case, this becomes $$1-\sum_{c\in C}\frac{\left|c\right|(b-\left|c\right|)}{b(b-1)}=\sum_{c\in C}\frac{\left|c\right|}{b}-\sum_{c\in C}\frac{\left|c\right|(b-\left|c\right|)}{b(b-1)}=\sum_{c\in C}\frac{\left|c\right|(\left|c\right|-1)}{b(b-1)},$$ agreeing with your answer. For $r=2$, the result is $$1-\sum_{c\in C}\frac{\left|c\right|(b-\left|c\right|)(b-\left|c\right|-1)}{b(b-1)(b-2)},$$ and so on.
• I'm not sure I follow. How can $$1-\sum_{c\in C}\frac{\left|c\right|(b-\left|c\right|)!(b-r-1)!}{b!(b-\left|c\right|-r)!}$$ give a correct answer for the case that there is only one set of balls (i.e., $s = 1$)? In this case $b = \left|c\right|$, so $b - \left|c\right| - r$ must be negative, and you can't compute the factorial of a negative number. – Psychonaut Apr 4 '14 at 9:52
• Oh, never mind, I see now that this sum, like the previous one you wrote, is meant to apply only to those sets where $b - \left|c\right| \geq r$. – Psychonaut Apr 4 '14 at 10:30