Restricted Tilings and Bijections
Department of Mathematics
345 Boyer Avenue
Walla Walla, WA 99362
A classic problem in elementary combinatorics asks in how many ways one
can tile a 1 × n chessboard using 1 × 1 and
1 × 2
squares. The number of such tilings is the nth Fibonacci number. In
a 2010 paper, Grimaldi generalized this problem by allowing for
1 × 1 tiles to have one of w types and 1 × 2 tiles to
have one of t types and found that the solutions, in w and t,
satisfied many of the same properties as do the Fibonacci and Lucas
numbers. In this paper, we present a variant of this generalization.
Namely, we require that no two adjacent 1 × 1 tiles be of the
same type. This restriction leads to interesting combinatorial
connections with coordination sequences and problems in enumerative set
theory. We explore these connections, as well as some formulas for
generating functions for the numbers of these types of tilings.
Full version: pdf,
(Concerned with sequences
Received April 4 2011;
revised versions received November 15 2011; December 29 2011.
Published in Journal of Integer Sequences, December 30 2011.
Journal of Integer Sequences home page