Dominos ($2 \times 1$ on $2 \times n$ and on $3 \times 2n$)

Question

How many ways are there to tile dominos (with size $2 × 1$) on a grid of $2 × n$?

How about on a grid of $3 × 2n$?

Answer 1

Let $ f_n$ be the number of ways to tile a 2 by n grid with dominoes.

Consider the first square in the grid (the leftmost square in the first row),

A) you could place a domino vertically on that, so there are $ f_{n-1}$ ways to tile the rest of the grid.

B) or you could place the domino horizontally on it, so you must place another domino horizontally below that and there are $ f_{n-2} $ ways to tile the rest of the grid.

So we have $ f_n= f_{n-1} + f_{n-2} $. We need to calculate $f_1$ and $f_2$ and then we can calculate $ f_n$ for any natural number.

It is not hard to see that $f_1=1$ and $f_2=2$.

For the 3 by 2n grid, let $f_n$ be the number of ways to tile the 3 by 2n grid with dominoes and $g_n$ be the number of ways to tile a 3 by 2n+1 grid missing its first square.

Use the above method to show that, $$ f_n=2g_{n-1}+f_{n-1} $$ and $$ g_n=f_n+g_{n-1} $$

Now you should just solve these equations to see that $$ f_{n+1}=4f_n-f_{n-1} $$

And again you should also calculate $f_1$ and $ f_2$.

Answer 2

In the case of a $2\times n$ grid, the resulting Fibonacci recurrence is pretty much clear, and you can read up on the solutions on Wikipedia. However, I believe the previous answers have not treated the $3\times n$ case with enough care, so I'd like to fill that gap. Please, let me know of mistakes if there are any.

So we start with a grid such as

To make a first step in the iteration, we ask the question: how can we put a number of dominos on this grid in all different ways such that the first column labeled by $n$ is covered completely?

The possible variations clearly are:

This reveals that apart from the initial $3\times n$ type grid, the number of different tilings for which we can denote as $f_n$, we also need to consider a second grid of $3\times n$ type with one corner missing, the number of tilings for which we call $g_n$. (By symmetry, it does not matter whether an upper or lower corner is missing, the number of tilings will be the same.)

Therefore, the above all possible coverings of the first column labeled by $n$ suggest the recurrence

$$f_n = f_{n-2}+2g_{n-1}$$

Since we have introduced the quantity $g_n$, it seems we need a recurrence relation for it as well. For that end, we consider all possible ways to add dominos to the grid 1) above, such that all squares of column $n-1$ are covered:

Note that in grid 5) we also have added an additional domino occupying columns $n-2$ and $n-3$ at the top, since this is the only possible way to cover the remaining square in column $n-2$ anyway.

This suggests the following recurrence for $g_n$:

$$g_{n-1}=f_{n-2}+g_{n-3}$$

With these two recurrence relations determined, we can proceed to solve for the general solution.

As is usual in such recurrence problems, we can attempt an exponential ansatz for the solution and fix free parameters by demanding consistency with the recurrence relations. For that end, we assume:

$$f_n= q^n\\ g_{n}= a q^n$$

for some unknown $q$, and allowing for a different relative factor $a$ in $g_n$ compared to $f_n$. Plugging the above ansatz into the two recurrence relations, we cancel all trivial overall coefficients and see that the relations reduce to the two equations

$$q^2-2 a q-1= 0 ~~~,~~~ a q^2-q-a =0$$

In total, these equations have four independent solutions:

$$\begin{align*}q_1&=-\sqrt{2-\sqrt{3}}~~~,~&&a_1=\frac{1}{\sqrt{2}}~,\\ q_2&=\sqrt{2-\sqrt{3}}~~~,~&&a_2=-\frac{1}{\sqrt{2}}~,\\ q_3&=-\sqrt{2+\sqrt{3}}~~~,~&&a_3=-\frac{1}{\sqrt{2}}~,\\ q_4&=\sqrt{2+\sqrt{3}}~~~,~&&a_4=\frac{1}{\sqrt{2}}~,\end{align*}$$

where $q_i$ and $a_i$ belong together as a single solution respectively.

Finally, the general solution for $f_n$ is therefore given by

$$f_n=c_1 q_1^n+c_2 q_2^n+c_3 q_3^n+c_4 q_4^n.$$

The four unknown coefficients $c_i$ can be fixed by taking the initial conditions

$$f_0=1~~,~~f_1=0~~,~~f_2=3~~,~~f_3=0~,$$

where we used that the $3\times n$ grid can only be successfully tiled if $n$ is even, and that by convention there is only one way to tile a grid of zero width: place no dominos at all. The case $f_2=3$ can be essentially read off of the grids 1), 2) and 3) above. These initial conditions lead to:

$$c_1=c_2=\frac{1}{12} \left(3-\sqrt{3}\right)~~~,~~~c_3=c_4=\frac{1}{12} \left(3+\sqrt{3}\right)~,$$

and we are done.

As a consistency check, we then observe e.g. $f_4=11$, as was mentioned in the article concerning this problem.

Answer 3

A solution is provided in https://www.m-a.org.uk/resources/Vol-23-No1_Jan_1994_Domino_tiling.pdf

"Domino Tiling" by Jon Brundan, Mathematics PGCE, Department of Education, Cambridge 1994.

Interestingly enough, the above mentioned Knuth book concrete mathematics proves that that g_4 = 12 (page 327), when the article proves that g_4 = 11. I could count 12, which made me suspect the conclusion of the article to be wrong.