CODEWITHSUNDEEP
algorithmrecursiondynamic-programmingcombinatorics
user3712917
user3712917

Reputation: 121

Counting derangements

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))
                       *******

Upvotes: 4

Views: 1233

Answers (2)

Paul Hankin
Paul Hankin

Reputation: 58369

There's two claims:

  1. There's a bijection between derangements of N where 1->i and i->1, and derangements of N-2.
  2. There's a bijection between derangements of N where 1->i and i-> j != 1, and derangements of N-1.

The first is obvious: once you've removed 1->i and i->1 from the derangement of {1, ..., n}, you're left with a derangement of the remaining n-2 items. And conversely, if you've got a derangement of {2, 3, ..., i-1, i+1, ..., n} then you can turn it into a derangement of {1, ..., n} by adding the mappings 1->i and i->1.

The second is observed by noting that if you have a derangement of {2, ..., n} then you can turn it into a derangement of {1, ..., n} by adding the map 1->i and changing whatever maps to i to mapping to 1 instead. And conversely, if you have a derangement of {1, ..., n} where 1->i and i doesn't map to 1, then you can create a derangement of {2, ..., n} by removing the 1->i mapping, and changing whatever maps to 1 to map to i instead.

This gives you a way of counting the derangements:

D(n) = sum(i=2..n) (D(n-1) + D(n-2)) = (n-1)(D(n-1) + D(n-2))

Upvotes: 1

dfb
dfb

Reputation: 13289

Lets call the derangement function f for clarity. At f(n), there are n hats and n people. Everyone can choose from n-1 hats. Person 1 takes hat i from n-1 choices. Person i still has n-1 hats to choose from and everyone else has n-2 has to choose from (they can't choose their own hat or i).

Now we need two cases for what person i does. Think of this as

  1. Person i takes hat 1
  2. Person i doesn't take hat 1 and we don't know what they'll take until later

In case 2, we know person i doesn't take hat 1, but nothing more. Previously we knew that person i had n-1 choices, now he has n-2, just like everyone else. This means we can calculate f(n-1) for this case. In case 1, person i is no longer forbidden to take hat 1. In essence, we know that person i and person 1 have swapped hats and no longer need to be matched, thus f(n-2).

Either of these cases is possible, so we have a recurrence that multiplies the (n-1) choices by the possibility of either happenning, f(n) = (n-1)(f(n-1) + f(n-2))

Upvotes: 4

Related Questions