Counting fixed-height tatami tilings

Frank Ruskey ; Jennifer Woodcock

The electronic journal of combinatorics, Tome 16 (2009) no. 1

Résumé

A tatami tiling is an arrangement of $1 \times 2$ dominoes (or mats) in a rectangle with $m$ rows and $n$ columns, subject to the constraint that no four corners meet at a point. For fixed $m$ we present and use Dean Hickerson's combinatorial decomposition of the set of tatami tilings — a decomposition that allows them to be viewed as certain classes of restricted compositions when $n \ge m$. Using this decomposition we find the ordinary generating functions of both unrestricted and inequivalent tatami tilings that fit in a rectangle with $m$ rows and $n$ columns, for fixed $m$ and $n \ge m$. This allows us to verify a modified version of a conjecture of Knuth. Finally, we give explicit solutions for the count of tatami tilings, in the form of sums of binomial coefficients.

Détail

DOI : 10.37236/215

Classification : 05B45, 05A19
Mots-clés : tatami tilings, arrangement of dominoes, combinatorial decomposition, binomial coefficients