Technical Report MSC-2021-32

TR#:MSC-2021-32
Class:MSC
Title: Enumerating Reduced Polyominoes with Fixed Perimeter Defect
Authors: Bar Magal
Supervisors: Gill Barequet
PDFCurrently accessibly only within the Technion network
Abstract: A <em>polyomino</em> is a shape best described as a connected set of cells in the square lattice. As part of recreational mathematics, polyominoes have seen active research since the 1950s. Simultaneously, polyominoes have been investigated in statistical physics under the name “lattice animals,” mainly in regards to percolation problems. One of the main points of interest is to solve the yet unanswered question of how many different polyominoes exist. Most of the focus, so far, went to estimating the number of different polyominoes that can be made with a given fixed number of cells. Recently, there are increased efforts to discover the number of polyominoes with not only a given area, but with a given perimeter size or perimeter defect as well.

Roughly speaking, the perimeter defect is a number that measures how many twists a polyomino has. Formally, the <em>defect</em> of a polyomino <em>P</em> is defined as the deviation of the perimeter size of <em>P</em> from the maximum possible perimeter size taken over all polyominoes of the same area as <em>P</em>. Interestingly, a polyomino might contain a column or row which can be “cut” out of the polyomino, then the remaining parts of the polyomino are “glued” back together along the cut, and result in a smaller polyomino with equal perimeter defect to the original. By repeating such “cut-and-glue” operations on a polyomino until all matching columns and rows have been removed, one obtains a-so called “reduced polyomino.”

We expand on the efforts regarding perimeter defect and reduced polyominoes, in two directions. First, given a fixed perimeter defect, we demonstrate and prove upper bounds on the width, height, and area of any reduced polyomino with a given perimeter defect. Second, we present an algorithm for enumerating all reduced polyominoes with a given perimeter defect, and calculate their combined generating function. From the generating function, we can extract a formula <em>A(n, k)</em> for the number of polyominoes that have the given perimeter defect <em>k</em> and a fixed area <em>n</em>, for any <em>n</em>. Using our new algorithm, and in the case of <em>k = 5</em> some additional manual calculations, we provide closed formulae of <em>A(n, k)</em>, for up to <em>k = 5</em>, as well as the generating functions for up to <em>k = 5</em>. This is an improvement over the previously known formulae, which were known only up to <em>k = 3</em>.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/2021/MSC/MSC-2021-32), rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the MSC technical reports of 2021
To the main CS technical reports page

Computer science department, Technion
admin