Summary: lozenge tilings are beautiful combinatorial objects with interesting properties. In my opinion, they should be much better known. (It took some asking around even to find out the name for what I was exploring.) The best known early work related to them may be MacMahon's formula for counting plane partitions in his text Combinatory Analysis (1916). Skimming this, I don't see where he notes the equivalence to lozenge tilings, but it was certainly well established by then. The equivalence between lozenge tilings and the flat projection of a plane partition is old enough to be used by Romans in their mosaics and the 1982 arcade game Q*bert (omitting links, which would be nice for those who don't know what I'm referring to). In both of those cases, the rhombuses are tiled regularly (Rhombille tiling, which you can read about at wikipedia) but the shape admits infinitely many irregular tilings as well.

Here is an earlier write-up I placed at conwaylife.com, which is really not the right place at all. It goes into more detail and includes pictures.

What is cool about lozenge tilings? What I find most interesting are the number of seemingly different representations that are all equivalent. Some equivalences may seem trivial (especially as you start to work with them) but they are all useful "coordinate systems" for these things, presenting them in a different light. Some easier to visualize, to work with on paper, or to write computer code to analyze.

(1) Take two triominoes, labeled 0-0-1 and 1-1-0. Use as many duplicates as you like, but match them up according to rules so that any six adjacent corners agree in number.

(2) On a hex grid, fill in the cells with 0s and 1s, but make sure that no three adjacent hexes all have the same number (so again, they must have two 0s and a 1 or two 1s and a 0).

(3) On a hex grid once again, find a bipartite matching of the edges between vertices. I.e. Each vertex is matched to exactly one of the three adjacent vertices.

(4) Tile the plane with lozenges (60°-120° rhombuses)

(5) Cover the plane with stacks of cubes such that the height of stacks is non-decreasing with increasing x or y position. Now project the cube edges onto the plane x+y+z=0.

One thing I liked enough that I made cardboard tiles was a lozenge with curved sides that can be flipped between an "s" and "z" orientation. When you tile with these, each side having a different color, the orientations make nice looking patterns. The orientations actually turn out to be the cube heights mod 2 (as do the 0-1 numbers in the first two representations). I did most of this before realizing the connection to plane partitions (5) and I was puzzling over the triomino representation (1) before even realizing I was reinventing lozenge tilings.

Disclaimer: I have not done anything like a complete literature search. I am not claiming anything above is new, and in fact I believe it is all very well known to those who have studied lozenge tilings.

]]>