A Reciprocity Theorem for Domino Tilings

Abstract

Let $T(m,n)$ denote the number of ways to tile an $m$-by-$n$ rectangle with dominos. For any fixed $m$, the numbers $T(m,n)$ satisfy a linear recurrence relation, and so may be extrapolated to negative values of $n$; these extrapolated values satisfy the relation $$T(m,-2-n)=\epsilon_{m,n}T(m,n),$$ where $\epsilon_{m,n}=-1$ if $m \equiv 2$ (mod 4) and $n$ is odd and where $\epsilon_{m,n}=+1$ otherwise. This is equivalent to a fact demonstrated by Stanley using algebraic methods. Here I give a proof that provides, among other things, a uniform combinatorial interpretation of $T(m,n)$ that applies regardless of the sign of $n$.