Tatami tilings

One of the most recognizable features of Japanese architecture is the matted flooring. The individual mats, called tatami, are made from rice straw and have a standard size1 and 1×2 rectangular shape. Tatami flooring has been widespread in Japan since the 17th and 18th centuries, but it took three hundred years before mathematicians got their hands on it.

According to the traditional rules for arranging tatami, grid patterns called bushūgishiki (不祝儀敷き) are used only for funerals.2 In all other situations, tatami mats are arranged in shūgishiki (祝儀敷き), where no four mats meet at the same point. In other words, the junctions between mats are allowed to form ┬, ┤, ┴, and ├ shapes but not ┼ shapes.

Two traditional tatami layouts.
Two traditional tatami layouts. The layout on the left follows the no-four-corners rule of shūgishiki. The grid layout on the right is a bushūgishiki, a “layout for sad occasions”.

Shūgishiki tatami arrangements were first considered as combinatorial objects by Kotani in 2001 and gained some attention after Knuth including them in The Art of Computer Programming.

Construction

Once you lay down the first couple tatami, you’ll find there aren’t many ways to extend them to a shūgishiki. For example, two side-by-side tatami force the position of all of the surrounding mats until you hit a wall.

Two side-by-side tatami force the arrangement of an entire square.
Two side-by-side tatami force the arrangement of an entire m×m square.

This observation can be used to decompose rectangular shūgishiki into

  • (m−2)×m blocks forced by vertical tatami,
  • m×m blocks forced by horizontal tatami, and
  • 1×m strips of vertical tiles,

and to derive their generating function

T(x) = \frac{(1+x)(1+x^{m-2}+x^m)}{1-x^{m-1}-x^{m+1}}

Including half-tatami

Four-and-a-half tatami rooms can also be found in Japanese homes and tea houses, so naturally mathematicians have also looked into tatami tilings with half-tatami. Alejandro Erickson’s PhD thesis reviews and extends the research into this area. Alejandro has also published a book of puzzles about tatami layouts.

  1. Floor space in Japan is commonly quoted in terms of the length of a tatami mat. ↩︎
  2. In reality, grid layouts are also used for practical reasons in inns, temples, and other large gathering halls. ↩︎