Written by Colin+ in probability, puzzles.

In a recent MathsJam Shout, courtesy of Bristol MathsJam, we were given a situation, which I paraphrase:

- Cards bearing the letters A to E are shuffled and placed face-down on the table.
- You predict which of the cards bears which letter
- (You make all of your guesses before anything is revealed, and must predict each letter exactly once).

What’s the probability of getting all five correct? How about the probabilities for 4, 3, 2, 1 and 0?

The probability of getting five correct is simply $\frac{1}{5} \times \frac{1}{4} \times \frac{1}{3} \times \frac{1}{2} \times \frac{1}{1}$, or $\frac{1}{120}$.

The probability of getting four correct is even more simple: it’s zero, because if you have four correct, the fifth must also be correct.

You might conceivably know that the number of derangements of five objects is 44 – I had a vague recollection – but let’s pretend we don’t know that. Instead, let’s use *generating functions*.

Generating functions have many uses, one of which is to turn problems involving distributions of integers into problems of algebra.

There’s a fairly natural bijective mapping between the possible probability distributions on the integers and the polynomials with non-negative coefficients $p(x)$ such that $p(1) = 1$: suppose $X$ is a random variable that takes integer values, there is a polynomial such that the $x^k$ term has coefficient $p_k$ if and only if $P(x=k) = p_k$.

That looks like gobbledygook, so let’s take an example: suppose $X$ is the number of sixes you get from rolling two fair dice. You can work out that $P(X=0) = \frac{25}{36}$, $P(X=2) = \frac{1}{36}$ and $P(X=1) = \frac{10}{36}$. The corresponding generating function is $\frac{25}{36} + \frac{10}{36}x + \frac{1}{36}x^2$.

This turns out to be $\br{ \frac{5}{6} - \frac{1}{6}x}^2$, which you might expand binomially. It’s not a coincidence that the probabilities come from the binomial distribution!

Let’s start with an easier problem: suppose you have only the letters A and B to deal with, rather than A to E. You have even chances of getting them both right, or of getting neither right, which corresponds to a generating function of $\frac{1}{2} + \frac{1}{2}x^2$. (I’m going to call this $g_{(2,0)}(x)$ - the generating function for when you have two cards, neither of which is a dud).

Suppose instead you have cards A and C to match with cards A and B. Here, you’ll get one correct match half the time, and neither correct the other half, making the generating function for this case $\frac{1}{2} + \frac{1}{2}x$. (This is $g_{(2,1)}(x)$: two cards, one of which is a dud.)

We can use this to extend the problem to three cards, A, B and C.

Without loss of generality, suppose you predict the first card to be A. You will be correct one time in three, leaving yourself with two cards and no duds; the remaining two-thirds, you will leave yourself with a possible match and a dud.

You would score a point in the first case, and thus need to increase all of the powers in the corresponding generating function by one - which you can do by multiplying by $x$.

That makes the generating function for the three-card case $\frac{1}{3}x g_{(2,0)}(x) + \frac{2}{3} g_{(2,1)}(x)$, or $\frac{1}{3}x\br{ \frac{1}{2} + \frac{1}{2}x^2} + \frac{2}{3}\br{\frac{1}{2}+\frac{1}{2}x}$, making $\frac{1}{3} + \frac{1}{2}x + \frac{1}{6}x^3$.

Even without counting the cases, that’s clearly plausible: the coefficients (and therefore probabilitities) add up to 1; there’s no way to get exactly two correct; and the probability of getting all three correct is $\frac{1}{6}$, as we’d have worked out.

Suppose you have $n$ cards, none of which are duds.

You have a probability of $\frac{1}{n}$ of getting the first card correct, in which case you now have $n-1$ cards, none of which are duds.

You have a probability of $1 - \frac{1}{n}$ of getting the first card wrong, in which case you now have one dud out of $n-1$ cards.

That makes a recursively-defined generating function of $g_{(n,0)}(x) = \frac{1}{n}x g_{(n-1,0)}(x) + \br{1 - \frac{1}{n}} g_{(n-1,1)}(x)$, with base cases still to come.

But we haven’t really considered dud cases yet!

There's a clever way to handle how duds to ensure you only ever have one in your hand at a time: if you know one of the cards you have to match is a dud, check that one next. Obviously, it will be wrong, but there are two flavours of wrong: either it matches a card you still have to match (the bad wrong, as it leaves you with another, different dud), or it matches a card you've already tried to match (the good wrong, as you now have no duds.)

For example, suppose I predict the ordering BDACE and the correct (but face-down) order is ABCDE.

I begin by checking my prediction for A - it's wrong, as I turn over a C.

The next card I check is my C - which is bad-wrong, as I turn over a D.

(Now I have B, D and E still to match; A, B and E are still face down. D is my only dud.)

I check my D, turning over a B - this is also bad-wrong (I now have B and E in my hand, and A and E face-down).

I check B, and turn over A, which is good-wrong - it leaves me with E to match with E, so I've matched one card correctly.

In general, if you have a single dud card out of a total of $n$, you have a $\frac{1}{n}$ probability of the next match involving $n-1$ non-duds, and a $1 - \frac{1}{n}$ chance of having a dud in your $n-1$ cards.

Logically, $g_{(n,1)} = \frac{1}{n} g_{(n-1,0)}(x) + \br{ 1- \frac{1}{n}} g_{(n-1,1)}(x)$.

The only difference between this and the $g_{(n,0)}$ function is that the first term is multiplied by $x$ in the other version. We could even write:

$g_{(n, d)}(x) = \frac{1}{n}x^{1-d} g_{(n-1,0)}(x) + \br{ 1- \frac{1}{n}} g_{(n-1,1)}(x)$ for $n \gt 0$ and $d \in \{0,1\}$.

We also need to work on the base cases: I *think* all we need to state is that $g_{(0,0)}(x) = 1$.

It’s simplest to build the functions up from the base, although it’s possible to work downwards if you’re really careful with your fractions. Let’s go from the very beginning:

$g_{(0,0)}(x) = 1$.

That means $g_{(1,0)}(x) = x$ and $g_{(1,1)}(x) = 1$, as we would hope.

For two cards, we have $g_{(2,0)}(x) = \frac{1}{2}x g_{(1,0)}(x) + \frac{1}{2} g_{(1,1)}(x) = 1 + x^2$, as before; also, $g_{(2,1)}(x) = \frac{1}{2}g_{(1,0)}(x) + \frac{1}{2}g_{(1,1)}(x) = 1+x$. It’s agreeing so far!

Keeping going, $g_{(3,0)}(x) = \frac{1}{3}x g_{(2,0)}(x) + \frac{2}{3} g_{(2,1)}(x) = \frac{1}{3} + \frac{1}{2}x + \frac{1}{6}x^2$, as before; $g_{(3,1)} = \frac{1}{3} g_{(2,0)}(x) + \frac{2}{3} g_{(2,1)}(x) = \frac{1}{2} + \frac{1}{3}x + \frac{1}{6}x^2$. This remains plausible.

Penultimately, $g_{(4,0)}(x) = \frac{1}{4}x g_{(3,0)}(x) + \frac{3}{4} g_{(3,1)}(x) = \frac{3}{8} + \frac{1}{3}x + \frac{1}{4}x^2 + \frac{1}{24}x^4$ - which is again plausible; $g_{(4,1)}(x) = \frac{1}{4} g_{(3,0)}(x) + \frac{3}{4} g_{(3,1)}(x) = \frac{11}{24} + \frac{3}{8}x + \frac{1}{8}x^2 + \frac{1}{24}x^3$.

Last push for a final answer - and this time, we only need $g_{(5,0)}(x)$. Working it out, $g_{(5,0)}(x) = \frac{1}{5}x g_{(4,0)}(x) + \frac{4}{5} g_{(4,1)}(x) = \frac{11}{30} + \frac{3}{8}x + \frac{1}{6}x^2 + \frac{1}{12}x^3 + \frac{1}{120}x^5$.

This gives the probabilities of the results at $\frac{1}{120}$ for 5, zero for 4, $\frac{1}{12}$ for 3, $\frac{1}{6}$ for 2, $\frac{3}{8}$ for 1 and $\frac{11}{30}$ for 0.

It turns out that for a generating function $G(x)$, the expected value is given by $G’(1)$. So, by differentiating, we get $g’_{(5,0)}(x) = \frac{3}{8} + \frac{1}{3}x + \frac{1}{4}x^2 + \frac{1}{24}x^3$.

Then $g’_{(5,0)}(1) = \frac{3}{8} + \frac{1}{3} + \frac{1}{4} + \frac{1}{24} = 1$: on average, we expect to get one card correct!

If your eyes are especially sharp, you might spot that $g’_{(5,0)} = g_{(4,0)}$. Does this pattern continue? Can you prove it?

A lovely puzzle, that – I’m sure there are less involved ways to solve it, but I like this one, dagnabbit.

* Thanks to Bristol MathsJam for the puzzle, and to Barney Maunder-Taylor and Adam Atkinson for helpful comments.

## Christopher Allan

Long ago I made some notes on this problem, known as “The Matching Problem”. As you say, a derangement means no matches. I did it with two numbered packs of cards. You have done it for 5 cards. For 6 there are 720 arrangements: 265 give zero matches, 264 give 1 match, 135 give 2 matches, 40 give 3 matches, 15 give 4 matches, zero give 5 and 1 gives 6, of course.

I have the general formula which resembles yours. Somewhere along this derangements thing there is a term known as ‘subfactorial N’. Subfactorial N can be expressed in terms of N! and associated lower factorials, but I forget the details. (You sometimes see it written with the exclamation mark upside down). Subfac 4 = 9, subfac 5 = 44, subfac 6 = 265, etc.

Also, as N gets large, it can be shown that probability of no matches (i.e. all the cards differing from their original positions) approximates to 1/e. This means it becomes very close to 0.36788 or about a 37% chance of zero matches.

Have just discovered I extended it to 8 cards:

N = 7 gives no. of derangements as 1854

N = 8 gives 14,833

I gave up at this point. The approx. to 1/e is quite good for N = 8.