"Derangement" is a counting problem that commonly occurs in many puzzles, probability questions etc. I wanted to solve another counting problem, that required building upon derangements. So I brushed up on combinatorics to find a quick formula for derangement. It was so elegant, that I had to put it up here.

Derangement is such an arrangement, that no object is in its correct place. For example, if you are to create a derangement of all letters in the alphabet

**(A .. Z)**, then such an arrangement should NOT have**A**at the first place, and**B**at the second place, and so on, till**Z**cannot be at 26th place. There is precisely one "forbidden" spot for every object.As an example, consider only 3 letters[A B C]. The only possible derangements for these letters are[BCA, CAB].

The question is, in how many ways you can do this for

**N**objects ? Let's use the notation for derangement as**D(N)**. Obviously,**D(N) < N!**.This problem can be phrased in different ways.

SayNpeople went to a party. Each was given a name tag. Assume they all had different names. To play a fun guessing game, they deliberately put on a wrong name tag on their shirts. No person had the right name tag. In how many ways can they do it ?

Answer : InD(N)ways.

Another one.

Start with 2 deck of cards. Shuffle each of them separately, and put it next to each other on a table. Start picking one card from the top of each deck, compare and discard. Keep doing it till all 52 pairs have been compared. What is the probability that not a single pair had same cards ?Answer :D(52) / 52!. Favorable outcomes divided by total number of outcomes.

But what's the formula for calculating

**D(N)**? It's very elegant.Think of

**N**numbered balls**(from 1..N)**to be put in**N**numbered bins**(from 1..N)**. The task is to arrange**N**balls so that no ball is in the bin with the same number.Start with any

*. It cannot be put in***ball i***, so there are***bin i****N-1**ways to choose a bin. Let's say it was put in*. For every such choice, following is true. We examine***bin k***, whose bin was chosen for***ball k***.***ball i**1. Either

*was put in***ball k***.***bin i**2. Or

*was NOT put in***ball k***.***bin i**These are mutually exclusive choices. So we can find the count of ways each can be done, and sum them up for getting final answer for

**D(N)**.First choice,

*was put in***ball k***. Just remove, the pair***bin i***and***bin i***, with***k***and***balls k***in them respectively. That leaves us***i****N-2**balls to be put in an derangement. Each having exactly one forbidden spot. This is nothing but**D(N-2)**.Second choice,

*is NOT to be put in***ball k***. Remove the***bin i***(with***bin k***in it). And rename the***ball i***to***bin i***, as the***bin k***is NOT to be put in it. That leaves with***ball k****N-1**balls to be put in derangement. Each having exactly one forbidden choice. This is nothing but**D(N-1)**.So for every choice of

**k**, there are**D(N-1) + D(N-2)**possible number of derangements. Since there are**(N-1)**choices for**k**, the formula isD(N) = (N-1) * ( D(N-1) + D(N-2) )

This formula is very similar to Fibonacci numbers ! But the multiplication makes it grow really faster than Fibonacci sequence.

By defining

**D(0) = 1**and noting that**D(1) = 0**, we can calculate all derangements. For numbers up to 10, they turn out to beD(2) = 1

D(3) = 2

D(4) = 9

D(5) = 44

D(6) = 265

D(7) = 1854

D(8) = 14833

D(9) = 133496

D(10) = 1334961

The math textbooks will also show another result that makes this even more beautiful.

The limit ofI will be building on this in another problems soon.(N!)/ D(N) asNapproaches infinity is the number

e (= 2.7182816576664037...).

This means, the answer to our probability question is very close to

1/e (= 0.367879464285714...).

**UPDATE**: See the solution to Partial Derangement which builds on this post.

## No comments:

## Post a Comment