Restricted Tilings and Bijections
Barry Balof
Department of Mathematics
Whitman College
345 Boyer Avenue
Walla Walla, WA 99362
USA
Abstract:
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,
dvi,
ps,
latex
(Concerned with sequences
A000931
A001590
A005899.)
Received April 4 2011;
revised versions received November 15 2011; December 29 2011.
Published in Journal of Integer Sequences, December 30 2011.
Return to
Journal of Integer Sequences home page