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.
The Engines of Our Ingenuity is Copyright © 1988-2010 by John H. Lienhard.