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 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 first person takes the hat¬†i. There are¬†n¬†‚ąí¬†1 ways for the first person to choose the number¬†i. Now there are 2 options:

  1. 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).
  2. Person¬†i¬†takes the hat of¬†1. Now the problem reduces to¬†n¬†‚ąí¬†2 persons and¬†n¬†‚ąí¬†2 hats
Now that you understand the concept, let us talk about counting the number of derangements. The number of derangements of an n-element set is called the subfactorial of n ( denoted as !n ). Now there is a simple recurrence relation we can see from the explanation above,
!n = n * !(n-1) + (-1)^n
and, !n = (n-1) * (!(n-1)+!(n-2))
The formula for it is, (image sourced from AoPSWiki, once again laziness comes into play)
Now I hope you all understand Derangement and its huge set of applications! A very important concept for programmers and mathematicians alike. ūüôā
Advertisements
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: