2001/04/01 by James Propp
Mathematics · #math.CO #msc:05A15
published as Electron. J. Combin. 8, no. 1, Research Paper 18 (2001). · 5 pages, 6 figures
arxiv created 2001/04/01 · arxiv updated 2009/11/30
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) = epsilonm,n T(m,n), where epsilonm,n is -1 if m is congruent to 2 (mod 4) and n is odd, and is +1 is 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.