7 Feb 2012; Mat-Nat Faculty (UiTø), room A228. Tuesday 14:15-16:00

Douglas Rogers (University of Hawaii)

“An area Polya missed and other polyomino enumeration problems”.

A polyomino is a finite collection of cells in the square grid with connected interior - it is not enough that cells are connected only corner to corner, but a restriction on holes seem to be optional. The terminology was introduced (and later copyrighted) by Solomon Golomb, at a talk to the Harvard Mathematical Club in 1953. Instances had been considered earlier, since, after all, such cellular `animals' are fairly natural creatures to consider, in play or as mathematical models. But Golomb was right to recognise the potential - even the commercial possibilities - of polyominoes.

The pieces of the "Catalan" jigsaw are the polyominoes defined by pairs of $(n+1)$-step walks on the integer square lattice, starting at the origin, moving forever to the right or up, but avoiding each other until coming together again at the end. Polya, amongst others, showed that the number of these polyominoes is the $n$-th Catalan number, $C_n = \frac{1}{n+1}\binom{2n}{n}$, $n\geq 0$.

But Polya did not consider the total area of this set of polyominoes which remarkably enough is exactly sufficient to tile a square. So, the question is: do they indeed form a set of jigsaw pieces for the square? And, although this may be an area Polya missed, has this striking observation gone unnoticed?

The talk provides an occasion to range over other objects in the Catalan menagerie which have become popular in mathematical courses in the last quarter century, notably those relating to computer science, and to muse as well on fashions in mathematical education. But polyomino enumeration more generally, besides providing numerous challenging problems, is significant in statistical mechanics and also in some models of biological growth.