Enumerating maximal tatami mat coverings of square grids with v vertical dominoes

Original · EN

We enumerate a certain class of monomino-domino coverings of square grids, which conform to the tatami restriction; no four tiles meet. Let Tₙ be the set of monomino-domino tatami coverings of the n× n grid with the maximum number, n, of monominoes, oriented so that they have a monomino in each of the top left and top right corners. We give an algorithm for exhaustively generating the coverings in Tₙ with exactly v vertical dominoes in constant amortized time, and an explicit formula for counting them. The polynomial that generates these counts has the factorisation align* Pₙ(z)∏ⱼ≥ ₁ S n-2/2ʲ (z), align* where Sₙ(z) = ∏ᵢ₌₁ⁿ (1 + zⁱ), and Pₙ(z) is an irreducible polynomial, at least for 1 < n < 200. We present some compelling properties and conjectures about Pₙ(z). For example Pₙ(1) = n2ν⁽ⁿ⁻²⁾⁻¹ for all n ≥ 2, where ν(n) is the number of 1s in the binary representation of n and deg(Pₙ(z)) = ∑ₖ₌₁ⁿ⁻² Od(k), where Od(k) is the largest odd divisor of k.