Math Tutoring Service

See my Mathematics Tutoring Service on Thumbtack

Changes in Mathematics Research Methods

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, 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: