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?

An easy start

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.

Genewhotothewhatnow?

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!

So how does it help here?

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.)

The three-card case

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.

More generally

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!

A clever strategy for dealing with duds

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.

Dud scoring

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$.

So how about $g_{(5,0)}(x)$?

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.

Special bonus!

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.