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 sizeFloor space in Japan is commonly quoted in terms of the length of a tatami mat. 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.In reality, grid layouts are also used for practical reasons in inns, temples, and other large gathering halls. 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. 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 2001Tatami tilings. Puzzlers’ Tribute: A Feast for the Mind. Yoshiyuki Kotani (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.

This observation can be used to decomposeA068920. On-Line Encyclopedia of Integer Sequences. Dean Hickerson (2002). rectangular shūgishiki into:

derive their generating functionCounting fixed-height tatami tilings. Electronic Journal of Combinatorics 16(R126). Frank Ruskey and Jennifer Woodcock (2009).

T(x)=(1+x)(1+xm2+xm)1xm1xm+1. 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 thesisMonomino-Domino Tatami Coverings. Alejandro Erickson (2013). reviews and extends the research into this area. Alejandro has also published a book of puzzles about tatami layouts.