Staircase / Tiling Counts

Problem. How many ways are there to climb $n$ stairs taking 1 or 2 steps at a time?

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

— the Fibonacci numbers, shifted: $f(n)=F_{n+1}$.

long long stairs(int n) {
    long long a = 1, b = 1;
    for (int i = 2; i <= n; i++) { long long c = a + b; a = b; b = c; }
    return b;
}

The generalisations

Steps allowed	Recurrence	Sequence
$\{1,2\}$	$f(n)=f(n-1)+f(n-2)$	Fibonacci
$\{1,2,3\}$	$f(n)=f(n-1)+f(n-2)+f(n-3)$	Tribonacci
$\{1,\dots ,k\}$	sum of the last $k$	$k$-bonacci; $O(n)$ with a sliding sum
Arbitrary set $S$	$f(n)={\sum }_{s\in S}f(n-s)$	coin change permutations
With costs	$\min$ instead of $+$	shortest path on a line
Cannot use the same step twice in a row	add a “last step” dimension
Some steps are broken	skip those states

For $\{1,\dots ,k\}$, keep a running window sum so each term is $O(1)$:

long long window = 0;
for (int i = 1; i <= n; i++) {
    window += f[i-1];
    if (i > k) window -= f[i-1-k];
    f[i] = window;
}

Huge $n$ — matrix exponentiation

All of these are linear recurrences, so matrix exponentiation handles $n$ up to $10^{18}$ in $O(k^3\log n)$, or Kitamasa in $O(k^2\log n)$.

For plain Fibonacci, fast doubling is best:
$F_{2k}=F_k(2F_{k+1}-F_k),F_{2k+1}=F_k^2+F_{k+1}^2.$

See Fibonacci Numbers.

Tiling problems — the same family

Problem	Count
Tile $2\times n$ with dominoes	$F_{n+1}$
Tile $1\times n$ with $1\times 1$ and $1\times 2$	$F_{n+1}$
Tile $3\times n$ with dominoes	$f(n)=4f(n-2)-f(n-4)$; 0 for odd $n$
Tile $2\times n$ with dominoes and L-trominoes	$f(n)=2f(n-1)+f(n-2)$
Tile $k\times n$, $k$ small	broken profile DP, $O(n{2}^k)$
Tile $k\times n$, huge $n$	profile DP + matrix power, $O(8^k\log n)$
Binary strings with no two adjacent 1s	$F_{n+2}$
Subsets of $[n]$ with no two consecutive	$F_{n+2}$
Compositions of $n$ into parts $\ge 2$	$F_{n-1}$

Domino tilings of $2\times n$ being Fibonacci is the standard first example of “a counting problem with a linear recurrence”, and the derivation (the last column is either one vertical domino or two horizontal ones) is the model for every profile DP.

When there is no obvious recurrence

Compute the first 10-15 terms by brute force and:

1. Check whether $f(n)=af(n-1)+bf(n-2)$ for small integer $a,b$.
2. Run Berlekamp-Massey to find the recurrence automatically.
3. Search OEIS.

The combination — brute-force a few terms, Berlekamp-Massey, then Kitamasa — solves “count the tilings of a $k\times n$ board for $n=10^{18}$” without ever deriving the recurrence by hand. See Solving Linear Recurrences.

The Kasteleyn formula

For domino tilings of an arbitrary planar region, the count is a Pfaffian (hence a determinant) computable in polynomial time — the FKT algorithm. For a $m\times n$ board:

${\prod }_{j=1}^{\lceil m/2\rceil }{\prod }_{k=1}^{\lceil n/2\rceil }\left(4{\cos }^2\frac{\pi j}{m+1}+4{\cos }^2\frac{\pi k}{n+1}\right).$

Striking, and a reminder that counting perfect matchings is polynomial on planar graphs even though it is p-hard in general.

Why it is worth knowing

The staircase problem is the smallest interesting DP, and it is the entry point to a chain of increasingly powerful techniques applied to the same recurrence: $O(n)$ iteration → $O(\log n)$ matrix power → profile DP for 2D → Berlekamp-Massey when the recurrence is unknown. Following that chain is a good way to learn all four.

See also: Fibonacci Numbers · Broken Profile DP · Matrix Exponentiation