דלג לתוכן (מקש קיצור 's')
Logo of Technion
Logo of CS Department
אירועים

אירועים

CGGC Seminar: Formulae Enumerating Polyominoes by both Area and Perimeter
event speaker icon
יופיי ז'נג (מדעי המחשב, טכניון)
event date icon
יום שני, 27.3.2017, 13:00
event location icon
חדר 337, בניין טאוב למדעי המחשב
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).
[בחזרה לאינדקס האירועים]