Enumerating tatami mat arrangements of square grids with $v$ vertical dimers
Alejandro Erickson,
Department of Computer Science,
University of Victoria, Canada.
Frank Ruskey,
Department of Computer Science,
University of Victoria, Canada.
Abstract:
Let $\mathbf{T}_{n}$ be the set of monomerdimer tatami tilings of the
$n\times n$ grid with the maximum number, $n$, of monomers, and which have a
monomer in each of the top left and top right corners. We consider
those tilings of $\mathbf{T}_n$ with exactly $v$ vertical dimers and prove
that their numbers are the coefficients of the polynomial
\begin{align}
\label{eq:tnzIntro}
V\hspace{5pt}H_n(z):=2\sum_{i=1}^{\lfloor (n1)/2 \rfloor}
S_{ni2}(z)S_{i1}(z)z^{ni1} +
\left(S_{\lfloor (n2)/2 \rfloor}(z)\right)^2,
\end{align}
where $S_n(z)$ is the generating function of the number of subets of
$\{1,2,\ldots, n\}$ whose members sum to $k$. Furthermore,
$V\hspace{5pt}H_h(z)$ has the factorization
\begin{align*}
P_n(z)\prod_{j\ge 1} S_{\lfloor (n2)/2^j \rfloor}(z),
\end{align*}
where $P_n(z)$ is a somewhat mysterious polynomial with several
observable patterns. We show for all $n\ge 2$, that $P_n(1) =
n2^{\nu(n2)1}$, where $\nu(n)$ is the number of $1$s in the binary
representation of $n$ and that $\deg(P_n(z)) = \sum_{k=1}^{n2} \text{Od}(k)$,
where $\text{Od}(k)$ is the largest odd divisor of $k$. In
addition $P_n(z)$ is irreducible and
\begin{align*}
\sum_{n\ge 2} P_n(1)z^{n2} = \frac{(1+z)(12z)}{(12z^2)\sqrt{14z^2}},
\end{align*}
at least for $2\le n < 200$.
The combinatorial decomposition underlying the polynomial
$ V\hspace{5pt}H_n(z)$ leads to an algorithm for exhaustively generating these
tilings in constant amortized time per tiling.
Below we show all tilings in $\mathbf{T}_8$ with $7$ vertical dimers.
The plots below show the roots of the polynomial $P_n(z)$ for $n$ even on the left and
for $n$ odd on the right. In both cases $3 \le n \le 49$.
Darker and smaller points are used for larger values of $n$.
Clicking on the image will bring up a (much) larger image of the respective plot.

Download: pdf file (not yet).

Submitted ??? ??, 2012.

Please send me a note if
you download one of these files.
It's always nice to know who's reading your papers.

Selected citations:
Back to list of publications.