A reciprocity theorem for domino tilings

James Propp

The electronic journal of combinatorics, Tome 8 (2001) no. 1

Résumé

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$.

Détail

DOI : 10.37236/1562

Classification : 05A15, 52C20, 05B45
Mots-clés : domino tilings, generating function, recurrence relations