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

preprint2013arXivOpen access

Abstract

We enumerate a certain class of monomino-domino coverings of square grids, which conform to the \emph{tatami} restriction; no four tiles meet. Let Tn\mathbf T_{n} be the set of monomino-domino tatami coverings of the n×nn\times n grid with the maximum number, nn, 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 Tn\mathbf T_{n} with exactly vv vertical dominoes in constant amortized time, and an explicit formula for counting them. The polynomial that generates these counts has the factorisation {align*} P_n(z)\prod_{j\ge 1} S_{\lfloor \frac{n-2}{2^j} \rfloor}(z), {align*} where Sn(z)=∏i=1n(1+zi)S_n(z) = \prod_{i=1}^{n} (1 + z^i), and Pn(z)P_n(z) is an irreducible polynomial, at least for 1<n<200{1 < n < 200}. We present some compelling properties and conjectures about Pn(z)P_n(z). For example Pn(1)=n2ν(n−2)−1P_n(1) = n2^{ν(n-2)-1} for all n≥2n \ge 2, where ν(n)ν(n) is the number of 1s in the binary representation of nn and deg(Pn(z))=∑k=1n−2Od(k)(P_n(z)) = \sum_{k=1}^{n-2} Od(k), where Od(k)Od(k) is the largest odd divisor of kk.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.