The number of Z-convex polyominoes

DOI10.1016/J.AAM.2006.07.004MaRDI QIDQ2474263zbMATH OpenOpenAlexFDO

Authors Gilles Schaeffer, Enrica Duchi, S. Rinaldi

Publication date 5 March 2008

Published in Advances in Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0602124

zbMATH Keywords

enumerationalgebraic generating functionsrecursive decomposition

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Polyominoes (05B50)

Abstract: 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.

Recommendations

• An efficient algorithm for the generation of Z-convex polyominoes
• Convex polyominoes and algebraic languages
• scientific article; zbMATH DE number 1357398
• The number of directed \(k\)-convex polyominoes
• Combinatorial aspects of \(L\)-convex polyominoes

Cites work

• scientific article; zbMATH DE number 17705 (Why is no real title available?)
• scientific article; zbMATH DE number 1268810 (Why is no real title available?)
• scientific article; zbMATH DE number 687006 (Why is no real title available?)
• Algebraic languages and polyominoes enumeration
• Checker Boards and Polyominoes
• Combinatorial aspects of \(L\)-convex polyominoes
• Counting polyominoes on twisted cylinders
• Discrete Geometry for Computer Imagery
• Enumeration of L-convex polyominoes by rows and columns
• Machines, Computations, and Universality
• Reconstruction of L-convex Polyominoes
• Statistics of lattice animals (polyominoes) and polygons

Cited in

(24)

• Enumeration of 4-stack polyominoes
• On counting Z-convex polyominoes
• Hilbert series of parallelogram polyominoes
• scientific article; zbMATH DE number 1357398 (Why is no real title available?)
• Asymptotics of Z-convex polyominoes
• On the number of convex polyominoes.
• Counting k-convex polyominoes
• Combinatorial Image Analysis
• The number of convex polyominoes with given perimeter
• On the generation of convex polyominoes
• Enumeration of plateau polycubes with respect to their lateral area
• scientific article; zbMATH DE number 1549850 (Why is no real title available?)
• The number of \(k\)-parallelogram polyominoes
• An efficient algorithm for the generation of Z-convex polyominoes
• Partially directed animals with a bounded number of holes
• Irregular polyomino tiling via integer programming with application in phased array antenna design
• Reconstruction of two subclasses of 2L-convex polyominoes
• On the enumeration of \(k\)-omino towers
• The number of directed \(k\)-convex polyominoes
• On computing the degree of convexity of polyominoes
• From Tetris to polyominoes generation
• Tomographic reconstruction of 2-convex polyominoes using dual Horn clauses
• A Dynamical System Approach to Polyominoes Generation*
• On the exhaustive generation of \(k\)-convex polyominoes

This page was built for publication: The number of Z-convex polyominoes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2474263)