The number of Z-convex polyominoes

DOI10.1016/J.AAM.2006.07.004zbMATH Open1133.05019arXivmath/0602124OpenAlexW2054903698MaRDI QIDQ2474263FDOQ2474263

Authors: Gilles Schaeffer, Enrica Duchi, S. Rinaldi 

Publication date: 5 March 2008

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

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.

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

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

zbMATH Keywords

enumerationalgebraic generating functionsrecursive decomposition

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Algebraic languages and polyominoes enumeration
• Combinatorial aspects of \(L\)-convex polyominoes
• Enumeration of L-convex polyominoes by rows and columns
• Reconstruction of L-convex Polyominoes
• Title not available (Why is that?)
• Discrete Geometry for Computer Imagery
• Machines, Computations, and Universality
• Checker Boards and Polyominoes
• Title not available (Why is that?)
• Statistics of lattice animals (polyominoes) and polygons
• Counting polyominoes on twisted cylinders

Cited In (23)

• Enumeration of 4-stack polyominoes
• Combinatorial Image Analysis
• On the number of convex polyominoes.
• Counting \(k\)-convex polyominoes
• The number of convex polyominoes with given perimeter
• On the generation of convex polyominoes
• Enumeration of plateau polycubes with respect to their lateral area
• Title not available (Why is that?)
• 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
• Asymptotics of Z-convex polyominoes
• Title not available (Why is that?)
• Hilbert series of parallelogram 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)