Derangements and the number e

If a teacher randomly hands back 20 homework assignments to the 20 students who wrote them, what is the probability that none of the students receives their own homework back? The answer turns out to be about 0.368, or 36.8%. Remarkably, this number is very close to 1/e, where the number e is the base of the natural logarithm (approximately 2.718). The more students there are in the class, the more accurate this approximation will be.

To understand why this should be the case, it is helpful to know about derangements. In mathematics, this word refers to a permutation of the elements of a set such that none of the elements appears in its original position. The derangements of a set with n elements can be identified with the possible ways of handing back n homeworks to n students in such a way that no student receives their own homework. 

In the case where n=4, the total number of ways of giving 4 homework assignments back to 4 students is 4! (4 factorial, or 4×3×2×1=24). The graphic above illustrates these 24 possibilities, with a red box around each of the 9 derangements. The animation at the top shows these 9 derangements in more detail. In terms of the homework metaphor, the four hollow circles correspond to four students, and the four dots correspond to the four assignments being handed back. In all cases, a dot is matched with a hollow circle of a different colour.

In general, the total number of ways to hand back n assignments to n students in such a way that each student receives one homework is n! (n factorial). The number of derangements of n is sometimes denoted by !n, so that for example !4=9. To see how one might go about counting derangements in a systematic way, consider the derangement of the set {1, 2, 3, 4, 5, 6} shown in the picture above, and focus on what happens to the element 1. The blue arrow from 1 to 5 shows that 5 receives 1’s homework, and the red arrow from 3 to 1 shows that 1 receives 3’s homework.

If 1 then insists on switching homeworks with 5, this has the effect of uncrossing the blue and red arrows, resulting in the situation shown above. The green arrow shows that 1 now receives the correct homework, and the magenta arrow shows that 5 now receives 3’s homework. If we ignore 1 completely, this results in a derangement of the set {2, 3, 4, 5, 6}. Furthermore, this derangement of {2, 3, 4, 5, 6} can be obtained from precisely 5 different derangements of {1, 2, 3, 4, 5, 6}, depending on which of the 5 non-green arrows is coloured magenta.

There is another type of derangement of the set {1, 2, 3, 4, 5, 6}, as shown in the picture above. In this case, 1 and 4 receive each other’s homeworks. If 1 insists on switching homeworks with 4, then this again has the effect of uncrossing the blue and red arrows, resulting in the situation shown below. In this case, 1 and 4 both receive the correct homework, and if we ignore both 1 and 4, we obtain a derangement of the other four elements, {2, 3, 5, 6}.

The argument above allows us to enumerate !6 (the number of derangements of a 6-element set) from knowing !4 and !5. The number of derangements in the previous paragraph, in which 1 and k receive each other’s homeworks, is given by 5×!4, because there are 5 possible choices for k, and !4 possible derangements of the remaining 4 objects. In contrast, the number of derangements of the first type that we considered is given by 5×!5, because there are !5 derangements of the set {2, 3, 4, 5, 6}, and 5 choices for which arrow is coloured magenta. In summary, we obtain !6=5(!4+!5), which leads to the recurrence relation  !n=(n–1)(!(n–1) + !(n–2)). If we know that !4=9 and !5=44, then this allows us to deduce that !6=5×(9+44)=265.

Using the recurrence relation and mathematical induction, we can establish the other formula for !n, which is n! times the sum from 0 to n of the terms (–1)^i/i!. The sum from 0 to infinity of this series agrees with the power series for e^x evaluated at x=–1. This proves that when n is large, the proportion of permutations of n objects that are also derangements is about 1/e. This is a very good approximation even for fairly small n. For example, if n=11, then the number of permutations of 11 objects is 11! (or 39,916,800) and the number of derangements is 14,684,570. Dividing the first number by the second gives 2.71828182842…, which agrees with e to 10 decimal places.

---

Picture credits and relevant links

The graphic of the 24 permutations of 4 objects is by RokerHRO and appears on the Wikipedia page on derangements. That page also gives a more satisfactory derivation of the formula in the animated graphic, using the inclusion-exclusion principle.

The other graphics are my own work.

The number of derangements on n elements is sequence A000166 in the On-Line Encyclopedia of Integer Sequences. The entry contains many other interpretations of these numbers, including “the number of distinct permutations for a Secret Santa gift exchange with n participants”. The first few entries of the sequence, starting with n=0, are 1, 0, 1, 2, 9, 44, 265, ...