On this page
How do you tile a 2 by n board with dominoes?
Consider an empty grid of 2 rows by n columns and an unlimited supply of identical 1 × 2 dominoes. The objective is to tile the board completely without gaps or overlaps. Each domino can lie vertically (covering 2 rows in 1 column) or horizontally (covering 1 row across 2 columns).
In exams like the Indian Olympiad Qualifier in Mathematics (IOQM) and JEE Advanced, students often try counting every layout by hand. Drawing dozens of possibilities invites errors. As our guide on preventing double counting in permutations and combinations shows, brute-force enumeration on symmetric grids easily misses cases.
Discrete mathematics instead decomposes grids at the boundary. In Enumerative Combinatorics, Volume 1, Richard P. Stanley shows how spatial tilings reduce directly to recurrence relations. Focusing on the rightmost column converts geometry into addition.
Why does the recurrence relation T(n) = T(n - 1) + T(n - 2) hold?
Let T(n) be the number of ways to tile a 2 × n board. Focusing on the rightmost column (column n), only two tile placements can cover the top-right cell:
A vertical domino covers column n. Since it spans both rows, removing it leaves a 2 × (n − 1) board with T(n − 1) tilings.
A horizontal domino covers row 1 across columns n − 1 and n. The empty square beneath it in row 2 cannot hold a vertical domino or extend past the edge. It must be covered by a second horizontal domino directly below.
Because horizontal tiles at the edge appear in stacked pairs, they take 2 columns. Removing this 2 × 2 block leaves an untiled 2 × (n − 2) board with T(n − 2) tilings.
These two outcomes are mutually exclusive and exhaustive: every valid tiling ends in either one vertical domino or two stacked horizontal dominoes. Adding them gives the recurrence:
T(n) = T(n − 1) + T(n − 2)
How do the base cases produce the Fibonacci sequence?
Every recurrence requires base cases. For small boards:
For n = 1: A 2 × 1 board fits only one vertical domino. Thus, T(1) = 1.
For n = 2: A 2 × 2 board fits two vertical dominoes or two stacked horizontal dominoes. Thus, T(2) = 2.
(For n = 0, an empty board has one trivial tiling, giving T(0) = 1 and confirming T(2) = T(1) + T(0) = 2.)
The additive recurrence generates each subsequent term:
T(3) = 2 + 1 = 3
T(4) = 3 + 2 = 5
T(5) = 5 + 3 = 8
T(6) = 8 + 5 = 13
T(7) = 13 + 8 = 21
In Proofs that Really Count: The Art of Combinatorial Proof, Arthur T. Benjamin and Jennifer J. Quinn show that domino tilings provide the natural combinatorial model for the Fibonacci numbers. With standard indexing where F(1) = 1, F(2) = 1, F(3) = 2, F(4) = 3, F(5) = 5, and F(6) = 8, the tilings for length n satisfy T(n) = F(n + 1).
Long before Leonardo of Pisa's rabbit recurrence in the Liber Abaci appeared in 1202, Indian scholars studied poetic meters built from short syllables (laghu, 1 beat) and long syllables (guru, 2 beats). As historian Parmanand Singh showed in Historia Mathematica90021-7), scholar Hemachandra formulated this exact additive rule around 1150 CE in Hemachandra's rules for counting poetic rhythms. A meter of n beats matches a board of length n.
What does the diagonal sum of Pascal's triangle reveal?
Domino tilings also link Fibonacci numbers to binomial coefficients. In Proofs that Really Count, Benjamin and Quinn demonstrate that conditioning tilings on the number of horizontal pairs connects the Fibonacci sequence directly to combinations.
Suppose a 2 × n board contains k stacked pairs of horizontal dominoes. These pairs occupy 2k columns, leaving n − 2k columns for vertical dominoes. The tiling consists of k horizontal pairs and n − 2k vertical dominoes, creating n − k total blocks. Choosing which k positions hold horizontal pairs gives C(n − k, k) arrangements. Summing over all possible k from 0 to ⌊n / 2⌋ counts every tiling:
T(n) = ∑ C(n − k, k) for k = 0 to ⌊n / 2⌋
For n = 5, evaluating this sum gives:
k = 0: C(5, 0) = 1
k = 1: C(4, 1) = 4
k = 2: C(3, 2) = 3
Adding these yields 1 + 4 + 3 = 8 tilings, matching T(5) = F(6). This identity confirms that the shallow diagonals of Pascal's triangle sum to the Fibonacci sequence.
Recognizing recursive structures in combinatorics prevents lengthy algebra. When practicing recurrence problems, the Fermi Problem Library provides worked problems with a step-by-step solver that explains the reasoning rather than printing an answer. For exploring related mathematical structures, the Fermi Concept Library covers every concept in physics, chemistry, biology, mathematics and computing, each with its own lesson and its place in the map.
