Alejandro Erickson

Low production value innovation.

Tatami

Tatami in the Margin - Canadian Mathematical Society

I am pleased to announce the publication Japanese tatami mat tilings: No four tiles meet, in the Notes from the Margin, Volume II, 2011, from the Student Committee of the Canadian Mathematical Society.

The title of the newsletter comes from the story behind Fermat's last theorem.  He had written in the margins of his notebook:

it is impossible to separate a cube into two cubes, or a fourth power into two fourth powers, or in general, any power higher than the second, into two like powers. I have discovered a truly marvelous proof of this, which this margin is too narrow to contain. (wikipedia)

This article is a condensed version of a result in the conference proceedings: 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:

Tatami mats are the type of mats used in traditional Japanese rooms. Often, an arrangement in which four mats meet at a point is considered unlucky, perhaps because the word “four” sounds like the word “death” in Japanese. So, a “lucky” layout has no “+” shapes formed by the lines where mats meet. Compare the following two arrangements.

Tatami tilings are accessible and fun, so go ahead and take a gander!

Last Updated on Sunday, 23 October 2011 17:31

Tatami Poster Smörgåsbord

This poster appeared at the 2010 CMS Winter Meeting.  Download the pdf for a larger version.

Last Updated on Wednesday, 15 December 2010 14:38

Collected Tatami Resources

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.
• 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.  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. 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.
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:

• 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.

Last Updated on Monday, 24 October 2011 16:24

There are no fault-free dimer-only tatami tilings

I had a word with Ron Graham at the 2010 CMS Winter Meeting and he mentioned a short paper of his in which he talks about fault-free dimer tilings.  A fault-free tiling of a rectangular grid is one in which every interior grid line intersects at least one tile.  Here is a 6 x 6 tiling with two faults.

Ron Graham gives a clever argument, due to S. W. Golomb and R. I. Jewett, that no 6 x 6 fault-free dimer tiling exists.  Try to prove it yourself! (hint:  a dimer blocks exactly one potential fault.  Use elementary arguments).

For which dimensions r x c can we have fault free tatami-dimer tilings?

The answer is simple.  It never happens, except, in the 1 x 2 rectangle.  I'll allow you to convince yourself (in keeping with the low production value of this post) by looking at this:

Dimer tatami tilings of rectangles are all compositions of these configurations.  Since their compositions create fault lines, we may assume that a fault-free tiling has a single bidimer (the configuration in the middle).  But each of these clearly has at least one fault line too.

(disclaimer:  I'm posting this before I'm done thinking about it.  If you want to cite it you should contact me and I'll write a better proof)

Last Updated on Sunday, 12 December 2010 17:11

Tutorial video below!

The Emperor needs you to prepare an auspicious floor for his tea ceremony, but the Ikea instructions only give the row and column projections of the tiling!  You must race the clock to reconstruct it before the Emperor has your head!

A tatami mat is a 1x1 or a 2x1 tile, used for traditional Japanese floorings.  In certain applications, it is "unlucky" to have four mats meeting at one point.

The game was conceived during a conversation with Martín Matamala , a mathematician from Universidad de Chile.  It is related to my PhD thesis work on the Tatami condition.  More details will be published in the upcoming journal version of "Auspicious tatami arrangements" by Frank Ruskey, Mark Schurch, Jennifer Woodock and myself.  A preprint should appear soon at http://arxiv.org/.

The in-game music is by Safary on ccmixter.org and the background photo is by 663highland on Wikipedia.

Here is an instructional video with wicked awesome Whaledub music from .  The music can be found at soundcloud.com - search for sness.

I appreciate your input and feedback in the comments.  Please link to the game through my site so I can measure the traffic before working on a commercial version.  If you are interested in doing the artwork for the commercial version, please contact me at This e-mail address is being protected from spambots. You need JavaScript enabled to view it

Last Updated on Monday, 25 October 2010 17:19

More Articles...
• «
•  Start
•  Prev
•  1
•  2
•  Next
•  End
• »

Page 1 of 2