2006/02/07 by Enrica Duchi, Duchi, Enrica, Simone Rinaldi +3
Computer Science · Mathematics · #05A15 #Advanced Combinatorial Mathematics #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #Digital Image Processing Techniques #FOS: Mathematics #math.CO #msc:05A15
paper · pdf · doi:10.48550/arxiv.math/0602124
15 pages, 14 figures
arxiv created 2006/02/07 · openalex publication_date 2006/02/07 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper we consider a restricted class of convex polyominoes that we call Z-convex polyominoes. Z-convex polyominoes are polyominoes such that any two pairs of cells can be connected by a monotone path making at most two turns (like the letter Z). In particular they are convex polyominoes, but they appear to resist standard decompositions. We propose a construction by ``inflation'' that allows to write a system of functional equations for their generating functions. The generating function P(t) of Z-convex polyominoes with respect to the semi-perimeter turns out to be algebraic all the same and surprisingly, like the generating function of convex polyominoes, it can be expressed as a rational function of t and the generating function of Catalan numbers.