Enumerating Reduced Polyominoes with Fixed Perimeter

Bar Magal (M.Sc. Thesis Seminar)

Monday, 12.07.2021, 14:30

Zoom Lecture: 94492573781

Advisor: Prof. G. Barequet

A \emph{polyomino} 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 \emph{defect} of a polyomino~$P$ is defined as
the deviation of the perimeter size of~$P$ from the maximum possible perimeter
size taken over all polyominoes of the same area as~$P$. Interestingly, a
polyomino might contain a column or row which can be ``cut'' out of the
polyomino, then the remaining parts of the polyomino ``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~$A(n, k)$ for the number of polyominoes that have the given perimeter
defect~$k$ and a fixed area~$n$, for any~$n$. Using our new algorithm, we
provide closed formulae of~$A(n, k)$, for up to~$k=4$, as well as the generating
function for~$k=5$. This is an improvement over the previously known formulae,
which were known only up to~$k=3$.