# How to count derangements?

I was going through this link.Suppose that there are n persons who are numbered 1, 2, ..., n. Let there be n hats also numbered 1, 2, ..., n. We have to find the number of ways in which no one gets the hat having same number as his/her number. Let us assume that the first person takes hat i. There are n − 1 ways for the first person to make such a choice. There are now two possibilities, depending on whether or not person i takes hat 1 in return:

A) Person i does not take the hat 1. This case is equivalent to solving the problem with n − 1 persons and n − 1 hats: each of the remaining n − 1 people has precisely 1 forbidden choice from among the remaining n − 1 hats (i's forbidden choice is hat 1).

B) Person i takes the hat 1. Now the problem reduces to n − 2 persons and n − 2 hats.

From this, the following relation is derived: !n = (n - 1) (!(n-1) + !(n-2))

I have a hard time understanding point B and the equation derived. I was trying to understand with an example of 4 people named A, B, C and D and the corresponding hats A, B, C and D. Everyone of them are supposed to wear any hat except their own matching hat i.e. A can wear B, C or D.

If suppose A wears B hat so we will be left with only 3 people and 3 hats. So I can understand "(n-1)!(n-1)" part but what i didn't understand is part B(marked above). Can anyone help?

• This is a math question and belongs to math.se. – Yuval Filmus Nov 25 '15 at 14:59

Suppose person 1 wears hat 2 and person 2 wears hat 1. People 3 up to $n$ have hats 3 up to $n$ remaining to them. The assignment of hats to the first to people can be completed to a derangement by any derangement of people 3 and up. Since there are $n-2$ people 3 and up, the problem reduces to $n-2$ people (people 3 and up) and $n-2$ hats (hats 3 and up).

Hint:The general formula for dearrangements is $n![1-\frac{1}{1!}+\frac{1}{2!}...\frac{(-1)^n}{n!}]$. now you can plug in your values and get the required answer. Note sometimes we actuallly need to do some mental stuff even if if the formula is available

I had exactly the same question. but my confusion is why !(n - 1) and !(n - 2) are exclusive. I thought they should be related to each other.

expand on the scenario of 4 helps, following my intuition

!(4) = 3 * !(3) = 3 * 2 = 6 // wrong


expand more.

2 (1 3 4) //suppose 2 is taken as the first
// !(3) means 1 should not be on 1, 3 not at second and 4 not at third.
// clear that 1 could be at first position