from the wiki, The way of counting derangements is,
Suppose that there are n persons 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:
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). 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))
Here I dont understand the second part. I try to think the problem like that ,
NO.1 : I am person i, So I can't take i'th hat. So I have n-1 option. That reduces the problem having n-1 person with n-1 hat which will be multiplied (n-1) times.
But I can't understand the second portion of the recursive call. from the passage , "person i takes the hat 1" how... ? Doesn't it true "i's forbidden hat is 1" ? Then how person i take hat 1. Otherwise if "i's forbidden hat is not 1" then doesn't it reduce to NO.1 ?
So more or less I trouble understanding this portion of the recursive call ,
!n = (n - 1) (!(n-1) + !(n-2)) *******