Enumeration of k-convex polyominoes by semi-perimeter
Abstract
We prove the Conway--Guttmann formula for the generating function of k-convex polyominoes by semi-perimeter, for every k≥2. A decomposition according to the two diagonal directions reduces the enumeration to convex polyominoes satisfying a one-bend condition in one diagonal direction. Splitting these polyominoes at the right endpoint of the top row leaves an initial part followed by columns whose vertical intervals decrease by inclusion. Ordered forests describe the initial part and retain the row information needed to determine when column extensions first exceed the prescribed bound. A first-passage calculation, together with a sum over initial parts already above the bound, gives the required generating function. The argument includes the case k=2.
Related
- Fibonacci Polyominoes: Refined Enumeration and Dyck-Path Bijections
- Geometric regularity for semi-convex viscosity solutions to the special Lagrangian equation
- Interior Curvature Estimates of Semi-convex Solutions for the scalar curvature equation with Lipschitz Right-Hand Sides
- One-Dimensional Symmetry Reductions of the Monge-Ampère Equation on Some Semi-Homogeneous Convex Cones in ℝ4
- Four-Dimensional Semi-Homogeneous Convex Cones: A Complete Classification
BibTeX
@misc{prellberg2026enumeration,
title = {{Enumeration of $k$-convex polyominoes by semi-perimeter}},
author = {Thomas Prellberg},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.02072},
eprint = {2611.02072},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.02072},
}
RIS
TY - UNPB
TI - Enumeration of k-convex polyominoes by semi-perimeter
AU - Thomas Prellberg
PY - 2026
DA - 2026/11/01
PB - arXiv
DO - 10.48550/arxiv.2611.02072
UR - https://arxiv.org/abs/2611.02072
AB - We prove the Conway--Guttmann formula for the generating function of k-convex polyominoes by semi-perimeter, for every k≥2. A decomposition according to the two diagonal directions reduces the enumeration to convex polyominoes satisfying a one-bend condition in one diagonal direction. Splitting these polyominoes at the right endpoint of the top row leaves an initial part followed by columns whose vertical intervals decrease by inclusion. Ordered forests describe the initial part and retain the row information needed to determine when column extensions first exceed the prescribed bound. A first-passage calculation, together with a sum over initial parts already above the bound, gives the required generating function. The argument includes the case k=2.
ER -