Learn / Library / Combinatorics

Handing back badges

CombinatoricsHard

$7$ people numbered $1$ to $7$ each own a distinct badge with the same number. The badges are handed back in some order, each person receiving exactly one. In how many of the $7!$ handbacks does none of the people $1$ to $4$ receive their own badge? People $5$ to $7$ may or may not receive theirs.

Checking an answer needs JavaScript. The hint and the solution open without it.

Hint

Apply inclusion-exclusion over the people from the restricted group who do get their own badge.

Solution

If a chosen set of $k$ people among the first $4$ all get their own badge, the remaining badges can be handed out in $(7 - k)!$ ways.
By inclusion-exclusion the count is $7! - 4 \times 6! + 6 \times 5! - 4 \times 4! + 3!$ , since there are $(k 4)$ choices of the set.
This equals $5040 - 2880 + 720 - 96 + 6 = 2790$ .

Answer: $2790$

Next question Back to the library