On the enumeration of column-convex permutominoes

Abstract

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.

Keywords

• polyominoes
• permutations
• generating functions
• [math.math-co] mathematics [math]/combinatorics [math.co]
• [info.info-dm] computer science [cs]/discrete mathematics [cs.dm]