There are 9 ways to put 4 letters into 4 addressed envelopes so that every letter lands in the wrong envelope, out of 4 × 3 × 2 × 1 = 24 equally likely ways in all. So if you shuffle blind, the chance that all of them go wrong is 9/24 = 37.5%, just above one third (33.3%). Most people guess lower. These total mix-ups are called derangements, and as the number of letters grows, the chance settles at 1/e ≈ 0.3679, where e is the same 2.718… that turns up in compound interest.
Counting the nine derangements
Call the letters A, B, C and D, and list what lands in envelopes A, B, C and D in order. So BADC means envelope A holds letter B, envelope B holds A, C holds D and D holds C: every envelope wrong.
A derangement of four letters can take only two shapes. (A single swap leaves two letters at home, and a loop of three leaves the fourth at home, so both are out.)
- Two swaps. Split the letters into two pairs and swap inside each pair. There are three ways to pair up four letters: BADC, CDAB and DCBA.
- One big loop through all four. Follow the chain from envelope A: it holds one of the other 3 letters, that letter’s envelope holds one of the 2 letters left besides A, and the last letter closes the loop. That gives 3 × 2 × 1 = 6: BCDA, BDAC, CADB, CDBA, DABC and DCAB.
3 + 6 = 9. The video lights these nine up in a grid of all 24 arrangements.
Montmort’s game of thirteen
The puzzle began at the card table. In Treize (“thirteen”), a game Pierre Rémond de Montmort described, a dealer shuffles a 52-card deck and turns the cards over one at a time, calling “one”, “two” and so on up to thirteen. He wins if a card matches the number he calls, such as an ace on “one”; if none of the thirteen matches, he pays the other players.
Montmort, born in Paris in 1678, first considered the counting problem in his Essay d’analyse sur les jeux de hazard of 1708. He solved it in the second edition of 1713, and Nicolaus Bernoulli, his correspondent since 1710, solved it at about the same time. The wider question, how many shuffles leave exactly k matches, is called the problème des rencontres, and the no-match counts are known as rencontres numbers or de Montmort numbers. Leonhard Euler took it up in a paper written in 1779, Solutio quaestionis curiosae ex doctrina combinationum, listing the first ten or so terms and proving the two rules that generate them.
From 9/24 to 1/e
One of Euler’s two rules is Dn = (n − 1)(Dn−1 + Dn−2). Letter A goes into one of the other n − 1 envelopes, say k; then letter k either swaps back into A or it does not, and those two cases give the two terms.
| Letters | All arrangements | All wrong | Chance |
|---|---|---|---|
| 3 | 6 | 2 | 0.3333 |
| 4 | 24 | 3 × (2 + 1) = 9 | 0.3750 |
| 5 | 120 | 4 × (9 + 2) = 44 | 0.3667 |
| 6 | 720 | 5 × (44 + 9) = 265 | 0.3681 |
| 7 | 5,040 | 1,854 | 0.3679 |
| 8 | 40,320 | 14,833 | 0.3679 |
The chance wobbles around one value and locks onto it almost at once. Inclusion and exclusion gives the exact chance as 1 − 1/1! + 1/2! − 1/3! + … ± 1/n!. For four letters that is 1 − 1 + 1/2 − 1/6 + 1/24 = 9/24. Run the series forever and it adds up to 1/e.
The same count answers the hat-check problem, where no one gets their own hat back. With 8 people or 8 million, the chance of a complete mix-up stays at about 36.8%. For why e turns up in so many places, read why e is 2.718.
More than a third of the time, every letter goes wrong.
