Domino tiling

Remarks

Example: the $2 \times 3$ rectangle $[0, 3] \times [0, 2]$ has exactly three domino tilings. They are: three vertical dominoes; one vertical domino on the left and two horizontal ones on the right; and the mirror image of the second. More generally, the $2 \times n$ rectangle has $F_{n+1}$ domino tilings, where $F_1 = F_2 = 1$ and $F_{k+1} = F_k + F_{k-1}$ are the Fibonacci numbers.

Non-example: remove two opposite corner cells from the $8 \times 8$ board. Colour the cells like a chessboard; each domino covers one black and one white cell, but the two removed cells have the same colour. So the remaining $62$ cells have $32$ of one colour and $30$ of the other, and no set of dominoes satisfies clauses 2 and 3.

Equivalently, a domino tiling of $R$ is a perfect matching of the graph whose vertices are the cells of $R$, two cells being adjacent when they share an edge.