Parity and Tiling by Trominoes

Parity and Tiling by Trominoes, by Michael Reid
The Australasian Journal of Combinatorics 40 (2008), pp. 115-136.
The problem of counting tilings by dominoes and other dimers and finding arithmetic significance in these numbers has received considerable attention. In contrast, little attention has been paid to the number of tilings by more complex shapes. In this paper, we consider tilings by trominoes and the parity of the number of tilings. We mostly consider reptilings and tilings of related shapes by the L tromino. We were led to this by revisiting a theorem of Hochberg and Reid [1] about tiling with d-dimensional notched cubes, for d ≥ 3 ; the L tromino is the 2-dimensional notched cube. We conjecture that the number of tilings of a region shaped like an L tromino, but scaled by a factor of n, is odd if and only if n is a power of 2 . More generally, we conjecture the the number of tilings of a region obtained by scaling an L tromino by a factor of m in the x direction and a factor of n in the y direction, is odd if and only if m = n and the common value is a power of 2 . The conjecture is proved for odd values of m and n, and also for several small even values. In the final section, we briefly consider tilings by other shapes.
[1] Robert Hochberg and Michael Reid, Tiling with Notched Cubes, Discrete Mathematics 214 (2000), no. 1-3, pp. 255-261. [Math Reviews] [Zentralblatt]
Research page Home page E-mail
Updated February 20, 2008.