The following math problem appeared in a math forum that I
follow:
You have a deck of 56 cards, labeled 1 through 56. All the
cards are drawn randomly one at a time. What is the probability that for
exactly one card, the face value of the card is one less than the face value of
the card before it.
The reason for considering the number 56 was not specified,
but that doesn't matter because it is clear that to solve the problem in any
kind of satisfying way we have to solve it in a more general case, where 56 is
replaced by n. In this case, the probability is P(n)/n!, where P(n) is the
number of permutations p of (1, … ,n) for which p(k – 1) – p(k) = 1 for exactly
one k. The problem reduces to finding P(n).
The answer is rather neat, and (SPOILER ALERT) I give it below.
However what I find most interesting is the way my finding the solution to this
problem depended so much on technology. To solve it I did not need to know much
mathematics at all. If I had had to solve the problem 30 years ago, it would
have taken much more knowledge and/or much more time.
The first thing I did was to generate some numerical
evidence. By writing out the acceptable permutations and counting them, I found
that P(2) = 1, P(3) = 2, P(4) = 9, and P(5) = 43. I sent the problem to a
friend of mine, Ken Cutter, who is a MATLAB guru, and he wrote a short program
in MATLAB, using perms(1 … n) to list all permutations and the diff function to
compute the differences p(k) – p(k-1). He discovered that I had missed one
acceptable permutation of (1 … 5) so that actually P(5) = 44. He also gave me
the list of a few more values of P, including P(6) = 265.
I now knew I was looking for a sequence 1 , 2, 9, 44, 265, …
, so I went to the Online Encyclopedia of Integer Sequences (OEIS, https://oeis.org/)
and entered 1 , 2, 9, 44, 265 into the search field, and out came two known
sequences. Only the first of these two sequences seemed to relate to
permutations, and sure enough, one the descriptions of this sequence identified
it as what I was looking for.
The answer turns out to be that P(n) number of derangements
of P(n), that is, the number of permutations with no fixed points. The formula
for P(n) is given on OEIS as P(n) = n!*Sum((-1)^k/k!, k=0..n). On the Wikipedia page for derangements,
it is noted that a common notation for P(n) is !n, so the desired probability
is !n/n! = Sum((-1)^k/k!,
k=0..n) which, as
Wikipedia notes, converges rapidly to 1/e. In fact, it is the first n terms of
the Taylor expansion for exp(x) about 0, evaluated at x = -1. For the original problem with n = 56, the
answer for all practical purposes is 1/e.
Looking
back, the most crucial tool in my finding the solution was The Online
Encyclopedia of Integer Sequences, started by Neil J. A. Sloane, and a
wonderful resource for anyone involved in mathematical work. MATLAB was also
very helpful. Without it, I might have still gotten the answer if I had gone
over my work and discovered my mistake which made me get P(5) off by one. If I
had entered the correct first 4 terms, Online Encyclopedia of Integer Sequences
would have returned 17 sequences, but it would still have been pretty easy to
find the correct sequence from amongst these 17. But MATLAB (and Ken Cutter) saved
a lot of time. Lastly, Wikipedia was a help in explaining the result.
When I was
in school, none of these resources were available. If I knew more about
combinatorial mathematics, I might have known the answer immediately, or at
least recognized it once I generated the numerical examples. Otherwise, I would
have had to look at my lists of acceptable permutations more carefully and perhaps
derived a recursion relation or induction step that would enable me to find the
solution. I would be interested in hearing from anyone would like to send me a
solution to this problem from scratch, imagining that they do not know the
answer already.
This
experiences brings home to me how much the methods of mathematics research have
changed since I was in school. I wonder what changes we should be making in
K-12 math education that take into account these changes.
No comments:
Post a Comment