Difference between revisions of "Page 9" - Rhea

Latest revision as of 23:53, 2 December 2018

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

$ 2 $ Derangements with $ 3 $ Elements

$ 9 $ Derangements with $ 4 $ Elements

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!\sum_{k=0}^{n}\frac{(-1)^k}{k!} \end{align} $

This formula may be recognizable yet again as it contains the previously mentioned Taylor Series definition of $ e^{-1} $. From here, it becomes quite easy to determine the ratio between permutations and derangements. As stated, $ n! $ indicates the overall number of permutations, so by dividing, we can see that, as $ n $ approaches infinity, the total number of permutations is $ e $ times as many as the total number of derangements.

In fact, this demonstrates to us another commonly used formula for the number of derangements. Because $ e $ is the common ratio between permutations and derangements, the following formula is also a standard definition for the number of derangements:

$ \begin{align} !n=[\frac{n!}{e}] \end{align} $

where $ [x] $ is the nearest integer function of $ x $.

This now demonstrates how, just as with the Binomial Distribution, $ e $ appears in relatively unexpected locations, and now that we have discovered several ways to define the number of derangements, we can once again look at our gift exchance example.

By viewing each person's name as one element in a set, it becomes apparent that the derangement of these elements will dictate permutations in which each person drew a valid name (that is, any name other than their own). Therefore, we can now state that, as the number of people increases, the probability that the method of drawing names from a hat yields a valid permutation becomes $ \frac{1}{e} $, which is approximately $ 36.8% $.

Overall, we have now seen several instances of the mysterious properties of $ e $ and how they cause it to appear in unexpected problems. To satisfy further interest in this topic, an article which provides a more general explanation of both examples and why the relationship with Poisson distribution causes $ e $ to appear can be found here^[5].

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

Yuan, Q. (2012, November 10). Short cycles in random permutations. Retrieved December 1, 2018, from https://qchu.wordpress.com/2012/11/09/short-cycles-in-random-permutations/

Back to Mysteries of the Number e