Site animals and polyominoes

Figure 12: Polyomino and site animal taxonomy. Directed site animals and polyominoes have been solved. Polyominoes also give rise to polygon models.

There is only one solved family of site animals and polyominoes (that is not a family of polygons) -- directed polyominoes¹⁷:

Definition 5
A polyomino is a directed polyomino if there exists a cell, called the root or source, from which all other cells can be reached by a path (remaining inside the polyomino) that takes only north and east steps. The definition of directed site animals is similar.

Directed animals enumerated according to area were first solved on the square and triangular lattices¹⁸ by Dhar [12,13] (using a formal connection with lattice gas models) and Gouyou-Beauchamps & Viennot [16] (by more combinatorial methods). The proof was substantially simplified by Bétréma and Penaud [3,4,36]; this proof has been extended to take the right half-width into account (see chapter 4). The generating function of directed animals, counted according to their area and number of cells only supported from below¹⁹ has been solved (both on the square and triangular lattices) using the connection between two-dimensional directed animals and one-dimensional gas models [6]. Directed animals on the hexagonal lattice (and polyominoes on the triangular lattice) have not been solved (possible reasons for this are discussed in [10]).

One of the few animal results in higher dimensions are directed site animals on a cubic lattice. Dhar [13] showed that a model of directed animals on the cubic lattice (in which nearest-neighbour and next-nearest neighbour steps are permitted) is equivalent to a statistical mechanical model called the hard-hexagon model which was solved by Baxter [2].

As noted above almost all solved models are either directed or convex or both. The largest families (in terms of their growth constants) with these properties -- directed animals and column-convex polyominoes²⁰ (see chapter 2) -- have been solved. Consequently if we are to find or invent larger classes of solvable animals and polyominoes, we must look beyond convexity and directedness. In chapter 4 we define and solve three new larger classes of triangular lattice animals (and two on the square lattice) that are neither convex nor directed; the starting point for this is the beautiful mapping between directed animals and pyramids of dimers first observed by Viennot.