## The Two Decks of Cards and the Drunken Hat Check Girl

1. Imagine you have two decks of playing cards, each thoroughly shuffled.  You give one deck to your friend and keep the other.  Now each of you goes through your deck, one card at a time, flipping cards face up.  You compare your top cards, then you compare your next cards, and so on all through the deck.  If it ever happens that you both reveal the same card at the same time, you win; if you go through the whole deck without such a match, your friend wins.  Who is more likely to win?  You or your friend?
2. Thirty-seven men attend a certain social event and check their hats as they enter.  However, the hat check girl has had a bit too much to drink, and when the time comes to leave, she gives back hats at random, with total disregard for which hat belongs to whom.  What are the chances that nobody ends up with his own hat?

The first thing to notice is that these are really the same problem.  In each case we have two correspondences between sets of things, and we wonder whether the two correspondences have anything in common.  In the first problem, the sets of things are the 52 cards in a deck and the 52 positions “first card, second card, third card, etc.”  Each time you shuffle a deck, you create a correspondence between the cards and the positions.  In the second problem, the things are hats and people.  One way of pairing people and hats is ownership, and another way of pairing people and hats is what the hat check girl does.

(There is another apparent difference between the two situations.  In the two-deck problem, both permutations are chosen randomly; in the hat check problem, one permutation is fixed and the other is random.  But this isn’t really a difference. To see why, imagine you are playing a game where you try to predict the outcome of a die roll.  It doesn’t really matter whether you guess a number in advance or roll a die of your own and guess that the dice will match.)

These things are usually called derangements.  Let $D_n$ be the number of derangements of $n$ objects.  (So, $D_100$ counts the number of different ways for the hat check girl to give back 100 hats to 100 people, giving no one the right hat. It also counts the number of ways for a teacher to redo the seating chart for her 100-student class so that nobody ends up in the same seat. $D_100$ is also the number of ways a group of 100 people can arrange a Secret Santa so that nobody ends up buying a gift for herself.)

Enough commentary on the problem. Let’s solve it.

For very small numbers we can do it just by listing.  $D_1=0, D_2=1$, of course.  $D_3=2$ because the derangements of ABC are BCA and CAB.  We have to work a little harder to see that $D_4=9$, but if you check the 24 orders of ABCD, you’ll find the only derangements are: BADC, BCDA, BDAC, CADB, CDAB, CDBA, DABC, DCAB, DCBA.

For larger n, this is impractical.  Suppose that there are n people with hats, and call the first one Max.  The hat check girl can give Max any of the $n-1$ other hats.  Suppose Max gets Sam’s hat.  Then either Sam gets Max’ s hat or else he doesn’t.  If Sam gets Max’s hat, then the hat check girl has to derange the other $n-2$ hats, and there are $D_{n-2}$ ways she can do that.  If Sam isn’t allowed to get Max’s hat, then she has to derange the remaining $n-1$ hats, and there are $D_{n-1}$ ways that can happen.

So there are $n-1$ to give back the first wrong hat, and then $D_{n-1}+D_{n-2}$ ways to give back the rest.

This shows that $D_n = (n-1)(D_{n-1}+D_{n-2})$.

An equation like that is called a recursion, and it allows us to quickly compute any value of $D_n$, provided we know the smaller values $D_{n-1},D_{n-2}$.  So now we can compute $D_5 = 4(9+2)=44$, $D_6 = 5(44+9)=265$, $D_7 = 6(265+44) = 2163$, etc.  I hope none of you were trying  to figure out $D_7$ by listing the possibilities!  Brute force has its limitations.

It turns out there is a nice formula for $D_n$.

$D_n = \frac{n!}{0!}-\frac{n!}{1!}+\frac{n!}{2!}-\frac{n!}{3!}+\cdots \pm \frac{n!}{n!}$

So, for example,

• $D_3 = 3\cdot 2\cdot 1 - 3\cdot 2 + 3 -1 = 6-6+3-1=2$,
• $D_4 = 4\cdot 3\cdot 2\cdot 1 - 4\cdot 3\cdot 2 + 4\cdot 3 -4+1 =24-24+12-4+1=9$,
• $D_5 = 120-120+60-20+5-1=44$.

Now, in the questions I asked at the beginning of the post, we weren’t interested in how many ways to derange a list of objects as we were in the likelihood of a given permutation being a derangement.  So we really want to study $p_n = \frac{D_n}{n!}$, which is the probability that one of the $n!$ permutations of n objects will be a derangement.  The result is a little unexpected.

$p_n = 1-1+\frac{1}{2!}-\frac{1}{3!}+\frac{1}{4!}-\frac{1}{5!}+\cdots \pm \frac{1}{n!}$

This kind of expression is actually rather famous in mathematics.  If we hold our breath and allow the summation to have infinitely many terms, it turns out that

$1-1+\frac{1}{2!}-\frac{1}{3!}+\frac{1}{4!}-\frac{1}{5!}+\cdots \pm \frac{1}{n!}\mp\cdots = \frac{1}{e}$.

This number $e$ I mention is about 2.71828183, and it is the other number (along with $\pi$) which is inexplicably ubiquitous in mathematics.

Because the numbers $\frac{1}{n!}$ are so small, even when n is moderately sized, the numbers $p_n$ approach $1/e\approx 0.367879441$ very very rapidly.  Provided n is at least 13, say, $p_n$ agrees with $1/e$ to ten decimal places no matter what specific n we are talking about.

By the time we reach 52 (in the case of playing cards), $p_n$ agrees with $1/e$ to more than 60 decimal places.  Bottom line: the changes of a derangement are about 36.79%, and the number of objects barely matters.

So the probability of nobody getting his hat back is about 0.3679, a bit more than 1 in 3.

And you’ll win the shuffling game about 63.2% of the time.

The fact that the numbers $p_n$ are, for all intents and purposes, independent of n can be looked at this way.  Suppose you and your friend are trying to decide what kind of deck of cards to use.  An ordinary deck of cards (52)?  A euchre deck (24)?  A tarot deck (78)? A deck from my favorite (imaginary) game, Ultimate Fanucci (42000000)?  Using more cards makes each individual match less likely, but gives more opportunities for a match, so the result is not obvious.  But what we have seen means that these two effects cancel either other out almost exactly, so it doesn’t matter.