A floor has 3 rows and 10 columns. It is covered completely, without overlap, by tiles of size 1 × 2 that can lie in either orientation. How many tilings are there?

Learn / Library / Combinatorics

Tiling a wider floor

CombinatoricsHard

A floor has $3$ rows and $10$ columns. It is covered completely, without overlap, by tiles of size $1 \times 2$ that can lie in either orientation. How many tilings are there?

Checking an answer needs JavaScript. The hint and the solution open without it.

Hint

Cut the floor at the first vertical line that no tile crosses and count the blocks.

Solution

Let $a (n)$ be the number of tilings with $n$ columns; it is $0$ for odd $n$ because the area is odd, and $a (0) = 1$ .
Cut at the first vertical line crossed by no tile: a first block of width $2$ has $3$ tilings, and every wider block with no such line has $2$ tilings, so $a (n) = 3 a (n - 2) + 2 (a (n - 4) + a (n - 6) + \dots + a (0))$ .
Subtracting the same formula for $n - 2$ gives $a (n) = 4 a (n - 2) - a (n - 4)$ with $a (2) = 3$ .
The values for $n = 4, 6, 8, 10$ are $11, 41, 153, 571$ , so $a (10) = 571$ .

Answer: $571$

Next question Back to the library