Journal of Integer Sequences, Vol. 15 (2012), Article 12.2.3

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