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

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$?

• I am not too familiar with dominos (strange I know) but they are cut half way so label those $A,B$. Here $2x1$ is two rows one column. So I can have A on top of B or flip and put B on top of A so would that be two ways for you? Commented Jun 9, 2015 at 1:51
• Commented Jun 9, 2015 at 2:14
• You can find this in Chapter 7.1 of Concrete Mathematics by Graham, Knuth, and Patashnik. Commented Jun 9, 2015 at 11:01
• Username checks out :) Commented Aug 5, 2023 at 9:23

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$.

• +1, but it is often better to start with $f_0$ in problems like this. Here $f_0=1$. Now you are left only to calculate $f_1$. Commented Jan 12, 2017 at 20:40
• @ Pegah Pournajafi I think $f_2 = 4$ for the $2\times n$ case. The first domino can be placed left vertical, right vertical, top horizontal, or bottom horizontal. Commented Jan 17, 2017 at 23:13
• Shouldn't the formula for $f_n$ be $$f_n = n f_{n-1} + n(n-1) f_{n-2}$$ to account for the fact that we have choices for which dominoes we initially place down? Commented Jan 17, 2017 at 23:31
• @user308973 Note that there is no difference between dominoes. For example for a $2 \times 2$ grid, if we place dominoes vertically, it doesn't matter if we put the first domino at the left or right. More precisely, dominoes are not numbered. They are all identical. Commented Jan 18, 2017 at 16:46
• Yeah I didn't understand the 3x2n case, how does the case where you're missing 1 square enter into the problem? If you're missing one square surely you can't even tile the dominos without any spaces. Commented Nov 29, 2019 at 7:57

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.

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.

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.