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 elements is called the *subfactorial* of . Various notations are used for subfactorials: , and ¡ are common; we will use (read as `bang-en’).

Of course, we see from this that . In fact, we can write a more precise connection between derangements and arrangements:

This means that is the nearest whole number to . The first ten values of are . See also Table 1.

**The Principle of Inclusion-Exclusion**

Let and be two finite sets and let and denote their cardinalities, that is, the number of elements they contain. It is clear that contains at most elements. If , the two sets share elements, and these must not be double-counted; thus,

For three sets, the count is

The principle of inclusion-exclusion (PIE) generalizes these results to give the number of elements in any finite union of finite sets we have

The process is summarized in the Wikipedia article on PIE:

- Include the cardinalities of all the sets .
- Exclude the cardinalities of the pairwise intersections.
- Include the cardinalities of the triple intersections.
- If is odd, include the -tuple intersection; if is even, exclude it.

**Recurrence Relations for Derangement Numbers**

The number of derangements of an -element set may be calculated using a second-order recurrence relation:

with and . The subfactorials also satisfy a first-order recurrence relation,

with initial condition . There is also an integral expression for the subfactorial,

which allows extension to non-integral arguments () and analytic continuation to the complex plane (). 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 possible orders. This is a breath-takingly large number: or, more precisely,

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

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

which has a value , making about 37% (Gorroochurn, 2012).

** References **

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/

* * * * *

You must be logged in to post a comment.