A Decomposition of Column-Convex Polyominoes and Two Vertex Statistics

We introduce a decomposition method for column-convex polyominoes and enumerate them in terms of two statistics: the number of internal vertices and the number of corners in the boundary. We first find the generating function for the column-convex polyominoes according to the horizontal and vertical...

Full description

Saved in:
Bibliographic Details
Published in:Mathematics in computer science 2022-03, Vol.16 (1), Article 9
Main Authors: Cakić, Nenad, Mansour, Toufik, Yıldırım, Gökhan
Format: Article
Language:English
Subjects:
Apexes
Asymptotic properties
Computer Science
Corners
Decomposition
Mathematics
Mathematics and Statistics
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We introduce a decomposition method for column-convex polyominoes and enumerate them in terms of two statistics: the number of internal vertices and the number of corners in the boundary. We first find the generating function for the column-convex polyominoes according to the horizontal and vertical half-perimeter, and the number of interior vertices. In particular, we show that the average number of interior vertices over all column-convex polyominoes of perimeter 2 n is asymptotic to α o n 3 / 2 where α o ≈ 0.57895563 … . We also find the generating function for the column-convex polyominoes according to the horizontal and vertical half-perimeter, and the number of corners in the boundary. In particular, we show that the average number of corners over all column-convex polyominoes of perimeter 2 n is asymptotic to α 1 n where α 1 ≈ 1.17157287 … .
ISSN:1661-8270
1661-8289
DOI:10.1007/s11786-022-00528-5