Auspicious Tatami Mat Arrangements
Alejandro Erickson,
Department of Computer Science,
University of Victoria, Canada.
Frank Ruskey,
Department of Computer Science,
University of Victoria, Canada.
Mark Schurch,
Department of Mathematics and Statistics,
University of Victoria, Canada.
Jennifer Woodcock,
Department of Computer Science,
University of Victoria, Canada.
Abstract:
The main purpose of this paper is to introduce the idea of tatami
tilings, and to present to the reader some of the many interesting
questions that arise when studying them.
Roughly speaking what we are considering are tilings of
rectilinear regions with dimer and monomer pieces, with the constraint
that no four corners of the pieces meet.
A typical problem is to minimize the number of monomers in a tiling, or
to count the number of tilings in a particular shape.
We determine the underlying structure of tatami tilings of rectangles and use
this to prove that the number of tatami tilings of an n by n
square with n monomers is n2n-1.
We also prove that for fixed height, that the number of tatami tilings
of a rectangle is a rational function and outline an algorithm that
produces the coefficients of the two polynomials of the numerator
and the denominator.
-
Files: pdf.
-
The 16th Annual International Computing and Combinatorics Conference
(COCOON 2010), July 19-21, Nha Trang, Vietnam.
LNCS, 6169 (2010) 288-297.
-
Conference presentation (given by Alejandro Erickson):
COCOONtalk.pdf.
-
Submitted February 22, 2010; accepted April 12, 2010.
-
Please send me a note if
you download one of these files.
It's always nice to know who's reading your papers.
-
Below are some links to sites about tatami layouts.
Note that the layouts considered in our paper are
"auspicious" layouts.
-
Don Knuth gave an informal talk about Tatami tilings that mentioned
some of these results
(See theory lunch).
-
Selected citations:
Back to list of publications.
