Combinatorial Approaches and Conjectures for 2-Divisibility Problems Concerning Domino Tilings of Polyominoes

Abstract

We give the first complete combinatorial proof of the fact that the number of domino tilings of the $2n \times 2n$ square grid is of the form $2^n(2k+1)^2$, thus settling a question raised by John, Sachs, and Zernitz. The proof lends itself naturally to some interesting generalizations, and leads to a number of new conjectures.