Let’s play a game:

1. Imagine you have some playing cards. Of course if you actually have some cards you don’t need to imagine!
2. Pick your favourite natural number $n$ and put a deck of $n$ cards in front of you. Then repeat the next step until the deck is empty.
3. Take $2$ cards from the top of the deck and throw them away, or just take $1$ card from the top and throw it away. The choice is yours.

If you pick a small $n$, such as $n=3$, it’s pretty easy to see how this game is going to play out. Choosing to throw away $2$ cards the first time means you’re then forced to throw away $1$ card the next time, but only throwing away $1$ card the first time leaves you with a choice of what to throw away the next time. So for $n=3$ there are exactly $3$ different ways to play the game: throw $2$ then $1$, throw $1$ then $2$, or throw $1$ then $1$ then $1$.

Now, here comes the big question. How does the number of different ways to play this game depend on the size of the starting deck? Or in other words, what integer sequence $a_0$, $a_1$, $a_2$, $a_3$, $a_4$, … do we get if $a_n$ represents the number of different ways to play the game with a deck of $n$ cards? (We already know that $a_3=3$.)

For $n=0$ you never get to step 3 because the deck of cards is already empty, so the game unceremoniously ends immediately after it begins. But you can still successfully “play” the game—it’s not as if the rules require you to do anything impossible—and there is exactly $1$ thing that will happen (i.e., nothing will happen). Therefore $a_0=1$.

For $n=1$ you’re forced to throw away the only card ($a_1=1$) and for $n=2$ you can either throw away the $2$ cards together or separately ($a_2=2$), so the sequence we’re looking for starts\[1,1,2,3,\dotsc.\]Fans of integer sequences will instantly recognise these numbers as being the first few Fibonacci numbers, and the reason why the Fibonacci numbers crop up here is the same as why they are the solution to any one of a seemingly endless supply of similar puzzles.

A notation for dealing cards

The realisation that the rules of this game encode the Fibonacci numbers prompted me to devise a notation to express these rules so that I could find other integer sequences by tweaking the rules in various ways. I decided to call a card game of this type a ‘deal’ because you’re taking cards from the top of a deck and putting them somewhere else, and I knew (from having studied regular expressions in formal language theory) roughly what actions should be allowed in a deal:

• The simplest action should be taking a fixed number of cards from the top of the deck. In my notation a number by itself means just this. For example, 1 means “take the top card” and 2 means “take the top $2$ cards”.
• It needs to be possible to choose between two actions because in step 3 of the Fibonacci deal you may either take $1$ card or $2$ cards. The word ‘or’ seemed appropriate for this purpose, so I would write step 3 as 1 or 2.
• It also needs to be possible to repeat an action indefinitely, as in step 2 of the Fibonacci deal. Putting ( and )^? around an action means “repeat this action an unspecified number of times”, and thus the full Fibonacci deal becomes (1 or 2)^?.
• Finally, although the Fibonacci deal happens not to require this, we might conceivably want to chain actions together. For instance, we might be interested in the deal “take the top card then do the Fibonacci deal”, which I would simply write as 1 (1 or 2)^?. (Side question: how many different ways are there to carry out this deal if the deck starts with $n=0$ cards?)

Once I had settled on this notation, I realised that I needed a way to automatically generate the integer sequence associated with a deal, as it was really becoming a pain to go through all the possibilities by hand. So I wrote a web app called Clear the Deck that (for each $n\geq0$) counts the number of different ways there are to carry out a given deal if the deck starts with $n$ cards, and then outputs the resulting integer sequence for inspection. It also tries to locate the sequence in the On-Line Encyclopedia of Integer Sequences.

Clear the Deck uses a very sneaky trick to generate sequences quickly: all we want is the number of ways to carry out a deal, not an actual list of all the different possibilities. I won’t go into too much detail, but the basic idea is that computing a sequence term $a_n$ from the preceding terms $a_0$, $a_1$, …, $a_{n-1}$ can be done in a constant time that does not depend on the values of the preceding terms, whereas the time it would take to compute the full list of $a_n$ different possibilities would be linked with the sizes of the preceding terms.

To see how this kind of thing is possible, try taking successive powers of the matrix $M=\left(\begin{smallmatrix}1&1\\1&0\end{smallmatrix}\right)$, starting with $M^0=\left(\begin{smallmatrix}1&0\\0&1\end{smallmatrix}\right)$. You should get\[\begin{pmatrix}
\boxed{1}&0\\0&1
\end{pmatrix},\quad
\begin{pmatrix}
\boxed{1}&1\\1&0
\end{pmatrix},\quad
\begin{pmatrix}
\boxed{2}&1\\1&1
\end{pmatrix},\quad
\begin{pmatrix}
\boxed{3}&2\\2&1
\end{pmatrix},\quad\dotsc,\]where if you kept going the boxed number would always be the next Fibonacci number! The fact that you’re multiplying by a fixed matrix at each stage means that no Fibonacci number is any harder to compute than the previous one was, and this is essentially how Clear the Deck works—except that the matrix corresponding to a particular deal might be much more complicated.

Some other examples

There are a couple more bits of notation that I didn’t tell you about yet. The first is a piece of syntactic sugar that makes it possible to instantly understand the meaning of some deals. To illustrate, let’s think about what the deal (1)^? 1 (1)^? means. Recall that 1 by itself means “take the top card”, and that ^? is used to repeat an action, so (1)^? means “take an unspecified number of cards from the top”. In other words, (1)^? simply specifies that a bunch of cards should be thrown away. It occurred to me that writing some dots ... (it doesn’t really matter how many) captures this “just get rid of some cards” idea quite well, and so I think it’s much more intuitive to write (1)^? 1 (1)^? as ...1..., which now pretty obviously means “choose $1$ distinguished card from the deck”.

How many different ways are there to carry out the deal ...1...? Well, if the deck starts with $n$ cards then any one of the $n$ cards could be chosen as the distinguished card, and thus there are exactly $n$ different ways to carry out this deal. That is, the integer sequence associated with ...1... is $0$, $1$, $2$, $3$, … (A001477).

Now things are really starting to get moving. If ...1... means “choose $1$ distinguished card” then presumably ...1...1... means “choose $2$ distinguished cards”, ((...2... means “choose a distinguished pair of cards”.)) and if we ask Clear the Deck that’s precisely what we find: the $n$th term in the sequence associated with ...1...1... is the binomial coefficient $n\choose2$. By adding another 1... at the end of this deal we get the sequence of binomial coefficients $n\choose3$, and by adding yet another one we get the sequence $n\choose4$. So, in general, by starting with ... and then repeating 1... $k$ times we get the sequence $n\choose k$ for any fixed $k\geq0$ we like. But we’ve already seen how to repeat an action; surely we just have to do ...(1...)^k if we want the sequence $n\choose k$. Yep.

By now some of you have probably already tried the deal ...(1...)^? and have noticed that you get the sequence $2^n$ (A000079). Can you explain why? A simpler way to get the powers of $2$ is to “cheat” by just declaring that each time you take a card from the top of the deck there are actually two different ways to do it. (This isn’t so silly; you probably do have two different hands.) The deal (2 * 1)^? means precisely this, and the number of different ways to carry it out is $2^n$ because there are $2^n$ binary numbers with $n$ digits.

As a final example, suppose you want to come up with a deal for your favourite integer sequence. It’s not always going to be possible, but the sequence’s OEIS page is a good place to start. Specifically, you want to search for a ‘G.f.’ (meaning generating function) formula, which will look something like\[\frac{x(1+x)}{(1-x)^3}.\]This is the one listed for the square numbers. You can turn such a generating function into a deal by changing $1/(1-x)^k$ into (...)^k, $+$ into or, and $x^k$ into k. Applying these transformations to the generating function for the square numbers gives the deal 1 (0 or 1) (...)^3, which works fine, but in this case there is actually a less cryptic (arguably) deal which comes from the fact that $n^2=2{n\choose2}+n$. Can you find it? Good luck!

Play Clear the Deck at Dave’s website.