Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People

The Taub Faculty of Computer Science Events and Talks

CGGC Seminar: Formulae Enumerating Polyominoes by both Area and Perimeter
event speaker icon
Yufei Zheng (CS,Technnion)
event date icon
Monday, 27.03.2017, 13:00
event location icon
Room 337 Taub Bld.
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).