## Derangement

You must have heard of arrangement, but today we’ll talk about Derangement. The exact opposite. Derangement is the concept of arranging a set of given items in such a manner so that no object is in its original place. For example, a question might say,

If you are given 4 cards with A, B, C, D written on them and they are placed in this specific order. Now you are supposed to count the number of ways these cards can be arranged so that no card is in its original place.

The answer is 9. And the different arrangements are as follows:

BADC, BCDA, BDAC,CADB, CDAB, CDBA,DABC, DCAB, DCBA

So how do you go about solving such problems? Well, of course you use Derangement. So let us discuss how we count derangements. I’ll just pick up a short explanation from Wikipedia since I am too lazy to explain it myself 😛

Suppose that there arenpersons numbered 1, 2, …,n. Let there benhats 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 first person takes the hati. There aren− 1 ways for the first person to choose the numberi. Now there are 2 options:

**Person***i*does not take the hat 1. This case is equivalent to solving the problem with*n*− 1 persons*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 of 1. Now the problem reduces to*n*− 2 persons and*n*− 2 hats

*subfactorial of n*( denoted as !n ). Now there is a simple recurrence relation we can see from the explanation above,