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?