Polyomino enumeration remains a central and challenging problem in enumerative combinatorics. Among convex polyominoes, geometrically defined subclasses such as L-convex and Z-convex families exhibit markedly different enumerative behaviours, showing how geometric constraints influence the nature of the generating function. In this paper, we introduce a new class of convex polyominoes, called centered ascending polyominoes, which extends L-convex polyominoes and forms a proper subclass of the Z-convex ones. We provide their first exact enumeration with respect to the semiperimeter (size). Our approach is based on a geometric characterisation involving horizontal inclusion and north–east shift constraints between rows, leading to a decomposition into six natural subclasses. We construct a generating tree that uniquely produces objects of size n + 1 from those of size n. This yields a system of functional equations whose solution provides an explicit algebraic generating function, a closed counting formula, and the corresponding asymptotic estimate.

Centered Ascending Polyominoes

paolo massazza;
In corso di stampa

Abstract

Polyomino enumeration remains a central and challenging problem in enumerative combinatorics. Among convex polyominoes, geometrically defined subclasses such as L-convex and Z-convex families exhibit markedly different enumerative behaviours, showing how geometric constraints influence the nature of the generating function. In this paper, we introduce a new class of convex polyominoes, called centered ascending polyominoes, which extends L-convex polyominoes and forms a proper subclass of the Z-convex ones. We provide their first exact enumeration with respect to the semiperimeter (size). Our approach is based on a geometric characterisation involving horizontal inclusion and north–east shift constraints between rows, leading to a decomposition into six natural subclasses. We construct a generating tree that uniquely produces objects of size n + 1 from those of size n. This yields a system of functional equations whose solution provides an explicit algebraic generating function, a closed counting formula, and the corresponding asymptotic estimate.
In corso di stampa
Lecture Notes in Computer Science
Developments in Language Theory 2026
Rouen
dal 29-6-26 al 3-7-26
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11383/2212592
 Attenzione

L'Ateneo sottopone a validazione solo i file PDF allegati

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact