A Partition-Based Generating Function for Row-Convex Polyominoes

Vincenzo M. Scarrica · 2026

Read A Partition-Based Generating Function for Row-Convex Polyominoes by Vincenzo M. Scarrica (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-03203.txt.

Introduction

Vincenzo M. Scarrica offers a partition-based counting method for row-convex polyominoes, grid shapes whose rows form single unbroken runs with no holes. Counting such shapes exactly is a classic hard counting problem in combinatorics.

Each integer partition of the total area gives a list of row lengths, and permuting those parts accounts for the ways rows can align. Summing over all partitions yields the count for each size, with small cases worked out. A transfer argument gives the exact generating function and the growth rate. The link may aid shape priors in image analysis and grid modeling.

Catalog record

CREATORVincenzo M. Scarrica
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE22 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.03203

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A Partition-Based Generating Function for Row-Convex Polyominoes Vincenzo M. Scarrica Abstract 1 Abstract An alternative generating function is proposed to enumerate row-convex polyominoes without internal holes on a discrete grid. The approach is based on integer partitions of the total area, where each partition corresponds to a sequence of row lengths, and the product of all permutations of the parts accounts for all possible horizontal alignments of consecutive rows. Summing over the products yields a formula for the total number of convex polyominoes of a given size. Numerical examples are provided for small areas, and the exact generating function is derived via a transfer series argument, establishing the asymptotic growth S(N)\sim A\cdot 2^{N}\cos(N\theta+\phi) with \theta=\arctan(\sqrt{7}/3) . The method establishes a direct connection between integer partitions and polyomino enumeration, offering a simple yet effective framework for both exact and asymptotic combinatorial analysis. Potential applications include shape priors in discrete image analysis, grid-based modeling, and combinatorial generation of convex structures. 2 Introduction A polyomino is a finite set of cells (unit squares) on the two-dimensional integer lattice \mathbb{Z}^{2} , such that any two cells in the set are connected by a path of adjacent cells sharing a common edge. Formally, let P\subset\mathbb{Z}^{2} be a set of n cells. P is said to be 4-connected if for every pair of cells c_{1},c_{2}\in P , there exists a sequence (c_{1}=d_{0},d_{1},\dots,d_{k}=c_{2}) with d_{i}\in P for all i , such that each d_{i} shares a side with d_{i+1} . This 4-connection ensures that the polyomino forms a single connected component without isolated cells [ 1 ] . The study of polyominoes encompasses a variety of subclasses, each defined by geometric or combinatorial constraints. Among the most studied are convex polyominoes, where the intersection with any horizontal or vertical line is connected, and more generally row-convex or column-convex polyominoes, which satisfy convexity in one direction only [ 7 ] . Directed polyominoes restrict growth to cells added along specific directions from a root cell, simplifying enumeration. Other classes include k -convex polyominoes (such as L-convex [ 2 ] or Z-convex [ 3 ] ), which limit the number of changes in direction along monotone paths connecting any two cells, and parallelogram polyominoes [ 4 ] , bounded by two monotone lattice paths. These distinctions are essential, as each class exhibits different combinatorial behaviors and challenges, and some also consider rigidity, where rotations or reflections yield distinct or equivalent configurations [ 8 ] . Despite significant research, closed-form formulas for counting polyominoes are largely unknown [ 9 ] . Existing results often rely on recurrence relations or generating functions that enumerate polyominoes according to area or perimeter [ 10 ] . Even for convex polyominoes without internal holes, explicit closed-form formulas remain limited, motivating the search for alternative combinatorial approaches. As a direct application of polyominoes tiling, in computer vision the method can be used to estimate or enumerate possible convex pixel masks of approximately or exactly N pixels, which is relevant in scenarios with a fixed camera and quasi-stationary subjects, such as counting or tracking cellular structures and image compression [ 11 ] . Beyond vision, convex polyomino enumeration may find use in statistical physics for lattice models, where the number of connected clusters of fixed size contributes to partition function calculations, or in computational chemistry for estimating configurations of molecules on discrete grids [ 14 ] , [ 13 ] . Further potential applications include tiling problems, grid-based procedural generation in computer graphics, and symbolic representations in formal languages, where convexity constraints simplify combinatorial analysis [ 12 ] . In this work, an alternative contribution is proposed: a method to enumerate convex polyominoes without internal holes using the integer partition function, as an alternative to the classical approach introduced by Klarner [ 5 ] and later revisited by Hickerson [ 6 ] . Each polyomino is associated with a sequence of row lengths forming a partition of its total area, and the product of the permutations of the parts accounts for horizontal alignments of consecutive rows. Summing over all products provides a combinatorial formula for the total number of convex polyominoes of size n , together with an exact generating function and asymptotic estimate of the growth of this function. The method also highlights the limitations in extending such formulas to concave polyominoes. In these cases, each row can contain subpartitions with variable spacing, making it difficult to satisfy the 4-connection constraint, and thereby complicating any direct combinatorial enumeration. Finally, simplifications using reflections and rotations are analyzed to reduce the number of distinct configurations, providing a practical framework to estimate reductions of complexity in these cases. 3 Preliminaries A polyomino is defined as a finite set of cells (unit squares) on the two-dimensional integer lattice \mathbb{Z}^{2} , such that the set is 4-connected, i.e., any two cells can be joined by a sequence of adjacent cells sharing a side. Formally, let P\subset\mathbb{Z}^{2} be a set of n cells. Then P is 4-connected if for every pair c_{1},c_{2}\in P , there exists a sequence (c_{1}=d_{0},d_{1},\dots,d_{k}=c_{2}) with d_{i}\in P for all i , such that d_{i} and d_{i+1} share a side for all i . Convex polyomino not row-convex, 17 cells Figure 1: A 17-cell convex polyomino with corner extensions showing lack of row-convexity. Polyominoes can be classified according to geometric constraints. In this work, we focus on the following classes: • Convex polyominoes : a polyomino P is convex if the intersection of P with any horizontal or vertical line is connected. Equivalently, for any two cells c_{1},c_{2}\in P , there exists a monotone path contained in P connecting them. In Fig. 1 , a convex polyomino example with 17 cells is shown. • Row-convex / Column-convex polyominoes : a polyomino is row-convex (column-convex) if each row (column) contains a contiguous sequence of cells. Even though the polyomino in Fig. 1 is convex, it is not row-convex or column-convex. • Polyominoes without holes : P is simply connected if every cell in the bounding rectangle that lies between two cells of P is also in P , ensuring no internal voids. Figure 2 illustrates examples of polyominoes of area 4, highlighting convex shapes of fixed size and showing how row and column convexity appear in simple configurations. I O L T S Figure 2: The five tetrominoes (polyominoes of area 4) commonly known from Tetris: I, O, L, T, and S. We denote by S(n) the total number of row-convex polyominoes without holes of area n . Later, we will introduce a combinatorial formula for S(n) based on integer partitions and products of row lengths, providing both exact enumeration for small n and an asymptotic estimate for large n . Area 8, with internal hole Figure 3: Example of the first polyomino with an internal hole (area 8). Remark. Convex polyominoes exist only for N\leq 7 . From N=8 , concavity can appear, and Figure 3 shows the first example of a polyomino with an internal hole. Convex, area 20 Concave, area 20, with holes Figure 4: Comparison of two polyominoes of area 20: left, convex without holes; right, concave with holes. Comment. Figure 4 compares two polyominoes of area 20. The left polyomino is convex: all

Read the complete text