1
$\begingroup$

Have a 2xn checkerboard made of 2 kinds of tiles:

  • 1x1 square tile
  • L-tile, which is a 2x2 square tile with a 1x1 square removed from the corner. This tile can be rotated.

I'm trying to create a recursive formula $t(n)$ to find the number of possible tilings. This is what I have so far:

n=1 t(1) = 1 because can only have 2 1x1 tiles

n=2 t(2) = 5 because you can have:

  • All 1x1 tiles (1 option)
  • A 1x1 tile and the L-tile rotated 4 different ways (4 options)

n=3 t(3) = 11 because you can have:

  • 0 L-tiles, so all 1x1 tiles (1 option)

  • 1 L-tile which can be rotated 8 ways and the rest filled with 1x1 squares (8 options)

  • 2 L-tiles, which can be rotated 2 ways (2 options)

Is this correct / am I on the right track? I'm not sure how to find the recursive formula this way.

$\endgroup$

1 Answer 1

1
$\begingroup$

That is correct so far for the base cases.

Now, suppose for our induction hypothesis that you know how to count all patterns of length strictly less than $n$ for some $n\geq 4$. We want to figure out how many there are for length $n$.

Consider the last column.

  • Case 1: Both spaces are $1\times 1$ tiles

  • Case 2: ...

  • Case 3: ...

    • subcase 3a:
    • subcase 3b:

Case 2: One is a $1\times 1$ tile and the other is part of an $L$-shaped tile. Case 3: Both are part of an $L$-shaped tile. Now, consider the second to last column...

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .