Arrangements and Derangements

Six students entering an examination hall place their cell-phones in a box. After the exam, they each grab a phone at random as they rush out. What is the likelihood that none of them gets their own phone? The surprising answer — about 37% whatever the number of students — emerges from the theory of derangements.

Arrangements and Derangements

We may call any permutation of the elements of a set an arrangement. A derangement is an arrangement for which every element is moved from its original position. Thus, a derangement is a permutation that has no fixed points. The number of derangements of a set of ${n}$ elements is called the subfactorial of ${n}$ . Various notations are used for subfactorials: ${!n}$ , ${d_n}$ and ${n}$ ¡ are common; we will use ${!n}$ (read as `bang-en’).

The 24 arrangements (permutations) of four objects, and the nine derangements (outlined in red) having no fixed point [Image Wikimedia Commons].

Derangements were first considered by Pierre Reymond de Montmort. In 1713, with help from Nicholas Bernoulli, he managed to find an expression for the connection between ${!n}$ and ${n!}$ . The answer, which he obtained using the inclusion-exclusion principle (see next subsection) is

$!n = n! \left(1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \frac{1}{4!} - \cdots \pm\frac{1}{n!}\right) = n! \sum_{k=0}^n \frac{(-1)^k}{k!} \,. \ \ \ \ \ (1)$

Of course, we see from this that ${\lim_{n\rightarrow\infty} (!n) = n!/e}$ . In fact, we can write a more precise connection between derangements and arrangements:

$\displaystyle !n = \left\lfloor\frac{n!+\frac{1}{2}}{e}\right\rfloor \,.$

This means that ${!n}$ is the nearest whole number to ${n!/e}$ . The first ten values of ${!n}$ are ${\{ 1, 0, 1, 2, 9, 44, 265, 1\,854, 14\,833, 133\,496 \}}$ . See also Table 1.

The Principle of Inclusion-Exclusion

Let ${A}$ and ${B}$ be two finite sets and let ${|A|}$ and ${|B|}$ denote their cardinalities, that is, the number of elements they contain. It is clear that ${|A\cup B|}$ contains at most ${|A|+|B|}$ elements. If ${A\cap B \ne \emptyset}$ , the two sets share elements, and these must not be double-counted; thus,

$\displaystyle |A\cup B|=|A|+|B|-|A\cap B| \,.$

For three sets, the count is

$\displaystyle |A\cup B\cup C|=|A|+|B|+|C| - ( |A\cap B| + |B\cap C| + |C\cap A| ) + |A\cap B\cap C| \,.$

The principle of inclusion-exclusion (PIE) generalizes these results to give the number of elements in any finite union of finite sets ${ A_1, A_2, \dots , A_n}$ we have

$\displaystyle \left|\bigcup _{i=1}^{n}A_{i}\right | = \sum _{i=1}^{n}|A_{i}| - \hspace{-3mm} \sum _{1\le i<j\le n}\hspace{-3mm}|A_{i}\cap A_{j}| +\hspace{-4mm} \sum _{1\le i<j <k\le n}\hspace{-4mm}|A_{i}\cap A_{j}\cap A_{k}| - \cdots + (-1)^{n-1}\left|A_{1}\cap \cdots \cap A_{n}\right|.$

The process is summarized in the Wikipedia article on PIE:

Include the cardinalities of all the sets ${A_i}$ .
Exclude the cardinalities of the pairwise intersections.
Include the cardinalities of the triple intersections.
$\dots$
If ${n}$ is odd, include the ${n}$ -tuple intersection; if ${n}$ is even, exclude it.

Recurrence Relations for Derangement Numbers

The number ${!n}$ of derangements of an ${n}$ -element set may be calculated using a second-order recurrence relation:

$\displaystyle !n = (n-1) [!(n-1)+!(n-2)]$

with ${!0 = 1}$ and ${!1 = 0}$ . The subfactorials also satisfy a first-order recurrence relation,

$\displaystyle !n = n\times !(n-1) + (-1)^n \,, \qquad [\mbox{compare\ \ } n! = n\times(n-1)! ]$

with initial condition ${!0 = 1}$ . There is also an integral expression for the subfactorial,

$\displaystyle !n = \int _{0}^\infty (x-1)^n e^{-x}\, dx \,, \qquad \left[ \mbox{compare\ \ } n! = \int _{0}^\infty x^n e^{-x} dx \right]$

which allows extension to non-integral arguments ( ${!x}$ ) and analytic continuation to the complex plane ( ${!z}$ ). De Montmort’s result (1) also follows from this integral.

Shuffling cards to get a pattern never seen before

If you shuffle a pack of 52 cards, it may be in any of ${52!}$ possible orders. This is a breath-takingly large number: ${52! \approx 8.066 \times 10^{67}}$ or, more precisely,

$\displaystyle \begin{array}{rcl} 52! = 80{,}658{,}175{,}170{,}943{,}878{,}571{,}660{,}636{,}856{,}403{,}766{,} \\ \quad \!\! 975{,}289{,}505{,}440{,}883{,}277{,}824{,}000{,}000{,}000{,}000\,. \end{array}$

Thus, a well-shuffled pack is almost certain to be in a sequence that has never occurred before and would not occur again if the pack were to be re-shuffled every second for billions of years. Indeed, with ${52!}$ permutations, the same sequence is unlikely to be repeated any time during the life of the universe.

Let us start with a deck of cards in canonical order

$\displaystyle \spadesuit\mathrm{A}, \spadesuit\mathrm{ 2}, \spadesuit\mathrm{3}, \dots \spadesuit\mathrm{Q}, \spadesuit\mathrm{K}, \ \ \heartsuit\mathrm{A}, \dots \heartsuit\mathrm{K}, \ \ \diamondsuit\mathrm{A}, \dots \diamondsuit\mathrm{K}, \ \ \clubsuit\mathrm{A}, \dots\clubsuit\mathrm{K} \,.$

We number the cards from ${1}$ to ${n=52}$ . What is the probability ${p_n}$ that, after shuffling, no card ${k}$ is in position ${k}$ ? That is, what is the probability that the sequence is a derangement? From de Montfort’s result (1), it follows that

$\displaystyle p_n = \frac{!n}{n!} = \sum_{k=0}^n \frac{(-1)^k}{k!} \approx \frac{1}{e} \,.$

which has a value ${0.367879}$ , making ${p_n}$ about 37% (Gorroochurn, 2012).

References

${\bullet}$ Gorroochurn, Prakash, 2012: Classic Problems of Probability. Wiley, ISBN: 978-1-118-06325-5

Next post: Derangements and Continued Fractions for e

* * * * *

That’s Maths II: A Ton of Wonders

by Peter Lynch has just appeared.
Full details and links to suppliers at
http://logicpress.ie/2020-3/

* * * * *

ThatsMaths