How to solve this probability/combinatorics question about balls in bins

362 Views Asked by At

Below is the problem that I need to solve

Suppose you blindly place five balls labeled A, B, C, D and E inside five bins labeled A, B, C, D and E. What are the chances that, in your selection, no ball has a label that matches its box?

I tried to break it down and think about the probability of one ball being placed blindly inside its matching bin as simply $\frac{1}{5}$ and the complementary event, the ball not being placed inside its matching bin, as $\frac{4}{5}$. But I know this is overly simplistic for the problem and any help on how to actually start approaching it would be appreciated.

1

There are 1 best solutions below

0
On

That sounds like a question of finding permutations without a fixed point.

The idea

Let's just assume we've got our balls sitting in a row, from A to E. Below, we've got our bins arranged from A to E. Once we've blindly done our permutation on the balls (more on that later), we'll put the leftmost ball in the row into the leftmost bin (bin A), the next ball into the next bin (bin B), and so on.

Now, all we have to do is think about how many permutations (rearrangements) of balls there are such that no ball is put into the same bin, i.e. such that no ball is sitting in the same position as it did before the permutation. We later divide the number of permutations that fulfill this condition by the total number of permutations of our balls to get the probability for this event.

The approach

Obviously, we've got an order of $5$ balls to permutate. For this, there are $5!$ possibilities in total ($5$ possibilities to choose the leftmost ball, multiplied by the remaining $4$ possibilities to choose the next ball, and so on).

For the amount of permutations without a fixed point (i.e., the amount of rearranged ball orders in which no ball is sitting in the same place as before), we need to construct the derangement number. Coming up with a way to do this is a little harder, but Wikipedia sketches a proof for it. This is the resulting formular: $$ !n = n! \cdot \sum_{i=0}^{n} \frac{(-1)^i}{i!} $$ where $n$ is the number of objects to rearrange.

Then you just plug $n=5$ into this formular and you receive the value for $!5$. Your probability will be $\frac{!5}{5!}$.

Fun fact: $\frac{!n}{n!} \approx \frac{1}{e}$ for $n \geq 5$!