# Combinatorial interpretation of CFs

This method of Benjamin and Quinn uses a model of tiling a row of squares with stackable tiles and (non-stackable) dominoes. For example, in the diagram below, the first square may be tiled with 1-3 square tiles, or a domino may be placed on the first 2 squares. The second square may be tiled with 1-7 squares, or by using a domino on squares 0 & 1 or 1 & 2.
++++So, just tiling the first two squares, without dominoes there are ways of stacking squares; using a domino, there’s one way. There are 7 ways of tiling the second square alone – by using 1-7 tiles.
So we have: ++++ .

Let’s take the first 4 squares (0-3) of this diagram, which represent the continued fraction:
++++++++++++++
To tile these 4 squares, we could use:
++++• no dominoes. Then there are 3 ways of tiling the first square: with 1, 2 or 3 square tiles. So there will be ways of tiling without using dominoes.
++++• 2 dominoes. There’s only 1 way to do this.
++++• 1 domino. It could be placed on the first square, the 2nd or the 3rd.
++++++++a. If on the first, there are ways to tile the last two squares.
++++++++b. If on the 2nd, there are ways.
++++++++c. If on the 3rd, there are ways.
So adding these: ways. This gets the numerator of the fraction. To obtain the denominator, we remove the first square, leaving 7, 15, 1.
There are 3 possibilities re the placement of the domino:
++++• no domino. ways
++++• domino on squares 1 & 2. 1 way
++++• domino on squares 2 & 3. 7 ways
So the total is , and the continued fraction is .

Why it works. For positive numbers , define the continuant to be the number of ways to tile a strip of length with dominoes (of length two) and stackable squares (of length one). For nonnegative integers and ,

since the first term counts tilings ending with a stack of tiles, and the second counts those ending with a domino. So for nonnegative ,

and for and ,

The first part counts tilings that don’t have a domino on cells and , while the second part counts those that do.++Also,

### Nonregular CFs

Nonregular continued fractions, i.e. of the form can be represented by a similar model, by using stackable dominoes also.
e.g.

The dominoes can be:
++++• not used. ways.
++++• on the first 2 cells, a stack of 1 or 2. ways.
++++• the the second 2 cells, a stack of 1 to 4. ways.
For the denominator, remove the first cell and find [3;4,5]:
++++• dominoes not used: ways.
++++• dominoes used. ways.
So the sought fraction is .

references

Benjamin, Quinn – Proofs that really count: the art of combinatorial proof, 2003
Benjamin, Zeilberger – Pythagorean primes and palindromic continued fractions