Counting Countdowns

Colin Beveridge

30 October 2020

• Click to share on X (Opens in new window)
• Click to share on Facebook (Opens in new window)
• Click to share on Reddit (Opens in new window)
• Click to share on LinkedIn (Opens in new window)
• Click to share on Threads (Opens in new window)
• Click to share on Mastodon (Opens in new window)

Rachel Riley puts the last of the six numbers on the rack and presses the button to generate a random target. The host—whoever the host is now, I haven’t really watched Countdown since Richard Whiteley died—says a few words and starts a 30-second timer. And the contestant thinks, ‘Now I need to combine those numbers to make the target. I know! I’ll just check all of the possible calculations with these six numbers! I wonder how many there are.’

The aim of the game is to combine the six given numbers using the four basic arithmetic operations ($+, -, \times$ and $\div$) to reach a target number. You do not need to use all of the numbers, but you may not use any number more often than it appears on the board. Also, you’re inexplicably not allowed to use fractions at any point.

For example, given the numbers in the big picture above, with the displayed target of 333, you might solve it as \[ ((50-4) \times 7)+5 + 6, \quad \text{or as} \quad ((50-6)\times 7) + 25,\] or several other acceptable ways.

TL;DR: including the trivial answer of 0, there are 974,861 distinct answers that can be reached by applying the four basic operations to combine six numbers, if you ignore (a) coincidences and (b) Countdown’s fraction-phobia.

Starting simple

…in which we analyse a much simpler version of the Countdown numbers game.

Ug, contemporary painting. Adapted from Wikimedia user James St John, (CC BY-SA 4.0)

Back in the Upper Palaeolithic, when humankind was first starting to emerge, Channel Lots launched a teatime chisel-marks-and-numbers game show hosted by Ug, in a horrible tie, and Thog (surprisingly, Thog is Neanderthal for ‘Carol’), famed for her ability to combine two numbers at speed.

Protocountdown’s numbers game required exactly this skill: Thog would select two numbers at random, and the contestants would combine them using the four basic operations. How many outcomes are there?

• You can add or multiply the two numbers (one way each, because these operations commute) $\to 2$ outcomes;
• you can subtract them or divide them (two ways each, because these operations don’t commute) $\to 4$ outcomes;
• you could also use either number alone $\to 2$ outcomes;
• or use no numbers at all to reach zero $\to 1$ outcome;

making 9 outcomes altogether.

As the show’s format—and humans—evolved, a third number was added to the numbers game, causing consternation among the audience of students and the elderly. This simple extension made the game ten times as difficult!

How to count

According to Williams’ First Law of Counting, counting is hard—
especially the bit about making sure you count every item exactly once. 

It’s usually a good idea to come up with an estimate first. Suppose we want to combine three numbers using two operations. Starting with any of the numbers, there are two ways to pick its partner; as we saw above, each pair generates about six answers, making 12. There is one way to pick the final number to combine (with the existing 12 pairs), and each generates about six answers, making 72. Heuristically, this gives an estimate of $(n-1)! 6^{n-1}$ ways to combine exactly $n$ numbers.

That estimate isn’t far off, but getting the right answer takes a bit more work. We need to get methodical.

In fact, there are not really four operations, there are only two. Subtraction and division are addition and multiplication, respectively, wearing funny hats—or, for the purposes of this article, dressed in a circle. We’ll consider $\oplus$, meaning ‘addition or subtraction’, and $\otimes$, meaning ‘multiplication or division’, as operations (not necessarily binary) that result in sets of values (for explanatory convenience, I’ll talk about these operations acting on sets or on elements; they act on elements as if the elements were really singleton sets).

Let’s start with a numerical example. The operation $2$ $\otimes$ $3$ gives the set of values $ \{ 2\times 3 , 2/3, 3/2 \} $. You can replace $ 2\times 3 $ with 6 if you prefer.

Meanwhile, $ 2$ $\oplus$ $3 $ gives the set of values $ \left\{ 2 + 3, 2-3, 3-2 \right\} $ , or $ \left\{ 5, 1, -1 \right\} $.

More generally, if $a$ and $b$ are single-valued numbers (of which more in a moment), the operation $a$ $\otimes$ $b$ gives the set of values

Meanwhile, $a$ $\oplus$ $b$ gives the set of values $\{ (a+b), (a-b), (b-a)\}$, or more parsimoniously,

$a$ $\oplus$ $b = \{ (a+b), \pm (a-b)\}.$

This second element is an example of a double-valued number. We’re getting to it, don’t worry. If set $A = \{ a_1, a_2, \dots\}$ and $B = \{ b_1, b_2, \dots \}$, then $A$ $\oplus$ $B$ and $A$ $\otimes$ $B$ are the sets

$A$ $\oplus$ $B = \bigcup_{i,j} a_i$ $\oplus$ $b_j, \quad A$ $\otimes$ $B = \bigcup_{i,j} a_i$ $\otimes$ $b_j.$

In both cases, the resulting set is all the possible values that come from applying the operation to an element from $A$ and an element from $B$.

$\oplus$ing and $\otimes$ing values and sets

…in which we calculate some non-trivial examples.

Since you asked, I pronounce $\oplus$ as ‘oplus’ and $\otimes$ as ‘otimes’, but you are free to call them whatever you please.

‘Can I have your single-valued number?’

It makes later calculations more straightforward if numbers are considered as single-valued, like $(a+b)$, or double-valued, like $\pm (a-b)$. By assumption, the initial inputs into the calculation are all single-valued: there isn’t a $\pm 7$ card, for example. Nor is there a zero. Zero would really mess things up.

Single-valued numbers are…special. Or, if you prefer, annoying. They need to be treated differently from double-valued numbers.

If you $\oplus$ two single-valued numbers, the resulting set consists of a single-valued and a double-valued number. Any other combination of two numbers gives a set of two double-valued numbers. For example, $ 7$ $\oplus$ $\pm 3 = \{ \pm (7+3), \pm (7-3) \}$: you can combine $7$ and $\pm 3$ to get $10$, $-10$, $4$ or $-4$. You can check other possibilities if you’re so inclined.

If you $\otimes$ two single-valued numbers, you get three single-valued numbers. Any other combination of two numbers gives three double-valued numbers. For example,

$4$ $\otimes$ $\pm 5 = \{ \pm 4 \times 5, \pm 4/5, \pm 5/4 \} $,

and again I encourage you to check the other possibilities.

Since we’re only counting, we don’t care precisely what the elements of an output set are—we’re interested in the number and type of elements involved. Rather than listing the elements, we can denote the sets as \[ \left\{ \begin{matrix} s \\ t \end{matrix}\right\}, \] where $s$ is the number of single-valued numbers in the set and $t$ the total number of values.

For example, the set consisting of the single-valued number 7 would be written as $ \left\{ \begin{smallmatrix} 1 \\ 1 \end{smallmatrix} \right\} $: there is one single-valued number out of a total of one. The set consisting of the double-valued number $\pm 3$ is $ \left\{ \begin{smallmatrix} 0 \\ 1 \end{smallmatrix} \right\} $: there are zero single-valued numbers out of one.

Some examples of combining these sets:

It turns out, when dealing with exactly two sets, the rules for $\oplus$ and $\otimes$ are:

$ \left\{ \begin{matrix} a \\ b \end{matrix} \right\}$ $\oplus$ $\left\{ \begin{matrix} c \\ d \end{matrix} \right\} = \left\{ \begin{matrix} ac \\ 2bd \end{matrix} \right\} \quad\text{and}\quad \left\{ \begin{matrix} a \\ b \end{matrix} \right\}$ $\otimes$ $\left\{ \begin{matrix} c \\ d \end{matrix} \right\} = \left\{ \begin{matrix} 3ac \\ 3bd \end{matrix} \right\}. $

Sadly, $\otimes$ is a bit messy when it comes to combining more sets.

2-calculations

…in which we solve Protocountdown again.

Even though we’ve already solved the two-number case, let’s go through it with the new notation. If we use both numbers, there is only one way to pair the two single-valued numbers up (ie with each other), and two possible calculations to do it with. We’ve got:

$\left\{ \begin{matrix} 1 \\ 1 \end{matrix}\right\}$ $\oplus$ $\left\{ \begin{matrix} 1 \\ 1 \end{matrix}\right\} = \left\{ \begin{matrix} 1 \\ 2 \end{matrix}\right\} \quad\text{and}\quad \left\{ \begin{matrix} 1 \\ 1 \end{matrix}\right\}$ $\otimes$ $\left\{ \begin{matrix} 1 \\ 1 \end{matrix}\right\} = \left\{ \begin{matrix} 3 \\ 3 \end{matrix}\right\}. $

In total, there are $2+3 = 5$ values, of which $1+3=4$ are single-valued. That accounts for six ways (4 single-valued $+$ 1 double-valued) to combine exactly two numbers, which is a relief. On top of this, there are two ways to pick a single number, and one way to pick no numbers at all, making nine in all.

3-calculations

…in which we extend the operations further.

With three numbers, there are two ways to proceed: firstly, we could combine them all in one go. If we $\oplus$ three single-valued numbers together, it works just as we’d expect:

$2$ $\oplus$ $5$ $\oplus$ $13 = \{ 2+5+13, \pm(2+5-13), \pm(2+13-5) \pm(5+13-2) \}$,

or in our curly notation

$\left\{ \begin{matrix} 1 \\ 1 \end{matrix}\right\}$ $\oplus$ $\left\{ \begin{matrix} 1 \\ 1 \end{matrix}\right\}$ $\oplus$ $\left\{ \begin{matrix} 1 \\ 1 \end{matrix}\right\} = \left\{ \begin{matrix} 1 \\ 4 \end{matrix}\right\}. $

Left: Sign o’ the Times. Right: Sign o’ the Otimes.

Unfortunately, $\otimes$ing several values is less well-behaved. Instead of the oproduct of three single-valued numbers being $\left\{ \begin{smallmatrix} 9 \\ 9 \end{smallmatrix}\right\}$, it’s $\left\{ \begin{smallmatrix} 7 \\ 7 \end{smallmatrix}\right\}$. In general, the recipe is to multiply the top values together, multiply the bottom values together, and multiply both by $2^k – 1$, where $k$ is the number of curly brackets you’ve $\otimes$ed together. Here, $k=3$, which makes the multiplier 7:

$ \left\{ \begin{matrix} 1 \\ 1 \end{matrix}\right\}$ $\otimes$ $\left\{ \begin{matrix} 1 \\ 1 \end{matrix}\right\}$ $\otimes$ $\left\{ \begin{matrix} 1 \\ 1 \end{matrix}\right\} = \left\{ \begin{matrix} 7 \\ 7 \end{matrix}\right\}. $

Alternatively, we could combine two of them using one operation and then combine this intermediate value with the final number using the other operation. Note that we can’t combine two values with one operation and then use the same operation for the third, because that’s the same as combining all three values at once. We have to insist on alternating $\oplus$ and $\otimes$.

Enumerating the total number of results is hardly arduous at this stage, but it’s a good time to introduce a shortcut: if the last calculation is a $\oplus$, we’re effectively $\oplus$ing a single-valued number to any possible 2-calculation generated by a $\otimes$. We’ve worked out how many of those there are—it’s $\left\{ \begin{smallmatrix} 3 \\ 3 \end{smallmatrix}\right\}$. In a parallel way, if our final calculation is an $\otimes$, we need to $\otimes$ a single-valued number (remembering all inputs are single-valued) with a 2-calculation which came from an $\oplus$. We can work out:

$ \left\{ \begin{matrix} 3 \\ 3 \end{matrix}\right\}$ $\oplus$ $\left\{ \begin{matrix} 1 \\ 1 \end{matrix}\right\} = \left\{ \begin{matrix} 3 \\ 6 \end{matrix}\right\} \quad\text{and}\quad \left\{ \begin{matrix} 1 \\ 2 \end{matrix}\right\}$ $\otimes$ $\left\{ \begin{matrix} 1 \\ 1 \end{matrix}\right\} = \left\{ \begin{matrix} 3 \\ 6 \end{matrix}\right\}. $

These two answers happen to be the same, but that’s coincidence rather than anything deep.

In each case, there are three ways to pick which number comes last, so each of these $\left\{ \begin{smallmatrix} 3 \\ 6 \end{smallmatrix}\right\}$s gives a final value of $\left\{ \begin{smallmatrix} 9 \\ 18 \end{smallmatrix}\right\}$.

The 3-calculations with $\oplus$ as their last operation give a total of $4+18=22$ values, including $1+9=10$ single-valued ones. Those with $\otimes$ at the end give $7+9=16$ single-valued answers out of $7+18=25$. Altogether, that’s 47 answers, of which 26 are single-valued. That means 21 are double-valued, making a total of 68 different calculations you can do with exactly three numbers.

If we choose to just use two numbers, there are three distinct pairs we could combine, each in six possible ways (making a further 18). With one number, there are three distinct single values to pick (a further 3), and with no numbers, there is only one way, making 90 altogether.

$n$-calculations

…in which we generalise.

When dealing with large $n$, it’s a big timesaver to consider the possible structures of an $n$-calculation before working them out. Any calculation will consist of some number of chains of operations of the same type.

The key is to realise that the final calculation consists of some number of sets being operated on, and to ask how the inputs can be distributed between those sets. The ways of doing this correspond to the non-trivial partitions of $n$.

For example, with $n=4$, the non-trivial partitions are $[1,1,1,1]$, $[2,1,1]$, $[2,2]$, and $[3,1]$ (but not $[4]$). If the final calculation is $\oplus$, these correspond to:

A parallel thing happens when the last calculation is $\otimes$.

The recipe for enumerating the number of $n$-calculations is:

1. List all of the non-trivial partitions of $n$;
2. For each partition, $\oplus$ together all of the multiplicative calculation counts according to the numbers in the partition, and multiply by the number of ways the inputs could be arranged between the partitions;
3. Similarly, $\otimes$ together all of the additive calculation counts and multiply by the number of arrangements.
4. It is worth keeping track of the final sum of the additive and multiplicative counts, in case you want to work out the number of higher-$n$ calculations.
5. To find the total number of $n$-calculations, add the additive and multiplicative counts together, and determine the total of single- and double-valued results.

In the example of $n=4$:

Adding these up altogether gives, therefore, 296 single-valued and 437 double-valued numbers, making a total of 1170—which agrees with the Online Encyclopedia of Integer Sequences. However, this doesn’t take into account the possibility of using fewer numbers. We also have four ways to select three numbers (68 ways each), six ways to pick pairs (6 ways each), four ways to pick a single number (one way each) and one way to pick no numbers, for a total of 1483.

The sequence we’re uncovering here is not, so far as I can find, in the OEIS.

Going further

It’s possible—although a bit tedious and error-prone—to take this higher. I got the right answer for combining exactly six numbers (793,002) this way after a few missteps. Doing the same Pascal’s triangle steps as previously, this gives 974,861 ways to combine up to six numbers.

Grasshoppers: hardly crickets

OEIS points to a Chinese-language article by Zhujun Zhang that discusses finding the generating functions for inequivalent expressions under different circumstances (are you allowed division and subtraction? are you allowed a unary negative? are $-3$ and $3$ different?). The answer seems to be ‘it’s complicated’—Zhang introduces four coupled generating functions and solves them numerically, which is hardly cricket.

It turns out our approximation of $(n-1)! 6^{n-1}$ is pretty good for combining exactly $ n $ numbers—at least for the cases in OEIS, it’s typically within about 30% correct answer.

Back to the studio

In any given Countdown numbers game, it is usually possible to reach only a small fraction of the full range of 6-calculations. For example, the analysis above would count the (arithmetic) calculation $2 \times 6$ as a different calculation to $3 \times 4$, even though the numerical answer is the same. Similarly, we’ve counted $1 \times 25$ as an entirely different thing to $25$—and don’t get me started on the rule that forbids fractions.

So how many possible Countdown numbers games are there using the actual rules? I’ll leave that as a conundrum for the interested reader.

Colin Beveridge

Colin is the author of Cracking Mathematics and The Maths Behind, written to prove that he has nothing to prove (by contradiction).

@icecolbeveridge   colinbeveridge.co.uk    All articles by Colin