This thesis (and a good number of other theses and articles) is motivated by the simple question:
Rather than leaping in at the deep end, let us start with a simpler question:
Since there are an infinite number of cells on the square grid, and a single tile can be placed on any of them, there are an infinite number of ways we can place a single tile. All of these different ways, however, are equivalent under translation -- there is only a single way to colour a single cell (up to translation).
In the same way, both of the arrangements in figure 3 are equivalent under some translation. In light of this, let us modify question 1:
We know that there is only a single way to place a single tile (up to translation). What about placing two tiles? Consider the three arrangements in figure 4. The tiles in the first two arrangements (left and centre) touch, while in the last the tiles are separated by at least a single lattice spacing. It is not difficult to see that there are only two connected arrangements of two tiles. Let us define connectedness a little more carefully:
|
If an arrangement of tiles is connected, then we call it an -celled polyomino, or a polyomino of area . Unless explicitly stated otherwise, we will consider polyominoes defined up to translation (i.e. if polyomino can be mapped to polyomino under some translation, then we will consider them to be the same).
The name, polyomino, was introduced by Golomb [14], and is the generalisation of dominoes.
On the other hand, we can easily create an infinite number of disconnected arrangements of two tiles -- take the single arrangement of a single tile, and then place another tile cells to its right, where is some integer strictly greater than . Using similar reasoning, it is not hard to see that there will always be an infinite number of disconnected arrangements of tiles (for finite ) .
Since there are always a finite number (up to translation) of polyominoes of area , and an infinite number of disconnected arrangements of tiles, we modify question 3:
Before we consider what is known about the number of polyominoes, let us first consider what we would accept as a solution to question 4.
Rather than delving into a deep discussion of computational complexity and mathematical philosophy, we will attempt to answer this question in a heuristic2 way.
Any answer to question 4 must be a two step process of the form:
This ``definition'' of a solution clearly allows a very wide range of possibilities -- ideally we would like to find the ``best'' possible solution, however this is really hard to define. It is much easier to start with the ``worst'' type of solution. Perhaps the ``worst'' way4 in which we can compute is to use brute force to list all of the polyominoes with cells; is then the length of the list5. For many problems no better method is forthcoming and this ``worst'' method is in fact the best available.
Any method that is ``faster'' than this ``worst'' approach (particularly when is a large number) is, in some weak way, a solution; combinatorialists consider a nice solution to be one of the following:
By an expression being ``easy to evaluate'' we mean that evaluating the expression should be substantially faster than the brute force method -- if we wish to compute all the elements in a set , then a solution of the form
Another slightly different way of ``solving'' a polyomino problem (which we do not explore in this thesis) is to somehow map the original problem to a new problem that can be solved. A solution to the new problem may not give us a means of calculating , but it may give us exact values of other quantities of interest, such as growth constants and critical exponents (see section 2.2 below).
As an example of the different forms of a solution, let us consider the simpler question of permutations:
Alternatively we could solve the recurrence for the (exponential) generating function,
Any solution to question 4 that took one of these three ``compact'' and ``efficient'' forms (i.e. a closed form expression for the coefficients or the generating function, or an efficient algorithm) would be most welcome. In this thesis we will almost exclusively consider solutions in terms of generating functions.
In one dimension, it is easy to see that there is only a single -celled polyomino for any given . As soon as one ventures into two or more dimensions, however, the answer is not so simple; it may come as a surprise that the answer to question 4 remains elusive even after more than years of intensive study [15,29,40]. Arguably the strongest rigorous result on the number of polyominoes concerns their asymptotics. Let denote the number of polyominoes of area on the square lattice. A concatenation argument [30] shows that
The existence of tells us that the number, , of polyominoes of area grows exponentially with ; for any we have (for sufficiently large ) . There are lots of them! It also allows us be a little more specific about what we would require of a good solution to question 4.
Since the number of polyominoes grows exponentially, the time taken by a brute-force approach must also grow exponentially (time ). Consequently, any method that evaluates in either bounded time (time ) or polynomial time (time , for some ) would be a very good answer to question 4. Even an exponential time algorithm (time , for some ) would be, in some weak sense, a solution. The best ``solution'' to date (in two dimensions) is an enumeration algorithm based on the finite lattice method [9] -- this still requires exponential time and space8, but is exponentially faster than brute force enumeration.
Since the enumeration of polyominoes (and related objects) in one dimension is trivial, in this thesis we mostly consider enumeration problems in two dimensions (on the square, triangular and honeycomb lattices).