Faultfree Tromino Tilings of Rectangles

Abstract

In this paper we consider faultfree tromino tilings of rectangles and characterize rectangles that admit such tilings. We introduce the notion of {\it crossing numbers} for tilings and derive bounds on the crossing numbers of faultfree tilings. We develop an iterative scheme for generating faultfree tromino tilings for rectangles and derive the closed form expression for the exact number of faultfree tromino tilings for $4\times 3t$ rectangles and the exact generating function for $5\times 3t$ rectangles, $t\ge 1$. Our iterative scheme generalizes to arbitrary rectangles; for $6\times 6t$ and $7\times 6t$ rectangles, $t\ge 1$, we derive generating functions for estimating lower bounds on the number of faultfree tilings. We also derive an upper bound on the number of tromino tilings of an $m\times n$ rectangle, where $3|mn$ and $m,n>0$.

arXiv comment34 pages, 17 figures