Derangements - Algebra, CSIR-NET Mathematical Sciences | Mathematics for IIT JAM, GATE, CSIR NET, UGC NET PDF Download

Here we apply the Inclusion-Exclusion Principle to a problem of derangements:

In an apartment complex with k mailboxes, how many ways can a mail carrier distribute k letters, one addressed to each letter box, such that no letter is placed in the correct box? Each of these is called a derangement.

Let us refer to a letter by a number and to a mailbox by a number. Our task is to determine the number of ways to pair letters and boxes so that no letter numbers match box numbers. If k = 1, there are no ways to derange the letter, for there is one letter to place in one box. If k = 2, we may place letter #2 in box #1 and letter #1 in box #2, that being the only derangement.

When we have three letters, there are 3! = 6 total ways to distribute them. We now write the letter numbers in the order they are delivered, such as 1 3 2, indicating letter #1 is delivered to box #1, letter #3 is delivered to box #2, and letter #2 is delivered to box #3. The 6 possible distributions for 3 letters are

The schemes 2 3 1 and 3 1 2 are the only derangements of three letters.

Summarizing our results thus far, using D(n) to represent the number of derangements of n letters, we have D(1) = 0, D(2) = 1, and D(3) = 2. Any guesses on D(4)? Let's find out what it is.

We know there are 4! = 24 ways to distribute the 4 letters. Rather than list the 24 cases, let us consider how the Inclusion-Exclusion Principle may help us. We seek the number of ways to place the numbers in the set {1,2,3,4} in line such that no value occurs in its natural position. Let X(1) represent the property that 1 occurs in its natural position when 1,2,3,4 are permuted. Then |X(1)| = (1)*3!. The 1 represents the 1 way to place the 1 in its natural position and the 3! shows the number of ways to permute the remaining 3 values. Note that we are not considering whether any of 2,3,4 wind up in their respective natural positions. We could argue similarly that |X(2)| = |X(3)| = |X(4)|. Therefore, there are 4*3! ways for a value to occur in its natural position.

What about |X(1) ^ X(2)|? Again there is 1 way to place 1,2 in their natural order, and then 2! ways to place the remaining values. This will be true for any pair of values we wish to restrict to their natural positions. How many pairs are there? This is just C(4,2) = 6. Therefore, there are C(4,2)*2! ways for two values to simultaneously occur in their natural positions.

And for |X(1) ^ X(2) ^ X(3)|? Again there is 1 way to place 1,2,3 in their natural order, and then 1! way to place the remaining value. This will be true for any set of three values we wish to restrict to their natural positions. How many 3-element sets are there? This is just C(4,3) = 4. Therefore, there are C(4,3)*1! ways for three values to simultaneously occur in their natural positions.

Finally, |X(1) ^ X(2) ^ X(3) ^ X(4)| = 1, for there is only one way for all 4 values to be in their natural positions.

Now apply the Inclusion-Exclusion Principle (I-E P):

|~X(1) ^ ~X(2) ^ ~X(3) ^ X(4)| = 4! - 4(3!) + 6(2!) - 4(1!) + 1 = 9. In words, using the I-E P, we are suggesting that to determine the number of derangements of the values 1,2,3,4, first calculate the number of permutations of those values (4!), subtract the number of ways to keep at least one element in its natural position, add back the number of ways to keep at least two values in their natural positions, subtract the number of ways to keep at least three values in their natural positions, and finally add back the number of ways to keep all values in their natural positions.

We can rewrite the right side of the above equation to better express the general result:

If we begin with n objects rather than 4, we can argue in a similar way that determines the number of derangements of n items.

Recursive Determination of Derangements

We now consider derangements recursively. That is, by knowing the few easy-to-calculate values for derangements of small numbers of objects, can we determine a pattern for the number of derangements of larger numbers of elements?

Suppose we want to determine the number of derangements of the n integers 1,2,...,n for n bigger than 2. Let us focus on k and move it into the first position. We thus have started a derangement, for 1 is not in its natural position. Where could 1 be placed? There are two cases we could consider: either 1 is in position k or 1 is not in position k.

If 1 is in position k, here's what we know: The integers 1 and k have simply traded positions.

Indicated by the question marks, there are (n-2) integers yet to derange. This can be done in D(n-2) ways.

If 1 is not in position k, we don't know as much. Note that we have shown 1 as a prohibited value twice. This is required for this case, because we cannot have 1 appear in the first position (its natural position) nor can 1 appear in position k.

Indicated by the question marks, there are now (n-1) integers yet to derange. This can be done in D(n-1) ways.

Putting this together, we have D(n-1) + D(n-2) possible derangements when k is in the first position. How many different integers could we put in position 1 and carry out this process? All the integers except 1. that is, (n-1) different integers.

This yields the recursive formula D(n) = (n-1)[D(n-1) + D(n-2)]. As long as we know D(1) = 0 and D(2) = 1, we can generate subsequent values for D(n).