$n$ people have participated in a party. each of whom brought an umbrella and a coat. At the end of the party...

308 Views Asked by At

$n$ people have participated in a party. each of whom brought an umbrella and a coat. At the end of the party, everyone picks an umbrella and a coat out of the stack and leaves.

$1$. In how many ways these coats and umbrellas can be selected such that no one is left with his/her own umbrella or his/her own coat?

$2$. In how many ways these coats and umbrellas can be selected such that no one is left with his/her own umbrella and his/her own coat?


$1$.

Let $A$ denote the selections such that no one left with his/her umbrella and denote by $B$ the selections that no one is left with his/her coat, then what the question wants is :

$$\left|A \cup B\right|=\left|A\right|+\left|B\right|-\left|A \cap B\right|$$ $$=D_nn!+D_nn!-(D_n)^2$$ $$=D_n(2(n!)-D_n)$$

$2$.

One may use PIE to find the answer which is :$$\sum_{k=0}^{n}\binom{n}{k}\left(n-k\right)!^{2}\left(-1\right)^{k}$$

But why we cannot say there are $D_n$ ways to distribute the umbrellas to the people and for each of these selections there are $D_n$ ways to distribute the coats to the people and so by the multiplication law $(D_n)^2$.

1

There are 1 best solutions below

1
On BEST ANSWER

Assuming that the author of the question uses the English language correctly, you’ve inverted their meanings. The first one is asking for the number of ways in which each person gets both the wrong coat and the wrong umbrella, which is $D_n^2$. It’s your inclusion-exclusion calculation that is wrong: you’re excluding only the ways in which the people who get the right coat also get the right umbrella, not the ways in which, for instance person $1$ is the only one to get the right coat, and person $2$ is the only one to get the right umbrella.

The second question is asking for the number of ways in which no person gets both the right coat and the right umbrella, i.e., the number of ways in which each person gets the wrong coat, the wrong umbrella, or both; this is what you calculated for the first question.