Thread: recurrences

Suppose you have large collections of red 1 * 2 tiles, blue 1 * 2 tiles
and green 1 * 2 tiles. For n >= 0, let tn be the number of ways to use
these to (exactly) cover the squares of a 2 * n checkerboard (i.e., without
overlapping of tiles). Note that tiles can be placed on the board either
vertically or horizontally.

(a) Determine t0, t1, t2 and t3.

(b) Find a recurrence relation and initial conditions for tn.

A couple of tips:

Given a 2 * n checkerboard,

1. you must use n tiles to cover it, each of which has 3 possible colors.

2. two horizontal tiles can be exchanged for two vertical tiles for a different configuration.

3. all possible configurations (without respect to color) can be obtained by starting with a configuration of all horizontal tiles and making exchanges of two horizontal tiles for two vertical tiles.