4

Suppose you have a large collections of red 1x2 tiles, blue 1x2 tiles and green 1x2 tiles. For $n\ge 0$, let $t_n$ be the number of ways to use these to exactly cover the squares of a 2xn checkerboard (without overlapping the tiles). The tiles can be places on the board either vertically or horizaontally. Determine $t_0 t_1 t_2 t_3$ and a recurrence relation, and initial condition for $t_n$

This is what I have:

$t_0 = 0$

$t_1 = 3$

$t_2 = (3)(3)+(3)(3) = 18$ $t_3 = (3)(3)(3)+(3)(3)(3)+(3)(3)(3) = 81$

I am not sure if this is right, and how to get a recurrence relation

user112213
  • 41

1 Answers1

1

The recurrence relation is $t_n=3t_{n-1}+9t_{n-2}$. Here is how I found this:

Consider an $2\times n$ checkerboard. ($2$ rows and $n$ columns) Looking at the top left tile. There are exactly $2$ positions to place a tile here. Either vertically or horizontally.

Case 1: Vertical placement. In this case, after putting on the tile, we are really just looking at how many ways to place tiles on a $2\times (n-1)$ board. Since we have $3$ colors for this tile, we have $3t_{n-1}$ possibilities.

Case 2: Horizontal placement. In this case, after putting on the tile, there can only be one position to place the tile directly under the first tile. After these $2$ tiles, we are really just looking at how many ways to place tiles on a $2\times (n-2)$ board. Since we have $3$ colors for the first tile and $3$ for the second tile. Thus, for this arrangement, we have $(3)(3)t_{n-2}=9t_{n-2}$ possibilities.

In total, we just add the result of the $2$ cases to get the desired result.

user44322
  • 993