Collected Tatami Resources
This page will be updated as new publications appear.
A careful search reveals the following publications and mentions of tatami tilings in mathematics:
Mitsuyoshi Yoshida, Japan 1641, Jinkōki ( translated as "Inalterable Treatise", first published in 1627 according to britannica.com).
Knuth reprints a 6 x 5 dimer (1 x 2) tiling from Yoshida's text in The Art of Computer Programming
David Wolfe, Tom Rodgers, 2002, Puzzlers' Tribute: A Feast for the Mind. Puzzle by Yoshiyuki Kotani, Y2K problem of dominoes and tatami carpeting.
Some of this puzzle can be seen in the Amazon.com preview for the hardcover, page 413. The puzzle seen in the preview is: Find a shape that has exactly 2000 domino tatami tilings.
Dean Hickerson, 2002: OEIS http://oeis.org/A068920/a068920.txt
Treats fixed height dimer (1 x 2) tilings and finds recurrences for them. References to several related OEIS sequences.
As of October 24, 2011, searching oeis.org for "tatami" returns 34 sequences related to tatami tilings.
Knuth, 2009: The Art of Computer Programming, volume 4, fascicle 1B, Binary decision diagrams, exercise 215 and errata.
Exercise on dimer (1 x 2) tilings: "Find all domino coverings of a chessboard that are also tatami tilings"
Frank Ruskey and Jennifer Woodcock, 2009: Counting Fixed-Height Tatami Tilings, Electronic J. of Combinatorics.
Generating function for fixed height dimer tilings, stemming from Knuth's exercise, above.
Alhazov, Morita, and Iwamoto, 2009: A note on tatami tilings, Proceedings of 2009 LA Winter Symposium.
Following Ruskey and Woodcock, this paper treated tilings with exactly one monomer (1 x 1). It motivates further the study of arbitrary monomers but was written prior to our discovery of their structure.
A mention by Don Knuth at theory lunch, 2010
Alejandro Erickson, Frank Ruskey, Mark Schurch, Jennifer Woodcock, 2010: Auspicious Tatami Mat Arrangements, 16th COCOON Conference, LNCS 6196, pp. 288–297.
Full characterization of the structure monomer-dimer (1x1 and 1x2) tatami tilings of rectangular regions.
Maximum number of monomers in an $r x c$ tiling is max(r,c) or max(r,c)+1 and has parity the same as rc.
The number of $n\times n$ tilings with $n$ monomers is $n2^{n-1}$.
The generating function for fixed height monomer-dimer tilings is a rational generating function.
Alejandro Erickson, Frank Ruskey, Mark Schurch, Jennifer Woodcock, 2011. Monomer-Dimer Tatami Tilings of Rectangular Regions. Electronic Journal of Combinatorics, 18(1) (2011) P109, 24 pages.
Expanded journal version of the above
A. Erickson, M. Schurch, 2011: Enumerating tatami mat arrangements of square grids, in 22nd International Workshop on Combinatorial Algorithms, University of Victoria, June 20-22, volume 7056 of Lecture Notes in Computer Science (LNCS), Springer Berlin / Heidelberg, 2011, p. 12 pages.
Abstract: We prove that the number of monomer-dimer tilings of an $n\times n$
square grid, with $m<n$ monomers in which no four tiles meet at any
point is $m2^m+(m+1)2^{m+1}$, when $m$ and $n$ have the same parity.
In addition, we present a new proof of the result that there are
$n2^{n-1}$ such tilings with $n$ monomers, which divides the tilings
into $n$ classes of size $2^{n-1}$. The sum of these over all $m\le
n$ has the closed form $2^{n-1}(3n-4)+2$ and, curiously, this is equal
to the sum of the squares of all parts in all compositions of $n$.
Alejandro Erickson, 2011: [**Japanese tatami mat tilings: No four tiles meet**](images/pdf/CMSS_newsletterSEPT11_v9.pdf). Notes from the Margin, Volume II, pages 1-3.
* This issue of the newsletter is tatami themed with images created by Alejandro Erickson. * Condensed version of A. Erickson, M. Schurch, Enumerating tatami mat arrangements of square grids, in: 22nd International Workshop on Combinatorial Algorithms (IWOCA), volume 7056 of Lecture Notes in Computer Science (LNCS), Springer Berlin / Heidelberg, 2011, p. 12 pages.
Alejandro Erickson, Mark Schurch, 2011: **[**Monomer-dimer tatami tilings of square regions**.](http://arxiv.org/abs/1110.5103)** Submitted to a journal.
* Expanded conference proceedings of A. Erickson, M. Schurch, Enumerating tatami mat arrangements of square grids, in: 22nd International Workshop on Combinatorial Algorithms (IWOCA), volume 7056 of Lecture Notes in Computer Science (LNCS), Springer Berlin / Heidelberg, 2011, p. 12 pages.
into $n$ classes of size $2^{n-1}$. The sum of these tilings over
all monomer counts has the closed form $2^{n-1}(3n-4)+2$ and,
curiously, this is equal to the sum of the squares of all parts in
all compositions of $n$. We also describe two algorithms and a Gray
code ordering for generating the $n2^{n-1}$ tilings with $n$
monomers, which are both based on our new proof.
Tatamibari, Nikoli
We are given a rectangular grid with certain symbols. The goal is to find a certain subdivision of the grid into rectangles which satisfies the tatami condition. My own post about this puzzle is here.
2010 Frank Ruskey, Alejandro Erickson
Players take turns adding tiles to a rectangular grid. They must not violate the tatami condition and the first player with no available move loses.
Tomoku! 2010, Martín Matamala, Alejandro Erickson
The player must reconstruct a tatami tiling given its row and column projections.
A website, web game and book are dedicated to this at http://tomokupuzzle.com
Tatami dots and boxes, 2010, Alejandro Erickson, Gwen Temmel
Played just like dots and boxes except that no four lines may touch at any point.
Water striders, Frank Ruskey, Alejandro Erickson, Brian Wyvill
Players place x shaped pieces which must not overlap. The first player with no available move loses. This is inspired by the rays formed by the tatami configurations called bidimers and vortices and the desire to pack them.
There is another puzzle due to Knuth I think, with 1x3 tiles, but I don't remember where I saw it.