The Taub Faculty of Computer Science Events and Talks

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$.