2
$\begingroup$

I have the following question:

Four men went to a party and hung their coats in a closet. When they left, each of them randomly and uniformly picked a coat. What is the probability that no one got the coat they came with to the party?

I tried to solve it with inclusion/exclusion:

A_i - Man #i took not his coat.
I know the probabilty space is 4!.
Hence I tried to calculate: $$P=\frac{|A_1\cup A_2\cup A_3\cup A_4|}{4!}$$

The problem is in the inclusion/exclusion formula.

I don't know how to calculate the cardinality of the intersections. i.e.:$$|A_2\cap A_3|$$ Because if man #2 took a coat that doesn't belong to man #3 then the cardinality is 3*2 (the man #2 can take 3 coats and man #2 can take 2).

But, there is also an option man #2 took a coat that belongs to man #3 so I dont know how really calculate the cardinalities. It gets more complicated when there are more than 2 sets in the intersection.

Maybe inclusion/exclusion isn't the right tool here?

$\endgroup$
6
  • 1
    $\begingroup$ Such a permutation is known as a Derangement $\endgroup$
    – lulu
    Commented Apr 21, 2017 at 12:59
  • $\begingroup$ @lulu Cant it be solved with Inclusion/exclusion? I prefer not using Derangement because we are not supposed to know it. $\endgroup$
    – TheLogicGuy
    Commented Apr 21, 2017 at 13:01
  • 1
    $\begingroup$ Sure, that's one of the standard approaches. See, e.g., this $\endgroup$
    – lulu
    Commented Apr 21, 2017 at 13:05
  • $\begingroup$ Note: for four people you could simply list all the permutations and count the ones you want. The other methods come in handy for larger collections. $\endgroup$
    – lulu
    Commented Apr 21, 2017 at 13:11
  • $\begingroup$ Yes, I noticed it from your link to Wikipedia. It has an example similiar to my problem. Thank you $\endgroup$
    – TheLogicGuy
    Commented Apr 21, 2017 at 13:16

2 Answers 2

Reset to default
2
$\begingroup$

Inclusion-exclusion is the right tool, but you need to work with the complementary events. So let $B_i$ be the event that man $i$ takes his own coat, then $\Pr(B_i)=1/4$ and $\Pr(B_i\cap B_j)=1/12$ (because if man $i$ chooses his own coat, there are three coats left for man $j$, one of which is his).

The probability you want is $1-\Pr(B_1\cup B_2\cup B_3\cup B_4)$.

$\endgroup$
0
$\begingroup$

You can use derangement.

$4!\left(1 - 1 + \frac 1{2!} - \frac 1{3!} + \frac 1{4!} \right)$

$= 24\left(1 - 1 + \frac 12 - \frac 16 + \frac 1{24} \right)$

$= 9$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .