The Universe of Disco

How many 24 puzzles are there?

[ Note: The tables in this article are important, and look unusually crappy if you read this blog through an aggregator. The properly-formatted version on my blog may be easier to follow. ]

A few months ago I wrote about puzzles of the following type: take four digits, say 1, 2, 7, 7, and, using only +, -, ×, and ÷, combine them to make the number 24. Since then I have been accumulating more and more material about these puzzles, which will eventually appear here. But meantime here is a delightful tangent.

In the course of investigating this I wrote programs to enumerate the solutions of all possible puzzles, and these programs were always much faster than I expected at first. It appears as if there are 10,000 possible puzzles, from «0,0,0,0» through «9,9,9,9». But a moment's thought shows that there are considerably fewer, because, for example, the puzzles «7,2,7,1», «1,2,7,7», «7,7,2,1», and «2,7,7,1» are all the same puzzle. How many puzzles are there really?

A back-of-the-envelope estimate is that only about 1 in 24 puzzles is really distinct (because there are typically 24 ways to rearrange the elements of a puzzle) and so there ought to be around !!\frac{10000}{24} \approx 417!! puzzles. This is an undercount, because there are fewer duplicates of many puzzles; for example there are not 24 variations of «1,2,7,7», but only 12. The actual number of puzzles turns out to be 715, which I think is not an obvious thing to guess.

Let's write !!S(d,n)!! for the set of sequences of length !!n!! containing up to !!d!! different symbols, with the duplicates removed: when two sequences are the same except for the order of their symbols, we will consider them the same sequence.

Or more concretely, we may imagine that the symbols are sorted into nondecreasing order, so that !!S(d,n)!! is the set of nondecreasing sequences of length !!n!! of !!d!! different symbols.

Let's also write !!C(d,n)!! for the number of elements of !!S(d,n)!!.

Then !!S(10, 4)!! is the set of puzzles where input is four digits. The claim that there are !!715!! such puzzles is just that !!C(10,4) = 715!!. A tabulation of !!C(\cdot,\cdot)!! reveals that it is closely related to binomial coefficients, and indeed that $$C(d,n)=\binom{n+d-1}{d-1}.\tag{$\heartsuit$}$$

so that the surprising !!715!! is actually !!\binom{13}{9}!!. This is not hard to prove by induction, because !!C(\cdot,\cdot)!! is easily shown to obey the same recurrence as !!\binom\cdot\cdot!!: $$C(d,n) = C(d-1,n) + C(d,n-1).\tag{$\spadesuit$}$$

To see this, observe that an element of !!C(d,n)!! either begins with a zero or with some other symbol. If it begins with a zero, there are !!C(d,n-1)!! ways to choose the remaining !!n-1!! symbols in the sequence. But if it begins with one of the other !!d-1!! symbols it cannot contain any zeroes, and what we really have is a length-!!n!! sequence of the symbols !!1\ldots (d-1)!!, of which there are !!C(d-1, n)!!.

Now we can observe that !!\binom74=\binom73!! (they are both 35) so that !!C(5,3) = C(4,4)!!. We might ask if there is a combinatorial proof of this fact, consisting of a natural bijection between !!S(5,3)!! and !!S(4,4)!!. Using the relation !!(\spadesuit)!! we have:

$$ \begin{eqnarray} C(4,4) & = & C(3, 4) + & C(4,3) \\ C(5,3) & = & & C(4,3) + C(5,2) \\ \end{eqnarray}$$

so part of the bijection, at least, is clear: There are !!C(4,3)!! elements of !!S(4,4)!! that begin with a zero, and also !!C(4,3)!! elements of !!S(5, 3)!! that do not begin with a zero, so whatever the bijection is, it ought to match up these two subsets of size 20. This is perfectly straightforward; simply match up !!«0, a, b, c»!! (blue) with !!«a+1, b+1, c+1»!! (pink), as shown at right.

But finding the other half of the bijection, between !!S(3,4)!! and !!S(5,2)!!, is not so straightforward. (Both have 15 elements, but we are looking for not just any bijection but for one that respects the structure of the elements.) We could apply the recurrence again, to obtain:

$$ \begin{eqnarray} C(3,4) & = \color{darkred}{C(2, 4)} + \color{darkblue}{C(3,3)} \\ C(5,2) & = \color{darkblue}{C(4,2)} + \color{darkred}{C(5,1)} \end{eqnarray}$$

and since $$ \begin{eqnarray} \color{darkred}{C(2, 4)} & = \color{darkred}{C(5,1)} \\ \color{darkblue}{C(3,3)} & = \color{darkblue}{C(4,2)} \end{eqnarray}$$

we might expect the bijection to continue in that way, mapping !!\color{darkred}{S(2,4) \leftrightarrow S(5,1)}!! and !!\color{darkblue}{S(3,3) \leftrightarrow S(4,2)}!!. Indeed there is such a bijection, and it is very nice.

To find the bijection we will take a detour through bitstrings. There is a natural bijection between !!S(d, n)!! and the bit strings that contain !!d-1!! zeroes and !!n!! ones. Rather than explain it with pseudocode, I will give some examples, which I think will make the point clear. Consider the sequence !!«1, 1, 3, 4»!!. Suppose you are trying to communicate this sequence to a computer. It will ask you the following questions, and you should give the corresponding answers:

• “Is the first symbol 0?” (“No”)
• “Is the first symbol 1?” (“Yes”)
• “Is the second symbol 1?” (“Yes”)
• “Is the third symbol 1?” (“No”)
• “Is the third symbol 2?” (“No”)
• “Is the third symbol 3?” (“Yes”)
• “Is the fourth symbol 3?” (“No”)
• “Is the fourth symbol 4?” (“Yes”)

At each stage the computer asks about the identity of the next symbol. If the answer is “yes” the computer has learned another symbol and moves on to the next element of the sequence. If it is “no” the computer tries guessing a different symbol. The “yes” answers become ones and “no” answers become zeroes, so that the resulting bit string is 0 1 1 0 0 1 0 1.

It sometimes happens that the computer figures out all the elements of the sequence before using up its !!n+d-1!! questions; in this case we pad out the bit string with zeroes, or we can imagine that the computer asks some pointless questions to which the answer is “no”. For example, suppose the sequence is !!«0, 1, 1, 1»!!:

• “Is the first symbol 0?” (“Yes”)
• “Is the second symbol 0?” (“No”)
• “Is the second symbol 1?” (“Yes”)
• “Is the third symbol 1?” (“Yes”)
• “Is the fourth symbol 1?” (“Yes”)

The bit string is 1 0 1 1 1 0 0 0, where the final three 0 bits are the padding.

We can reverse the process, simply taking over the role of the computer. To find the sequence that corresponds to the bit string 0 1 1 0 1 0 0 1, we ask the questions ourselves and use the bits as the answers:

• “Is the first symbol 0?” (“No”)
• “Is the first symbol 1?” (“Yes”)
• “Is the second symbol 1?” (“Yes”)
• “Is the third symbol 1?” (“No”)
• “Is the third symbol 2?” (“Yes”)
• “Is the fourth symbol 2?” (“No”)
• “Is the fourth symbol 3?” (“No”)
• “Is the fourth symbol 4?” (“Yes”)

We have recovered the sequence !!«1, 1, 2, 4»!! from the bit string 0 1 1 0 1 0 0 1.

This correspondence establishes relation !!(\heartsuit)!! in a different way from before: since there is a natural bijection between !!S(d, n)!! and the bit strings with !!d-1!! zeroes and !!n!! ones, there are certainly !!\binom{n+d-1}{d-1}!! of them as !!(\heartsuit)!! says because there are !!n+d-1!! bits and we may choose any !!d-1!! to be the zeroes.

We wanted to see why !!C(5,3) = C(4,4)!!. The detour above shows that there is a simple bijection between

!!S(5,3)!! and the bit strings with 4 zeroes and 3 ones

on one hand, and between

!!S(4,4)!! and the bit strings with 3 zeroes and 4 ones

on the other hand. And of course the bijection between the two sets of bit strings is completely obvious: just exchange the zeroes and the ones.

The table below shows the complete bijection between !!S(4,4)!! and its descriptive bit strings (on the left in blue) and between !!S(5, 3)!! and its descriptive bit strings (on the right in pink) and that the two sets of bit strings are complementary. Furthermore the top portion of the table shows that the !!S(4,3)!! subsets of the two families correspond, as they should—although the correct correspondence is the reverse of the one that was displayed earlier in the article, not the suggested !!«0, a, b, c» \leftrightarrow «a+1, b+1, c+1»!! at all. Instead, in the correct table, the initial digit of the !!S(4,4)!! entry says how many zeroes appear in the !!S(5,3)!! entry, and vice versa; then the increment to the next digit says how many ones, and so forth.

!!S(4,4)!!	(bits)	(complement bits)	!!S(5,3)!!
0 0 0 0	1 1 1 1 0 0 0	0 0 0 0 1 1 1	4 4 4
0 0 0 1	1 1 1 0 1 0 0	0 0 0 1 0 1 1	3 4 4
0 0 0 2	1 1 1 0 0 1 0	0 0 0 1 1 0 1	3 3 4
0 0 0 3	1 1 1 0 0 0 1	0 0 0 1 1 1 0	3 3 3
0 0 1 1	1 1 0 1 1 0 0	0 0 1 0 0 1 1	2 4 4
0 0 1 2	1 1 0 1 0 1 0	0 0 1 0 1 0 1	2 3 4
0 0 1 3	1 1 0 1 0 0 1	0 0 1 0 1 1 0	2 3 3
0 0 2 2	1 1 0 0 1 1 0	0 0 1 1 0 0 1	2 2 4
0 0 2 3	1 1 0 0 1 0 1	0 0 1 1 0 1 0	2 2 3
0 0 3 3	1 1 0 0 0 1 1	0 0 1 1 1 0 0	2 2 2
0 1 1 1	1 0 1 1 1 0 0	0 1 0 0 0 1 1	1 4 4
0 1 1 2	1 0 1 1 0 1 0	0 1 0 0 1 0 1	1 3 4
0 1 1 3	1 0 1 1 0 0 1	0 1 0 0 1 1 0	1 3 3
0 1 2 2	1 0 1 0 1 1 0	0 1 0 1 0 0 1	1 2 4
0 1 2 3	1 0 1 0 1 0 1	0 1 0 1 0 1 0	1 2 3
0 1 3 3	1 0 1 0 0 1 1	0 1 0 1 1 0 0	1 2 2
0 2 2 2	1 0 0 1 1 1 0	0 1 1 0 0 0 1	1 1 4
0 2 2 3	1 0 0 1 1 0 1	0 1 1 0 0 1 0	1 1 3
0 2 3 3	1 0 0 1 0 1 1	0 1 1 0 1 0 0	1 1 2
0 3 3 3	1 0 0 0 1 1 1	0 1 1 1 0 0 0	1 1 1
1 1 1 1	0 1 1 1 1 0 0	1 0 0 0 0 1 1	0 4 4
1 1 1 2	0 1 1 1 0 1 0	1 0 0 0 1 0 1	0 3 4
1 1 1 3	0 1 1 1 0 0 1	1 0 0 0 1 1 0	0 3 3
1 1 2 2	0 1 1 0 1 1 0	1 0 0 1 0 0 1	0 2 4
1 1 2 3	0 1 1 0 1 0 1	1 0 0 1 0 1 0	0 2 3
1 1 3 3	0 1 1 0 0 1 1	1 0 0 1 1 0 0	0 2 2
1 2 2 2	0 1 0 1 1 1 0	1 0 1 0 0 0 1	0 1 4
1 2 2 3	0 1 0 1 1 0 1	1 0 1 0 0 1 0	0 1 3
1 2 3 3	0 1 0 1 0 1 1	1 0 1 0 1 0 0	0 1 2
1 3 3 3	0 1 0 0 1 1 1	1 0 1 1 0 0 0	0 1 1
2 2 2 2	0 0 1 1 1 1 0	1 1 0 0 0 0 1	0 0 4
2 2 2 3	0 0 1 1 1 0 1	1 1 0 0 0 1 0	0 0 3
2 2 3 3	0 0 1 1 0 1 1	1 1 0 0 1 0 0	0 0 2
2 3 3 3	0 0 1 0 1 1 1	1 1 0 1 0 0 0	0 0 1
3 3 3 3	0 0 0 1 1 1 1	1 1 1 0 0 0 0	0 0 0

Observe that since !!C(d,n) = \binom{n+d-1}{d-1} = \binom{n+d-1}{n} = C(n+1, d-1)!! we have in general that !!C(d,n) = C(n+1, d-1)!!, which may be surprising. One might have guessed that since !!C(5,3) = C(4,4)!!, the relation was !!C(d,n) = C(d+1, n-1)!! and that !!S(d,n)!! would have the same structure as !!S(d+1, n-1)!!, but it isn't so. The two arguments exchange roles. Following the same path, we can identify many similar ‘coincidences’. For example, there is a simple bijection between the original set of 715 puzzles, which was !!S(10,4)!!, and !!S(5,9)!!, the set of nondecreasing sequences of !!0\ldots 4!! of length !!9!!.

[ Thanks to Bence Kodaj for a correction. ]

[ Addendum 20170829: Conway and Guy, in The Book of Numbers, describe the same bijection, but a little differently; see their discussion of the Sweet Seventeen deck on pages 70–71. ]

[ Addendum 20171015: More about this, using Burnside's lemma. ]

[Other articles in category /math] permanent link