🔢 mathematics

A Partition-Based Generating Function for Row-Convex Polyominoes

This paper proposes a novel partition-based generating function that enumerates row-convex polyominoes without internal holes by linking integer partitions of area to row length sequences, thereby deriving an exact formula and establishing the asymptotic growth rate $S(N) \sim A2^N \cos(N\theta + \phi)$ .

Original authors: Vincenzo M. Scarrica

Published 2026-05-06

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Vincenzo M. Scarrica

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are building a tower out of flat, rectangular Lego bricks. You want to stack them to create a shape, but you have a very specific rule: every single horizontal layer of your tower must be a solid, unbroken line of bricks. You cannot have a layer that looks like a "U" or has a gap in the middle. In the world of math, these shapes are called row-convex polyominoes.

This paper by Vincenzo Scarrica is essentially a new instruction manual for counting how many different towers you can build if you are limited to using exactly $N$ bricks.

Here is the breakdown of the paper's ideas using simple analogies:

1. The "Recipe" for a Shape

Traditionally, mathematicians have struggled to count these shapes because they are tricky to organize. Scarrica proposes a new way to think about them. Instead of trying to draw every possible shape, he suggests looking at the recipe for the shape.

The Ingredients (Partitions): Imagine you have 10 bricks. You can break them down into layers in many ways: a layer of 10, or 5+5, or 4+3+2+1, or 3+3+2+2, and so on. In math, these ways of breaking a number into smaller numbers are called integer partitions.
The Assembly (Permutations): Once you decide on a recipe (e.g., layers of 4, 3, and 2), you can stack them in different orders. You could put the 4 on the bottom, or the 2 on the bottom. The paper calculates how many unique ways you can order these layers.
The "Wobble" Factor (Shifts): This is the clever part. When you stack a layer of 4 bricks on top of a layer of 3 bricks, you don't have to line them up perfectly on the left. You can slide the top layer left or right, as long as at least one brick touches the one below it. The paper calculates exactly how many "slide positions" are possible for every pair of layers.

The Formula: To get the total count, the author says:

Take every possible way to break your total number of bricks into layers.
Count how many ways you can order those layers.
Multiply by the number of ways you can slide them together.
Add all those results up.

2. The "Mirror" Trick

The paper also asks: "What if we flip the tower over?"
If you build a shape and then look at its reflection in a mirror, is it a new shape or the same one?

If the shape is perfectly symmetrical (like a pyramid), flipping it doesn't change it.
If it's lopsided, the mirror image is a different shape.
The author provides a way to estimate how many unique shapes exist if we decide that a shape and its mirror image count as just one thing. This helps simplify the counting process, though the paper notes it's a bit tricky to do perfectly.

3. The "Magic Number" Result

After doing all this complex counting, the paper derives a "magic formula" (a generating function) that predicts how the number of shapes grows as you add more bricks.

The Growth: The number of shapes doesn't grow slowly; it explodes exponentially.
The Pattern: The growth follows a wave-like pattern that gets bigger and bigger. The paper calculates that for a large number of bricks ( $N$ ), the number of shapes is roughly proportional to $2^N$ (doubling every time you add a brick, with a slight wobble).
The "Wobble": The growth isn't a straight line; it oscillates (goes up and down slightly) based on a specific angle related to the number $\sqrt{7}$ .

4. What This Can and Cannot Do

The paper is very clear about its limits:

What it works for: It works perfectly for shapes where every row is a solid block (row-convex).
What it fails at: It cannot easily count "concave" shapes (shapes with holes or gaps in the rows). Imagine trying to build a tower where a layer has a gap in the middle, like a bridge. The math gets too messy because the "sliding" rules become incredibly complicated when pieces aren't connected. The paper admits that extending this method to those messy shapes is currently too difficult.

Summary

In short, this paper offers a new, simpler way to count specific types of blocky shapes by treating them like recipes made of numbers. It confirms that the number of these shapes grows very fast (doubling with every added block) and provides a precise mathematical tool to predict exactly how many there will be, matching previous famous results in the field.

Technical Summary: A Partition-Based Generating Function for Row-Convex Polyominoes

Problem Statement
The enumeration of polyominoes—finite sets of connected unit squares on a 2D integer lattice—remains a challenging problem in combinatorics, particularly for classes defined by geometric constraints. While closed-form formulas for general polyominoes are largely unknown, specific subclasses such as convex, row-convex, and column-convex polyominoes have been studied extensively. Existing methods, notably those by Klarner and Hickerson, rely on recurrence relations and transfer-matrix arguments to derive generating functions. However, explicit closed-form formulas for counting convex polyominoes without internal holes remain limited. This paper addresses the enumeration of row-convex polyominoes (where every row consists of a contiguous sequence of cells) without internal holes, seeking an alternative combinatorial approach that links polyomino enumeration directly to integer partitions.

Methodology
The proposed method establishes a direct correspondence between row-convex polyominoes and integer partitions of the total area $N$ . The core logic proceeds as follows:

Partition Decomposition: Every row-convex polyomino of area $N$ is decomposed into a sequence of row lengths $(\lambda_1, \lambda_2, \dots, \lambda_k)$ such that $\sum \lambda_i = N$ . This sequence forms an integer partition of $N$ .
Horizontal Alignment (Shifts): For a fixed sequence of row lengths, the number of valid horizontal alignments is determined by the "shift" between consecutive rows. If row $i$ has length $L_i$ and row $i+1$ has length $L_{i+1}$ , the number of positions where they can touch (ensuring 4-connectivity) is $L_i + L_{i+1} - 1$ . The total number of configurations for a fixed ordered sequence is the product of these shift factors: $\prod_{i=1}^{k-1} (\lambda_i + \lambda_{i+1} - 1)$ .
Permutation Factor: Since the order of rows matters for the shape of the polyomino, the method accounts for distinct permutations of the partition parts. A factor $\Phi(\lambda)$ is introduced to count the number of distinct permutations of the partition $\lambda$ , adjusting for repeated part sizes (multiplicities).
Enumeration Formula: The total number of row-convex polyominoes of size $N$ , denoted $S(N)$ , is obtained by summing the product of the permutation factor and the shift product over all integer partitions of $N$ :
$S(N) = \sum_{\lambda \in P(N)} \Phi(\lambda) \prod_{i=1}^{\ell(\lambda)-1} (\lambda_i + \lambda_{i+1} - 1)$
Generating Function Derivation: The paper translates this combinatorial sum into a generating function $G(x) = \sum S(N)x^N$ . By modeling the problem as a transfer series of ordered compositions and solving the resulting system of linear equations, the exact rational generating function is derived.

Key Results

Exact Generating Function: The paper derives the generating function for row-convex polyominoes as:
$G(x) = \frac{x(1-x)^3}{1 - 5x + 7x^2 - 4x^3}$
This result is shown to coincide exactly with the generating function for column-convex polyominoes previously derived by Klarner and Hickerson, validating the partition-based approach.
Asymptotic Growth: Analysis of the poles of $G(x)$ reveals the asymptotic behavior of the sequence. The dominant singularities are complex conjugate poles at $x = \frac{3 \pm i\sqrt{7}}{8}$ , with modulus $1/2$ . Consequently, the number of polyominoes grows as:
$S(N) \sim A \cdot 2^N \cos(N\theta + \phi)$
where $\theta = \arctan(\sqrt{7}/3)$ . This indicates purely exponential growth with a base of 2, contrasting with the sub-exponential growth of unrestricted integer partitions.
Numerical Verification: The formula was implemented in Python (Algorithm 1) and verified against known values from the OEIS sequence A001169 for $N$ up to 12, showing perfect agreement.
Symmetry Reduction: The paper discusses bounds for reducing the count by identifying mirror-image configurations, noting that while exact halving is possible for specific parity cases, a general closed-form reduction for symmetric polyominoes is difficult to derive directly from the partition formula.

Significance and Limitations
The primary contribution of this work is the establishment of a direct combinatorial link between integer partitions and the enumeration of row-convex polyominoes. By reformulating the problem in terms of partitions and their permutations, the paper offers a "simple yet effective framework" for both exact enumeration and asymptotic analysis without relying on the more complex transfer-matrix arguments traditionally used.

The paper explicitly notes the limitations of this approach: it applies strictly to row-convex polyominoes without internal holes. Extending the method to concave polyominoes is deemed combinatorially intractable because concave rows can split into multiple disconnected components (sub-partitions) with variable gaps, making the enforcement of the 4-connectivity constraint significantly more complex.

The work positions itself as an alternative to classical methods (Klarner, Hickerson) rather than a replacement, providing a new perspective that simplifies the derivation of the generating function and asymptotic estimates for this specific class of polyominoes. Potential applications mentioned include shape priors in discrete image analysis, grid-based modeling, and procedural generation, though these are presented as contexts where such enumeration is relevant rather than as experimental results of this specific study.