A Partition-Based Generating Function for Row-Convex Polyominoes
Provides a new combinatorial framework for enumerating convex polyominoes, but the problem is niche and the result is incremental.
The paper proposes a generating function for row-convex polyominoes based on integer partitions, deriving exact and asymptotic counts (e.g., S(N) ~ A 2^N cos(Nθ+φ) with θ=arctan(√7/3)).
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) as A2^(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.