The Taub Faculty of Computer Science Events and Talks

A polyomino of area n is an edge-connected set of n cells on the square lattice. To-date, no formulae enumerating polyominoes by area (number of cells) or perimeter (number of empty cells neighboring the polyomino) are known.

The area of a given polyomino will be denoted by n, and its area by p. We first prove that the maximum perimeter of a polyomino of area n is 2n+2. Then we present a few formulae enumerating polyominoes with small perimeter defect (i.e., deviation from the maximum possible perimeter) by means of case analysis. Finally, we prove that the generating function that enumerates polyominoes with defect k with respect to their area is rational. Moreover, its denominator is the product of cyclotomic polynomials. Equivalently, the enumerating sequence of such polyominoes satisfies a linear recursion, and its characteristic polynomial is the product of cyclotomic polynomials.

Joint work with Gill Barequet (Dept. of Computer Science, Technion) and Andrei Asinowski (Inst. of Discrete Mathematics and Geometry, Vienna Univ.of Technology).