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 n2^n-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.
This paper is the journal version of the paper, "Auspicious Tatami Mat Arrangements, presented at 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 March ??, 2011; accepted March 29, 2011.
Please send me a note if you download one of these files. It's always nice to know who's reading your papers.
This paper provides the solution to the problem posed in my 2010 New Year's Greeting.
Below are some links to sites about tatami layouts. Note that the layouts considered in our paper are "auspicious" layouts.
- http://en.wikipedia.org/wiki/Tatami
- http://kikuko.web.infoseek.co.jp/english/japanese-style-rooms.html.
Don Knuth gave an informal talk about Tatami tilings that mentioned some of these results (See theory lunch).
Selected citations:
- TBA.

Back to list of publications.