Probability question - inclusion/exclusion doesn't work. What else possible here?

Question

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?

Answer 1

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)$.

Answer 2

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$