2006/06/13 by Mridul Aanjaneya, Aanjaneya, Mridul
Computer Science · Mathematics · #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #cs.DM #math.CO
paper · pdf · doi:10.48550/arxiv.cs/0606059
19 pages, 13 figures
arxiv created 2007/08/13 · arxiv updated 2009/12/01
We consider tromino tilings of m× n domino-deficient rectangles, where 3|(mn-2) and m,n≥0, and characterize all cases of domino removal that admit such tilings, thereby settling the open problem posed by J. M. Ash and S. Golomb in \cite marshall. Based on this characterization, we design a procedure for constructing such a tiling if one exists. We also consider the problem of counting such tilings and derive the exact formula for the number of tilings for 2×(3t+1) rectangles, the exact generating function for 4×(3t+2) rectangles, where t≥0, and an upper bound on the number of tromino tilings for m× n domino-deficient rectangles. We also consider general 2-deficiency in n×4 rectangles, where n≥8, and characterize all pairs of squares which do not permit a tromino tiling.