Derangement

"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.

Say N people 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 : In D(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 ball i. It cannot be put in bin i, so there are N-1 ways to choose a bin. Let's say it was put in bin k. For every such choice, following is true. We examine ball k, whose bin was chosen for ball i.

1. Either ball k was put in bin i.

2. Or ball k was NOT put in 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, ball k was put in bin i. Just remove, the pair bin i and k, with balls k and i in them respectively. That leaves us N-2 balls to be put in an derangement. Each having exactly one forbidden spot. This is nothing but D(N-2).

Second choice, ball k is NOT to be put in bin i. Remove the bin k (with ball i in it). And rename the bin i to bin k, as the ball k is NOT to be put in it. That leaves with 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 is

D(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 be

D(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 of (N!)/ D(N)  as  N  approaches infinity is the number
e (= 2.7182816576664037...).
This means, the answer to our probability question is very close to
1/e (= 0.367879464285714...).

I will be building on this in another problems soon.

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