7
$\begingroup$

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

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

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.