But That Would Almost NEVER Happen, Would It?

Click on images to see higher resoultion images

A young man in one of my classes, obviously trying to improve his A+ by sucking up to the teacher, mentioned that he had read my recent blog on the pigeon-hole principle. He went on to suggest that he really doubted the idea that 39 people could randomly seat themselves and ALL be in the wrong seat. "It just seems VERY unlikely." he suggested.

Rather than tell him the answer, I set him the task of simulating the activity with a deck of cards. Pull out any suit, say the spades, and really shuffle the remaining cards well. Now we need to decide on an order for the remaining suits, so let clubs be the numbers one to thirteen in order from Ace, two, up to King for thirteen. Then the ace of diamonds can be 14, up through the King of diamonds for 26. Finally the ace of hearts is 27 up to the king of hearts for 39. Now turn over the cards and as you do count, one, two, etc... and if you get a card that is where it should be, stop.. they didn't all sit in the wrong chairs. You need not go on forever, just ten or so trials should give you an idea of whether the event is really, really uncommon, or not so very uncommon.

I didn't tell him that I knew the probability, and that he should probably get three or four trials in a string of ten shuffles in which none of the cards landed in the right place. Such a mis-ordering of the cards was just the idea behind the first critical study of the idea we now call derangements by Leonhard Euler, the great Swiss mathematician. Euler was studying the probability of winning in the game of rencontre, now called "coincidences" in his paper "Calcul de la Probabilite dans le jeu de Rencontre", published around 1751. An English translation of the paper by Richard J. Pulskamp is available and the original document can be seen here.

So what did Euler discover? Well for larger values of N, say 39 or so, the probability of having a perfect mis-sorting of the items approaches 1/e, or about 36.8%, more than a third of the time. It is not an unusual event at all. For smaller numbers you can find the probability by using the idea shown here for six items..
. This can be rewritten more easily using the factorial notation as P= 1/2! - 1/3! + 1/4! - 1/5! + 1/6! which is only a tiny bit above 36.8%, already very close to the 1/e value given above for the limiting value. If the number of items is even, the series will be a little more than 1/e, and if it is odd (and the last term is subtracted) then the probability will be a little below 1/e, with the propbability approaching 1/e as a limit as n gets greater and greater.

I decided to simulate a lot more times than would be practical with a deck of cards, so I cranked up Fathom, a wonderful simulation software by the folks at Key Curriculum, and had it repeat the experiment of seating the 39 people at random 1000 times, and then count how many landed in the right place. The results are shown in the graph below.

It happened that no one landed in the right place 371 times.... Hmmmm, I guess Euler got it right.