= Domino tiling
{title2=$T_n=T_{n-1}+T_{n-2}$}
A <domino tiling> covers a region made of unit <squares> by nonoverlapping $1\times2$ rectangles, each occupying two adjacent squares. Equivalently, it is a <perfect matching> in the <graph> whose vertices are squares and whose edges join squares sharing a side. This translates a geometric covering problem into <graph theory>.
A $2\times n$ rectangle has $T_n$ tilings satisfying $T_n=T_{n-1}+T_{n-2}$, with $T_0=T_1=1$. At the left edge, either one vertical domino leaves a $2\times(n-1)$ rectangle, or two horizontal dominoes leave a $2\times(n-2)$ rectangle. Hence $T_2=2$, $T_3=3$ and $T_4=5$. A checkerboard colouring gives a different tool: every domino covers one square of each colour, so unequal colour counts obstruct a tiling. Equal counts are necessary but need not suffice for arbitrary regions.
Back to article page
