Nicholas R. Beaton ; Filippo Disanto ; Anthony J. Guttmann ; Simone Rinaldi - On the enumeration of column-convex permutominoes

dmtcs:2895 - Discrete Mathematics & Theoretical Computer Science, January 1, 2011, DMTCS Proceedings vol. AO, 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011) - https://doi.org/10.46298/dmtcs.2895
On the enumeration of column-convex permutominoesArticle

Authors: Nicholas R. Beaton 1; Filippo Disanto 2; Anthony J. Guttmann ORCID1; Simone Rinaldi ORCID2

  • 1 Department of Mathematics and Statistics [Melbourne]
  • 2 Department of Mathematics and Computer Science / Dipartimento di Scienze Matematiche e Informatiche "Roberto Magari"

We study the enumeration of \emphcolumn-convex permutominoes, i.e. column-convex polyominoes defined by a pair of permutations. We provide a direct recursive construction for the column-convex permutominoes of a given size, based on the application of the ECO method and generating trees, which leads to a functional equation. Then we obtain some upper and lower bounds for the number of column-convex permutominoes, and conjecture its asymptotic behavior using numerical analysis.


Volume: DMTCS Proceedings vol. AO, 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011)
Section: Proceedings
Published on: January 1, 2011
Imported on: January 31, 2017
Keywords: polyominoes,permutations,generating functions,[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO],[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

1 Document citing this article

Consultation statistics

This page has been seen 252 times.
This article's PDF has been downloaded 190 times.