What the newest item's swap does to the rest
Decide the last item's partner, and the remaining count splits into exactly two smaller cases. About 12 minutes.
Follow the last person's coat
The last person's coat has to go to someone else: any of the other n − 1 people. Say it goes to Priya. Now there are two cases, depending on what happens to Priya's coat.
If Priya's coat goes to the last person, the two of them simply swapped. Everyone else must be mixed up among themselves: the answer for n − 2 people.
The other case, and the rule
If Priya's coat doesn't go to the last person, look at who's still waiting: everyone except Priya, including the last person. Nobody may get their own coat, and the last person also mustn't get Priya's. Pretend Priya's coat is the last person's own, and that's exactly the puzzle for n − 1 people.
So for each of the n − 1 people who could get the last coat, add the two cases: n − 1 times (the answer for n − 1 plus the answer for n − 2). For 4 people: 3 × (2 + 1) = 9.
der = [1, 0, 1] # 0, 1, 2 items
With one person, the only coat is their own: 0 ways. (With nobody at all, there's 1 way: nothing to get wrong.)
3 people can be mixed up in 2 ways and 2 people in 1 way. How many ways can 4 people all get the wrong coat?
- A9
- B3
- C6
Show the answer
9. (4 − 1) × (2 + 1) = 3 × 3 = 9.
Count derangements
Given n items numbered 1 to n, each starting in its own matching spot, return how many ways to rearrange them so that no item ends up in its own original spot.
n = 4 → 9
0 ≤ n ≤ 18 · return a long