Probability of finding a non-repeating combination

Question

This is a real life problem, which I'm turning into balls just to make it easier to understand.

Suppose balls can be numbered from 1 to 12.

Suppose I have 10 boxes. Each box has 3 distinct balls, distributed at random.

A valid combination is if I can find, from those 10 boxes and taking 1 ball from each, a combination where all balls have distinct numbers (i.e. there are (12,10) valid combinations).

Here are some examples, to make it more concrete:

• Box 1 has (1,2,3), Box 2 has (2,3,4), Box 3 has (3,4,5)... Box 10 has (10,11,12). This is the best case scenario, I can easily make valid combinations such as (1,2,3,4,5,6,7,8,9,10); (1,2,3,..,9,11); and so on
• Box 1 has (1,2,3), Box 2 has (1,2,3), Box 3 has (1,2,3), Box 4 has (1,2,3). This is the worst case scenario, as I can't find any valid combination. I will always have to repeat 1, 2 or 3.

I would like to know what is the probability of finding scenarios that yield valid combinations from such a setup. In other words - given a scenario of 10 box with 3 distinct balls in each, what is the probability that from those 10 boxes I can find at least one valid combination (it doesn't matter if there is more than 1 valid combination).

Here's a potential approach:

The universe of potential combinations: A = C(12,3)^10

The cases where numbers repeat and I get an invalid scenario:

B = C(12,9) * C(9,3)^10

Probability is then 1 - B/A.

Answer 1

Consider a simpler case: 4 boxes and balls numbered from 1 to 6. We still put 3 balls in each box. I have chosen this case, since it is possible to write out all combinations and check corresponding probabilities.

For each box, we now have $6\choose3$ possible combinations.

In the first box, we can select any ball, yielding a probability of 1. For the second box, we have two options to select a valid ball (i.e. a ball not selected previously):

• A box without the ball that we already selected. The total number of possibilities for this case are ${1\choose0}{5\choose3}$. ${1\choose0}$ specifies the number of balls we select from the previously selected balls. ${5\choose3}$ specifies the number of combinations of choosing three balls from the remaining five that have not been selected previously. The probability of selecting a valid ball is 1, since the previously selected ball is not in the box.
• A box with the ball that we already have selected. Out of the $6\choose3$ possibilities, ${1\choose1}{5\choose2}$ have the already selected ball. Selecting a valid ball has a probability of $\frac{2}{3}$.

Thus, selecting a valid ball from the second box is given by $\frac{1\times {1\choose0}{5\choose3} + \frac{2}{3}\times{1\choose1}{5\choose2}}{6\choose3} = \frac{5}{6}$.

For the third box, we have the following cases:

• A box without the previously selected balls: ${2\choose0}{4\choose3}$ possibilities. The probability of selecting a valid ball is 1.
• A box with one previously selected ball: ${2\choose1} {4\choose2}$. The probability of selecting a valid ball is $\frac{2}{3}$.
• A box with two previously selected balls: ${2\choose2}{4\choose1}$ possibilities, with a probability of $\frac{1}{3}$ of not selecting a previously selected ball.

For the third box, the probability of selecting a valid ball is consequently: $\frac{1 \times {2\choose0}{4\choose3} + \frac{2}{3} \times {2\choose1} {4\choose2} + \frac{1}{3}\times {2\choose2}{4\choose1}}{6\choose3} = \frac{4}{6}$.

For the fourth box, we have the following cases:

• No previously selected balls: ${3\choose0}{3\choose3}$ possibilities. We have a probability of 1 of selecting a valid ball.
• One previously selected ball: ${3\choose1}{3\choose2}$. Corresponding probability is $\frac{2}{3}$.
• Two previously selected balls: ${3\choose2}{3\choose1}$. Corresponding probability is $\frac{1}{3}$.
• Three previously selected balls: ${3\choose3}{3\choose0}$. Corresponding probability is 0.

For the fourth box, the probability of selecting a valid ball is thus given by: $\frac{1 \times {3\choose0}{3\choose3} + \frac{2}{3}\times {3\choose1}{3\choose2} + \frac{1}{3} \times {3\choose2}{3\choose1} + 0 \times {3\choose3}{3\choose0}}{6\choose3} = \frac{3}{6}$.

We thus find the probability of valid combinations for this scenario as follows: $\text{P(selected balls are distinct)} = \frac{6}{6}\times\frac{5}{6}\times\frac{4}{6}\times\frac{3}{6} = \frac{\frac{6!}{(6-4)!}}{6^4}$.

This pattern also arises in your scenario. In your scenario, we find a probability of: $\text{P(Selected balls are all distinct)} = \frac{\frac{12!}{(12-10)!}}{12^{10}}\approx 0.003868$.