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 3\times7 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: ++++ \displaystyle\frac{3\times7+1}{7}=\frac{22}{7}=3\fr{7}.

pi cf tiling

Let’s take the first 4 squares (0-3) of this diagram, which represent the continued fraction:
++++++++++++++3+\cfrac{1}{7+\cfrac{1}{15+\frac{1}{1}}}
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 3\times7\times15\times1=315 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 15\times1 ways to tile the last two squares.
++++++++b. If on the 2nd, there are 3\times1 ways.
++++++++c. If on the 3rd, there are 3\times7 ways.
So adding these: 315+1+15+3+21=355 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. \to 7\times15\times1 ways
++++• domino on squares 1 & 2. \to 1 way
++++• domino on squares 2 & 3. \to 7 ways
So the total is 105+1+7=113, and the continued fraction is 355/113.

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

    \begin{align*} K() &=1 \\ K(a) &=a \\ K(a,b) &=ab+1 \\ \text{For }n\ges 2\text{, }\quad K(a_0,\dots,a_n) &=a_n K(a_0,\dots,a_{n-1})+K(a_0,\dots,a_{n-2}), \end{align*}

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

    \[ [a_0,\dots,a_n]=\frac{K(a_0,\dots,a_n)}{K(a_1,\dots,a_n)} \]

and for n \ges 1 and 0\les k \les n-1,

    \[K(a_0,\dots,a_n)=K(a_0,\dots,a_k)K(a_{k+1},\dots,a_n)+K(a_0,\dots,a_{k-1})K(a_{k+2},\dots,a_n). \]

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

    \[K(a_n,\dots,a_0)=K(a_0,\dots,a_n)\]

Nonregular CFs

Nonregular continued fractions, i.e. of the form b_0+\cfrac{a_1}{b_1+\cfrac{a_2}{b_2+\dots}} can be represented by a similar model, by using stackable dominoes also.
e.g. 1+\cfrac{2}{3+\cfrac{4}{5}}=[1;2,3;4,5]
nonreg cf tiling
The dominoes can be:
++++• not used. \to 1\times3\times5 ways.
++++• on the first 2 cells, a stack of 1 or 2. \to 2\times5 ways.
++++• the the second 2 cells, a stack of 1 to 4. \to 4\times1 ways.
For the denominator, remove the first cell and find [3;4,5]:
++++• dominoes not used: \to 1\times3\times5 ways.
++++• dominoes used. \to 4 ways.
So the sought fraction is \dfrac{1\times 3\times 5+2\times 5+4\times 1}{3\times 5+4}=29/19.

references

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

Leave a Reply

Your email address will not be published. Required fields are marked *