A strip of 1 row and 9 cells is covered completely, without overlap, by tiles that are either 1 × 1 squares or 1 × 2 dominoes. How many different coverings are there?

Learn / Library / Combinatorics

Strip of squares and dominoes

CombinatoricsEasy

A strip of $1$ row and $9$ cells is covered completely, without overlap, by tiles that are either $1 \times 1$ squares or $1 \times 2$ dominoes. How many different coverings are there?

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

Hint

Look at what covers the last cell.

Solution

Let $a (n)$ be the number of coverings of a strip of $n$ cells.
The last cell is covered either by a square, leaving $n - 1$ cells, or by the end of a domino, leaving $n - 2$ cells.
So $a (n) = a (n - 1) + a (n - 2)$ with $a (1) = 1$ and $a (2) = 2$ .
The values for $n = 1, \dots, 9$ are $1, 2, 3, 5, 8, 13, 21, 34, 55$ , so $a (9) = 55$ .

Answer: $55$

Next question Back to the library