Blog

Tilings with Tetris pieces, and squared Fibonacci numbers

Saw this great observation by Ruud de Rooij (via Robin Houston):

Combinatorics can be a bit weird sometimes: the number of ways to arrange N Tetris pieces into a 2-by-2N rectangle is the Nth Fibonacci number squared.

First to understand the statement: the picture shows tilings of $2 \times 2N$ rectangles by tetris pieces for $N = 1, 2, 3, 4, 5$, and the number of such tilings (shown) happens to be $1, 2^2, 3^2, 5^2, 8^2$ respectively.

What are tetris pieces and how many of them are there? I vaguely remembered seeing polyominoes in Knuth’s TAOCP Volume 4B so I looked it up, and it mentions that there are five tetrominoes:

According to the Tetromino article on Wikipedia, turns out these five are called the free tetrominoes, i.e. five is the number of distinct tetrominoes with rotation and reflection allowed:

With only rotation (not reflection) allowed (as in Tetris), there are seven one-sided tetrominoes, and they have standard names apparently:

If you look at the original diagram of tilings above, it uses only the I, O, J, L tetrominoes, and not T, S, Z. (It is not hard to see why the T, S, Z shapes cannot be used: just try to imagine what could fit next to them.)

If we do not allow even rotation, there are 19 fixed tetrominoes, and only some (six) of them appear in the diagram above:

In short, we have these six tiles: (which the file names on Wikipedia respectively call “J-left”, “L-left”, “J-right”, “L-right”, and the last two we’ll call “bar” and “square”)

So to return to the beginning, what we’re talking about is the number of tilings of a $2 \times 2N$ rectangle using these six fixed shapes. (Each such tiling will use exactly $N$ tetrominoes, as the $2 \times 2N$ rectangle has area $4N$ and each tetromino has area $4$.)

How would we prove this?

BTW, the squared Fibonacci numbers are OEIS A007598, where it says:

a(n+1) is the number of tilings of a 2 X 2n rectangle with n tetrominoes of any shape, cf. A230031. - Alois P. Heinz, Nov 29 2013

Mechanical proof

There’s a standard way of enumeration in such tiling problems, and that is to write down recurrence relations.

Let $A(n)$ be the number of tilings using $n$ of these shapes such that they occupy two equal rows of $2n$ columns each, and let $B(n)$ be the number of tilings using $n$ of these shapes such that they occupy two rows with $2n+1$ and $2n-1$ columns respectively, i.e. an overhang of $2$. (By symmetry, $B(n)$ is also the number with the rows having $2n-1$ and $2n+1$ respectively, i.e. an overhang of $-2$.) Then we can write down
$$ \def\F{\Large\blacksquare} \def\W{\Large\square} \def\D{\cdots} \substack{\D\W\W\W\W\W \cr \D\W\W\W\W\W} \ = \substack{\D\W\W\W\W\F \cr \D\W\W\F\F\F} + \substack{\D\W\W\F\F\F \cr \D\W\W\W\W\F} + \substack{\D\W\F\F\F\F \cr \D\W\F\F\F\F} + \substack{\D\W\W\W\F\F \cr \D\W\W\W\F\F} $$ $$A(n) = B(n-1) + B(n-1) + A(n-2) + A(n-1)$$

(depending on whether it ends with an L-left, J-left, two bars one below the other, or a single square respectively)

and similarly $$ \def\q{\phantom{\W}} \substack{\D\W\W\W\W\W \cr \D\W\W\W\q\q} = \substack{\D\W\W\F\F\F \cr \D\W\W\F\q\q} + \substack{\D\W\F\F\F\F \cr \D\W\W\W\q\q} $$

$$B(n) = A(n-1) + B(n-1)$$ (depending on whether it ends with an L-right, or a bar on the top row), along with the initial conditions $B(0) = 0$ and $A(0) = 1$ (and $A(-1) = 0$).

Now we can solve these recurrences, and it turns out that $B(n) = F_{n}F_{n+1}$ and $A(n) = F_{n+1}^2$ where $F_0, F_1, F_2, F_3, F_4, F_5, F_6\ldots = 0, 1, 1, 2, 3, 5, 8\ldots$ is the sequence of Fibonacci numbers. There are standard ways of deriving this (e.g. use the second recurrence relation to write $A(n) = B(n + 1) - B(n)$, and plug that into the first and simplify to get $B(n+1) = 2B(n) + 2B(n-1) - B(n-2)$, then we end up using the roots of the characteristic equation $x^3 = 2x^2 + 2x - 1$ etc), but it’s easiest to work it out for a few small numbers, to guess-and-verify that with $A(n) = F_{n+1}^2$ and $B(n) = F_nF_{n+1}$, our (initial conditions and) recurrence relations are satisfied: $$F_{n+1}^2 = 2F_{n-1}F_n + F_{n-1}^2 + F_n^2$$ and $$F_nF_{n+1} = F_n^2 + F_{n-1}F_n.$$

Elegant proof

The proof above is fine, but the squared Fibonacci numbers just happen to show up magically in the solution to the recurrence relations. We’d like a nicer/combinatorial proof, and one was provided (I’ll explain it in more detail below) by the original author Ruud de Rooij, with a small notational improvement by Andreas Nuyts:

ruud de rooij@ruuddotorg@hachyderm.io

Something along these lines:

Arranging A and BB into words of N symbols is one of the classic Fibonacci number examples. (E.g. 4 symbol words can be done in 5 ways: AAAA, AABB, ABBA, BBAA, BBBB).

There’s a bijection between the 2x2N tetris rectangles and pairs of such words.
Pairwise symbols map to tetris pieces (from left to right) as follows:

A, A <-> O
A, B <-> L
B, A <-> J
B, B <-> I

and

Andreas Nuyts@anuytstt@fosstodon.org

I think it’s more easy to confirm this reasoning by considering words consisting of A and BC. Then the distinction between B and C can be used to also mention how to position the piece. The 2x2 modes (was the previous symbol above/below a B or not?) correspond to right edge shapes that your new piece needs to fit with.

To explain these in more detail, let’s first consider the problem of words: how many ways are there to form a word of length $n$ by putting together the strings $\newcommand\A{\Large\mathtt{A}}\newcommand{\B}{\Large\mathtt{B}}\newcommand{\C}{\Large\mathtt{C}}\newcommand{\BC}{\Large\mathtt{BC}}\newcommand{\b}{\Large\mathtt{b}}\A$ and $\BC$? For example, here are the words for length $n \le 4$:

$$ \begin{align} \A \cr \cr \A\A \cr \BC \cr \cr \A\A\A \cr \BC\A \cr \A\BC \cr \cr \A\A\A\A \cr \BC\A\A \cr \A\BC\A \cr \A\A\BC \cr \BC\BC \cr \end{align} $$

In general, we can form a word of length $n$ either by appending an $\A$ to a word of length $n-1$, or a $\BC$ to a word of length $n-2$. So if $W(n)$ is the number of words of length $n$, then $W(n) = W(n-1) + W(n-2)$, which along with $W(1) = 1$ and $W(2) = 2$ (or if you think about it, $W(0) = 1$), gives $W(n) = F_{n+1}$. (As an aside, something like this—counting the number of ways to get to length $n$ using syllables of length $1$ and $2$—is in fact the earliest occurrence of Fibonacci numbers, originally in the context of Sanskrit poetry, or rather theorists writing about metrics/prosody: I still plan to write a post about it some other time.)

The left-hand side of our bijection is pairs of such words of length $n$. Clearly, the number of such pairs is $W(n)^2 = F_{n+1}^2$.

Let’s also look at these pairs of words more closely, and what constraints exist as we move left to right.

For a single word, if we think of building it up by moving left to right and appending letters one by one, we have two cases:

For pairs of words, we’ll write each pair of words one below the other, e.g. for length $n=3$ where there are three words $\{\A\A\A, \BC\A, \A\BC\}$, the $9$ pairs are:

$$\Large \substack{\A\A\A \cr \A\A\A} \quad \substack{\A\A\A \cr \BC\A} \quad \substack{\A\A\A \cr \A\BC} \quad \substack{\BC\A \cr \A\A\A} \quad \substack{\BC\A \cr \BC\A} \quad \substack{\BC\A \cr \A\BC} \quad \substack{\A\BC \cr \A\A\A} \quad \substack{\A\BC \cr \BC\A} \quad \substack{\A\BC \cr \A\BC} $$ In a pair of words like this, if we imagine moving left-to-right and laying down pairs of letters (one below the other), then we can enumerate cases:

Now we turn to the tetromino tilings. We’ll imagine laying down these tetrominoes one-by-one, left to right (and in the case of bars one below the other, the top bar before the bottom bar). Then, we have cases depending on how much “overhang” currently exists:

Spelled out in full, these are:

$$ \begin{array}{rlcccc} \substack{\D\W \cr \D\W} & \to & \substack{\D\W\F\F \cr \D\W\F\F} & \substack{\D\W\F\q\q \cr \D\W\F\F\F} & \substack{\D\W\F\F\F \cr \D\W\F\q\q} & \substack{\D\W\F\F\F\F \cr \D\W\q\q\q\q} \cr \cr % \substack{\D\W\q\q \cr \D\W\W\W} & \to & \substack{\D\W\F\F\F \cr \D\W\W\W\F} & \times & \substack{\D\W\F\F\F\F \cr \D\W\W\W\q\q} & \times \cr \cr % \substack{\D\W\W\W \cr \D\W\q\q} & \to & \substack{\D\W\W\W\F \cr \D\W\F\F\F} & \substack{\D\W\W\W\q\q \cr \D\W\F\F\F\F} & \times & \times \cr \cr % \substack{\D\W\W\W\W\W \cr \D\W\q\q\q\q} & \to & \substack{\D\W\W\W\W\W \cr \D\W\F\F\F\F} & \times & \times & \times \end{array} $$

corresponding to (showing only the new pair of letters appended, and where $\cancel{\B}$ means “not ending in $\B$”):

$$ \begin{array}{rlcccc} \substack{\cancel{\B} \cr \cancel{\B}} & \to & \substack{\A \cr \A} & \substack{\B \cr \A} & \substack{\A \cr \B} & \substack{\B \cr \B} \cr \cr \substack{\B \cr \cancel{\B}} & \to & \substack{\C \cr \A} & \times & \substack{\C \cr \B} & \times & \cr \cr \substack{\cancel\B \cr \B} & \to & \substack{\A \cr \C} & \substack{\B \cr \C} & \times & \times & \cr \cr \substack{\B \cr \B} & \to & \substack{\C \cr \C} & \times & \times & \times & \end{array} $$

So this is the bijection between pairs of letters and tetromino placement, to spell it out explicitly:

Overall, this gives the bijection we sought, between pairs of words of length $n$ made of $\A$ and $\BC$, and tetromino tilings of a $2 \times 2n$ rectangle using $n$ tetrominoes.

Here’s a diagram (excuse the handwriting) showing the nine pairs of words for $n=3$, along with the nine tilings using $3$ tetrominoes.

Sjoerd Visscher observed that this bijection makes it easy to generate diagrams of these tilings in the original style, using some clever CSS: Codepen. It was very instructive, and I even enjoyed making a minor change, changing the function that returns such words:

function seqs(n) {
  if (n == 1) { return ["a"] }
  if (n == 2) { return ["aa", "bc"] }
  return seqs(n - 1).map(function(s) { return "a" + s }).concat(seqs(n - 2).map(function(s) { return "bc" + s }));
}

into (changing only the base cases):

function seqs(n) {
  if (n < 0) { return [] }
  if (n == 0) { return [""] }
  return seqs(n - 1).map(function(s) { return "a" + s }).concat(seqs(n - 2).map(function(s) { return "bc" + s }));
}

:-)

[Added later 2026-03-12]: After thinking about it a bit more, I think the following may be a good way to see what’s going on here.

The process we described above, of making a single word by successively setting down either $\A$ or $\BC$, can be thought of traversing a state machine (deterministic finite-state automaton):

$$\def\a{\Large \rlap{\sqsubset}\rlap{\sqsupset}\kern{0.75em}} \def\b{\Large \rlap{\sqsubset}\kern{0.75em}} \def\c{\Large \rlap{\sqsupset}\kern{0.75em}}$$ We start at the green node. From the green node we can either take the self-loop ($\A$), or move to the red node with $\B$, after which we can only return to the first node by taking $\C$. For these, as we saw, $W(n) = F_{n+1}$ is the number of ways of returning to the green node after taking $n$ steps.

The following doesn’t make a difference, but if you are more visually inclined, you could think of tilings of a $1 \times N$ rectangle using $1 \times 1$ “single” (square) tiles and $1 \times 2$ “domino” tiles. This is the same thing, as becomes clear if we think of the alphabet not as $\{\A, \B, \C\}$ but instead as $\{\a, \b, \c\}$ so that for example the word $\A\A\B\C\B\C\A\B\C$ corresponds to the word $\Large \a\a\b\c\b\c\a\b\c$ (two singles, two dominoes, a single and another domino). So we could also write the automaton as:

(In this notation, $\A$ and $\B\C$ (or $\Large \a$ and $\Large \b \, \c\,$ equivalently), are simply the different (minimal) ways of starting at the green node and returning to the green node.)

Now, if we consider pairs of such words (or pairs of such tilings), writing one below the other, we get an automaton that is I believe called the product of the two automata:

After placing a pair of letters (one at the top and one at the bottom), we end up in state as indicated above: the red and green indicate whether the corresponding word (the top word and the bottom word) are “pending” a return to green (have had a $\B$, to be followed by a $\C$).

Here’s the same state machine using the $\Large \{\a\,, \b\,, \c\,\}$ alphabet:

Because this is the product automaton and corresponds to pairs of words, the number of ways of returning to the green node after $n$ steps is $W(n)^2 = F_{n+1}^2$.

But now if we think about placing our Tetris shapes and draw an automaton to indicate what happens to the right edge (how much overhang), then we get:

(This time, the numbers inside the states denote how much more overhang the top row has than the bottom row. The edge transitions denote what piece is placed next.)

This is basically the same automaton! This fact proves the correspondence, that the number of ways to return to the green node after placing $n$ tetrominoes is the same $W(n)^2 = F_{n+1}^2$.

(We can kind of see why we happen to get the same automaton: just as a $\b$ (on either the top or bottom row) is a “pending” state that must be completed with a $\c$ in the same row, an overhang of $2$ or $-2$ is a “pending” state that must be completed with either its corresponding J/L, or the bar. The overhang $4$ state looks different from $\substack{\b \cr \b}$, but like it it must be “immediately” completed, so the effect is the same.)

Recall what we said above, that $\A$ and $\B\C$ (or $\Large \a\,$ and $\Large \b \, \c\,$ equivalently), were the different minimal ways of returning to the green node, and thus we were counting words made of these minimal pieces. What are similar minimal sequences in the four-state graph, for pairs of words (or pairs of tilings)? Well we can start at the green-green node and either:

So there are six kinds of minimal sequences (one of length $1$, one of length $2$, and four of arbitrary length).

To any such minimal sequence in the “pairs of tilings” automaton, the “tetrominoes” automaton has a corresponding minimal sequence, and this was directly noted by @jcreed on Mathstodon (without explicitly constructing the state automaton as far as I know!), who showed the same bijection with this picture:

He also has Javascript code to show this bijection.