Inclusion Exclusion combinatorics problem.

Question

Seven people leave their jackets on a rack. In how many ways can their jackets be returned so that no one gets their own coat back?

Clearly this invokes the Inclusion exclusion principle of the form:

$$ |\bar{A_1} \cap \bar{A_2} \cap \cdots \bar{A_n}| = |X| - \sum^n_{k=1}\sum_{1\leq i_1 < i_2 < \ldots < i_k\leq n}(-1)^{k+1}|{A_{i_k}} \cap {A_{i_2}} \cap \cdots {A_{i_n}}|$$

where $\bar{A_1}$ is 1 person not getting his jacket back, $\bar{A_2}$ is person 2, and so on.

thus $A_1$ is the number of permutations where person 1 gets his jacket back, which is should equal $6!$ as thats how many ways we can permute the jackets of the remaining 6 people.

$A_1\cap A_2$ then is number of permutations where person 1 and 2 gets his jacket back, which is 5! and so on.

Thus is the answer

$$ = 7! - (6! - 5! + 4! -3! + 2! -1! + 0! ) = 4420$$

is this correct? Or do I need to consider that for the $A_1$ case there are $\binom{7}{1}$ ways to choose the person who gets his jacket back, $\binom{7}{2}$ ways to choose the two people who get their jacket back, and so on?

If this is true, would the 6 person case only be = 1? Because even though this pattern suggests $\binom{7}{6}\cdot 1$ ways to have exactly 6 people with the right jackets, I cannot see how this could be possible. If everyone except for 1 has the right jacket, then the last person must also have the right jacket. So by this logic, the answer should be

$$ = 7! - (\binom{7}{1}6! - \binom{7}{2}5! + \binom{7}{3}4! -\binom{7}{4}3! + \binom{7}{5}2! -\binom{7}{6}1! + \binom{7}{7}0! ) = 1854$$

Please let me know if I made a mistake somewhere, any advice would be appreciated!

Answer 1

A permutation of $n$ objects such that no object remains in its original position is called a derangement. So you are asking for the number of derangements of seven objects, i.e. the $7$-th derangement number, which is $1854$.

Your approach to compute this number by means of inclusion-exclusion is a good one. Your first argument, however, is wrong. You indeed vastly miscount the numbers $A_i$. For example, as you later note, it is impossible for exactly six people to get their own jacket back. After all, the only remaining person must then get the only remaining jacket, which must then be correct as well.

For another example, the number of ways at least $5$ people can get their own jacket is $$1+\tbinom{7}{5}=22.$$ After all, either everyone gets their own jacket back, or exactly $5$ people get their own jacket back.

Your second argument starts off in the right direction. But it is entirely unclear to my how you get:

So by this logic, the answer should be $$= 7! - (\binom{7}{1}6! - \binom{7}{2}5! + \binom{7}{3}4! -\binom{7}{4}3! + \binom{7}{5}2! -\binom{7}{6}1! + \binom{7}{7}0! ) = 1854.$$

The number that pops out is correct, but the argument is missing.