# 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? – Mr.Fry Jun 9 '15 at 1:51
• – David Jun 9 '15 at 2:14
• You can find this in Chapter 7.1 of Concrete Mathematics by Graham, Knuth, and Patashnik. – user109360 Jun 9 '15 at 11:01

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$. – Thomas Andrews Jan 12 '17 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. – user308973 Jan 17 '17 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? – user308973 Jan 17 '17 at 23:31
• @ThomasAndrews Yes, this is much simpler. – Pegah Pournajafi Jan 18 '17 at 16:34
• This problem is assuming we have identical dominoes, not different dominos. @user308973 – Thomas Andrews Jan 18 '17 at 16:45