$\begingroup$

Five people check identical suitcases before boarding an airplane. At the baggage claim, each person takes one of the five suitcases at random. What is the probability that every person ends up with the wrong suitcase?

I think I need to use the principle of inclusion exclusion to solve this but I'm not quite sure how.

$\endgroup$ 4

2 Answers

$\begingroup$

Yes, the answer in your comment is right; the probability is

$$ \frac{!5}{5!}=\frac{\left[\frac{5!}{\mathrm e}\right]}{5!}=\frac{44}{120}=\frac{11}{30}\;. $$

$\endgroup$ $\begingroup$

There are $5!=120$ ways for the five suitcases to be claimed. We can think of these as permutations of $(1,2,3,4,5),$ where the people are numbered $1$ through $5$ and their suitcases are numbered correspondingly. Then we want to determine what fraction of the permutations have no fixed points (no people matched to their own suitcases). We can use complementary counting, subtracting the permutations that have at least one fixed point from the total.

There are $4!$ permutations with (at least) a given fixed point -- thus, $4!$ permutations that match person $1$ with his own suitcase, $4!$ that match person $2$ with her own suitcase, and so on, making $\binom 51\cdot 4!$ permutations that have a fixed point. But some permutations have more than one fixed point and have been overcounted, so we need to use PIE.

There are $\binom 52$ ways to choose two fixed points, and $3!$ permutations that have (at least) those two fixed points. Thus we subtract $\binom 52\cdot 3!$ permutations that have two fixed points, then correct for those that have more than two fixed points.

Continuing in this way, there are $\binom 53$ ways to choose three fixed points, and $2!$ permutations that have (at least) those three fixed points. There are $\binom 54$ ways to choose four fixed points, and $1!$ permutation that has those four fixed points. Finally, there is $0! = 1$ permutation that fixes all five points.

Thus, by complementary counting and PIE, the number of permutations with no fixed points is \begin{align*} 5! - \binom 51\cdot 4! + \binom 52\cdot 3! - \binom 53\cdot 2! + \binom 54\cdot 1! - 0! ~&= 120 - 120 + 60 - 20 + 5 - 1 \\ &= 44. \end{align*}

The probability that a random permutation has no fixed points is $\frac{44}{120} = \boxed{\frac{11}{30}}$.

$\endgroup$

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy