Derangements
In the last section, we observed an instance of how $ e $ relates to probability, specifically the binomial distribution. Now, we will consider its relationship with derangements and will explain how, along a similar concept, it proves important in key ways. We will begin with an example to illustrate this property. Consider the following description of a Secret Santa gift exchange, which will be used to illustrate the properties relating $ e $ to derangements in this section.
- Around certain holidays, such as Christmas, one popular tradition among friends is to organize a gift exchange, in which each person buys a gift for another randomly selected participant, but recipients do not know from whom they are receiving their gift. To accomplish this, it is often standard to participate in a drawing, of sorts, in which everyone's name is put into a hat, and each person draws a name to determine for whom they will be getting a gift.
- Because everyone wants to be surprised by the gift they receive, however, this method only works when no one happens to draw their own name. If this does occur, the names must be redrawn, which can lead one to consider how often this method will work the first time. To accomplish this, let us observe all permutations pertaining to who draws which name and determine which cases will have every person draw someone else's name.
What are Derangements?
Consider the set $ \{1,2,3\} $. It has six different permutations: $ \{1,2,3\}, \{1,3,2\}, \{2,1,3\}, \{2,3,1\}, \{3,1,2\},\{3,2,1\} $. However, only in two of these permutations, $ \{2,3,1\} $ and $ \{3,1,2\} $, do none of the numbers appear in their "original" spot. These two permutations are called derangements of $ \{1,2,3\} $.
Derangements are defined as permutations in which none of the objects appear in their "natural" (i.e., ordered) place[1].
We have already seen that, with three elements, there are only two derangements. With slightly more work along the same lines, it can be determined that there are nine derangements with four elements. A visual depiction of these derangements can be seen below. Both of these images, along with a depiction of the forty-four derangements with five elements can be found here[2].
For a large number of elements, it becomes useful to have specific notation to indicate how many derangements there are with a set number of elements. While $ n! $, read "n factorial", is used to indicate the total number of permutations of a set of $ n $ elements, the notation $ !n $, read "n subfactorial", indicates the number of derangements of a set with $ n $ elements.
Defining $ !n $
Typically, $ !n $ is defined using the Inclusion-Exclusion Principle. You can read more about that method here[3]. Additionally, there is a nice proof of the formula which relies on the recurrence relation which can be found here[4]. The formula we will use is shown below.
- $ \begin{align} !n=n! \end{align} $
References
Dickau, R. M. (n.d.). Derangement diagrams [Digital image]. Retrieved December 1, 2018, from http://mathforum.org/advanced/robertd/derangements.html
Spivey, M. (2014, June 20). A Nice Proof of the Derangements Formula. Retrieved December 1, 2018, from https://mikespivey.wordpress.com/2011/11/22/derangements/
Weisstein, E. W. (n.d.). Derangements. MathWorld--A Wolfram Web Resource. Retrieved December 1, 2018, from http://mathworld.wolfram.com/Derangement.html
Weisstein, E. W. (n.d.). Inclusion-Exclusion Principle. MathWorld--A Wolfram Web Resource. Retrieved December 1, 2018, from http://mathworld.wolfram.com/Inclusion-ExclusionPrinciple.html
