Tiling Counts via a Leftmost-Piece Recurrence

The leftmost-piece principle

Many combinatorial counting problems on a one-dimensional strip — climbing a staircase, tiling a $1 \times n$ or $2 \times n$ board, sequences avoiding a pattern — count the same family of objects of size $n$. Let $f(n)$ be that count. The trick is to partition all valid configurations by their leftmost piece (the first move, the first column's tiles). Each possible leftmost piece consumes a fixed-width prefix and leaves a strictly smaller, self-similar sub-instance whose count is some $f(n-k)$. Summing over the disjoint cases gives a linear recurrence with constant coefficients.

$f(n) \;=\; \sum_{\text{leftmost pieces } p}\; (\text{\# ways to place } p)\cdot f\!\left(n - w_p\right),$

where $w_p$ is the width the piece removes. The cases must be exhaustive (every configuration has a unique leftmost piece) and disjoint (no configuration is counted twice).

Two canonical cases

Staircase / steps of size 1 or 2. Climbing $n$ stairs, each move is $+1$ or $+2$. Casing on the first move:

• first move $+1$ leaves $n-1$ stairs $\Rightarrow f(n-1)$,
• first move $+2$ leaves $n-2$ stairs $\Rightarrow f(n-2)$.

So $f(n) = f(n-1) + f(n-2)$ — the Fibonacci recurrence, with $f(1)=1,\ f(2)=2$ (so $f(n)=F_{n+1}$).

$2 \times n$ board with $1\times2$ and $2\times2$ pieces. Look at how the leftmost column gets filled:

Two distinct pieces both remove width $2$, so they add a coefficient:

$f(n) = f(n-1) + 2\,f(n-2),\qquad f(0)=1,\ f(1)=1.$

Worked mini-example

Tile a $2\times 3$ board with the pieces above. Using $f(n)=f(n-1)+2f(n-2)$ with $f(0)=f(1)=1$:

$f(2)=f(1)+2f(0)=3,\qquad f(3)=f(2)+2f(1)=3+2=5.$

The five tilings: three vertical dominoes; (vertical)(two-horizontal); (vertical)($2\times2$); (two-horizontal)(vertical); ($2\times2$)(vertical). Casing on the leftmost column makes the enumeration mechanical instead of error-prone.

From recurrence to closed form

Once you have the recurrence, solve it with the characteristic equation (see related card). For $f(n)=f(n-1)+2f(n-2)$, the equation $x^2-x-2=0$ has roots $2,-1$, giving $f(n)=\tfrac{2}{3}2^{n}+\tfrac{1}{3}(-1)^{n}=\dfrac{2^{n+1}+(-1)^{n}}{3}$. For the Fibonacci case the roots are the golden-ratio pair $\tfrac{1\pm\sqrt5}{2}$.

Exam trick: Coefficients in the recurrence come from counting how many distinct pieces remove the same width, not from the number of cases. Mislabeling the $2\times n$ board as plain Fibonacci ($f(n)=f(n-1)+f(n-2)$) is the classic trap — you must remember that a horizontal-domino pair and a $2\times2$ block both leave a $2\times(n-2)$ board, producing the coefficient $2$. Always sanity-check with $n=2$ (here $f(2)=3$, not $2$) before trusting a closed form.