Vrftsjtryk

Question:

Four men go into a restaurant and leave their umbrellas at the door. On their way out, each man picks up an umbrella and they discover when they get outside that no man has his own umbrella. In how many different ways can this situation arise?

My logic: total no - the combination that four men take their own umbrella.

first one: 1/4 prob choose her's umbrella. second one: 1/3 prob...third 1/2...last 1/1

but it sounds my answer is not correct ...

Is there anyone can help? The answer should be 9.

I'll give the general solution. Let $D_n$ be the number you want to count when there are n men. Assume first man(Let's denote him $m_1$.) takes the k'th men(Let's denote him $m_k$.)'s umbrella.(k will be $2,cdots,n$. So you have to multiply $n-1$ at the last) Then there are two cases.

(1) $m_k$ takes $m_1$'s umbrella.
(2) $m_k$ takes other one's umbrella.

For the first case, then you only have to count the case that none of remaining $n-2$ men takes his own umbrella. It's $D_{n-2}$.

For the second case, assume $m_1$ exchange $m_k$'s umbrella and his own umbrella. (Note that this exchange doesn't affect the counting.) It means now, $m_1$ has his umbrella, and no other one has his own umbrella. It's $D_{n-1}$.

Now you get the difference equation of $D_n$.
$$
D_n=(n-1)(D_{n-1}+D_{n-2})
$$

And $D_1=0$, $D_2=1$. I'll skip how to get general term of $D_n$. You can find it by googling Derangement.

The men aren't in any order. Randomly pick a man to be the first man.

There are $3$ possible ways for him to pick an umbrella that is not his. Call the man whose umbrella he picks man number $2$.

There are $3$ possible ways for man number two pick an umbrella that is not his. $1$ of them is to pick the umbrella that is the first mans. And $2$ of them is to pick an umbrella of another man.

If he picks the first man's umbrella there is umbrella then there are two men and their umbrellas left and there is only one way to the two remaining men can take each others umbrellas. So there are $3$ ways that can happen. (i.e. the first man has three choices of umbrellas. Everyone else has only a single choice for this to occur.)

If he picks one of the two other men's umbrella call the owner of that umbrella the third man. There are two umbrella's left: The umbrella belonging to the first man and the umbrella belonging to the last man. For no man to get their own the third man can't leave the last man's umbrella for the last man so he must take the first man's umbrella. So there were $3*2$ ways for this to occur. (Three choices for the first man to pick how the 2nd man is, and two choices for the second man to pick who the third is.

So $3 + 3*2 = 9$ ways total.

They are if the men are $A,B,C,D$ and their respective umbrellas are $a,b,c,d$.

$Ab,Ba,Cd,Dc$

$Ab,Bc,Cd,Da$

$Ab,Bd,Dc,Ca$

$Ac,Ca,Bd,Db$

$Ac,Cb,Bd,Da$

$Ac,Cd,Db,Ba$

$Ad, Da,Cb,Bc$

$Ad, Db,Bc,Ca$

$Ad,Dc,Cb,Ba$

Consider the event first man gets his own umbrella this is possible in 3! ways.
Similarly for 2nd 3rd and 4th, thus each of these sets contains 3! elements.

However these sets are overlapping as more than 1 peron can have his own umbrella
Thus the union will be given by:

$binom{4}{1}3!-binom{4}{2}2!+ binom{4}{3}1!-binom{4}{4}$

Number of ways 1 or more people can have their own umbrella is given by formula given above. Since total number of way umbrellas can be distributed is 4! number of ways no one gets his own umbrella is $4!-{binom{4}{1}3!-binom{4}{2}2!+ binom{4}{3}1!-binom{4}{4}}=9$