 |
 |
 |
Consider n letters with n different
address headings and n letters each addressed to one of these addresses.
Suppose before the letters are stuffed into the envelopes, they are dropped
on the floor and then carelessly (randomly) assigned to the n envelopes.
Another statement of essentially the problem is as follows: n men
check in their hats at a club. Due to employee shortages at the club, as
the men leave they are randomly given a hat from the collection of n
hats. A more dramatic but equivalent scenario might have n patients’
medical records and n lab results. Because of some mix up, the tests
results are randomly assigned to the medical records. An assignment of
the n objects (letters, test results, etc.) to n receptacles
(envelopes, lab reports, etc.) such that none of them is in the
proper position is called a derangement of the n objects. A more
abstract algebraic definition of a derangement of n objects is a
permutation of order n which has no fixed points. Over two hundred
fifty years ago Leonhard Euler derived a formula for the number of different
derangements of n objects in the context of analyzing the probability
of winning a card game called Rencontre (see Ed Sandifer's " How Euler
Did It" for September 2004 on the MAA website at http://www.maa.org/editorial/euler/How
Euler Did It 11 Derangements.pdf )
Let x stand for the number of correct matches (i.e., the number of fixed points of the permutation). Assuming a random assignment of letters to envelopes, the probability distribution of x is given by the following formula:
Note: The probabilityof
a derangement, P(0, n) differs from 
by no more than 
and the probability of exactly one match, P(1,
n)
differs from
by no more than
.
Surprisingly, for any value of n > 1 the mean number of matches
is always 1 with a standard deviation of 1 .
A class demonstration experiment and a derivation of the probability distribution is found in the file at
An Excel file to analyze the class demonstation is available at
"A GREAT discovery solves a great problem, but there is a grain
of discovery in the solution of any problem. Your problem may be modest,
but if it challenges your curiosity and brings into play your inventive
faculties, and if you solve it by your own means, you may experience the
tension and enjoy the triumph of discovery."
George Pólya in How to Solve It .
I would like to thank Chia Sheng Huang, an instructor in MATC's Alternative
Learning Division (CPAAC), for bringing this problem to my attention.
|
|||||||||