Sunday, June 8, 2014

a bit of combinatorics: Derangement

A mail man had a tough job every morning. He had to deliver N letters to N destinations. One day, a lifetime of contemplation had struck him; he had always imagined how it would be like if everyone gets the wrong letter? He also wonder, in how many ways he could do this?
Eg: for 3 letters 1,2,3 and with destinations A,B,C respectively, to send every letter wrongly he has 2 ways:
2->A
3->B
1->C

OR

3->A
1->B
2->C

Can you help him solve the wonder of the beautiful mind of a post man?

Formal introduction: Derangement
A special class of permuting 1,2,3,4,5,...,n such that the number k is not in k-th position (or in other words, none of the letters are correctly delivered).

This problem can be solved recursively:
Suppose we are finding the total number of derangements of n numbers 1,2,3,...,n, let's call it D(n).
Firstly, 1 must not be in position 1. So, let's say that it's in position k. We have 2 cases:

Case 1: the number k is at position 1.
Essentially, 1 and k swap positions. In this setting, we are now left with the task of permuting n-2 numbers. This exactly is D(n-2). Since there are n-1 ways to choose k (from 2 to n), the total possibilities for case 1 is (n-1)*D(n-2).

Case 2: the number k is not at position 1.
This means that position 1 is occupied with some other number than k. This seems to be more complicated than case 1, but it's not. This is equivalent to our initial problem (where 1 cannot be in position 1, but instead of 1, we now have k), which is equal to finding total number of derangements of n-1 numbers, D(n-1).

Therefore, D(n) = D(n-1) + (n-1)*D(n-2).