Math Corner

John Derbyshire has another good one up in his August Diary. It's another probability question, this time about cards:

I have an ordinary deck of 52 playing cards. I shuffle it thoroughly. What is the probability that not one card is in its original position?

As often happens, the way to approach this is to look at the conjugate question: what is the probability that at least one card is in its original position? Suppose, for example, that one card is in its original position - we'll call this a stationary card, because it didn't move after shuffling. There are C(52,1) ways to pick this one card, and the other 51 cards can be arranged arbitrarily, so there are 51! ways to arrange them. However, we've done some double-counting here, because some of those 51! include arrangements that have a second stationary card.

It's worth going over this point in some detail, because this is an argument we're going to come back to again. To see what's happening here, it's useful to reduce the number of cards. So let's say there are only 4 cards, numbered 1, 2, 3 and 4. There are, of course, 4! = 24 possible arrangements of these cards. Let's look at all the arrangements with the "1" card in its original position:

1,2,3,4
1,2,4,3
1,3,2,4
1,3,4,2
1,4,2,3
1,4,3,2

Also, let's look at all the arrangements with the "2" card in its original position:

1,2,3,4
1,2,4,3
3,2,1,4
3,2,4,1
4,2,1,3
4,2,3,1

Notice something? The lists aren't distinct. Those first two entries are common to both lists. What we've done is double-count arrangements that contain at least two stationary cards.

We can subtract those back out pretty easily: there are C(52,2) ways to pick two cards, and then 50! arrangements of the other 50 cards. So we'll subtract C(52,2)50! arrangements.

But wait! We've removed too much, because both of the previous sets included arrangements that had at least three stationary cards. Going back to the 4-card example, take a look at the arrangement "1,2,3,4". We originally double-counted it, but then we double-removed it. So to count those arrangements we have to add back in arrangements with at least three stationary cards, and that's C(52,3)49!.

It should be no surprise at this point that this pattern continues. Now we've double counted arrangements with four stationary cards, so we subtract C(52,4)48! of those, at which point we need to add back the ones with five - there are C(52,5)47! of them - and so on. We end up with this many arrangements:

C(52,1)51! - C(52,2)50! + C(52,3)49! - C(52,4)48! + ... + C(52,51)1! - C(52,52)0!

There are 52! total arrangements of 52 cards, so to get the probability, we divide the above expression by 52!. This simplifies down to:

1/1! - 1/2! + 1/3! - 1/4! + ... + 1/51! - 1/52!

But this is the probability of having at least one stationary card, and we wanted the probability of having zero stationary cards, which is:

1 - 1/1! + 1/2! - 1/3! + 1/4! + ... - 1/51! + 1/52!

Reasoning the same way you can see that if you had n cards, the probability would be the first n+1 terms of this series. (It's an interesting fact that the above expression is the first n+1 terms of something called the Taylor series for 1/e, where e is the base of natural logarithms that you may dimly remember from high school or college. For more than 8 or so cards, the difference between the actual probability and 1/e is very small: less than 0.01%.)

Let's look at Derbyshire's second (related) problem:

I have a deck of n cards, numbered from 1 to n. I shuffle the deck thoroughly. Then I turn the cards over one by one. If the k-th card I turn over bears the number k, call that a "match." What is the probability that after going through the whole deck I shall have tallied m matches, where m is some number in the range from zero to n?

Based on the work we did before, this isn't hard at all.

Let's write the number of arrangements of n cards that have m matches (what I earlier called "stationary cards") as A(n,m). Then the probability p(n,m) that Derbyshire seeks is just A(n,m)/n!. Furthermore, we can reason about A(n,m) as follows: Suppose we select m cards and call them the matches. There are C(n,m) ways to make this selection. For each selection, there are A(n-m,0) arrangements of the remaining cards that have no matches. Any combination of a selection of m matches along with an arrangement of n-m cards that have no matches is equivalent to an arrangement of n cards with m matches. So A(n,m) = A(n-m,0)C(n,m).

Furthermore, since p(n,m) = A(n,m)/n!, we can write p(n,m) = A(n-m,0)C(n,m)/n! = p(n-m,0)C(n,m)(n-m)!/n! = p(n-m,0)/m!. Since our solution to the first problem gave us p(n,0) for every n, we now know how to calculate p(n,m) for every n and m.