by Andrew Boyd
Today, derangements. The University of Houston's College of Engineering presents this series about the machines that make our civilization run, and the people whose ingenuity created them.
Let's do an experiment. In my hand I hold a bag with ten cards labeled one through ten. I'm going to reach in the bag, grab a card at random, and set it on the table in front of me with the number facing up. I'll repeat the process until all ten cards are lined up in the order I've pulled them from the bag. Here's the question. What's the chance that none of the cards has a number matching its position? That is, what's the chance that the first card isn't labeled one, the second isn't labeled two, and so on, right through card ten?
The question was brought to my attention by an Engines listener. He'd come up with the question while playing a board game with his daughter. What he'd stumbled upon was a famous problem from the very earliest days of probability.
The question was first posed by French mathematician Pierre de Montmort in 1708. It was solved independently by de Montmort and by Nicholas Bernoulli a few years later. A sequence of cards in which no number matches a card's position is called a derangement.
De Montmort's ultimate question wasn't about a bag filled with ten cards, but an arbitrary number of cards. With ten cards, there's about a thirty-seven percent chance no label matches its position. But what happens when we have more than ten cards, say, one-hundred? There's a smaller chance that any particular card winds up in the right location. But there are many more chances for this rare event to occur — one-hundred instead of ten. De Montmort asked what happens when the number of cards grows ever larger.
And the answer? One divided by lower case e, where e is a mathematical constant equal to about 2.7. Students normally meet e in their first calculus course. Like the names Elvis or Madonna, e needs no further explanation to a mathematician. It's one of a handful of numbers so fundamental it has a reserved symbol. The same is true of pi. The symbol pi isn't actually a number, it's a Greek letter. But it comes up so often that the number and symbol are all but indistinguishable.
Jacob Bernoulli, brother of Nicholas, is often credited with the discovery of e in his studies of compound interest. If I put a dollar in the bank at an annual interest rate of 100% (I'm free to dream), I'll have two dollars to show at the end of the year — if interest is compounded annually. If it's compounded monthly, $2.61. Compounded at every instant, e dollars — about $2.72.
e pops up in all sorts of unexpected places, and that's part of its charm. Type a lower case e into your favorite search engine and see what you find.
I'm Andy Boyd at the University of Houston, where we're interested in the way inventive minds work.
Notes and references:
Thanks to David Zimmerman (and his daughter) for bringing the topic of this episode to my attention.
The problem originally stated by de Montmort is often referred to as the hat check problem. The name derives from the following scenario. A hat checker at a party checks hats but fails to properly tag them. When guests return to retrieve their hats, the checker returns the hats at random. What is the chance that not a single guest receives his own hat?
The number e is sometimes referred to as Euler's number (not to be confused with Euler's constant), though the designation is misplaced. The expression is probably due to the fact that Euler suggested the notation 'e' and because Euler's last name begins with the letter e.
Derangement. From the Wolfram Math World Web Site: http://mathworld.wolfram.com/Derangement.html. Accessed November 16, 2010.
The Number e. From the MacTutor of History of Mathematics Archive at the University of Saint Andrews, Scotland: http://www-history.mcs.st-and.ac.uk/HistTopics/e.html. Accessed November 16, 2010.
All pictures by E. A. Boyd.