0
$\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$
  • 3
    $\begingroup$ This looks to me like a question about derangements. en.wikipedia.org/wiki/Derangement; Edit: this may also prove useful math.illinoisstate.edu/day/courses/old/305/… $\endgroup$ – Alex Wertheim May 9 '13 at 21:53
  • 1
    $\begingroup$ For $5$ people, we can do it by reasonably well organized counting. Don't need PIE. By the time we get to $7$, need more structure. But in case you want crude, A's suitcase goes to one of the other $4$. Say it goes to B. We will count possibilities, then multiply by $4$. So A's goes to B. Two possibilities (i) B's goes to A or (ii) to someone else. Counting the possibilities for (i) is easy. Also for (ii). B's can go to one of C, D, E. Say it is C, but then we will multiply by $3$. Almost done. $\endgroup$ – André Nicolas May 9 '13 at 22:16
  • $\begingroup$ It is a derangement question. Just use the formula. $\endgroup$ – user67773 May 9 '13 at 22:46
  • $\begingroup$ So using the derangement formula we get, $!5=[\frac{5!}{e}]=44$ So our answer is $\frac{44}{120}=\frac{11}{30}$. Is that right? $\endgroup$ – John Marty May 9 '13 at 22:52
1
$\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$
1
$\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

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.