Treize: A Card-Matching Puzzle

Probability theory is full of surprises. Possibly the best-known paradoxical results are the Monty Hall Problem and the two-envelope problem, but there are many others. Here we consider a simple problem using playing cards, first analysed by Pierre Raymond de Montmort (1678–1719).

Shuffle spades in one pile, hearts in another. Place both piles face downwards. Turn over a card from each pile. Do the two cards match?

Montmort’s Problem

Take two piles of cards faced down, one with the 13 spades, the other with the 13 hearts. Assume the two piles are well-shuffled, and turn over a single card at a time from each pile. The two cards may or may not have matching values. The question is this: what is the probability ${P_0}$ that none of the 13 pairs of cards match?

With no loss of generality, we may assume that the pile of spades is in order from Ace up to King, while the hearts are in random order. Then we see that the problem is equivalent to the game that Montmort called the Jeu de Treize: given a bag with 13 balls labelled from one to thirteen, pick them out one by one. The question now is: what is the probability ${P_0}$ that no label of a ball matches its place in the sequence of draws.

Derangements

Given a set of ${n}$ elements, such as cards or balls, there are ${n!}$ permutations of the set. A derangement is a permutation that leaves no element in its original position. In other words, a derangement is a permutation with no fixed points. The number of derangements of ${n}$ elements is written ${!n}$ , known as a subfactorial or, sometimes, a de Montmort number.

Derangement-Table

The first few values of the permutations and derangements are as in the Table above. We see that the pattern is not obvious. There are several expressions for the derangement number ${!n}$ . There is a recurrence relation for subfactorials:

$\displaystyle !n = (n-1)[!(n-1)+!(n-2)] \qquad\mbox{with\ } !1 = 0 \mbox{ and } !2 = 1 \,. (*)$

Using this, we can easily extend the table above: the sequence of derangement numbers is ${\{ 0, 1, 2, 9, 44, 265, 1854, 14833, \dots \}}$ .

To prove (*) let us assume ${!k}$ is known for all ${k}$ up to ${n-1}$ . Now consider a derangement of ${n}$ elements ${(x_1, x_2, \dots, x_n)}$ . Element ${x_n}$ can be in any of ${n-1}$ positions. Suppose it is in position ${k}$ . There are two possibilities: ${x_k}$ is in position ${n}$ and there are ${!(n-1)}$ derangements of the remaining ${n-1}$ elements; or ${x_k}$ is elsewhere, and there are ${!(n-2)}$ derangements of the remaining ${n-2}$ elements. Thus we have

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

It can be shown (see Wikipedia: Derangements) that:

$\displaystyle !n = n! \sum_{k=0}^n \frac{(-1)^{k}}{k!}$

Using this formula it follows that

$\displaystyle \lim_{n\rightarrow\infty} \frac{!n}{n!} = e^{-1} \approx 0.3679 \,.$

Returning to Montmort’s problem, we see that the required probability is

$\displaystyle P_0 = \frac{\mbox{Number of derangements}}{\mbox{Number of permutations}} = \frac{!n}{n!}$

The surprising result is that, even for moderate values of ${n}$ , this probability is remarkably close to ${1/e \approx 0.3679}$ . This means that in about four out of every ten trials we may expect no matches.

Equivalent Problems

There are various equivalent formulations of Montmort’s problem. Suppose we have ${n}$ individual letters each addressed to a different person, and also ${n}$ pre-addressed envelopes. A scatter-brained secretary places the letters in the envelopes in a haphazard manner; what is the probability that no letter will be in the correct envelope? Again, suppose ${n}$ hats are held in a music-hall cloakroom. After the performance, the concert-goers rush out, grabbing the first hat they can get. The probability that nobody gets their own hat is about ${1/e}$ .

The problem was analysed by William Feller in his book An Introduction to Probability Theory and Its Applications. He uses the basic result giving the probability that two events ${A}$ and ${B}$ will occur, in terms of the probabilities of either or both:

$\displaystyle p(A\cup B) = p(A) + p(B) - p(A\cap B)$

If the events are mutually exclusive (cannot both occur) then the probability of one or other occurring is simply the sum of the probabilities of each: ${p(A\cup B) = p(A) + p(B)}$ . There is a theorem in set theory known as the inclusion-exclusion principle that allows this result to be extended to ${n}$ events. This enables us to derive an expression for the probability ${P_0}$ of a derangement (see Feller, 1957, Chapter IV).

Sources

${\bullet}$ Feller, William, 1957: An Introduction to Probability Theory and Its Applications. John Wiley & Sons Inc.

${\bullet}$ Gorroochurn, Prakash, 2012: Classic Problems of Probability. John Wiley & Sons Inc.

${\bullet}$ Wikipedia: Derangements.

${\bullet}$ Wikipedia: Inclusion–exclusion principle.

ThatsMaths