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/

*      *      *      *      *


Last 50 Posts

Categories


%d bloggers like this: