×

Tiling parity results and the holey square solution. (English) Zbl 1080.05016

A holey square \(\mathcal H (m,n)\) is a \(2n \times 2n\) square with a centered hole of size \(2m \times 2m\). The number of domino tilings of an \(\mathcal H (m,n)\) was conjectured by Edward Early to have the form \(2^{n-m}(2k_{m;n}+1)^2\). Let #\(R\) denote the number of domino tilings of a region \(R\). In this paper the author confirms Early’s conjecture by showing that #\(\mathcal H (m,n) = 2^{n-m}(\)#\(H(m,n))^2\), where \(H(m,n)\) is a particular “half” subregion of \(\mathcal H (m,n)\), and then determining the parity of #\(H(m,n)\). The techniques in the paper enable combinatorial proofs of several other tiling parity results, including the fact that the number of domino tilings of a particular family of rectangles is always odd.

MSC:

05B45 Combinatorial aspects of tessellation and tiling problems
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
PDFBibTeX XMLCite
Full Text: arXiv EuDML EMIS