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

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.