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.
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.
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$.
- 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.
- 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.
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 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.
There is also a growing list of tatami puzzles:
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.
Oku! 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.
